An Efficiently Computable Lower Bound for the Independence Number of Hypergraphs

Abstract

Let $k\ge 2$ be fixed. We study the integer lower bound $\ell (G)$ obtained by inverting the classical counting inequality for Turán systems. For a $k$-uniform hypergraph with $n$ vertices and $m$ edges, the bound can be evaluated exactly by binary search in time polynomial in the binary lengths of $n$ and $m$. We exhibit separations from the Turán-Spencer and Caro-Tuza bounds for every fixed $k\ge 3$, and from the Csaba-Plick--hokoufandeh bound in the $3$-uniform case. For the Caro-Tuza comparison, the separation grows linearly in $k$ on infinitely many regular $k$-uniform hypergraphs.

14 pages, major revision