View PDF

Abstract:A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph with maximum degree $\Delta$ contains an independent set of size $c_k n{\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}}$, for some constant $c_k>0$. Determining the optimal leading constant $c_k$ in this bound is a major open problem. A natural target is the so-called shattering-threshold constant $\left(\frac{1}{k-1}\right)^{\frac{1}{k-1}}$, which appears in the solution-space geometry of random constraint satisfaction problems, in average-case complexity theory, and in statistical physics, among other areas.
We prove that uncrowded hypergraphs attain this threshold. More precisely, for every $\epsilon>0$ and $k\geq 2$, every $n$-vertex $k$-uniform uncrowded hypergraph of sufficiently large maximum degree $\Delta$ contains an independent set of size at least $(1-\epsilon) n {\left(\frac{1}{k-1}\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}}$. Consequently, we obtain the first pseudorandom class of hypergraphs whose guaranteed independence number matches the shattering threshold, resolving a folklore conjecture. Moreover, as another direct consequence, we resolve a conjecture of Verstraëte and Wilson by proving that there exists a constant $c_k=1-o_k(1)$ such that every $n$-vertex $k$-uniform linear hypergraph of maximum degree $\Delta$ has independence number at least $c_k n\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}$.
Our techniques are constructive yielding efficient algorithms for both static and distributed settings. Specifically, we provide an $\tilde O(n\Delta)$-time randomized static algorithm and an $\tilde O(1)$-round randomized $\textsf{LOCAL}$ algorithm to find an independent set in uncrowded hypergraphs at the shattering threshold. These results extend seamlessly to the the setting of linear hypergraphs.

Submission history

From: Abhishek Dhawan [view email]
[v1] Tue, 16 Jun 2026 15:24:58 UTC (43 KB)