Testing the Independent Set Property in Hypergraphs

Abstract

The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $\ddot{I}n$, or is $\epsilon$-far from having an independent set of size $\ddot{I}n$, was established to be $\tilde{O}(\ddot{I}{}^3/{\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}\left(\frac{q\ddot{I}{}^{2q-3}}{{\epsilon }^2(q-2){!}^2}\right)$ on the sample complexity of testing the $\ddot{I}$-independent set property. The previous best known upper bound was $\tilde{O}\left(\frac{2^{q}q!\ddot{I}{}^{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.

Topics & keywords