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