Title: The chromatic number of triangle-free hypergraphs
| Speaker: | Lina Li |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 or please contact Emma Watson for Zoom link |
Abstract:
A classical result of Johansson showed that for any triangle-free graph $G$ with maximum degree $\Delta$, it chromatic number is $O(\Delta/\log\Delta)$. This result was later generalized to all rank 3 hypergraphs due to the work of Copper and Mubayi. In this talk, I will present a common generalization of the above results to all hypergraphs, and this is sharp apart from the constant. Moreover, our result implies, generalizes, and improves several earlier results on the chromatic number and also independence number of hypergraphs, while its proof is based on a different approach than prior works in hypergraphs (and therefore provides alternative proofs to them). In particular, as an application, we establish a bound on chromatic number of sparse hypergraphs in which each vertex is contained in few triangles, and thus extend results of Alon, Krivelevich and Sudakov and Cooper and Mubayi from hypergraphs of rank 2 and 3, respectively, to all hypergraphs.
This is joint work with Luke Postle.