On Almost Complete Caps in PG(N, q)

Davydov, Alexander A.; Marcugini, Stefano; Pambianco, Fernanda

doi:10.2478/cait-2018-0020

Abstract

We propose the concepts of almost complete subset of an elliptic quadric in the projective space PG(3, q) and of almost complete cap in the space PG(N, q), N ≥ 3, as generalizations of the concepts of almost complete subset of a conic and of almost complete arc in PG(2, q). Upper bounds of the smallest size of the introduced geometrical objects are obtained by probabilistic and algorithmic methods.

References

1. Bartoli, D., 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. Transm., Vol. 50, 2014, No 4, pp. 320-339.10.1134/S0032946014040036
Search in Google Scholar Back to article
2. Bartoli, D., A. A. Davydov., G. Faina, S. Marcugini, F. Pambianco. Conjectural Upper Bounds on the Smallest Size of a Complete ap in PG(N, q), N ≥ 3. – Electron. Notes Discrete Math., Vol. 57, 2017, pp. 15-20.10.1016/j.endm.2017.02.004
Open DOI Search in Google Scholar Back to article
3. Bartoli, D., A. A. Davydov., S. Marcugini, F. Pambianco. On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, q) and Extendability of Reed-Solomon Codes. – arXiv:1609.05657 [math.CO], 2016.
Search in Google Scholar Back to article
4. Bartoli, D., G. Faina, S. Marcugini, F. Pambianco. A Construction of Small Complete Caps in Projective Spaces. – J. Geom., Vol. 108, 2017, No 1, pp. 215-246.10.1007/s00022-016-0335-1
Search in Google Scholar Back to article
5. Clevenson, M. L., W. Watkins. Majorization and the Birthday Inequality. – Math. Magazine, Vol. 64, 1991, No 3, pp. 183-188.10.1080/0025570X.1991.11977606
Search in Google Scholar Back to article
6. Davydov., A. A., G. Faina, S. Marcugini, F. Pambianco. Upper Bounds on the Smallest Size of a Complete Cap in PG(N, q), N ≥ 3, under a Certain Probabilistic Conjecture. – arXiv:1706.01941 [math.CO], 2017.
Search in Google Scholar Back to article
7. Davydov., A. A., S. Marcugini, F. Pambianco. Upper Bounds on the Smallest Size of an Almost Complete Cap in PG(N, q). – In: Proc. of 8th International Workshop on Optimal Codes and Related Topics, OC’17 (in Second International Conference “Mathematics Days in Sofia”), Sofia, Bulgaria, 2017, pp. 67-72.
Search in Google Scholar Back to article
8. Hirschfeld, J. W. P. Projective Geometries over Finite Fields. Second Edition. Oxford, Oxford University Press, 1998.
Search in Google Scholar Back to article
9. Hirschfeld, J. W. P. Finite Projective Spaces of Three Dimensions. Oxford, Oxford University Press, 1985.
Search in Google Scholar Back to article
10. Hirschfeld, J. W. P., L. Storme. The Packing Problem in Statistics, Coding Theory and Finite Geometry: Update 2001. – In: A. Blokhuis, J. W. P. Hirschfeld et al. Eds. Proc. of 4th Isle of Thorns Conf., Chelwood Gate, 2000, Kluwer Academic Publisher, Boston, Finite Geometries, Developments of Mathematics, Vol. 3, 2001, pp. 201-246.10.1007/978-1-4613-0283-4_13
Search in Google Scholar Back to article
11. Hirschfeld, J. W. P., J. A. Thas. Open Problems in Finite Projective Spaces. – Finite Fields and their Appl., Vol. 32, 2015, No 1, pp. 44-81.10.1016/j.ffa.2014.10.006
Search in Google Scholar Back to article
12. Kovàcs, S. J. Small Saturated Sets in Finite Projective Planes. – Rend. Mat. (Roma), Vol. 12, 1992, No 1, pp. 157-164.
Search in Google Scholar Back to article
13. Sayrafiezadeh, M. The Birthday Problem Revisited – Math. Magazine, Vol. 67, 1994, No 3, pp. 220-223.10.1080/0025570X.1994.11996217
Search in Google Scholar Back to article
14. Storme, L. Completeness of Normal Rational Curves. – J. Algebraic Combin., Vol. 1, 1992, No 2, pp. 197-202.10.1023/A:1022428405084
Search in Google Scholar Back to article
15. Ughi, E. Small Almost Complete Arcs. – Discrete Math., Vol. 255, 2002, No 3, pp. 367-379.10.1016/S0012-365X(01)00412-5
Search in Google Scholar Back to article

On Almost Complete Caps in PG(N, q)

Abstract

Paradigm

My account