|
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:
- expander graphs and eigenvalues,
- the polynomial method and
- error-correcting codes.
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
|