Paperlane

no. 16 · Tuesday 17 November 2026

Maximal Independent Sets in Set Systems

Jeroen Schillewaert and Jacques Verstraete

math.CO · 160 pp

Abstract

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 large bounded degree, we find an independent set of explicit asymptotic size. Among the applications, we obtain complete arcs in finite projective spaces that come within logarithmic factors of the counting lower bound, improving the known results on Segre's complete arc problem. We also show that, for a wide class of multivariable polynomials, there is a maximal set in a finite field avoiding solutions of the polynomial whose size lies within logarithmic factors of the elementary lower bound.

comments
160 pages, comments welcome, for the actual abstract see the paper, this is an abbreviation due to Arxiv size restriction of abstract
fields
Combinatorics
pdf ↗ page arXiv:2611.20167 ↗