Zach Hunter

Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers

Strahinja Gvozdić, Zach Hunter, Aleksa Milojević +1

The canonical Ramsey theorem establishes that for every positive integer $t$ , there is a sufficiently large $n$ such that every edge-colouring of a complete graph $K_{n}$ contains a…

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Micha Christoph, Zach Hunter, Benny Sudakov

We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling. Using it, we show that random induced subgr…

math.PR2026

Distinguishability threshold for random geometric graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov

The spherical random geometric graph $G (n, d, p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $S^{d - 1} \subseteq R^{d}$ and joining pair…

Gilbreath's conjecture: a Cramér random model and a deterministic analysis

Zachary Chase, Zach Hunter, Terence Tao

Gilbreath's conjecture asserts that if one starts with the sequence of primes and takes successive absolute differences to create a triangular array, then the left diagonal of this…

Nearly tight bounds for induced subdivisions

Zach Hunter, Aleksa Milojević, Patryk Morawski +1

Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conject…

Three-color van der Waerden numbers grow super-exponentially

Jacob Fox, Zach Hunter

For $k$ sufficiently large, we show that there is a three-coloring of the first $2^{k (l o g^{*} k) /4}$ positive integers without any monochromatic $k$ -term arithmetic progressions. T…

cs.CC2026

Communication Complexity of Disjointness under Product Distributions

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of B…

Permanents of random matrices over finite fields

Zach Hunter, Matthew Kwan, Lisa Sauermann

Fix a finite field $F_{q}$ and let $A \in F_{q}^{n \times n}$ be a uniformly random $n \times n$ matrix over $F_{q}$ . The asymptotic distribution of the determinant…

Induced subdivisions of $K_{d + 1}$ in graphs of high girth

António Girão, Zach Hunter

In this paper, we show that for all $k \geq 1 0^{8}$ , every graph with minimum degree $k$ and girth at least $1 0^{8}$ contains an induced subdivision of a $K_{k + 1}$ . This answers a probl…

Large point-line matchings and small Nikodym sets

Zach Hunter, Cosmin Pohoata, Jacques Verstraete +1

For any integer $d \geq 2$ and prime power $q$ , we construct unexpectedly large induced matchings in the point-line incidence graph of $F_{q}^{d}$ by leveraging a new conn…

Gaussian random graphs and Ramsey numbers

Zach Hunter, Aleksa Milojević, Benny Sudakov

We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction bas…

Cyclic subsets of tournaments

Zach Hunter, Teng Liu, Aleksa Milojević +1

Let $G$ be a Dirac graph, and let $S$ be a vertex subset of $G$ , chosen uniformly at random. How likely is the induced subgraph $G [S]$ to be Hamiltonian? This question, proposed by…

An improved construction for the triangle removal lemma

Zach Hunter

We construct $n$ -vertex graphs $G$ where $ε n^{2}$ edges must be deleted to become triangle-free, which contain less than $ε^{(C_{new} - o (1)) l o g_{2} 1/ ε} n^{3}$ triangles for $C_{\t…

$C_{4}$ -free subgraphs of high degree with geometric applications

Zach Hunter, Aleksa Milojević, Istvan Tomon +1

The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$ -vertex graph that does not contain the complete bipartite g…

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Domagoj Bradač, Zach Hunter, Benny Sudakov

We prove that, for all $k \geq 3,$ and any integers $Δ, n$ with $n \geq Δ,$ there exists a $k$ -uniform hypergraph on $n$ vertices with maximum degree at most $Δ$ whose $4$ -color Rams…

Monochromatic odd cycles in edge-coloured complete graphs

António Girão, Zach Hunter

It is easy to see that every $q$ -edge-colouring of the complete graph on $2^{q} + 1$ vertices must contain a monochromatic odd cycle. A natural question raised by Erdős and Graham in $…

Disjoint pairs in set systems and combinatorics of low rank matrices

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

We study and solve several problems in two closely related settings: set families in $2^{[n]}$ with many disjoint pairs of sets and low rank matrices with many zero entries. - More…

Long induced paths in $K_{s, s}$ -free graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov +1

More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$ -free graph containing an $n$ -vertex path must contain an induced path of length $f (n)$ , where $f(n)\to…

Blowups of triangle-free graphs

António Girão, Zach Hunter, Yuval Wigderson

A highly influential result of Nikiforov states that if an $n$ -vertex graph $G$ contains at least $γ n^{h}$ copies of a fixed $h$ -vertex graph $H$ , then $G$ contains a blowup of $H$ o…

math.NT2024

Improving Behrend's construction: Sets without arithmetic progressions in integers and over finite fields

Christian Elsholtz, Zach Hunter, Laura Proske +1

We prove new lower bounds on the maximum size of subsets $A \subseteq {1, \dots, N}$ or $A \subseteq F_{p}^{n}$ not containing three-term arithmetic progressions. In the setting…

Induced Ramsey problems for trees and graphs with bounded treewidth

Zach Hunter, Benny Sudakov

The induced $q$ -color size-Ramsey number $r^_{ind} (H; q)$ of a graph $H$ is the minimal number of edges a host graph $G$ can have so that every $q$ -edge-coloring of $G$ …