Delphi.science

Maximal Independent Sets in Set Systems

Source: arxiv.org/abs/2611.20167

Jeroen Schillewaert, Jacques Verstraete

arXivarxiv/2611.20167Nov 15, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'