Jukna, S.,

Extremal Combinatorics

With Applications in Computer Science

Preface to the Second Edition

This second edition has been extended with substantial new material, and has been revised and updated throughout. In particular, it offers three new chapters about: Most of the remaining chapters also include new material such as the Kruskal--Katona theorem about shadows, the Lovasz--Stein theorem about coverings, large cliques in dense graphs without induced 4-cycles, a new lower bounds argument for monotone formulas, Dvir's solution of finite field Kakeya's conjecture, Moser's algorithmic version of the Lovasz Local Lemma, Schoning's algorithm for 3-SAT, the Szemeredi--Trotter theorem about the number of point-line incidences, applications of expander graphs in extremal number theory, and some other results. Also, some proofs are made shorter and new exercises are added. And, of course, all errors and typos observed by the readers in the first edition are corrected.

I received a lot of letters from many readers pointing to omissions, errors or typos as well as suggestions for alternative proofs -- such an enthusiastic reception of the first edition came as a great surprise. The second edition gives me an opportunity to incorporate all the suggestions and corrections in a new version. I am therefore thankful to all who wrote me, and in particular to: S. Akbari, S. Bova, E. Dekel, T. van Erven, D. Gavinsky, Qi Ge, D. Gunderson, S. Hada, H. Hennings, T. Hofmeister, Chien-Chung Huang, J. Hünten, H. Klauck, W. Koolen-Wijkstra, D. Krämer, U. Leck, Ben Pak Ching Li, D. McLaury, T. Mielikäinen, G. Mota, G. Nyul, V. Petrovic, H. Prothmann, P. Rastas, A. Razen, C.J. Renteria, M. Scheel, N. Schmitt, D. Sieling, T. Tassa, A. Utturwar, J. Volec, F. Voloch, E. Weinreb, A. Windsor, R. de Wolf, Qiqi Yan, A. Zilberstein, and P. Zumstein.

I thank everyone whose input has made a difference for this new edition. I am especially thankful to Thomas Hofmeister, Detlef Sieling and Ronald de Wolf who supplied me with the reaction of their students. The ``error-probability'' in the 2nd edition was reduced by Ronald de Wolf and Philipp Zumstein who gave me a lot of corrections for the new stuff included in this edition. I am especially thankful to Ronald for many discussions---his help was extremely useful during the whole preparation of this edition. All remaining errors are entirely my fault.


    Frankfurt/Vilnius, August 2011
    Stasys Jukna

Return to the home page of the book