Method of Containers

Siddharth Bhandari
Siddharth Bhandari
Friday, 11 Aug 2017, 17:15 to 18:15
A-201 (STCS Seminar Room)
A recent powerful method has been independently developed by Saxton and Thomason (2012) and by Balogh, Morris, Samotij (2014). This method supplies a structural characterisation of the independent sets in uniform hypergraphs satisfying certain natural conditions, by showing that in such hypergraphs every independent set is almost fully contained in one of a small number of sparse sets (called containers). We shall see an application of the above method by Saxton and Thomason to prove the following result (Alon'00): list chromatic number of any graph with average degree $d$ is $\Omega(\log d)$.