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, sum-free 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_3-free 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 0-471-37046-0).
-
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 0-471-17541-2).