Combinatorial mathematics has been pursued since time immemorial, and at a reasonable scientific level at least since Leonhard Euler (1707-1783). It rendered many services to both pure and applied mathematics. Then along came the prince of computer science with its many mathematical problems and needs - and it was combinatorics that best fitted the glass slipper held out. Moreover, it has been gradually more and more realized that combinatorics has all sorts of deep connections with ``mainstream areas'' of mathematics, such as algebra, geometry and probability. This is why combinatorics is now a part of the standard mathematics and computer science curriculum. This book is as an introduction to extremal combinatorics - a field of combinatorial mathematics which has undergone a period of spectacular growth in recent decades. The word ``extremal'' comes from the nature of problems this field deals with: if a collection of finite objects (numbers, graphs, vectors, sets, etc.) satisfies certain restrictions, how large or how small can it be? For example, how many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? An easy Ramsey-type argument shows that at most five persons can attend such a party. Or, suppose we are given a finite set of nonzero integers, and are asked to mark an as large as possible subset of them under the restriction that the sum of any two marked integers cannot be marked. It appears that (independent of what the given integers actually are!) we can always mark at least one-third of them. Besides classical tools, like the pigeonhole principle, the inclusion-exclusion principle, the double counting argument, induction, Ramsey argument, etc., some recent weapons -- the probabilistic method and the linear algebra method -- have shown their surprising power in solving such problems. With a mere knowledge of the concepts of linear independence and discrete probability, completely unexpected connections can be made between algebra, probability, and combinatorics. These techniques have also found striking applications in other areas of discrete mathematics and, in particular, in the theory of computing. Nowadays we have comprehensive monographs covering different parts of extremal combinatorics. These books provide an invaluable source for students and researchers in combinatorics. Still, I feel that, despite its great potential and surprising applications, this fascinating field is not so well known for students and researchers in computer science. One reason could be that, being comprehensive and in-depth, these monographs are somewhat too difficult to start with for the beginner. I have therefore tried to write a ``guide tour'' to this field -- an introductory text which should Intended for use as an introductory
course, the text is, therefore, far from being all-inclusive. Emphasis
has been given to theorems with elegant and beautiful proofs: those which
may be called the gems of the theory and may be relatively easy to grasp
by non-specialists. Some of the selected arguments are possible candidates
for The Book, in which, according to Paul Erdös, God
collects the perfect mathematical proofs.
Extremal combinatorics itself is much broader. To keep the introductory character of the text and to minimize the overlap with existing books, some important and subtle ideas (like the shifting method in extremal set theory, applications of Janson's and Talagrand's inequalities in probabilistic existence proofs, use of tensor product methods, etc.) are not even mentioned here. In particular, only a few results from extremal graph theory are discussed and the presentation of the whole Ramsey theory is reduced to the proof of one of its core results --the Hales-Jewett theorem and some of its consequences. Fortunately, most of these advanced techniques have an excellent treatment in existing monographs by Bollobás (1978) on extremal graph theory, by Babai and Frankl (1992) on the linear algebra method, by Alon and Spencer (1992) on the probabilistic method, and by Graham, Rothschild, and Spencer (1990) on Ramsey theory. We can therefore pay more attention to the recent applications of combinatorial techniques in the theory of computing. A possible feature and main departure from traditional books in combinatorics is the choice of topics and results, influenced by the author's twenty years of research experience in the theory of computing. Another departure is the inclusion of combinatorial results that originally appeared in computer science literature. In particular, some recent applications of combinatorial methods in the theory of computing TeachingThe text is self-contained. It assumes a certain mathematical maturity but no special knowledge in combinatorics, linear algebra, probability theory, or in the theory of computing --a standard mathematical background at undergraduate level should be enough to enjoy the proofs. All necessary concepts are introduced and, with very few exceptions, all results are proved before they are used, even if they are indeed ``well-known.'' Fortunately, the problems and results of combinatorics are usually quite easy to state and explain, even for the layman. Its accessibility is one of its many appealing aspects.The book contains much more material than is necessary for getting acquainted with the field. I have split it into 29 relatively short chapters, each devoted to a particular proof technique. I have tried to make the chapters almost independent, so that the reader can choose his/her own order to follow the book. The (linear) order, in which the chapters appear, is just an extension of a (partial) order, ``core facts first, applications and recent developments later.'' Combinatorics is broad rather than deep, it appears in different (often unrelated) corners of mathematics and computer science, and it is about techniques rather than results -- this is where the independence of chapters comes from. Each chapter starts with
results demonstrating the particular technique in the simplest (or most
illustrative) way. The relative importance of the topics discussed in separate
chapters is not reflected in their length -- only the topics which appear
for the first time in the book are dealt with in greater detail. To facilitate
the understanding of the material, over 300 exercises of varying difficulty,
together with hints to their solution, are included. This is a vital part
of the book -- many of the examples were chosen to complement the main
narrative of the text. I have made an attempt to grade them: problems marked
by ``-'' are particularly easy, while the ones marked by ``+'' are more
difficult than unmarked problems. The mark ``(!)'' indicates that the exercise
may be particularly valuable, instructive, or entertaining. Needless to
say, this grading is subjective. Some of the hints are quite detailed so
that they actually sketch the entire solution; in these cases the reader
should try to fill out all missing details.
AcknowledgmentsI would like to thank everybody who was directly or indirectly involved in the process of writing this book. First of all, I am grateful to Alessandra Capretti, Anna Gál, Thomas Hofmeister, Daniel Kral, G. Murali Krishnan, Martin Mundhenk, Gurumurthi V. Ramanan, Martin Sauerhoff and P.R. Subramania for comments and corrections.Although not always directly reflected in the text, numerous earlier discussions with Anna Gál, Pavel Pudlák, and Sasha Razborov on various combinatorial problems in computational complexity, as well as short communications with Noga Alon, Aart Blokhuis, Armin Haken, Johan Håstad, Zoltan Füredi, Hanno Lefmann, Ran Raz, Mike Sipser, Mario Szegedy, and Avi Wigderson, have broadened my understanding of things. I especially benefited from the comments of Aleksandar Pekec and Jaikumar Radhakrishnan after they tested parts of the draft version in their courses in the BRICS International Ph.D. school (University of Aarhus, Denmark) and Tata Institute (Bombay, India), and from valuable comments of László Babai on the part devoted to the linear algebra method. I would like to thank the Alexander von Humboldt Foundation and the German Research Foundation (Deutsche Forschungsgemeinschaft) for supporting my research in Germany since 1992. Last but not least, I would like to acknowledge the hospitality of the University of Dortmund, the University of Trier and the University of Frankfurt; many thanks, in particular, to Ingo Wegener, Christoph Meinel and Georg Schnitger, respectively, for their help during my stay in Germany. This was the time when the idea of this book was born and realized. I am indebted to Hans Wössner and Ingeborg Mayer of Springer-Verlag for their editorial help, comments and suggestions which essentially contributed to the quality of the presentation in the book. My deepest thanks to my wife, Daiva, and my daughter, Indrê, for being there. Frankfurt/Vilnius, March
2001
|