UBC Discrete Math Seminar: Jonathan Tidor

The degeneracy of a graph is a measure of sparseness that gives important information about its Ramsey- and Turán-type properties. I will talk about the hypergraph extension of these problems. The typical notion of hypergraph degeneracy does not give any information about either the Ramsey or Turán numbers of hypergraphs; instead we introduce a notion called skeletal degeneracy. We prove the hypergraph generalization 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 exponent of partite hypergraphs in terms of their skeletal degeneracy. The proofs of these results use probabilistic techniques including dependent random choice.

Based on joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou.