New upper bounds on the smallest size of a saturating set in a projective plane

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, more general than those previously used for saturating sets, an upper bound on the smallest size of a saturating set in Πq is proven. Our probabilistic approach is also applied to multiple saturating sets. 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.