2015/05/06 by Daniele Bartoli, Alexander A. Davydov, Bartoli, Daniele +7
Computer Science · Mathematics · #51E22 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #Primary: 51E21 #Secondary: 94B05 #math.CO #msc:51E21 #msc:51E22 #msc:94B05
paper · pdf · doi:10.48550/arxiv.1505.01426
15 pages, 24 references, misprints are corrected, Sections 3-5 and some references are added
openalex publication_date 2015/05/06 · arxiv created 2016/05/17 · arxiv updated 2016/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Using probabilistic methods, the following upper bound on the smallest size s(2,q) of a saturating set in Πq is proved: s(2,q)≤ 2√((q+1)ln (q+1))+2\thicksim 2√(qln q). We also show that for any constant c≥ 1 a random point set of size k in Πq with 2c√((q+1)ln(q+1))+2≤ k<\fracq2-1q+2\thicksim q is a saturating set with probability greater than 1-1/(q+1)^2c2-2. Our probabilistic approach is also applied to multiple saturating sets. A point set S⊂ Πq is (1,μ)-saturating if for every point Q of Πq∖ S the number of secants of S through Q is at least μ, counted with multiplicity. The multiplicity of a secant ℓ is computed as \binom#(ℓ ∩ S)2. The following upper bound on the smallest size sμ(2,q) of a (1,μ)-saturating set in Πq is proved: sμ(2,q)≤ 2(μ+1)√((q+1)ln (q+1))+2\thicksim 2(μ+1)√( qln q) for 2≤ μ≤ √(q). By using inductive constructions, upper bounds on the smallest size of a saturating set (as well as on a (1,μ)-saturating set) in the projective space PG(N,q) are obtained. All the results are also stated in terms of linear covering codes.