Further results on multiple coverings of the farthest-off points

Daniele  Bartoli; Alexander A. Davydov; Massimo  Giulietti; Stefano  Marcugini; Fernanda  Pambianco

doi:10.3934/amc.2016030

Article Contents

2016, Volume 10, Issue 3: 613-632. Doi: 10.3934/amc.2016030

This issue Previous Article The non-existence of $(104,22;3,5)$-arcs Next Article On self-dual MRD codes

Further results on multiple coverings of the farthest-off points

1.
Department of Mathematics, Ghent University, Gent, 9000
2.
Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, GSP-4, Moscow, 127994
3.
Department of Mathematics and Informatics, Perugia University, Perugia, 06123

Received: May 2015

Revised: October 2015

Published: August 2016

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 51E21, 51E22; Secondary: 94B05.

Citation:

Related Papers

Cited by

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, ACCT2012, Pomoria, Bulgaria, 2012, 53-59.
[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-85.doi: 10.3934/amc.2015.9.63.
[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-419.doi: 10.1007/s00022-013-0178-y.
[4]	E. Boros, T. Szőnyi and K. Tichler, On defining sets for projective planes, Discrete Math., 303 (2005), 17-31.doi: 10.1016/j.disc.2004.12.015.
[5]	R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, in Handbook of Coding Theory (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, 1998, 755-826.
[6]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[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-2080.doi: 10.1109/18.476339.
[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-147.doi: 10.1007/s10623-015-0070-x.
[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, Saint-Petersburg, Russia, 2009, 59-64.
[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-201.
[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-147.doi: 10.3934/amc.2011.5.119.
[12]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes, Graphs Combin., 29 (2013), 187-212.doi: 10.1007/s00373-011-1103-5.
[13]	M. Giulietti, On small dense sets in Galois planes, Electr. J. Combin., 14 (2007), #75.
[14]	M. Giulietti, Small complete caps in $PG(N,q), q$ even, J. Combin. Des., 15 (2007), 420-436.doi: 10.1002/jcd.20131.
[15]	M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces, in Surveys in Combinatorics, Cambridge Univ. Press, 2013, 51-90.
[16]	M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4, IEEE Trans. Inform. Theory, 53 (2007), 1928-1935.doi: 10.1109/TIT.2007.894688.
[17]	M. Giulietti and F. Torres, On dense sets related to plane algebraic curves, Ars Combin., 72 (2004), 33-40.
[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-275.doi: 10.1007/BF01388486.
[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-207.doi: 10.1137/S0895480193252100.
[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-588.doi: 10.2307/2974552.
[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-95.doi: 10.1016/0097-3165(91)90024-B.
[22]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Univ. Press, 1998.
[23]	I. S. Honkala, On the normality of multiple covering codes, Discrete Math., 125 (1994), 229-239.doi: 10.1016/0012-365X(94)90164-3.
[24]	I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory, Bull. Inst. Combin., 17 (1996), 39-46.
[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-178.doi: 10.1023/A:1008228721072.
[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-233.
[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-293.
[28]	J. Quistorff, On Codes with given minimum distance and covering radius, Beiträge Algebra Geom., 41 (2000) 469-478.
[29]	J. Quistorff, Correction: On codes with given minimum distance and covering radius, Beiträge Algebra Geom., 42 (2001), 601-611.
[30]	T. Szőnyi, Complete arcs in Galois planes: a survey, in Quaderni del Seminario di Geometrie Combinatorie 94, Univ. degli Studi di Roma "La Sapienza'', Roma, 1989.
[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-682.