E-Book Content
26 Algorithms and Combinatorics Topics in Discrete Mathematics Dedicated to Jarik Nesetfil on the Occasion of his 60th Birthday M. Klazar J. Kratochvil M. Loebl J. Matousek R.Thomas P. Valtr Editors ~ Springer A Algorithms and Combinatorics 26 Editorial Board R.1. Graham, La Jolla B. Korte, Bonn 1. Lovasz, Budapest A. Wigderson, Princeton G. M. Ziegler, Berlin Martin Klazar . Jan Kratochvil Martin Loebl . Jiff Matousek Robin Thomas· Pavel Valtr Editors Topics in Discrete Mathelllatics Dedicated to Jarik Nesetfil on the Occasion of his 60th Birthday With 62 Figures ~ Springer Editors Martin Klazar Jan Kratochvil Martin Loebl Jiff Matousek Pavel Valtr Robin Thomas School of Mathematics Georgia Institute of Technology Atlanta, GA 30332-0160, USA Department of Applied Mathematics and Institute for Theoretical Computer Science IT! Faculty of Mathematics and Physics Charles University, Prague Malostranske nam. 2S 118 00 Praha 1, Czech Republic library of Congress Control Number: 2006926241 Mathematics Subject Classification (2000): OSClO, OSClS, OSC30, OSCSS, oSC6S, OSC70, oSC8S ISSN 0937-5511 ISBN-lO 3-540-33698-2 Springer Berlin Heidelberg New York ISBN-I3 978-3-540-33698-3 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer and Hindustan Book Agency. Violations are liable for prosecution under the German Copyright Law. Springer is a part of Springer Science+ Business Media springer. com © Springer-Verlag Berlin Heidelberg 2006 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: by the authors, copyedited by Helena Nyklova using a Springer m]lX macro package Production: LE-T]lX Jelonek, Schmidt & Vockler GbR, Leipzig Cover design: design & production GmbH, Heidelberg Printed on acid-free paper 46/3100YL - 5 4 3 2 1 0 To our teacher, colleague and friend Preface The purpose of this book is twofold. We would like to offer our readers a collection of high quality papers in selected topics of Discrete Mathematics, and, at the same time, celebrate the 60th birthday of Jarik Nesetfil. Since our discipline has experienced an explosive growth during the last half century, it is impossible to cover all of its recent developments in one modest volume. Instead, we concentrate on six topics, those closest to Jarik's interests. We have invited leading experts and close friends of Jarik's to contribute to this endeavor, and the response has been overwhelmingly positive. We were fortunate to receive many outstanding contributions. They are divided into six parts. Contents The topics of the first part are rather diverse, including Algebra, Geometry, and Numbers and Games. Michael E. Adams and Ales Pultr consider rigidity (lack of nontrivial homomorphisms) of algebraic structures, and they construct 2No rigid countable Heyting algebras. Vitaly Bergelson, Hillel Furstenberg, and Benjamin Weiss introduce a new notion of "large" sets of integers, piecewise-Bohr sets, and they show, in particular, that the sum of two