CSC 2427/MAT 1500: The Probabilistic Method

Spring 2015

Thursday 2-4, PB255

Text: The Probabilistic Method by Alon and Spencer

Course Information

Assignments

Assignment 1 is due on Jan 26.

Assignment 2 is due on Mar 11.

Assignment 3 is due on Apr 7.

Readings

Radhakrishnan and Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures and Algorithms 16, 4-32 (2000).

Alon, McDiarmid and Molloy. Edge disjoint cycles in regular directed graphs. Journal of Graph Theory 22, 231-237 (1996).

Alon, McDiarmid and Reed. Acyclic coloring of graphs. Random Structures and Algorithms 2, 277-288 (1991).

Molloy and Reed. Colouring graphs when the number of colours is almost the maximum degree. Journal of Combinatorial Theory (B) 109, 134-195 (2014).

McDiarmid and Reed. On total colourings of graphs. Journal of Combinatorial Theory (B) 57, 122-130 (1993).

Kim. On Brook's Theorem for sparse graphs. Combinatorics, Probability and Computing 4, 97-132 (1995).

Moser and Tardos. A constructive proof of the general Lovasz Local Lemma. Journal of the ACM 57(2) (2010).

Molloy and Reed. Asymptotically optimal frugal colouring. Journal of Combinatorial Theory (B) 100, 226-246 (2010).

Molloy. The list chromatic number of graphs with small clique number. Journal of Combinatorial Theory (B) 134, 264-284 (2019).

Bradshaw, Mohar, Stacho. Bipartite graphs are (4/5 - \eps) D/log D choosable. arXiv

Shearer. On the independence number of sparse graphs. Random Structures and Algorithms 7, 269-271 (1995).

Bissacot, Fernandez, Procacci, Scoppola An Improvement of the Lovász Local Lemma via Cluster Expansion Combinatorics, Probability and Computing 20, 709-719 (2011).

Campos, Griffiths, Morrix, Sahasrabudhe An exponential improvement for diagonal Ramsey arXiv

Gupta, Ndiaye, Norin, Wei. Optimizing the CGMS upper bound on Ramsey numbers arXiv

Wigderson Upper bounds on diagonal Ramsey numbers (after CGMS) arXiv

Mattheus, Verstraete. The asymptotics of r(4,t) arxiv