Contents:
Part 1: The Classics
Counting
binomial theorem, selection with repetitions, partitions,
double-counting, the averaging principle
Advanced Counting
bounds on intersection size, Zarankiewicz's problem
density of 0-1 matrices
Principle of Inclusion and Exclusion
the principle, generalizations, the number of derangements
The Pigeon-hole Principle
several quickies, Erdos-Szekeres theorem,
Mantel's theorem, Turan's theorem , Dirichlet's theorem,
swell-colored graphs, the weight-shifting argument,
pigeonhole and resolution, Haken's lower bound
Systems of distinct representatives
Hall's theorem, latin squares,
decomposition of double-stochastic matrices,
Min-Max theorems, matchings in bipartite graphs
Colorings
2-colorable families, property B, the averaging argument
the number of mixed triangles, Papadimitriou-Sipser's theorem
colouring the n-cube, Plumstead's lower bound
Part 2: Extremal Set Theory
Sunflowers
the sunflower lemma and its modifications,
the number of minterms,
small-depth formulae for threshold functions
Intersecting Families
Erdos-Ko-Rado theorem, finite ultrafilters,
maximal intersecting families, a Hely-type result,
intersecting systems of families
Chains and Antichains
chains, symmetric chains,
decomposition of posets, Dilworth's theorem,
application: the memory allocation problem,
antichains, Sperner's and the Bollobas' theorems,
application: strong systems of distinct representatives
union-free families
Blocking Sets and the Duality
duality, the blocking number,
generalized Helly theorems,
decision trees, depth, certificates, block sensitivity,
switching lemma (Razborov's proof)
lower bounds for monotone circuits (a new argument)
Density and Universality
dense sets, hereditary sets,
universal sets, Paley graphs, full graphs
Witness Sets and Isolation
Bondy's theorem, average witnesses,
the isolation lemma
application: NL is a subset of Parity-L
isolation in politics: the `dictator' paradox
Designs
regularity, finite linear spaces, difference sets,
projective planes, the construction, Bruen's theorem,
resolvable designs, affine planes,
blocking sets in affine planes
Part 3: The Linear Algebra Method
The basic method
the linear algebra background,
universality of linear codes, short linear combinations,
Fisher's inequality, balanced families, orthogonal coding,
spaces of polynomials, inclusion matrices, disjointness matrices,
sets with few intersection sizes, constructive Ramsey graphs
Scalar Product and Rank Arguments
the flipping cards game, Hadamard matrices, rigidity
rank arguments for Boolean formulae,
super-polynomial lower bounds for monotone formulae
Span Programs
the model and relation to switching networks,
small span programs for explicit problems: threshold,
non-bipartitness, odd-factors,
a general lower bound,
a lower bound for Paley graphs
Part 4: The Probabilistic Method
Basic Tools
probabilistic preliminaries,
elementary tools, advanced tools
Counting Sieve
Ramsey numbers, Van der Waerden, tournaments,
property B revised, small universal sets,
cross-intersecting families
Lovász Sieve
the local lemma,
applications: colorings and hashing functions
counting sieve with k-wise independence
Linearity of Expectation
Hamilton paths, sum-free sets, dominating sets,
the independence number, hashing functions,
low degree polynomials, maximum satisfiability
submodular complexity measures
discrepancy of matrix multiplication
The Deletion Method
Ramsey numbers, independent sets,
coloring large girth graphs,
points without obtuse trangles,
covering designs, affine cubes of integers
The Second Moment Method
the method, separators,
threshold for cliques
The Entropy Function
basic properties, subadditivity,
combinatorial applications
Random Walks
satisfying assignments for 2-CNF,
the best bet for simpletons (Conway's formula)
random walks in linear spaces and formula size,
random walks in graphs and search problems
Randomized Algorithms
Zeroes of multivariate polynomials,
verifying equality of long strings,
equivalence of branching programs,
a min-cut algorithm
Derandomization
the method of conditional probabilities,
the method of small sample spaces, k-wise independence
Part 5: Fragments of Ramsey Theory
The Ramsey's Theorem
colorings and Ramsey function, Ramsey's theorem for graphs,
general Ramsey's theorem, Schur's theorem
Ramseyan Theorems for Numbers
sum-free sets, zero-sum sets,
Szemerédi's cube lemma
The Hales-Jewett Theorem
the theorem, its consequnces,
Van der Waerden's theorem, Gallai's theorem,
Alon-Shelah proof of HJ theorem
applications: multi-party games
References and Index