Combinatorial Theory Seminar

The study of combinatorial designs includes some of the oldest questions at the heart of combinatorics. In a breakthrough result of 2014, Keevash proved the longstanding Existence Conjecture by showing the existence of (n,q,r)-Steiner systems (equivalently K_q^r-decompositions of K_n^r) for all large enough n satisfying the necessary divisibility conditions. Meanwhile, in recent decades, incremental progress has been made on the celebrated Nash-Williams' Conjecture of 1970, which posits that any large enough, triangle-divisible graph on n vertices with minimum degree at least 3n/4 admits a triangle decomposition. In 2021, Glock, Kühn, and Osthus proposed a generalization of these results by conjecturing a hypergraph version of the Nash-Williams' Conjecture, where their proposed minimum degree K_q^r-decomposition threshold is motivated by hypergraph Turán theory. By using the recently developed method of refined absorption and establishing a non-uniform Turán theory, we tie the K_q^r-decomposition threshold to its fractional relaxation. Combined with the best-known fractional decomposition threshold from Delcourt, Lesgourgues, and Postle, this dramatically closes the gap between what was known and the above conjecture. This talk is based on joint work with Luke Postle.

We introduce a new spanning tree model which we call Random Spanning Trees in Random Environment (RSTRE), which was introduced independently by A. Kúsz. As the inverse temperature beta varies in the underlying Gibbs measure, it interpolates between the uniform spanning tree and the minimum spanning tree. On the complete graph with n vertices, we show that with high probability, the diameter of the random spanning tree is of order n^1/2 when β=o(n/log n), and is of order n^1/3 when β > n^4/3 log n. We conjecture that the diameter exponent linearly interpolates between these two regimes as the power exponent of beta varies. Based on joint work with L. Makowiec and M. Salvi.

TBC