Upper bounds on the smallest size of a saturating set in projective planes and spaces of even dimension
Daniele Bartoli Alexander Davydov Massimo Giulietti Stefano Marcugini Fernanda Pambianco




Upper bounds on the smallest size of a saturating set in
projective planes and spaces of even dimensionThe research of  D. Bartoli, M. Giulietti, S. Marcugini, and F. Pambianco was
 supported in part by Ministry for Education, University
and Research of Italy (MIUR) (Project “Geometrie di Galois e
strutture di incidenza”)
 and by the Italian National Group for Algebraic and Geometric Structures and their Applications
 (GNSAGA - INDAM).
 The research of A.A. Davydov was carried out at the IITP RAS at the expense of the Russian
Foundation for Sciences (project 14-50-00150).
    S. Capozziello^1,2,3, G. Lambiase^4,5, and E.N. Saridakis^6,7
    
==================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



Daniele Bartoli

Dipartimento di Matematica  e Informatica,
   Università degli Studi di Perugia

Perugia, 06123, Italy
 E-mail address: daniele.bartoli@unipg.it

Alexander A. Davydov

Institute for Information Transmission Problems (Kharkevich institute)

 Russian Academy of
 Sciences
 GSP-4, Moscow, 127994, Russian Federation
E-mail address: adav@iitp.ru

 Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco

 Dipartimento di Matematica  e Informatica,
  Università degli Studi di Perugia

 Perugia, 06123, Italy

 E-mail address: massimo.giulietti, stefano.marcugini, fernanda.pambianco@unipg.it



In a projective plane Π _q (not necessarily Desarguesian)
of order q, a point subset  is saturating (or dense) if
any point of Π _q∖ is collinear with two points
in. Modifying an approach of <cit.>, 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 +ln3/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 (N,q) with even dimension N are obtained.

All the results are also stated in terms of linear covering codes.




§ INTRODUCTION


We denote by Π _q a projective plane (not necessarily
Desarguesian) of order q and by (2,q) the projective
plane over the Galois field with q elements.


 A point set ⊂Π _q is
saturating if any point of Π _q∖ is
collinear with two points in .


Saturating sets are considered, for example, in <cit.>;
see also the references therein. It should be noted that
saturating sets are also called “saturated
sets” <cit.>, “spanning
sets” <cit.>, “dense sets”
<cit.>, and “1-saturating sets”
<cit.>.

A particular kind of saturating sets in a projective plane is complete arcs.  An arc is a set
of points no three of which are collinear. An arc is said to be complete if it cannot be extended to a large arc;
see <cit.> and the references therein.

The homogeneous coordinates of the points of a saturating set
of size k in PG(2,q) form a parity check matrix of a
q-ary linear code with length k, codimension 3, and
covering radius 2. For an introduction to covering codes see
<cit.>. An online
bibliography on covering codes is given in <cit.>.

The main problem in this context is to find small saturating
sets (i.e. short covering codes).

Denote by s(2,q)  the
smallest size of a saturating set in Π _q.

Let s_D(2,q) be
the smallest size of a saturating set in the Desarguesian plane (2,q).

Let t_2(2,q) be
the smallest size of a complete arc in  (2,q).

Clearly,

    s_D(2,q)≤ t_2(2,q).


The trivial lower bound is

    s(2,q),s_D(2,q),t_2(2,q)>√(2q)+1.


Saturating sets in (2,q) obtained by
algebraic constructions or computer search can be found in
<cit.>.

