Tata Institute of Fundamental Research

Method of Containers

STCS Student Seminar
Speaker: Siddharth Bhandari
Organiser: Siddharth Bhandari
Date: Friday, 11 Aug 2017, 17:15 to 18:15
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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)$.