Geodesic
EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS
Forum of Mathematics, Pi, Tome 4 (2016)

Voir la notice de l'article provenant de la source Cambridge University Press

Let $\mathbb{F}_{q}^{n}$ be a vector space of dimension $n$ over the finite field $\mathbb{F}_{q}$ . A $q$ -analog of a Steiner system (also known as a $q$ -Steiner system), denoted ${\mathcal{S}}_{q}(t,\!k,\!n)$ , is a set ${\mathcal{S}}$ of $k$ -dimensional subspaces of $\mathbb{F}_{q}^{n}$ such that each $t$ -dimensional subspace of $\mathbb{F}_{q}^{n}$ is contained in exactly one element of ${\mathcal{S}}$ . Presently, $q$ -Steiner systems are known only for $t\,=\,1\!$ , and in the trivial cases $t\,=\,k$ and $k\,=\,n$ . In this paper, the first nontrivial $q$ -Steiner systems with $t\,\geqslant \,2$ are constructed. Specifically, several nonisomorphic $q$ -Steiner systems ${\mathcal{S}}_{2}(2,3,13)$ are found by requiring that their automorphism groups contain the normalizer of a Singer subgroup of $\text{GL}(13,2)$ . This approach leads to an instance of the exact cover problem, which turns out to have many solutions. 
@article{10_1017_fmp_2016_5,
     author = {MICHAEL BRAUN and TUVI ETZION and PATRIC R. J. \"OSTERG\r{A}RD and ALEXANDER VARDY and ALFRED WASSERMANN},
     title = {EXISTENCE {OF} $q$ {-ANALOGS} {OF} {STEINER} {SYSTEMS}},
     journal = {Forum of Mathematics, Pi},
     publisher = {mathdoc},
     volume = {4},
     year = {2016},
     doi = {10.1017/fmp.2016.5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2016.5/}
}
TY  - JOUR
AU  - MICHAEL BRAUN
AU  - TUVI ETZION
AU  - PATRIC R. J. ÖSTERGÅRD
AU  - ALEXANDER VARDY
AU  - ALFRED WASSERMANN
TI  - EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS
JO  - Forum of Mathematics, Pi
PY  - 2016
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2016.5/
DO  - 10.1017/fmp.2016.5
LA  - en
ID  - 10_1017_fmp_2016_5
ER  - 
%0 Journal Article
%A MICHAEL BRAUN
%A TUVI ETZION
%A PATRIC R. J. ÖSTERGÅRD
%A ALEXANDER VARDY
%A ALFRED WASSERMANN
%T EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS
%J Forum of Mathematics, Pi
%D 2016
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2016.5/
%R 10.1017/fmp.2016.5
%G en
%F 10_1017_fmp_2016_5
MICHAEL BRAUN; TUVI ETZION; PATRIC R. J. ÖSTERGÅRD; ALEXANDER VARDY; ALFRED WASSERMANN. EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS. Forum of Mathematics, Pi, Tome 4 (2016). doi: 10.1017/fmp.2016.5

[1] Abel, R. J. R. and Buratti, M., ‘Difference families’, inHandbook of Combinatorial Designs, 2nd edn, (eds. Colbourn, C. J. and Dinitz, J. H.) (Chapman & Hall/CRC, Boca Raton, 2007), 392–410.Google Scholar

[2] Abel, R. J. R. and Greig, M., ‘BIBDs with small block size’, inHandbook of Combinatorial Designs, 2nd edn, (eds. Colbourn, C. J. and Dinitz, J. H.) (Chapman & Hall/CRC, Boca Raton, 2007), 72–79.Google Scholar

[3] Ahlswede, R., Aydinian, H. K. and Khachatrian, L. H., ‘On perfect codes and related concepts’, Des. Codes Cryptogr. 22 (2001), 221–237.Google Scholar | DOI

[4] Baer, R., Linear Algebra and Projective Geometry (Academic Press, New York, 1952).Google Scholar

[5] Beth, T., Jungnickel, D. and Lenz, H., Design Theory, 2nd edn, Vol. I. (Cambridge University Press, Cambridge, 1999).Google Scholar

[6] Beutelspacher, A., ‘Parallelismen in unendlichen projektiven Raumen endlicher Dimension’, Geom. Dedicata 7 (1978), 499–506.Google Scholar | DOI

[7] Braun, M., Kerber, A. and Laue, R., ‘Systematic construction of q-analogs of designs’, Des. Codes Cryptogr. 34 (2005), 55–70.Google Scholar | DOI

[8] Cameron, P., ‘Generalisation of Fisher’s inequality to fields with more than one element’, inCombinatorics, (eds. Mcdonough, T. P. and Mavron, V. C.) London Math. Soc. Lecture Note, 13 (Cambridge University Press, Cambridge, 1974), 9–13.Google Scholar | DOI

[9] Cameron, P., ‘Locally symmetric designs’, Geom. Dedicata 3 (1974), 65–76.Google Scholar | DOI

[10] Cayley, A., ‘On the triadic arrangements of seven and fifteen things’, Philos. Mag. 37 (1850), 50–53.Google Scholar

[11] Cohn, H., ‘Projective geometry over F and the Gaussian binomial coefficients’, Amer. Math. Monthly 111 (2004), 487–495.Google Scholar

[12] Colbourn, C. J. and Dinitz, J. H. (Eds.), Handbook of Combinatorial Designs, 2nd edn, (Chapman & Hall/CRC, Boca Raton, 2007).Google Scholar

[13] Cossidente, A. and De Resmini, M. J., ‘Remarks on Singer cyclic groups and their normalizers’, Des. Codes Cryptogr. 32 (2004), 97–102.Google Scholar | DOI

[14] Delsarte, P., ‘Association schemes and t-designs in regular semilattices’, J. Combin. Theory Ser. A 20 (1976), 230–243.Google Scholar | DOI

[15] Dye, R. H., ‘Maximal subgroups of symplectic groups stabilizing spreads II’, J. Lond. Math. Soc. 40(2) (1989), 215–226.Google Scholar | DOI

[16] Etzion, T., ‘Covering of subspaces by subspaces’, Des. Codes Cryptogr. 72 (2014), 405–421.Google Scholar | DOI

[17] Etzion, T. and Vardy, A., ‘Error-correcting codes in projective space’, IEEE Trans. Inform. Theory 57 (2011), 1165–1173.Google Scholar | DOI

[18] Etzion, T. and Vardy, A., ‘On q-analogs for Steiner systems and covering designs’, Adv. Math. Commun. 5 (2011), 161–176.Google Scholar

[19] Euler, L., ‘Consideratio quarumdam serierum quae singularibus proprietatibus sunt praeditae’, Novi Comment. Acad. Sci. Petropolitanae 3(1750–1751) 10–12. 86–108; Opera Omnia, Ser. I, vol. 14, B. G. Teubner, Leipzig, 1925, pp. 516–541.Google Scholar

[20] Fazeli, A., Lovett, S. and Vardy, A., ‘Nontrivial t-designs over finite fields exist for all t ’, J. Combin. Theory Ser. A 127 (2014), 149–160.Google Scholar | DOI

[21] Goldman, J. R. and Rota, G.-C., ‘On the foundations of combinatorial theory IV: finite vector spaces and Eulerian generating functions’, Stud. Appl. Math. 49 (1970), 239–258.Google Scholar | DOI

[22] Greig, M., ‘Some balanced incomplete block design constructions’, Congr. Numer. 77 (1990), 121–134.Google Scholar

[23] Hanani, H., ‘A class of three-designs’, J. Combin. Theory Ser. A 26 (1979), 1–19.Google Scholar | DOI

[24] Ho, T., Médard, M., Koetter, R., Karger, D., Effros, M., Shi, J. and Leong, B., ‘A random linear network coding approach to multicast’, IEEE Trans. Inform. Theory 52 (2006), 4413–4430.Google Scholar | DOI

[25] Huppert, B., Endliche Gruppen I (Springer, Berlin, 1967).Google Scholar | DOI

[26] Kantor, W. M., ‘Linear groups containing a Singer cycle’, J. Algebra 62 (1980), 232–234.Google Scholar | DOI

[27] Kaski, P. and Östergård, P. R. J., Classification Algorithms for Codes and Designs (Springer, Berlin, 2006).Google Scholar

[28] Kaski, P. and Pottonen, O., ‘Libexact user guide, Version 1.0’, HIIT Technical Reports 2008-1, Helsinki Institute for Information Technology, 2008.Google Scholar

[29] Keevash, P., ‘The existence of designs’, Preprint 2014, arXiv:1401.3665.Google Scholar

[30] Kiermaier, M. and Laue, R., ‘Derived and residual subspace designs’, Adv. Math. Commun. 9 (2015), 105–115.Google Scholar | DOI

[31] Kirkman, T. P., ‘On a problem in combinations’, Cambridge Dublin Math. J. II (1847), 191–204.Google Scholar

[32] Knuth, D. E., ‘Dancing links’, inMillennial Perspectives in Computer Science (eds. Davies, J., Roscoe, B. and Woodcock, J.) (Palgrave Macmillan, Basingstoke, 2000), 187–214.Google Scholar

[33] Koelink, E. and Van Assche, W., ‘Leonhard Euler and a q-analogue of the logarithm’, Proc. Amer. Math. Soc. 137 (2009), 1663–1676.Google Scholar | DOI

[34] Koetter, R. and Kschischang, F. R., ‘Coding for errors and erasures in random network coding’, IEEE Trans. Inform. Theory 54 (2008), 3579–3591.Google Scholar | DOI

[35] Kohnert, A. and Kurz, S., ‘Construction of large constant dimension codes with a prescribed minimum distance’, inMathematical Methods in Computer Science, (eds. Calmet, J., Geiselmann, W. and Müller-Quade, J.) Lecture Notes in Computer Science, 5393 (Springer, Berlin, 2008), 31–42.Google Scholar | DOI

[36] Kramer, E. and Mesner, D., ‘ t-designs on hypergraphs’, Discrete Math. 15 (1976), 263–296.Google Scholar | DOI

[37] Laue, R., ‘Eine konstruktive Version des Lemmas von Burnside’, Bayreuther Math. Schr. 28 (1989), 111–125.Google Scholar

[38] Van Lint, J. H. and Wilson, R. M., A Course in Combinatorics, 2nd edn (Cambridge University Press, Cambridge, 2001).Google Scholar | DOI

[39] Metsch, K., ‘Bose-Burton type theorems for finite projective, affine and polar spaces’, inSurveys in Combinatorics (eds. Lamb, J. D. and Preece, D. A.) London Math. Soc. Lecture Note, 267 (Cambridge University Press, Cambridge, 1999), 137–166.Google Scholar

[40] Miyakawa, M., Munemasa, A. and Yoshiara, S., ‘On a class of small 2-designs over GF(q)’, J. Combin. Des. 3 (1995), 61–77.Google Scholar | DOI

[41] Plücker, J., System der analytischen Geometrie: auf neue Betrachtungsweisen gegründet, und insbesondere eine ausführliche Theorie der Curven dritter Ordnung enthaltend, (Duncker und Humblot, Berlin, 1835).Google Scholar

[42] Ray-Chaudhuri, D. K. and Singhi, N. M., ‘ q-analogues of t-designs and their existence’, Linear Algebra Appl. 114/115 (1989), 57–68.Google Scholar | DOI

[43] Schmalz, B., ‘The t-designs with prescribed automorphism group, new simple 6-designs’, J. Combin. Des. 1 (1993), 125–170.Google Scholar | DOI

[44] Schwartz, M. and Etzion, T., ‘Codes and anticodes in the Grassmann graph’, J. Combin. Theory Ser. A 97 (2002), 27–42.Google Scholar | DOI

[45] Steiner, J., ‘Combinatorische Aufgabe’, J. reine angew. Math. 45 (1853), 181–182.Google Scholar

[46] Suzuki, H., ‘2-designs over GF(2 m )’, Graphs Combin. 6 (1990), 293–296.Google Scholar | DOI

[47] Suzuki, H., ‘2-designs over GF(q)’, Graphs Combin. 8 (1992), 381–389.Google Scholar | DOI

[48] Teirlinck, L., ‘Non-trivial t-designs without repeated blocks exist for all t ’, Discrete Math. 65 (1987), 301–311.Google Scholar | DOI

[49] Thomas, S., ‘Designs over finite fields’, Geom. Dedicata 21 (1987), 237–242.Google Scholar

[50] Thomas, S., ‘Designs and partial geometries over finite fields’, Geom. Dedicata 63 (1996), 247–253.Google Scholar | DOI

[51] Tits, J., ‘Sur les analogues algébriques des groupes semi-simples complexes’, inColloque d’Algébre Supèrieure, tenu á Bruxelles du 19 au 22 décembre 1956, Centre Belge de Recherches Mathématiques Établissements Ceuterick (Louvain, Paris, Librairie Gauthier-Villars, 1957), 261–289.Google Scholar

[52] Wang, J., ‘Quotient sets and subset-subspace analogy’, Adv. Appl. Math. 23 (1999), 333–339.Google Scholar | DOI

[53] Wilson, R. M., ‘Cyclotomy and difference families in elementary abelian groups’, J. Number Theory 4 (1972), 17–47.Google Scholar | DOI

[54] Yeung, R. W., Information Theory and Network Coding (Springer, Berlin, 2008).Google Scholar

Cité par Sources :