August  2016, 10(3): 613-632. doi: 10.3934/amc.2016030

Further results on multiple coverings of the farthest-off points

1. 

Department of Mathematics, Ghent University, Gent, 9000, Belgium

2. 

Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, GSP-4, Moscow, 127994, Russian Federation

3. 

Department of Mathematics and Informatics, Perugia University, Perugia, 06123, Italy, Italy, Italy

Received  May 2015 Revised  October 2015 Published  August 2016

Multiple coverings of the farthest-off points ($(R,\mu)$-MCF codes) and the corresponding $(\rho,\mu)$-saturating sets in projective spa\-ces $\mathrm{PG}(N,q)$ are considered. We propose some methods which allow us to obtain new small $(1,\mu)$-saturating sets and short $(2,\mu)$-MCF codes with $\mu$-density either equal to 1 (optimal saturating sets and almost perfect MCF-codes) or close to 1 (roughly $1+1/cq$, $c\ge1$). In particular, we provide some algebraic constructions and bounds. Also, we classify minimal and optimal $(1,\mu)$-saturating sets in $\mathrm{PG}(2,q)$, $q$ small.
Citation: Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Further results on multiple coverings of the farthest-off points. Advances in Mathematics of Communications, 2016, 10 (3) : 613-632. doi: 10.3934/amc.2016030
References:
[1]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points and multiple saturating sets in projective spaces,, in Proc. XIII Int. Workshop Algebr. Combin. Coding Theory, (2012), 53.   Google Scholar

[2]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points with small density from projective geometry,, Adv. Math. Commun., 9 (2015), 63.  doi: 10.3934/amc.2015.9.63.  Google Scholar

[3]

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.  doi: 10.1007/s00022-013-0178-y.  Google Scholar

[4]

E. Boros, T. Szőnyi and K. Tichler, On defining sets for projective planes,, Discrete Math., 303 (2005), 17.  doi: 10.1016/j.disc.2004.12.015.  Google Scholar

[5]

R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius,, in Handbook of Coding Theory (eds. V.S. Pless, (1998), 755.   Google Scholar

[6]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes,, North-Holland, (1997).   Google Scholar

[7]

A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry,, IEEE Trans. Inform. Theory, 41 (1995), 2071.  doi: 10.1109/18.476339.  Google Scholar

[8]

A. A. Davydov, G. Faina, M. Giulietti, S. Marcugini and F. Pambianco, On constructions and parameters of symmetric configurations $v_k$,, Des. Codes Cryptogr., 80 (2016), 125.  doi: 10.1007/s10623-015-0070-x.  Google Scholar

[9]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, On the spectrum of possible parameters of symmetric configurations,, in Proc. XII Int. Symp. Probl. Redundancy Inform. Control Systems, (2009), 59.   Google Scholar

[10]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New inductive constructions of complete caps in $PG(N,q)$, $q$ even,, J. Comb. Des., 18 (2010), 176.   Google Scholar

[11]

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.  doi: 10.3934/amc.2011.5.119.  Google Scholar

[12]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes,, Graphs Combin., 29 (2013), 187.  doi: 10.1007/s00373-011-1103-5.  Google Scholar

[13]

M. Giulietti, On small dense sets in Galois planes,, Electr. J. Combin., 14 (2007).   Google Scholar

[14]

M. Giulietti, Small complete caps in $PG(N,q), q$ even,, J. Combin. Des., 15 (2007), 420.  doi: 10.1002/jcd.20131.  Google Scholar

[15]

M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces,, in Surveys in Combinatorics, (2013), 51.   Google Scholar

[16]

M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4,, IEEE Trans. Inform. Theory, 53 (2007), 1928.  doi: 10.1109/TIT.2007.894688.  Google Scholar

[17]

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

[18]

H. O. Hämäläinen, I. S. Honkala, M. K. Kaikkonen and S. N. Litsyn, Bounds for binary multiple covering codes,, Des. Codes Cryptogr., 3 (1993), 251.  doi: 10.1007/BF01388486.  Google Scholar

[19]

H. O. Hämäläinen, I. S. Honkala, S. N. Litsyn and P. R. J. Östergård, Bounds for binary codes that are multiple coverings of the farthest-off points,, SIAM J. Discrete Math., 8 (1995), 196.  doi: 10.1137/S0895480193252100.  Google Scholar

[20]

H. Hämäläinen, I. Honkala, S. Litsyn and P. Östergård, Football pools - a game for mathematicians,, Amer. Math. Monthly, 102 (1995), 579.  doi: 10.2307/2974552.  Google Scholar

[21]

H. O. Hämäläinen and S. Rankinen, Upper bounds for football pool problems and mixed covering codes,, J. Combin. Theory Ser. A, 56 (1991), 84.  doi: 10.1016/0097-3165(91)90024-B.  Google Scholar

[22]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields,, Oxford Univ. Press, (1998).   Google Scholar

[23]

I. S. Honkala, On the normality of multiple covering codes,, Discrete Math., 125 (1994), 229.  doi: 10.1016/0012-365X(94)90164-3.  Google Scholar

[24]

I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory,, Bull. Inst. Combin., 17 (1996), 39.   Google Scholar

[25]

P. R. J. Östergård and H. O. Hämäläinen, A new table of binary/ternary mixed covering codes,, Des. Codes Cryptogr., 11 (1997), 151.  doi: 10.1023/A:1008228721072.  Google Scholar

[26]

F. Pambianco, D. Bartoli, G. Faina and S. Marcugini, Classification of the smallest minimal 1-saturating sets in $PG(2,q)$, $q\le 23$,, Electron. Notes Discrete Math., 40 (2013), 229.   Google Scholar

[27]

F. Pambianco, A. A. Davydov, D. Bartoli, M. Giulietti and S. Marcugini, A note on multiple coverings of the farthest-off points,, Electron. Notes Discrete Math., 40 (2013), 289.   Google Scholar

[28]

J. Quistorff, On Codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 41 (2000), 469.   Google Scholar

[29]

J. Quistorff, Correction: On codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 42 (2001), 601.   Google Scholar

[30]

T. Szőnyi, Complete arcs in Galois planes: a survey,, in Quaderni del Seminario di Geometrie Combinatorie 94, (1989).   Google Scholar

[31]

G. J. M. van Wee, G. D. Cohen and S. N. Litsyn, A note on perfect multiple coverings of the Hamming space,, IEEE Trans. Inform. Theory, 37 (1991), 678.   Google Scholar

show all references

References:
[1]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points and multiple saturating sets in projective spaces,, in Proc. XIII Int. Workshop Algebr. Combin. Coding Theory, (2012), 53.   Google Scholar

[2]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points with small density from projective geometry,, Adv. Math. Commun., 9 (2015), 63.  doi: 10.3934/amc.2015.9.63.  Google Scholar

[3]

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.  doi: 10.1007/s00022-013-0178-y.  Google Scholar

[4]

E. Boros, T. Szőnyi and K. Tichler, On defining sets for projective planes,, Discrete Math., 303 (2005), 17.  doi: 10.1016/j.disc.2004.12.015.  Google Scholar

[5]

R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius,, in Handbook of Coding Theory (eds. V.S. Pless, (1998), 755.   Google Scholar

[6]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes,, North-Holland, (1997).   Google Scholar

[7]

A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry,, IEEE Trans. Inform. Theory, 41 (1995), 2071.  doi: 10.1109/18.476339.  Google Scholar

[8]

A. A. Davydov, G. Faina, M. Giulietti, S. Marcugini and F. Pambianco, On constructions and parameters of symmetric configurations $v_k$,, Des. Codes Cryptogr., 80 (2016), 125.  doi: 10.1007/s10623-015-0070-x.  Google Scholar

[9]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, On the spectrum of possible parameters of symmetric configurations,, in Proc. XII Int. Symp. Probl. Redundancy Inform. Control Systems, (2009), 59.   Google Scholar

[10]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New inductive constructions of complete caps in $PG(N,q)$, $q$ even,, J. Comb. Des., 18 (2010), 176.   Google Scholar

[11]

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.  doi: 10.3934/amc.2011.5.119.  Google Scholar

[12]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes,, Graphs Combin., 29 (2013), 187.  doi: 10.1007/s00373-011-1103-5.  Google Scholar

[13]

M. Giulietti, On small dense sets in Galois planes,, Electr. J. Combin., 14 (2007).   Google Scholar

[14]

M. Giulietti, Small complete caps in $PG(N,q), q$ even,, J. Combin. Des., 15 (2007), 420.  doi: 10.1002/jcd.20131.  Google Scholar

[15]

M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces,, in Surveys in Combinatorics, (2013), 51.   Google Scholar

[16]

M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4,, IEEE Trans. Inform. Theory, 53 (2007), 1928.  doi: 10.1109/TIT.2007.894688.  Google Scholar

[17]

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

[18]

H. O. Hämäläinen, I. S. Honkala, M. K. Kaikkonen and S. N. Litsyn, Bounds for binary multiple covering codes,, Des. Codes Cryptogr., 3 (1993), 251.  doi: 10.1007/BF01388486.  Google Scholar

[19]

H. O. Hämäläinen, I. S. Honkala, S. N. Litsyn and P. R. J. Östergård, Bounds for binary codes that are multiple coverings of the farthest-off points,, SIAM J. Discrete Math., 8 (1995), 196.  doi: 10.1137/S0895480193252100.  Google Scholar

[20]

H. Hämäläinen, I. Honkala, S. Litsyn and P. Östergård, Football pools - a game for mathematicians,, Amer. Math. Monthly, 102 (1995), 579.  doi: 10.2307/2974552.  Google Scholar

[21]

H. O. Hämäläinen and S. Rankinen, Upper bounds for football pool problems and mixed covering codes,, J. Combin. Theory Ser. A, 56 (1991), 84.  doi: 10.1016/0097-3165(91)90024-B.  Google Scholar

[22]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields,, Oxford Univ. Press, (1998).   Google Scholar

[23]

I. S. Honkala, On the normality of multiple covering codes,, Discrete Math., 125 (1994), 229.  doi: 10.1016/0012-365X(94)90164-3.  Google Scholar

[24]

I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory,, Bull. Inst. Combin., 17 (1996), 39.   Google Scholar

[25]

P. R. J. Östergård and H. O. Hämäläinen, A new table of binary/ternary mixed covering codes,, Des. Codes Cryptogr., 11 (1997), 151.  doi: 10.1023/A:1008228721072.  Google Scholar

[26]

F. Pambianco, D. Bartoli, G. Faina and S. Marcugini, Classification of the smallest minimal 1-saturating sets in $PG(2,q)$, $q\le 23$,, Electron. Notes Discrete Math., 40 (2013), 229.   Google Scholar

[27]

F. Pambianco, A. A. Davydov, D. Bartoli, M. Giulietti and S. Marcugini, A note on multiple coverings of the farthest-off points,, Electron. Notes Discrete Math., 40 (2013), 289.   Google Scholar

[28]

J. Quistorff, On Codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 41 (2000), 469.   Google Scholar

[29]

J. Quistorff, Correction: On codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 42 (2001), 601.   Google Scholar

[30]

T. Szőnyi, Complete arcs in Galois planes: a survey,, in Quaderni del Seminario di Geometrie Combinatorie 94, (1989).   Google Scholar

[31]

G. J. M. van Wee, G. D. Cohen and S. N. Litsyn, A note on perfect multiple coverings of the Hamming space,, IEEE Trans. Inform. Theory, 37 (1991), 678.   Google Scholar

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[2]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[3]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020381

[4]

Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117

[5]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[6]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[7]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158

[8]

Federico Rodriguez Hertz, Zhiren Wang. On $ \epsilon $-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365

[9]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[10]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

[11]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[12]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (45)
  • HTML views (0)
  • Cited by (1)

[Back to Top]