Combinatorics Seminar
The Probabilistic
Method: Some Techniques and Results
Spring 2003
Topics
 The basic method: a lower bound on ramsey numbers,
S_k property of tournaments, sumfree subsets, bipartite subgraphs,
balancing vectors in R^n.
 The second moment method. An estimate on the number
of prime divisors (Turan).
 The random graph: definition, thresholds of properties,
the clique number, thresholds of balanced subgraphs.
Additional reading (suitable for presentation):
 J. Spencer: Nine lectures on random graphs.
[postscript]
A nice introduction to the probabilistic method and random graphs.

J. Spencer: Applications of Talagrand's inequality.
[postscript]
An intoduction to concentration with applications.

M. Krivelevich: Bounding ramsey number through large
deviation inequalities.
[postscript]
A lower bound on ramsey numbers via the chernoff inequality.

J. Spencer: Maximal K_3free graphs and ramsey r(3,k).
[postscript]
A continuous approach to random combinatorial constructions.

A. Frieze, B. Reed: Covering the edges of a random graph by cliques.
[postscript]
An analysis of a probabilistic algorithm
with a nice combinatorial application.

N. Alon, J. Spencer:
The probabilistic method.
John Wiley 2000 (ISBN 0471370460).

B. Bollobas:
Random graphs.
Cambridge University PRess 2001 (ISBN 0521809207).

S. Janson, T. Luczak, A. Rucinski:
Random graphs.
John Wiley & Sons, N.Y. 2000 (ISBN 0471175412).