On independent sets in uncrowded uniform hypergraphs

Abstract

We prove an average-degree lower bound on the independence number of uncrowded uniform hypergraphs. For every fixed $r\ge 2$ and every $\hat{I}\cdot >0$, there exists $d_{\ast }=d_{\ast }(r,\hat{I}\cdot )$ such that any uncrowded $(r+1)$-uniform hypergraph $G$ with $n$ vertices and average degree $d\ge d_{\ast }$ satisfies \[ α(G)\geq (1-η)r^{-1/r}\left(\frac{\log d}{d}\right)^{1/r}n. \] The proof combines a cleaning procedure, which reduces the maximum top-layer degree to the average scale, with a random nibble procedure that repeatedly extracts independent vertices while controlling all lower-order degrees created by the process. After an initial top-layer cleaning, we run a trace nibble. Since the residual hypergraph contains traces of all sizes $2,\dots ,r+1$, we track the maximum degrees in every layer. A binomial-type recurrence for this degree profile yields the stated leading constant.

21 pages. More details added and typos corrected