Jukna, S.,

Extremal Combinatorics

With Applications in Computer Science


    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 

    • be self-contained,
    • be more or less up-to-date,
    • present a wide spectrum of basic ideas of extremal combinatorics,
    • show how these ideas work in the theory of computing, and
    • be accessible for graduate and motivated undergraduate students in mathematics and computer science.
    Even if not all of these goals were achieved, I hope that the book will at least give a first impression about the power of extremal combinatorics, the type of problems this field deals with, and what its methods could be good for. This should help students in computer science to become more familiar with combinatorial reasoning and so be encouraged to open one of these monographs for more advanced study.

    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.  
    I hope that the reader will enjoy them despite the imperfections of the presentation.

    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 

    • a new proof of Haken's exponential lower bound for the resolution refutation proofs,
    • a non-probabilistic proof of the switching lemma,
    • a new lower bounds argument for monotone circuits,
    • a rank argument for boolean formulae,
    • the proof that NL is contained in Parity-L,
    • lower and upper bounds for span programs,
    • highest lower bounds on the multi-party communication complexity,
    • a probabilistic construction of surprisingly small boolean formulas, etc.
    are discussed in detail. To some extent, this feature may also be interesting for students and researchers in combinatorics.


    The 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.


    I 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
    Stasys Jukna

Return to the home page of the book