Maximal Independent Sets in Set Systems
Source: arxiv.org/abs/2611.20167
We prove a general theorem on the existence of small maximal independent sets in set systems satisfying natural local density conditions. For an antichain whose degrees are uniform and whose small sets lie in few blocks and whose links overlap little, we show that there is a maximal independent set whose size is asymptotically given by an explicit expression in the degrees, as the degrees grow. The proof comes with a polynomial-time algorithm that finds such a set. This improves on known results for independent sets in uniform hypergraphs; in particular, in a linear uniform hypergraph of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.20167
curl -X POST /api/v1/records/arxiv/2611.20167/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.20167/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'