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