The independence number of uncrowded hypergraphs: bounds matching the shattering threshold

A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph with maximum degree $\mathrm{\Delta }$ contains an independent set of size $c_{k}n{\left(\frac{\log \mathrm{\Delta }}{\mathrm{\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\ge 2$, every $n$-vertex $k$-uniform uncrowded hypergraph of sufficiently large maximum degree $\mathrm{\Delta }$ contains an independent set of size at least $(1-\epsilon )n{\left(\frac{1}{k-1}\frac{\log \mathrm{\Delta }}{\mathrm{\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 $\mathrm{\Delta }$ has independence number at least $c_{k}n{\left(\frac{\log \mathrm{\Delta }}{\mathrm{\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\mathrm{\Delta })$-time randomized static algorithm and an $\tilde{O}(1)$-round randomized $\mathsf{\text{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.