Thursday, December 5, 2019 2:00 PM
Xiaoyu He (Stanford)
A well-known result of Chung, Graham, and Wilson states that all notions of graph quasirandomness are the same, but it turns out that several different notions of quasirandomness exist for hypergraphs. In this talk, we mix-and-match these notions to produce new Ramsey hypergraphs which are quasirandom in one way yet structured in a different way. In particular, we give a probabilistic construction for a 3-uniform hypergraph on N vertices with independence number O(log N / loglog N) in which there are at most two edges among any four vertices. This bound is tight and solves a problem of Erdős and Hajnal from 1972. Joint work with Jacob Fox.