For  (2,q) with q non-prime, in the literature there are a few algebraic constructions
of relatively small saturating sets providing, for instance, the following upper bounds:

    s_D(2,q)<3√(q)-1      if      q=(q')^2   ;
       s_D(2,q)<2√(q)+2√(q)+2      if      q=(q')^4   ;
       s_D(2,q)<2√(q)+2√(q)+2√(q)+2      if      q=(q')^6, q' , q'≤73   ;
       s_D(2,q)<2√(q^m-1)+√(q)      if      q=(q')^m, m≥2   <cit.>.


Saturating sets of size approximately Cq^3/4, with C a constant independent on q, have been explicitly described in several
papers; see <cit.>.

In <cit.>, algebraic constructions of saturating sets in
(2,q) of size about 3q^2/3 are proposed
and the following bounds are obtained (here p is prime):

    s_D(2,q)<2q/p^ t+(p^ t-1)^2/p-1+1      if       q=p^m, m≥ 2t;
       s_D(2,q)<2/p√((qp)^2)+√((qp)^2)-2√(qp)+1/p-1
    +1      if       q=p^3t-1;
       s_D(2,q)<min_v=1,… ,2t+1Φ(t,p,v)      if       q=p^2t+1,


    where Φ(t,p,v)={ (v+1)p^t+1+(p^t-1)^2v/
    (p-1)^v(p^2t+1-1)^(v-1)+2}.

For many triples (t,p,v), constructions of (<ref>) provide relatively small saturating sets, see <cit.>.

In <cit.>, by computer search in a wide region of q, the following upper bounds for the smallest sizes of complete arcs in (2,q) are obtained:

    s_D(2,q)≤ t_2(2,q)<0.998√(3qln q)            7≤ q≤ 160001;
       s_D(2,q)≤ t_2(2,q)<1.05√(3qln q)            160001< q≤ 301813.

For q≤160001 greedy algorithms are used while for 160001< q≤ 301813 the algorithm with fixed order of points (FOP) is applied.

In <cit.>, for (2,q)  an iterative step-by-step construction of complete
arcs, which adds a new point in each step, is considered. As an example, it is noted
the step-by-step greedy algorithm that in every step adds to the arc a point providing the maximal possible (for the
given step) number of new covered points. For more than half of steps of the iterative process, an
estimate for the number of new covered points in every step is proved. A natural (and well-founded)
conjecture is made that the estimate holds for the other steps too. Under this conjecture, the following upper
bound on the smallest size  of a complete arc in  (2,q) is obtained.

    conjectural bound:  s_D(2,q)≤ t_2(2,q)<√(q)√(3ln q+lnln q+ln 3)+√(q/3ln q)+3.

Note also that in <cit.> a truncated iterative step-by-step process is considered. The process stops when  the
number of uncovered points attains some (a priori arbitrary assigned) value. Then this value is summarized with the number of steps, executed before stopping of the iterative process. The estimate (<ref>) is obtained when the value, a priori assigned to stop the process, is √(q/3ln q); it implies that
the number of the steps, executed before stopping of the step-by-step process, is √(q)√(3ln q+lnln q+ln 3).

Surveys and results of probabilistic constructions for geometrical objects can be
found in <cit.>; see also the
references therein.

In <cit.>, by using a modified probabilistic approach
introduced in <cit.>, the following upper
bound for an arbitrary (not necessarily Desarguesian) plane is proved:

    s(2,q)<3√(2)√(qln q)<5√(qln q).

In <cit.>, see also <cit.>, by probabilistic methods different from these in <cit.> the upper bound

    s(2,q)≤ 2√((q+1)ln (q+1))+2 2√(qln q)

is obtained.

In <cit.>, Z. Nagy obtained the following bound

    s(2,q)≤ (√(3)+o(1))√(qln q)).

The proof of (<ref>) is given in <cit.> by two approaches: probabilistic and algorithmic. In the both approaches, starting with some stage of the proof,
it is assumed (by the context) that q is large enough.

The algorithmic
approach in <cit.> considers an original  step-by-step greedy algorithm and obtains estimates for the number of new covered points in every step of the algorithm.
In order to obtain the bound, the
iterative process stops after executing of ⌈√(3qln q) ⌉ steps. It is proved in <cit.>, that in this case the number of uncovered points is not greater than √(q). Then the half of the number of uncovered points is summarized with the number of executed steps. As the result of the algorithmic proof of <cit.>, the following form of the bound can be derived.

    s(2,q)≤⌈√(3qln q) ⌉+⌈1/2√(q)⌉≤√(3qln q)+1/2√(q)+2,   q large enough.


In some sense the algorithmic approach of <cit.> is close to consideration of bounds in <cit.>.  But in <cit.> the number of steps, executed before stopping of the iterative process, depends on a priori assigned number of uncovered points. At the same time, in <cit.> the
iterative process always stops after executing of ⌈√(3qln q) ⌉ steps. Of course, it must be noted that
in <cit.> the bound is conjectural (as the estimates are not proved for all steps of the iterative greedy process)
 whereas in <cit.> the bound is proved. Note also that problems considered in <cit.>  and <cit.> are close but not the same (small complete arcs in <cit.>  and small saturating sets in <cit.>).

In this paper, we modify the algorithmic approach of <cit.> so that the final formula holds for an arbitrary q (not necessarily large) and, moreover,
the value of a new bound is smaller  than in (<ref>), see (<ref>)–(<ref>).

Our main results is Theorem <ref>.

 For the smallest size s(2,q) of a saturating set
in a projective plane (not necessarily Desarguesian) of order q (not necessarily large) the following upper bound
holds:

    s(2,q)≤√((q+1)(3ln q+lnln q +ln3/4))+√(q/3ln q)+3.



Note that modifying the algorithmic approach of <cit.>, we (similarly to <cit.>) stop the iterative process when  the
number of uncovered points attains a priori assigned value, ξ say. If ξ=1 we obtain the bound coinciding with   (<ref>); if ξ=√(q) we obtain the bound coinciding with   (<ref>), see Remark <ref>. Finally, if ξ=√(4q/3ln q) we get the bound    (<ref>).



It is interesting that the main term √(3qln q) is the same in the bounds (<ref>), (<ref>) for complete arcs and (<ref>)–(<ref>),
(<ref>) for saturating sets.


Theorem <ref> can be expressed in terms of covering codes.

The length function ℓ (R,r,q) denotes the smallest
length of a q-ary linear code with covering radius R and
codimension r; see <cit.>.

Theorem <ref>
can be read as follows.


The following upper bound on the length function holds.

    ℓ (2,3,q)≤√((q+1)(3ln q+lnln q +ln3/4))+√(q/3ln q)+3.



Let (N,q) be the N-dimensional projective space over the
Galois field of q elements.


A point set ⊂(N,q) is saturating if any
point of (N,q)∖ is collinear with two points in
.


A particular kind of saturating sets in a projective space is complete caps.  A cap is a set
of points no three of which are collinear. A cap is said to be complete if it cannot be extended to a large cap.

Let [n,n-r]_qR be a linear q-ary code of length n,
codimension r, and covering radiusR. The homogeneous
coordinates of the points of a saturating set with size n in
(r-1,q), form a parity check matrix of an [n,n-r]_q2
code.

 Results on saturating sets in (N,q) and the corresponding covering codes can be found  in <cit.>
and the references therein.

Let s(N,q) be the smallest size of a saturating set in
(N,q), N≥ 3.

In terms of covering codes, we recall the
equality

    s(N,q)=ℓ (2,N+1,q).


The trivial lower bound for s(N,q) is

    s(N,q)>√(2)q^N-1/2.

Constructions of saturating sets (or the corresponding covering codes) whose
size is close to this lower bound are only known for N odd, see <cit.> for survey. In particular,
in <cit.>, see also <cit.>, the following bound is obtained by algebraic constructions:

    s(N,q)=ℓ (2,N+1,q)≤ 2q^N-1/2+q^N-3/2,   N=2t-1≥3, N≠7,11, q≥7, q≠9,

where t=2,3,5, and t≥7.

From (<ref>), by
using inductive constructions from <cit.>, we obtained upper bounds on the
smallest size of a saturating set in the N-dimensional
projective space (N,q) with N even; see Section
<ref>. In many cases these bounds are better than the
known ones.

The paper is organized as follows. In Section
<ref>, we deal with upper bounds on the smallest
size of a saturating set in a projective plane.  In Section <ref>, bounds
for saturating  sets in the projective
space (N,q) are obtained.



§ A MODIFICATION OF NAGY'S APPROACH FOR UPPER BOUND ON THE SMALLEST SIZE OF A SATURATING SET IN A
PROJECTIVE PLANE


Assume that in Π_q a saturating set
 is constructed by a step-by-step algorithm adding one new point to the set in
every step.

Let i>0 be an integer. Denote by _i the running set obtained after the
i-th step of the algorithm. A point P of Π_q∖_i is covered by _i if P lies on t-secant of _i with t≥2.
 Let _i be the subset of  Π_q∖_i consisting of points not covered by _i.

 In <cit.> the following ingenious greedy algorithm is proposed. One takes the line ℓ skew to _i such that the cardinality of intersection |_i∩ℓ| is the minimal among all skew lines.
Then one adds to _i the point on ℓ providing the greatest number of new covered points (in comparison with other points of ℓ). As a result we obtain the set _i+1 and the corresponding set _i+1.

The following Proposition is proved in <cit.>.
<cit.> It holds that

    |_i+1|≤|_i|·(1-i(q-1)/q(q+1)).



Clearly, that always

    _2=q^2.


Iteratively applying the relation (<ref>) to _2=q^2, we obtain for some k the following:

    |_k+1|≤ q^2∏_i=2^k(1-i(q-1)/q(q+1)).


We denote

    f_q(k)=∏_i=2^k(1-i(q-1)/q(q+1)).


Similarly to <cit.>, we consider a truncated iterative process. We will stop the iterative process when |_k+1|≤ξ where ξ≥ 1 is some value that we may assign arbitrary to improve estimates.

By <cit.> after the end of the iterative process we can add at most ⌈ |_k+1|/2⌉ points to
the running subset _k+1 in order to get the final saturating set .

The size s of the obtained set  is

    s≤ k+1+⌈ξ/2⌉ under condition q^2f_q(k)≤ξ.


Using the inequality 1-x≤ e^-x we obtain that

    f_q(k)<e^-∑_i=2^ki(q-1)/q^2+q=e^-(k^2+k-2)(q-1)/
    2(q^2+q),

which implies

    f_q(k) <e^-(k^2+k-2)(q-1)/2(q^2+q)<e^-k^2/2q+2,

provided that

    (k^2+k-2)(q-1)/q>k^2

or, equivalently,

    k^2/k-2<q-1,


    k<q-4.



  Let ξ≥1 be a fixed value independent of k. The value

    k≥⌈√(2(q+1))√(lnq^2/ξ)  ⌉

satisfies  inequality q^2f_q(k)≤ξ.



By (<ref>), to provide q^2f_q(k)≤ξ it
is sufficient to find k such that

    e^-k^2/2q+2< ξ/q^2.





In a plane Π_q it holds that

    s(2,q)≤√(2(q+1))√(ln
    q^2/ξ)+ξ/2+3,  ξ≥ 1,

where ξ is an arbitrarily chosen value.



The assertion follows from (<ref>) and (<ref>).


     We consider
the function of ξ of the form

    ϕ(ξ)=√(2(q+1))√(ln
    q^2/ξ)+ξ/2+3.

Its derivative by ξ is

    ϕ'(ξ)=1/2-1/ξ√(q+1/2lnq^2/ξ).

Put ϕ'(ξ)=0. Then it is easy to see that

    ξ^2=q+1/ln q-1/2lnξ.

We find ξ in the form ξ=√(q+1/cln q). By (<ref>),

    c=1-ln(q+1)/4ln q+ln c+lnln q/4ln q.

For simplicity, we choose c≈3/4 and put

    ξ =√(4q/3ln q).


Now, substituting ξ =√(4q/3ln q) in (<ref>), we obtain Theorem <ref>.


                
  (i) Let ξ=1. From (<ref>) we have
    
    s(2,q)≤2√((q+1)ln q)+3,

that practically coincides with  bound (<ref>) from <cit.>.
                
  (ii)  Let ξ=√(q). From (<ref>) we obtain the estimate
    
    s(2,q)≤√(3(q+1)ln q)+1/2√(q)+3
which  practically coincides with Nagy's bound (<ref>).
However, as it is noted below, the value ξ =√(4q/3ln q) gives a better estimate than (<ref>).
              


We denote the difference

    Δ(q)=√(3qln q)+1/2√(q)+2-(√((q+1)(3ln q+lnln q +ln3/4))+√(q/3ln q)+3).

It can be shown (e.g. by consideration of the corresponding derivations) that

    Δ(q)>0  for  q≥919,

and, moreover, Δ(q) and Δ(q)/√(q) are increasing functions of q.
For illustration, see Fig. <ref> where the top dashed-dotted black curve shows Δ(q) while the bottom solid red curve √(q/7) is given for comparison.






Note also that

    Δ(q)/√(q)≈√(3ln q)+1/2-√(3ln q+lnln q)-1/√(3ln q) ,
       Δ(q)/√(qln q)≈√(3)+1/2√(ln q)-√(3+lnln q/ln q)-1/√(3)ln q ,

whence

    lim_q→∞Δ(q)/√(q)=1/2,
    lim_q→∞Δ(q)/√(qln q)=0.




§ UPPER BOUNDS ON THE SMALLEST SIZE OF A SATURATING SET IN THE
PROJECTIVE SPACE (N,Q), N EVEN


In further we use the results of <cit.> that give the following inductive construction.

 <cit.> <cit.>
  Let  exist an [n_q,n_q-3]_q2 code with n_q<q.
 Then, under condition q+1≥ 2n_q, there is an infinite family of
[n,n-r]_q2 codes with r=2t-1≥
5, r≠ 9,13, n=n_qq^t-2+2q^t-3, where t=3,4,6, and t≥8.
For r=9,13, it holds that n=n_qq^t-2+2q^t-3+q^t-4+q^t-5.


Now due to one-to-one correspondence between covering codes and saturating sets we obtain the corollary from Theorem <ref> and Proposition <ref>.
We denote

    Υ(q)=√((q+1)(3ln q+lnln q +ln3/4))+√(q/3ln q)+3.



For the smallest size s(N,q) of a
saturating set in the projective space (N,q) and for the length function ℓ (2,N+1,q),
the following upper bounds hold:
                                  
  (i) 
    s(N,q)=ℓ (2,N+1,q)≤Υ(q)· q^N-2/2+2q^N-4/2,   N=2t-2≥
    4,   N≠ 8,12,

where  t=3,4,6, and t≥8,  q≥79.
                                  
  (ii) 
    s(N,q)=ℓ (2,N+1,q)≤Υ(q)· q^N-2/2+2q^N-4/2+q^N-6/2+q^N-8/2,   N=8,12.

                                



By Theorem <ref>, in (2,q) there is a saturating set with size n_q=Υ(q).
 From the corresponding [n_q,n_q-3]_q2
code,
one can obtain an [n,n-r]_q2 codes with parameters as in Proposition <ref>. The condition q+1≥ 2n_q holds for q≥79.


Surveys of the known [n,n-r]_q2 codes and saturating sets
in (N,q) with N even can be found in <cit.>.
In many cases bounds (<ref>), (<ref>) is better
than the known ones.

99
Bartocci U. Bartocci, Dense k-systems in Galois planes, Boll. Un. Mat. Ital. D
(6), 2(1), (1983) 71–77.

BDGMP_SatSetArxiv D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco, On upper bounds on the smallest size of a saturating
set in a projective plane, arXiv:1505.01426 [math.CO] (2015). https://arxiv.org/abs/1505.01426

BDGMP_SatSet_Petersb D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco,
New upper bounds on the smallest size of a saturating set in a projective plane.
In: Proc. 2016 XV International Symposium Problems of Redundancy in Information and Control Systems (REDUNDANCY),
Russia, St.-Petersburg, September 2016, pp. 18–22. http://ieeexplore.ieee.org/document/7779320/

BDFKMP-PIT2014 D. Bartoli, A. A. Davydov, G. Faina,
    A.A. Kreshchuk, S. Marcugini, F. Pambianco,
    Upper bounds on the smallest size  of a complete arc in PG(2,q)
 under a certain probabilistic conjecture, Problems
 Inform. Transmission 50 (2014), 320–339.

BDFKMP_ComplArc_JG2016 D. Bartoli, A. A. Davydov, G. Faina, A. A. Kreshchuk, S. Marcugini, and F. Pambianco,
Upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane based on
computer search, J. Geom. 107 (2016), 89–117.

BFMP-JG2013 D. Bartoli, G. Faina, S. Marcugini, and  F.
    Pambianco, On the minimum size of complete arcs and minimal
    saturating sets in projective planes, J. Geom. 104
    (2013), 409–419.

BFMP-JG2017 D. Bartoli, G. Faina, S. Marcugini, and F. Pambianco, A construction of small complete
caps in projective spaces, J. Geom., to appear, DOI: 10.1007/s00022-016-0335-1

BorSzTic E. Boros, T. Szőnyi, and K. Tichler, On
    defining sets for projective planes, Discrete Math.
    303 (2005), 17–31.

Handbook-coverings R. A. Brualdi, S. Litsyn, and V.S.
    Pless, Covering Radius, V.
    S. Pless, W. C. Huffman, and R. A. Brualdi (Eds.), Handbook of Coding Theory,
   vol. 1, pp. 755–826, Elsevier, Amsterdam, The Netherlands, 1998.

BrPlWi R. A. Brualdi, V. S. Pless, and R. M. Wilson,
    Short codes with a given covering radius, IEEE Trans.
    Inform. Theory 35 (1989), 99–109.

CHLS-bookCovCod G. Cohen, I. Honkala, S. Litsyn, and A.
    Lobstein, Covering Codes, North-Holland, Amsterdam, The
    Netherlands, 1997.

DavCovCodeSatSetIEEE1995 A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry,
  IEEE Trans. Inform. Theory 41, (1995) 2071-2080.

DavCovRad2 A. A. Davydov, Constructions and families
    of nonbinary linear codes with covering radius 2, IEEE
    Trans. Inform. Theory 45 (1999), 1679–1686.

DGMP_CovCodeNonBin_Pamporovo A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco,
Linear covering codes over nonbinary finite fields. In:
Proc. XI Int. Workshop on Algebraic and Combintorial Coding Theory, ACCT2008, Pamporovo, Bulgaria, June 2008, pp. 70–75.
http://www.moi.math.bas.bg/acct2008/b12.pdf

DGMP_CovCodeR23_Petersb2008 A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco,
Linear covering codes of radius 2 and 3. In:
Proc. Workshop “Coding Theory Days in St. Petersburg”, Saint-Petersburg, Russia, October 2008, pp. 12-17. ISBN 978-5-8088-0378-7
http://iitp.ru/upload/publications/1538/CoverPeter2008.pdf

DGMP-AMC A. A. Davydov, M. Giulietti, S. Marcugini, and
     F. Pambianco, Linear nonbinary covering codes and
    saturating sets in projective spaces, Adv. Math. Commun.
    5 (2011), 119–147.

DMP-JCTA2003 A. A. Davydov, S. Marcugini, and  F.
    Pambianco, On saturating sets in projective spaces, J.
    Combin. Theory Ser. A 103 (2003), 1–15.

DavOst-EJC A. A. Davydov and P. R. J. Östergård,
On saturating sets in small projective geometries,
Europ. J. Combinatorics 21 (2000), 563–570.

DavOst-IEEE2001 A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius R = 2,3 and
codimension tR, IEEE Trans. Inform. Theory 47 (2001), 416–421.

FainaGiul  G. Faina and M. Giulietti, On
    small dense
    arcs in Galois planes of square order, Discrete Math. 267 (2003),
    113-125.

GacsSzonyi A. Gács and T. Szőnyi, Random
    constructions and density results, Des. Codes Cryptogr.
    47 (2008), 267–287.

Giul-plane M. Giulietti, On small dense sets in
    Galois planes, Electronic J. Combin. 14 (2007), #75.

Giul2013Survey M. Giulietti, The geometry of covering
    codes: small complete caps and saturating sets in Galois
    spaces,  S. R. Blackburn,
    R. Holloway, and M. Wildon (Eds.), Surveys in Combinatorics 2013, London Math. Soc. Lect.
    Note Series, vol. 409, pp.
    51–90, Cambridge Univ Press, 2013.

GiulTor M. Giulietti and F. Torres, On
    dense sets related to plane algebraic curves, Ars Combin. 72 (2004),
    33-40.

Janwa1990 H. Janwa, Some optimal codes from algebraic
    geometry and their covering radii, Europ. J. Combin. 11
    (1990), 249–266.

KV J. H. Kim and V. H. Vu, Small complete arcs in
    projective planes, Combinatorica 23 (2003),
    311–363.

 Kiss_Cayley  G. Kiss, I. Kovács, K. Kutnar, J. Ruff, and P. Ŝparl,
 A note on a geometric construction of large Cayley graphs of given degree and diameter,
 Stud. Univ. Babes-Bolyai Math. 54 (2009), no. 3, 77–84.

Kovacs S. J. Kovács, Small saturated sets in
    finite projective planes, Rend. Mat. (Roma) 12
    (1992), 157–164.

LobstBibl A. Lobstein, Covering radius, an online
    bibliography, 

    http://perso.telecom-paristech.fr/126lobstein/bib-a-jour.pdf

MP_Austr2003 S. Marcugini and F. Pambianco,  Minimal
    1-saturating sets in PG(2,q),
Australas. J.  Combin. 28 (2003), 161-169.

Nagy Z. L. Nagy, Saturating sets in projective planes and hypergraph
covers,arXiv:1701.01379 [math.CO] (2017) http://arxiv.org/abs/1701.01379

SzonyiPhD T. Szönyi, Complete arcs in finite projective geometries. PhD thesis, Univ.
L. Eötvös, Budapest, 1984.

SzonyiSurvey T. Szönyi, Complete arcs in galois planes: a survey, Quaderni del Seminario
di Geometrie Combinatorie 94, Dipartimento di Matematica “G. Castelnuovo”,
Università degli Studi di Roma “La Sapienza”, Roma, January 1989.

Ughi E. Ughi, Saturated configurations of points in
    projective Galois spaces, Europ. J. Combin. 8 (1987),
    325–334.


