Martin Loebl Discrete Mathematics in Statistical Physics
Martin Loebl
Discrete Mathematics in Statistical Physics Introductory Lectures
Bibliographic information published by the Deutsche Nationalbibliothek The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available in the Internet at http://dnb.d-nb.de.
Dr. Martin Loebl Charles University Department of Applied Mathematics Institut of Theoretical Computer Science Malostranske 25 CZ-118 00 Praha Tschechische Republik E-Mail:
[email protected]
1st Edition 2010 All rights reserved © Vieweg +Teubner | GWV Fachverlage GmbH, Wiesbaden 2010 Editorial Office: Ulrike Schmickler-Hirzebruch | Nastassja Vanselow Vieweg+Teubner is part of the specialist publishing group Springer Science+Business Media. www.viewegteubner.de No part of this publication may be reproduced, stored in a retrieval system or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the copyright holder. Registered and/or industrial names, trade names, trade descriptions etc. cited in this publication are part of the law for trade-mark protection and may not be used free in any form or by any means even if this is not specifically marked. Cover design: KünkelLopka Medienentwicklung, Heidelberg Printing company: STRAUSS GMBH, Mörlenbach Printed on acid-free paper Printed in Germany ISBN 978-3-528-03219-7
dedicated to Zbynˇek and Jaroslava, my parents
Preface The purpose of these lecture notes is to briefly describe some of the basic concepts interlacing discrete mathematics, statistical physics and knot theory. I tried to emphasize a ’combinatorial common sense’ as the main method. No attempt of completeness was made. The book should be accessible to the students of both mathematics and physics. I profited from previous books and expositions on discrete mathematics, statistical physics, knot theory and others, namely [B1], [BRJ], [BB], [J1], [KG], [LL], [MN], [MJ], [MT], [S0], [S3], [SM], [WFY], [WD], [KSV]. Most of the material contained in the book is introductory and appears without a reference to the original source. This book has been an idea of my editor Martin Aigner. I would like to thank to him for his support and help. Many other colleagues helped me with the book. Mihyun Kang, Jirka Matouˇsek, Iain Moffatt, Jarik Neˇsetˇril, Dominic Welsh and Christian Krattenthaler read earlier versions, and without their extensive comments the book would probably not exist. I had enlightening discussions on several topics discussed in the book, in particular with Martin Klazar, Roman Koteck´ y, Ondˇrej Pangr´ ac, Gregor Masbaum, Xavier Viennot and Uli Wagner. Marcos Kiwi saved the whole project by gently teaching me how to draw pictures amd Winfried Hochstaettler drew one; I am sure you will be able to detect it. Large part of the book was written during my visit, in the whole year 2006, at