betaFeedback

WorksMathematics

Maximal Independent Sets in Set Systems

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.

Paper details

vlnc:W_3v5ykhgd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…