Tutorial on the Container Method
Many important theorems and conjectures in combinatorics can be rephrased as problems about counting independent sets in some specific graphs and hypergraphs. The Container Method, whose basic idea can be traced back to Kleitman-Winston, and has recently been further developed by Balogh-Morris-Samotij and Saxton-Thomason, essentially states that hypergraphs satisfying some natural conditions have very few independent sets. In this survey-style talk I will show some recent applications of the method, and try to give an easy recipe containing all the key ideas one needs to know to prove similar results.
Hamiltonicity games on random graphs with Waiter and Client
In this talk, we consider two types of two player, perfect information games with no chance moves; the Waiter-Client and Client-Waiter Hamiltonicity games played on the edge set of the binomial random graph G(n,p). We determine a sharp probability threshold for both games. Namely, for every fixed positive integer q, we prove that the smallest edge probability p for which a.a.s. Waiter has a winning strategy for the (1:q) Waiter-Client Hamiltonicity game on G(n,p) is (1+o(1))log n/n, and the smallest p for which a.a.s. Client has a winning strategy for the (1:q) Client-Waiter Hamiltonicity game on G(n,p) is (q+1+o(1))log n/n. We discuss these results in relation to a surprising heuristic, known as the probabilistic intuition, that suggests that the player with the highest chance of winning when both players play randomly is the winner when both players play optimally. This is joint work with Dan Hefetz and Michael Krivelevich (Tel Aviv University).
Multicolour Ramsey numbers of paths and even cycles
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that the k-colour Ramsey number of both an n-vertex path and, for even n, an n-vertex cycle is between (k-1)n+o(n) and kn+o(n).
Here we obtain the first improvement to the coefficient of the linear term in the upper bound by an absolute constant.
On the average size of independent sets in triangle-free graphs
We prove an asymptotically tight lower bound on the average size of an independent set in a triangle-free graph on n vertices with maximum degree d, showing that an independent set drawn uniformly at random from such a graph has expected size at least n(1 + o_d(1))log d /d. This gives an alternative proof of Shearer's upper bound on the Ramsey number R(3, k). In fact we work with the hard-core model from statistical physics, obtaining a lower bound on the occupancy fraction of triangle-free graphs that implies the above result and more, including a lower bound on the total number of independent sets. Finally, we make several conjectures which give a new perspective on the problem of determining R(3,k).