American Institute of Mathematical Sciences

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

Further results on multiple coverings of the farthest-off points

Daniele Bartoli 1, , Alexander A. Davydov 2, , Massimo Giulietti 3, , Stefano Marcugini 3, and  Fernanda Pambianco 3,

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.
Keywords: farthest-off points, Multiple coverings, covering density., covering codes, saturating sets in projective spaces.
Mathematics Subject Classification: Primary: 51E21, 51E22; Secondary: 94B0.
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]

Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Multiple coverings of the farthest-off points with small density from projective geometry. Advances in Mathematics of Communications, 2015, 9 (1) : 63-85. doi: 10.3934/amc.2015.9.63
[2]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[3]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129
[4]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025
[5]

Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035
[6]

Maciej J. Capiński. Covering relations and the existence of topologically normally hyperbolic invariant sets. Discrete & Continuous Dynamical Systems - A, 2009, 23 (3) : 705-725. doi: 10.3934/dcds.2009.23.705
[7]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251
[8]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399
[9]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161
[10]

Maciej J. Capiński, Piotr Zgliczyński. Covering relations and non-autonomous perturbations of ODEs. Discrete & Continuous Dynamical Systems - A, 2006, 14 (2) : 281-293. doi: 10.3934/dcds.2006.14.281
[11]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[12]

Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672
[13]

Simon Lloyd, Edson Vargas. Critical covering maps without absolutely continuous invariant probability measure. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2393-2412. doi: 10.3934/dcds.2019101
[14]

Maciej J. Capiński, Piotr Zgliczyński. Cone conditions and covering relations for topologically normally hyperbolic invariant manifolds. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 641-670. doi: 10.3934/dcds.2011.30.641
[15]

Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül. The set covering problem revisited: An empirical study of the value of dual information. Journal of Industrial & Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575
[16]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[17]

Ivan Landjev. On blocking sets in projective Hjelmslev planes. Advances in Mathematics of Communications, 2007, 1 (1) : 65-81. doi: 10.3934/amc.2007.1.65
[18]

J. C. Alvarez Paiva and E. Fernandes. Crofton formulas in projective Finsler spaces. Electronic Research Announcements, 1998, 4: 91-100.

[19]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019128
[20]

Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences