Saturating sets in projective planes and hypergraph covers

2017/01/05 by Zoltán Lóránt Nagy, Nagy, Zoltán Lóránt
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1701.01379

10 pages, detailed calculations are included compared to V1

arxiv created 2017/11/25 · arxiv updated 2017/11/28

Abstract

Let Π_q be an arbitrary finite projective plane of order q. A subset S of its points is called saturating if any point outside S is collinear with a pair of points from S. Applying probabilistic tools we improve the upper bound on the smallest possible size of the saturating set to \lceil√3qlnq\rceil+ \lceil(√(q)+1)/2\rceil. The same result is presented using an algorithmic approach as well, which points out the connection with the transversal number of uniform multiple intersecting hypergraphs.

Related

• On upper bounds on the smallest size of a saturating set in a projective plane
• Upper bounds on the smallest size of a saturating set in projective planes and spaces of even dimension
• Blocking Planes by Lines in PG(n,q)
• A new lower bound for the size of an affine blocking set
• Classification of minimal 1-saturating sets in PG(2,q), q≤ 23