Independence number of hypergraphs under degree conditions

Abstract

A well-known result of Ajtai et al. from 1982 states that every $k$-graph $H$ on $n$ vertices, with girth at least five, and average degree $t^{k-1}$ contains an independent set of size $cn(\log t{)}^{1/(k-1)}/t$ for some $c>0$. In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3 and 4. Our work is motivated by a problem of Lo and Zhao, who asked for $k\ge 4$, how large of an independent set a $k$-graph $H$ on $n$ vertices necessarily has when its maximum $(k-2)$-degree ${\Delta }_{k-2}(H)\le dn$. (The corresponding problem with respect to $(k-1)$-degrees was solved by Kostochka, Mubayi, and Varstraëte [Random Structures & Algorithms 44, 224--239, 2014].) In this paper we show that every $k$-graph $H$ on $n$ vertices with ${\Delta }_{k-2}(H)\le dn$ contains an independent set of size $c(\frac{n}{d}\log \log \frac{n}{d}{)}^{1/(k-1)}$, and under additional conditions, an independent set of size $c(\frac{n}{d}\log \frac{n}{d}{)}^{1/(k-1)}$. The former assertion gives a new upper bound for the $(k-2)$-degree Turán density of complete $k$-graphs.

To appear in Random Structures & Algorithms