On independent sets in uncrowded uniform hypergraphs
We prove an average-degree lower bound on the independence number of uncrowded uniform hypergraphs. For every fixed $r\geq 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\geq d_*$ 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.18171
curl -X POST /api/v1/records/arxiv/2606.18171/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.18171/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'