Richard P. Stanley Seminar in Combinatorics: Pair constructions for hypergraph Ramsey numbers

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Xiaoyu He - Princeton University

The Ramsey number r_k(G, H) of two k-uniform hypergraphs G and H is the smallest n such that any edge-coloring of the complete k-uniform hypergraph on n vertices contains either a red copy of G or a blue copy of H. Hypergraph Ramsey theory is concerned with the growth rates of such Ramsey numbers, particularly when one or both of {G, H} is a clique of size tending to infinity. Classical arguments of Erdős-Rado and Erdős-Hajnal reduce most major problems in this area from all higher uniformities to uniformity k=3, but fail to bridge the gap from the graph case k=2 to the hypergraph case k=3.

In this talk, we survey the known approaches for lifting Ramsey graphs to 3-uniform hypergraphs, most famously the stepping-up construction of Erdős-Hajnal. We collect these constructions under the umbrella term "pair constructions" and present new variations proving new lower bounds. In particular, we describe an explicit family of 3-uniform hypergraphs H (including links of odd cycles and tight cycles of length not divisible by 3) which satisfy r_3(H, K_n) > 2^{c n log n}. We also prove the existence of a linear 3-uniform hypergraph H for which r_3(H, K_n) grows superpolynomially.

Based on joint work with David Conlon, Benjamin Gunby, Jacob Fox, Dhruv Mubayi, Andrew Suk, and Jacques Verstraete.

===============================

For more info, see https://math.mit.edu/combin/