2026/06/16 by Jing Yu, Junchi Zhang
#math.CO
We prove an average-degree lower bound on the independence number of uncrowded uniform hypergraphs. For every fixed r≥ 2 and every η>0, there exists d_*=d_*(r,η) such that any uncrowded (r+1)-uniform hypergraph G with n vertices and average degree d≥ d_* satisfies α(G)≥ (1-η)r-1/r((log d)/(d))1/rn. 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,…,r+1, we track the maximum degrees in every layer. A binomial-type recurrence for this degree profile yields the stated leading constant.