Testing the Independent Set Property in Hypergraphs

The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $\rho n$, or is $\epsilon$-far from having an independent set of size $\rho n$, was established to be $\tilde{O}({\rho }^3\mathrm{/}{\epsilon }^2)$, in a notable result by Blais and Seth (SICOMP 2025). In contrast, for $q$-uniform hypergraphs, there is a significant gap between the best known upper and lower bounds, and there has been no progress on the problem for the last two decades. In this work, we prove a new upper bound of $\tilde{O}\text{\hspace{0.17em}⁣}\left(\frac{q{\rho }^{2q-3}}{{\epsilon }^2(q-2){!}^2}\right)$ on the sample complexity of testing the $\rho$-independent set property. The previous best known upper bound was $\tilde{O}\text{\hspace{0.17em}⁣}\left(\frac{2^{q}q!{\rho }^{2q}}{{\epsilon }^3}\right)$, due to Langberg (RANDOM 2004). This establishes the optimal dependence on $\epsilon$ and gives an exponential improvement in the dependence on $q$. We prove our result via a new application of the hypergraph container method.