{"id":"arxiv/2611.20167","url":"https://arxiv.org/abs/2611.20167","tags":["math.CO"],"score":0,"title":"Maximal Independent Sets in Set Systems","domain":"math.CO","source":"arxiv","authors":["Jeroen Schillewaert","Jacques Verstraete"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-15","reactions":{}}