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)
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)$. |