New upper bounds on the smallest size of a saturating set in a projective plane
Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco · 2016
In a projective plane Πq(not necessarily Desar-guesian) 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, more general than those previously used for saturating sets, the following upper bound on the smallest size s(2, q) of a saturating set in Πqis proved: s(2, q)1 a random point set of size k in Πqwith 2c√(q + 1) ln(q + 1) + 22-1/q+2 ~ 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 ⊂ Πqis (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 l is computed as (#(l∩S)2). The following upper bound on the smallest size sμ(2, q) of a (1,μ)-saturating set in Πqis proved: sμ(2, q) <; 2(μ + 1)√(q + 1)ln(q + 1) + 2 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.