School of Technology and Computer Science Seminars

Method of Containers

by Siddharth Bhandari (School of Technology and Computer Science (TIFR))

Friday, August 11, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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)$.