Richard P. Stanley Seminar in Combinatorics: Ramsey and Turán numbers of sparse hypergraphs

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Jonathan Tidor - Stanford

**Special Time and Location**

The degeneracy of a graph is a central measure of sparseness in extremal graph theory. In 1966, Erdős conjectured that $d$-degenerate bipartite graphs have Turán number $O(n^{2-1/d})$. Though this is still far from solved, the bound $O(n^{2-1/4d})$ was proved by Alon, Krivelevich, and Sudakov in 2003. In a similar vein, the Burr--Erdős conjecture states that graphs of bounded degeneracy have Ramsey number linear in their number of vertices. (This is in contrast to general graphs whose Ramsey number can be as large as exponential in the number of vertices.) This conjecture was proved in a breakthrough work of Lee in 2017.In this talk, we investigate the hypergraph analogues of these two questions. Though the typical notion of hypergraph degeneracy does not give any information about either the Ramsey or Turán numbers of hypergraphs, we instead define a notion that we call skeletal degeneracy. We prove the hypergraph analogue of the Burr--Erdős conjecture: hypergraphs of bounded skeletal degeneracy have Ramsey number linear in their number of vertices. Furthermore, we give good bounds on the Turán number of partite hypergraphs in terms of their skeletal degeneracy. Both of these results use the technique of dependent random choice.

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

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