Computer Science/Discrete Mathematics Seminar II

The study of Turán numbers of graphs and hypergraphs is a rich problem in extremal combinatorics. The Turán problem asks, given a fixed forbidden (hyper)graph F, what is the maximum number of edges in an F-free (hyper)graph in terms of the number of vertices?

In the first half of this talk, I hope to survey some fundamental results in this area, including the techniques of Lagrangians and supersaturation. In the second half of this talk, I will talk about a recent result of mine regardinf the Turán numbers of long tight cycles, a class of hypergraphs generalizing cycles. One key ingredient in this framework, which I hope to prove in full, is a hypergraph analogue of the statement that a graph has no odd closed walks if and only if it is bipartite. More precisely, for various classes C of "cycle-like" r-uniform hypergraphs, we equivalently characterize C-free hypergraphs as those admitting a certain type of coloring of (r-1)-tuples of vertices. This provides a common generalization of several results in uniformity r=3 due to Kamčev-Letzter-Pokrovskiy and Balogh-Luo, and provides a framework with which one could understand the Turán numbers of a much larger family of "cycle like" hypergraphs.