Spring 2016-2017, Tuesday 16-19, Schreiber 6

School of Mathematical Sciences,

Exercises will be given during the course and their solutions will be graded.

N. Alon and J. H. Spencer,

The Probabilistic Method, Wiley, 1992. (Second Edition, 2000, Third Edition 2008, Fourth Edition 2016).B. Bollobas,

Random Graphs, Academic Press, 1985. (Second Edition, Cambridge University Press, 2001.)S. Janson, T. Luczak and A. Rucinski,

Random Graphs, Wiley, 2000.M. Molloy and B. Reed,

Graph Colouring and the Probabilistic Method, Springer, 2002.-
**: March 14**

The basic method, Ramsey numbers, Dominating sets in graphs, Hypergraph 2-coloring, Sum-free subsets, Set pairs theorem. -
**: March 21**

Linearity of expectation, Hamiltonian paths in tournaments and the conjecture of Szele, Minc Conjecture. -
**: March 28**

No class -
**: April 4**

The second moment method, Turan's proof of the Hardy Ramanujan theorem, distinct sums, random graphs and threshold functions, cliques in random graphs. -
**: April 5**

More on cliques in random graphs. Alterations: Graphs with high girth and high chromatic number, bounding of large deviations and consistent arcs in tournaments. -
**: April 11,18**

Passover -
**: April 25**

The local lemma: the general lemma and its symmetric version, Straus' problem, directed cycles. -
**: May 2**

Independence Day -
**: May 9**

Correlation inequalities: the four functions theorem and its applications, the FKG Inequality, The Harris-Kleitman Theorem, correlation between properties of random graphs. -
**: May 16**

Martingales: the edge exposure and the vertex exposure martingales, Azuma's Inequality. -
**: May 23**

More martingales, chromatic number of sparse random graphs, solution of exercises. -
**: May 30**

Shavuoth -
**: June 6**

Poisson approximation: The Janson Inequalities and their application for constructing Ramsey type graphs and for estimating the chromatic number of G(n,1/2). -
**: June 13**

Geometry: the VC dimension of a range space and its applications. -
**: June 20**

More on the VC dimension and its applications. Dominating sets in k-majority tournaments. -
**: June 27**

Gems including crossing numbers, incidences and additive number theory, the Ramsey number r(3,k), Turan numbers and dependent random choice, summary.

- Homework assignment number I
- Homework assignment number II
- Homework assignment number III
- Homework assignment number IV

redesigned by barak soreq