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

详细信息    查看全文

• 作者：Maarten De Boeck
• 关键词：Erd?s–Ko–Rado set ; Block design ; Steiner system ; Unital ; 05B05 ; 05B07 ; 51E10 ; 52C10
• 刊名：Designs, Codes and Cryptography
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：75
• 期：3
• 页码：465-481
• 全文大小：244 KB
• 参考文献：1.Assmus E.F., Key J.D.: Designs and Their Codes. Cambridge Tracts in Mathematics, vol. 103. Cambridge University Press, Cambridge (1992).
  2.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).
  3.Blokhuis A., Brouwer A.E., Sz?nyi T., Weiner Z.: On \(q\) -analogues and stability theorems. J. Geom. 101(1-), 31-0 (2011).
  4.Blokhuis A., Brouwer A.E., Sz?nyi T.: On the chromatic number of \(q\) -Kneser graphs. Des. Codes Cryptogr. 65(3), 187-97 (2012).
  5.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-88. Springer, Berlin (1981).
  6.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).
  7.Colbourn C.J., Dinitz J.H.: Handbook of Combinatorial Designs. Discrete Mathematics and Its Applications, vol. 42. Chapman & Hall/Taylor & Francis, Boca Raton (2006).
  8.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.-007/?s10623-013-9812-9 .
  9.De Boeck M., Storme L.: Theorems of Erd?s–Ko–Rado type in geometrical settings. Sci. China Math. 56(7), 1333-348 (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-20 (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.-007/?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-11 (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-312 (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-05. 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-95 (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-10 (2006).
  20.Wilson R.M.: The exact bound in the Erd?s–Ko–Rado theorem. Combinatorica 4(2-), 247-57 (1984).
  
• 作者单位：Maarten De Boeck (1)
  
  1. Department of Mathematics, UGent, Krijgslaan 281-S22, 9000?, Ghent, Flanders, Belgium
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Coding and Information Theory
  Data Structures, Cryptology and Information Theory
  Data Encryption
  Discrete Mathematics in Computer Science
  Information, Communication and Circuits
  
• 出版者：Springer Netherlands
• ISSN：1573-7586

文摘

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.