Abstract: A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of n points in the plane. Since then a great variety of extremal problems in finite point sets have been studied. Here, we look at generalizations of this question concerning regular simplices. Among others we answer the following question asked by Erdős: Given n points in R^6, how many triangles can be equilateral triangles? For our proofs we use hypergraph Turán theory and linear algebra. This is joint work with Dumitrescu and Liu.

Abstract: We show that every K4-free graph on n vertices can be made balanced bipartite by removing at most n^2/9 edges. This proves the conjecture of Balogh, Clemen and Lidický, as well as generalizes Sudakov’s result on the bipartite distance of K4-free graphs and Reiher’s result on the sparse half of K4-free graphs.

Based on a joint work with József Balogh, Ignacy Buczek and Piotr Kuc.

Abstract: TBA

Abstract: In 1984, Frankl and Pach proved that, for positive integers $n$ and $d$, the maximum size of a $(d+1)$-uniform set family $\mathcal{F}$ on an $n$-element set with  VC-dimension at most $d$ is at most ${n\choose d}$; and they suspected that ${n\choose d}$ could be replaced by ${n-1\choose d}$, which would generalize the famous Erd\H{o}s-Ko-Rado theorem.  Ahlswede and Khachatrian in 1997 constructed $(d+1)$-uniform families on an $n$-element set with VC-dimension at most $d$ and size  $\binom{n-1}{d}+\binom{n-4}{d-2}$, and Mubayi and Zhao in 2007 constructed more such families. In a recent breakthrough, Chao, Xu, Yip, and Zhang reduced the upper bound $\binom{n }{d}$ to $ \binom{n-1}{d}+O( n^{d-1-\frac{1}{4d-2}})$.  We reduce the upper bound further to $\binom{n-1}{d} + O(n^{d-2})$, asymptotically matching the lower bound $\binom{n-1}{d}+\binom{n-4}{d-2}$. This is joint work with Tianzhi Yang.

Abstract: TBA

Abstract: The Rödl nibble is a fundamental probabilistic approach for finding large matchings in hypergraphs. Classical results of Pippenger and Frankl–Rödl show that the nibble produces almost-perfect matchings in nearly D-regular hypergraphs when the maximum 2-degree is much smaller than D, and later work of Vu sharpened the quantitative dependence by incorporating higher codegrees. In this talk, I will discuss joint work with Stephen Gould that pushes this line further: we show that the nibble can essentially exhaust the full codegree sequence, up to natural bottlenecks, even when codegrees exhibit significant “clustering". I will explain the main idea behind the improvement, some generalizations to matchings in “partite” settings, and some applications to Latin squares and designs.

Abstract: TBA

Abstract: Combinatorial restrictions on additive configurations in groups often force strong algebraic structure. For example, independent work by Alon-Fox-Zhao, Sisask, and Pillay-Conant-Terry showed that if the sum graph of a set A has bounded VC-dimension, then set itself is approximately equal to unions of cosets of a subgroup.  

In this talk, I present higher-order analogues of these phenomena, joint with Julia Wolf. Here, combinatorial restrictions on the ternary sum graph of a subset of $\mathbb{F}_p^n$ lead not to linear structure, but to quadratic structure. In particular,  subsets of bounded $\mathrm{VC}_2$-dimension are approximated by unions of atoms of bounded-complexity quadratic factors. I will also discuss more recent works, joint with Wolf and Sheats respectively, which improve the quantitative aspects of these quadratic structure theorems.

Abstract: TBA

Abstract: A perfect cycle tiling is a partition of the vertex set such that each part induces a cycle.

Two examples of theorems on this topic are the Corr\'adi-Hajnal Theorem, indicating that for every $n$ divisible by $3$, every graph with minimum degree $2n/3$ contains $n/3$ vertex-disjoint triangles, and Dirac's Theorem, specifying that when $n \ge 3$, every $n$-vertex graph with minimum degree at least $n/2$ contains a Hamiltonian cycle. A common generalization of these two theorems is the El-Zahar conjecture, proved for large graphs by Abbasi, asserting that every $n$-vertex graph with minimum degree at least $(n+t)/2$ contains any given perfect cycle tiling that includes at most $t$ cycles of odd length.

In this talk, we will discuss problems on perfect cycle tilings in directed graphs, including a result that can be viewed as an asymptotically best possible analogue of the El-Zahar conjecture when all of the desired cycles have odd length.

This is joint work with Andrew Treglown.

Abstract: We present a random construction proving that the extreme off-diagonal Ramsey numbers satisfy $R(3,k)\ge  \left(\frac12+o(1)\right)\frac{k^2}{\log{k}}$ (conjectured to be asymptotically tight), improving the previously best bound $R(3,k)\ge  \left(\frac13+o(1)\right)\frac{k^2}{\log{k}}$. In contrast to all previous constructions achieving the correct order of magnitude, we do not use a nibble argument.

Beyond the paper, we will explore a bit further how the approach can be used for other problems.

This is joint work with Zion Hefty, Paul Horn and Dylan King