Upper bounds on the smallest size of a saturating set in projective planes and spaces of even dimension

2017/02/25 by Daniele Bartoli, Alexander Davydov, Bartoli, Daniele +7
Computer Science · Mathematics · #51E21 #51E22 #94B05 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.IT #math.CO #math.IT #msc:51E21 #msc:51E22 #msc:94B05

paper · pdf · doi:10.48550/arxiv.1702.07939

14 pages, 34 references, 1 figure

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

Abstract

In a projective plane Π_q (not necessarily Desarguesian) of order q, a point subset S is saturating (or dense) if any point of Π_q∖ S is collinear with two points in S. Modifying an approach of [31], we proved the following upper bound on the smallest size s(2,q) of a saturating set in Π_q: s(2,q)≤ √((q+1)(3ln q+lnln q +ln(3)/(4)))+√((q)/(3ln q))+3. The bound holds for all q, not necessarily large. By using inductive constructions, upper bounds on the smallest size of a saturating set in the projective space PG(N,q) with even dimension N are obtained. All the results are also stated in terms of linear covering codes.

Related

• On upper bounds on the smallest size of a saturating set in a projective plane
• Saturating sets in projective planes and hypergraph covers
• On the minimum size of linear sets
• Large (k; r, s; n, q)-sets in Projective Spaces
• Untouchable sets of size 2q ± 1 in PG(2,q)