Testing the Independent Set Property in Hypergraphs
2026-07-14 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors focus on the problem of how many samples are needed to test whether a large hypergraph has a big independent set or is far from having one. While this problem was well-understood for normal graphs, there was a big gap for hypergraphs for over twenty years. The authors improve the known upper bound significantly, showing that fewer samples are needed than previously thought, especially in terms of the parameters involved. They achieved this by using a technique called the hypergraph container method.
sample complexityindependent sethypergraphproperty testinghypergraph container methoduniform hypergraphapproximation algorithmscombinatoricsprobabilistic methodcomplexity bounds
Authors
Elena Grigorescu, Shreya Nasa, Cameron Seth
Abstract
The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $ρn$, or is $\varepsilon$-far from having an independent set of size $ρn$, was established to be $\widetilde{O}(ρ^3/\varepsilon^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 $\widetilde{O}\!\left(\frac{qρ^{2q-3}}{\varepsilon^2 (q-2)!^2}\right)$ on the sample complexity of testing the $ρ$-independent set property. The previous best known upper bound was $\widetilde{O}\!\left(\frac{2^q q! ρ^{2q}}{\varepsilon^3}\right)$, due to Langberg (RANDOM 2004). This establishes the optimal dependence on $\varepsilon$ and gives an exponential improvement in the dependence on $q$. We prove our result via a new application of the hypergraph container method.