Three fifteen-minute talks by local speakers.
Logan Post: Almost all even-parity binary words are shuffle squares
Jasper Seabold: Using Grid Graphs to Study Hypergraph Ramsey Questions
Adri Wessels:
Using the theory of total linear stability for Dynkin quivers and an interplay between the Bruhat order and the noncrossing partition lattice, we define a family of triangulations of the permutohedron indexed by Coxeter elements. Each triangulation is constructed to give an explicit homotopy between two complexes (the Salvetti complex and the Bessis--Brady--Watt complex) associated to two different presentations of the corresponding braid group (the standard Artin presentation and Bessis's dual presentation). Our triangulations have several notable combinatorial properties. In addition, they refine similar Bruhat interval polytope decompositions of Knutson, Sanchez, and Sherman-Bennett. This is based on joint work with Melissa Sherman-Bennett and Nathan Williams.
Given a graph $F$, a graph $G$ is weakly $F$-saturated if all non-edges of $G$ can be added in some order so that each new edge introduces a copy of $F$. The weak saturation number $wsat(n,F)$ is the minimum number of edges in a weakly $F$-saturated graph on $n$ vertices. Bollobás initiated the study of weak saturation in 1968 to study percolation processes, which originated in biology and have applications in physics and computer science. It was shown by Alon that for each $F$, there is a constant $w_F$ such that $wsat(n,F) = w_F n + o(n)$. We characterize all possible rational values of $w_F$, proving in particular that $w_F$ can equal any rational number at least $3/2$. The techniques involve a combination of random and deterministic constructions and structural methods. Joint work with Xiaoyu He.
Given an $r$-uniform hypergraph $H$, the random Turán number $\mathrm{ex}(G^r_{n,p},H)$ is the maximum number of edges in an $H$-free subgraph of $G^r_{n,p}$, where $G^r_{n,p}$ is the Erdős-Rényi random hypergraph with parameter $p$. In the case when $H$ is not r-partite, the problem has been essentially solved independently by Conlon-Gowers and Schacht. In the case when $H$ is $r$-partite, the degenerate case, only some sporadic results are known.
The Sidorenko conjecture is a notorious problem in extremal combinatorics. It is known that its hypergraph analog is not true. Recently, Conlon, Lee, and Sidorenko discovered a relation between the Sidorenko conjecture and the Turán problem.
In this talk, we introduce some recent results on the degenerate random Turan problem and its relation to the hypergraph analog of the Sidorenko conjecture.
What is the smallest number of edges that a graph can have if it contains all $D$-degenerate graphs on $n$ vertices as subgraphs? A counting argument shows that this number is at least of order $n^{2−1/D}$, assuming n is large enough. We show that this is tight up to a polylogarithmic factor.
Joint work with Peter Allen and Julia Böttcher.
In this talk, the speaker will present three applications of information theory in applied spaces. No background on information theory, hypergraphs, or RF signals analysis will be assumed. Bill Kay is a pure mathematician in combinatorics by training who now lives in an applied space at Pacific Northwest National Laboratory.
It is a fundamental question in Ramsey theory to determine the smallest possible independence number of an H-free hypergraph on n vertices. In the case of graphs, the problem was famously solved for H=K3 by Kim and for H=K4 (up to a logarithmic factor) by Mattheus-Verstraete in 2023. Even C4 and K5 remain wide open. We study the problem for 3-uniform hypergraphs and conjecture a full classification: the minimum independence number is poly(n) if and only if H is contained in the iterated blowup of the single-edge hypergraph. We prove this conjecture for all H with at most two tightly connected components. Based on joint work with Conlon, Fox, Gunby, Mubayi, Suk, Verstraete, and Yu.
Let $d\geq 2$, and $n\geq 2d+2$. Frankl and Pach initiated the study of the maximum size of a $(d+1)$-uniform set system in $[n]$ with VC-dimension at most $d$. The best-known upper bound is essentially $\binom{n}{d}$, and the best-known lower bound is $\binom{n-1}{d} + \binom{n-4}{d-2}$. In this talk, I will discuss some recent improvements on the upper bound and some interesting connections between this problem and the celebrated Erdős--Ko--Rado theorem. In particular, I will discuss our conjecture, which can be viewed as a generalization of the EKR as well as an "uniform version" of the disproved Erdős--Frankl--Pach conjecture, and highlight some of our partial progress. Joint work with Ting-Wei Chao, Zixiang Xu, and Shengtong Zhang.
The Hales--Jewett theorem, one of the fundamental results of Ramsey theory, guarantees that when an $n$-dimensional $t \times t \times \dots \times t$ grid is colored with $r$ colors, if $n$ is sufficiently large depending on $r$ and $t$, then the grid contains a line of $t$ collinear points of the same color (possibly with some further restrictions on the line). If you know a second fact about the Hales--Jewett theorem, it is probably that the upper bounds on $n$ grow incredibly quickly (even after tremendous improvement from Shelah in 1988).
In this talk, we will survey the general upper bounds on the Hales--Jewett numbers and move on to results for specific values of $r$ and $t$. We show an upper bound of ``only'' about $10^{11}$ on $n$ when $r=2$ and $t=4$, and discuss the challenges and open questions in extending this to larger cases.
A basic result of probabilistic combinatorics, originally due to Erdős and Rényi, is the determination of the threshold at which the random graph $G_{n,p}$ contains a triangle with high probability. But one can also ask more refined versions of this question, where we ask not just for one triangle but for many triangles which interact in complicated ways. For example, what is the threshold at which we can no longer partition $G_{n,p}$ into two triangle-free subgraphs?
In this talk, I will discuss the proof of the Kohayakawa–Kreuter conjecture, which gives a general answer to all such questions. Rather surprisingly, a key step of the proof is a purely deterministic graph decomposition statement, closely related to classical results such as Nash-Williams' tree decomposition theorem, whose proof uses techniques from combinatorial optimization and structural graph theory.
Based on joint works with Micha Christoph, Eden Kuperwasser, Anders Martinsson, Wojciech Samotij, and Raphael Steiner.
