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

preprint2016arXivOpen access

Abstract

In a projective plane ΠqΠ_{q} (not necessarily Desarguesian) of order q,q, a point subset SS is saturating (or dense) if any point of Πq∖SΠ_{q}\setminus S is collinear with two points in S~S. Using probabilistic methods, the following upper bound on the smallest size s(2,q) s(2,q) of a saturating set in ΠqΠ_{q} is proved: \begin{equation*} s(2,q)\leq 2\sqrt{(q+1)\ln (q+1)}+2\thicksim 2\sqrt{q\ln q}. \end{equation*} We also show that for any constant c≥1c\ge 1 a random point set of size kk in ΠqΠ_{q} with 2c(q+1)ln⁡(q+1)+2≤k<q2−1q+2∼q 2c\sqrt{(q+1)\ln(q+1)}+2\le k<\frac{q^{2}-1}{q+2}\thicksim q is a saturating set with probability greater than 1−1/(q+1)2c2−2.1-1/(q+1)^{2c^{2}-2}. Our probabilistic approach is also applied to multiple saturating sets. A point set S⊂ΠqS\subset Π_{q} is (1,μ)(1,μ)-saturating if for every point QQ of Πq∖SΠ_{q}\setminus S the number of secants of SS through QQ is at least μμ, counted with multiplicity. The multiplicity of a secant ℓ \ell is computed as (#(ℓ ∩S)2).{\binom{\#(\ell \,\cap S)}{2}}. The following upper bound on the smallest size sμ(2,q)s_{μ}(2,q) of a (1,μ)(1,μ)-saturating set in ΠqΠ_{q} is proved: \begin{equation*} s_{μ}(2,q)\leq 2(μ+1)\sqrt{(q+1)\ln (q+1)}+2\thicksim 2(μ+1)\sqrt{ q\ln q}\,\text{ for }\,2\leq μ\leq \sqrt{q}. \end{equation*} By using inductive constructions, upper bounds on the smallest size of a saturating set (as well as on a (1,μ)(1,μ)-saturating set) in the projective space PG(N,q)PG(N,q) are obtained. All the results are also stated in terms of linear covering codes.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.