A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman’s celebrated theorem first provided a structural characterization of sets with small doubling over the integers, and subsequently Ruzsa in 1999 proved an analog for abelian groups with bounded exponent. Ruzsa further conjectured the correct quantitative dependence on the doubling K in his structural result, which has attracted several interesting developments over the next two decades. I will discuss a complete resolution of (a strengthening of) Ruzsa’s conjecture. Surprisingly, our approach is crucially motivated by purely graph-theoretic insights, where we find that the group structure is superfluous and can be replaced by much more general combinatorial structures. Using this general approach, we also obtain combinatorial and nonabelian generalizations of classical results in additive combinatorics, and solve longstanding open problems around Cayley graphs and random Cayley graphs motivated by Ramsey theory, information theory and computer science. Based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.

An edge-weighted graph $G$, possibly with loops, is said to be antiferromagnetic if it has nonnegative weights and at most one positive eigenvalue, counting multiplicities. The number of graph homomorphisms from a graph $H$ to an antiferromagnetic graph $G$ generalises various important parameters in graph theory, including the number of independent sets and proper vertex colourings. We obtain a number of new homomorphism inequalities for antiferromagnetic target graphs $G$. In particular, we prove that, for any antiferromagnetic $G$, $|\mathrm{Hom}(K_d, G)|^{1/d} ≤ |\mathrm{Hom}(K_{d,d} \setminus M, G)|^{1/(2d)}$ holds, where $K_{d,d} \setminus M$ denotes the complete bipartite graph $K_{d,d}$ minus a perfect matching $M$. This confirms a conjecture of Sah, Sawhney, Stoner and Zhao for complete graphs $K_d$. Our method uses the emerging theory of Lorentzian polynomials due to Brändén and Huh, which may be of independent interest. Joint work with Jaeseong Oh and Jaehyeon Seo.

For a positive real number $p$, the $p$-norm $\|G\|_p$ of a graph $G$ is the sum of the $p$-th powers of all vertex degrees. We study the maximum $p$-norm $\mathrm{ex}_{p}(n,F)$ of $F$-free graphs on $n$ vertices, focusing on the case where $F$ is a bipartite graph. It is natural to conjecture that for every bipartite graph $F$, there exists a threshold $p_F$ such that for $p< p_{F}$, the order of $\mathrm{ex}_{p}(n,F)$ is governed by pseudorandom constructions, while for $p > p_{F}$, it is governed by star-like constructions. We determine the exact value of $p_{F}$, under a mild assumption on the growth rate of $\mathrm{ex}(n,F)$. Our results extend to $r$-uniform hypergraphs as well. We also prove a general upper bound that is tight up to a $\log n$ factor for $\mathrm{ex}_{p}(n,F)$ when $p = p_{F}$. We conjecture that this $\log n$ factor is unnecessary and prove this conjecture for several classes of well-studied bipartite graphs, including one-side degree-bounded graphs and families of short even cycles. This is a joint work with Xizhi Liu, Jie Ma and Oleg Pikhurko.

TBA

An $r$-graph is an $r$-regular graph in which every odd set of vertices is connected to its complement by at least $r$ edges. A central question regarding $r$-graphs is determining the maximum number of pairwise disjoint perfect matchings they can contain. This talk explores how edge connectivity influences this parameter. For ${0 \leq \lambda \leq r}$, let $m(\lambda,r)$ denote the maximum number $s$ such that every $\lambda$-edge-connected $r$-graph contains $s$ pairwise disjoint perfect matchings. The values of $m(\lambda,r)$ are known only in limited cases; for example, $m(3,3)=m(4,r)=1$, and $m(r,r) \leq r-2$ for all $r \not = 5$, with $m(r,r) \leq r-3$ when $r$ is a multiple of $4$. In this talk, we present new upper bounds for $m(\lambda,r)$ and examine connections between $m(5,5)$ and several well-known conjectures for cubic graphs. This is joint work with Davide Mattiolo, Eckhard Steffen, and Isaak H. Wolf.