nach oben

Designs, Codes and Cryptography

Erschienen in:

01.06.2015

The largest Erdős–Ko–Rado sets in \(2-(v,k,1)\) designs

verfasst von: Maarten De Boeck

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An Erdős–Ko–Rado set in a block design is a set of pairwise intersecting blocks. In this article we study Erdős–Ko–Rado sets in \(2\,-\,(v,k,1)\) designs, Steiner systems. The Steiner triple systems and other special classes are treated separately. For \(k\ge 4\), we prove that the largest Erdős–Ko–Rado sets cannot be larger than a point-pencil if \(r\ge k^{2}-3k+\frac{3}{4}\sqrt{k}+2\) and that the largest Erdős–Ko–Rado sets are point-pencils if also \(r\ne k^{2}-k+1\) and \((r,k)\ne (8,4)\). For unitals we also determine an upper bound on the size of the second-largest maximal Erdős–Ko–Rado sets.

Vorheriger Artikel On small line sets with few odd-points

Nächster Artikel New cube root algorithm based on the third order linear recurrence relations in finite fields

Assmus E.F., Key J.D.: Designs and Their Codes. Cambridge Tracts in Mathematics, vol. 103. Cambridge University Press, Cambridge (1992).

Blokhuis A., Brouwer A.E., Chowdhury A., Frankl P., Patkos B., Mussche T., Szőnyi T.: A Hilton–Milner theorem for vector spaces. Electron. J. Comb. 17(1), R71 (2010).

Blokhuis A., Brouwer A.E., Szőnyi T., Weiner Z.: On \(q\)-analogues and stability theorems. J. Geom. 101(1–2), 31–50 (2011).

Blokhuis A., Brouwer A.E., Szőnyi T.: On the chromatic number of \(q\)-Kneser graphs. Des. Codes Cryptogr. 65(3), 187–197 (2012).

Brouwer A.E.: Some unitals on 28 points and their embeddings in projective planes of order 9. In: Geometries and Groups (Berlin, 1981). Lecture Notes in Mathematics, vol. 893, pp. 183–188. Springer, Berlin (1981).

Cameron P.J., van Lint J.H.: Designs, Graphs, Codes and Their Links. London Mathematical Society Student Texts, vol. 22. Cambridge University Press, Cambridge (1991).

Colbourn C.J., Dinitz J.H.: Handbook of Combinatorial Designs. Discrete Mathematics and Its Applications, vol. 42. Chapman & Hall/Taylor & Francis, Boca Raton (2006).

De Boeck M.: The largest Erdős–Ko–Rado sets of planes in finite projective and finite classical polar spaces. Des. Codes Cryptogr. (2013). Special issue “Finite Geometries, in honor of F. De Clerck”. doi:10.1007/s10623-013-9812-9.

De Boeck M., Storme L.: Theorems of Erdős–Ko–Rado type in geometrical settings. Sci. China Math. 56(7), 1333–1348 (2013).

10.

Dembowski P.: Finite Geometries. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44. Springer, New York (1968).

11.

Erdős P., Ko C., Rado R.: Intersection theorems for systems of finite sets. Quart. J. Math. 12(1), 313–320 (1961).

12.

Hughes D.R., Piper F.C.: Design Theory. Cambridge University Press, Cambridge (1985).

13.

Ihringer F., Metsch K.: On the maximal size of Erdős–Ko–Rado sets in \(H(2d+1, q^{2})\). Des. Codes Cryptogr. (2012). doi:10.1007/s10623-012-9765-4.

14.

Newman M.: Independent sets and eigenspaces. PhD Thesis, University of Waterloo (2004).

15.

O’Nan M.E.: Automorphisms of unitary block designs. J. Algebra 20, 495–511 (1972).

16.

Pepe V., Storme L., Vanhove F.: Theorems of Erdős–Ko–Rado type in polar spaces. J. Combin. Theory A 118(4), 1291–1312 (2011).

17.

Piper F.: Unitary block designs. Graph theory and combinatorics. In: Proceedings Conference, Open University, Milton Keynes, 1978. Research Notes in Mathematics, vol. 34, pp. 98–105. Pitman, Boston (1979).

18.

Rands B.M.I.: An extension of the Erdős, Ko, Rado theorem to \(t\)-designs. J. Comb. Theory A 32(3), 391–395 (1982).

19.

Tanaka H.: Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs. J. Comb. Theory A 113(5), 903–910 (2006).

20.

Wilson R.M.: The exact bound in the Erdős–Ko–Rado theorem. Combinatorica 4(2–3), 247–257 (1984).

Titel: The largest Erdős–Ko–Rado sets in designs
verfasst von: Maarten De Boeck
Publikationsdatum: 01.06.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-014-9929-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2015

Self-embeddings of Hamming Steiner triple systems of small order and APN permutations

Difference matrices related to Sophie Germain primes using functions on the fields

Worst-case to average-case reductions for module lattices

Permutation codes invariant under isometries

False positive probabilities in q-ary Tardos codes: comparison of attacks

Triple arrays and Youden squares