Tao Jiang
Miami University
Title
Balanced supersaturation and its applications to enumeration problems
Abstract
In extremal combinatorics, supersaturation problems study how many copies of a given substructure $F$ there are when a host set system is sufficiently dense. Recently, a lot of attention was focused on a balanced variant of the problem in which we wish to find a collection of copies of $F$ that is not only dense but also covers every subset of edges ``uniformly''. Such balanced supersaturation results have been used in conjunction with the powerful container method to yield much progress on the problem of enumerating $F$-free graphs or hypergraphs.
In this talk, we discuss two recent results on the enumeration problem obtained via the balanced supersaturation approach. Given an $r$-graph $F$, an $r$-graph $G$ is $F$-free if it does not contain $F$ as a subgraph. Let ${\rm ex}_r(n,F)$ denote the maximum number of edges in an $n$-vertex $F$-free $r$-graph and let ${\rm forb}(n,F)$ denote the number of $n$-vertex $F$-free $r$-graphs. We show for $r\geq 4$, ${\rm forb} (n,F)=2^{(1+o(1)){\rm ex}_r(n,F)}$ for a large family of $r$-partite $r$-graphs known as $2$-contractible hypertrees. This is the first known family of $r$-partite $r$-graphs achieving such a bound. For $r\geq 5$, it answers a conjecture of Balogh, Narayanan, and Skokan on the number of $r$-graphs not containing a given linear cycle. This is joint work with Sean Longbrake.
Let $H$ be any tree poset of height $k$. Let $La^*(n,H)$ denote the maximum size of a subfamily of the boolean lattice $B_n$ that does not contain $H$ as an induced subposet. Let ${\rm forb^*}(n,H)$ denote the number of induced $P$-free subfamily of $B_n$. We show that ${\rm forb^*}(n,H)=2^{(k-1+o(1))\binom{n}{n/2}}$, and that with high probability the largest induced $H$-free subfamily of a $p$-random subfamily of $B_n$, for
$p\gg n^{-1}$ has size $(k-1+o(1))p\binom{n}{n/2}$. These strengthen or extend earlier work of Balogh, Garcia, and Wigal, and of Balogh, Mycroft, and Treglown, and of Collares and Morris. This is joint work with Sean Longbrake, Sam Spiro, and Liana Yepremyan.