A survey on tight Euclidean $t$-designs and tight relative $t$-designs in certain association schemes

Eiichi Bannai ; Etsuko Bannai ; Yan Zhu

Informatics and Automation, Geometry, topology, and applications, Tome 288 (2015), pp. 209-223.

Résumé

It is known that there is a close analogy between the two relations "Euclidean $t$-designs vs. spherical $t$-designs" and "relative $t$-designs in binary Hamming association schemes vs. combinatorial $t$-designs." We first look at this analogy and survey the known results, putting emphasis on the study of tight relative $t$-designs in certain $Q$-polynomial association schemes. We then specifically study tight relative $2$-designs on two shells in binary Hamming association schemes $H(n,2)$ and Johnson association schemes $J(v,k)$. The purpose of this paper is to convince the reader that there is a rich theory even for these special cases and that the time is ripe to study tight relative $t$-designs more systematically for general $Q$-polynomial association schemes.

Bibliographie

[1] Bannai Ei., “On tight designs”, Q. J. Math., 28 (1977), 433–448 | DOI | MR | Zbl

[2] Bannai Ei., Bannai Et., “On Euclidean tight $4$-designs”, J. Math. Soc. Japan., 58 (2006), 775–804 | DOI | MR | Zbl

[3] Bannai Ei., Bannai Et., “Spherical designs and Euclidean designs”, Recent developments in algebra and related areas, Beijing, 2007, Adv. Lect. Math., 8, Higher Educ. Press, Beijing, 2009, 1–37 | MR | Zbl

[4] Bannai Ei., Bannai Et., “A survey on spherical designs and algebraic combinatorics on spheres”, Eur. J. Comb., 30 (2009), 1392–1425 | DOI | MR | Zbl

[5] Bannai Ei., Bannai Et., “Euclidean designs and coherent configurations”, Combinatorics and graphs, Contemp. Math., 531, Amer. Math. Soc., Providence, RI, 2010, 59–93 | DOI | MR | Zbl

[6] Bannai Ei., Bannai Et., “Remarks on the concepts of $t$-designs”, J. Appl. Math. Comput., 40:1–2 (2012), 195–207 | DOI | MR | Zbl

[7] Bannai Ei., Bannai Et., “Tight $t$-designs on two concentric spheres”, Moscow J. Comb. Number Theory, 4:1 (2014), 52–77 | MR | Zbl

[8] Bannai Ei., Bannai Et., Bannai H., “On the existence of tight relative 2-designs on binary Hamming association schemes”, Discrete Math., 314 (2014), 17–37 | DOI | MR | Zbl

[9] Bannai Ei., Bannai Et., Hirao M., Sawa M., “Cubature formulas in numerical analysis and Euclidean tight designs”, Eur. J. Comb., 31 (2010), 423–441 | DOI | MR | Zbl

[10] Bannai Ei., Bannai Et., Suda S., Tanaka H., On relative $t$-designs in polynomial association schemes, E-print, 2013, arXiv: 1303.7163 [math.CO]

[11] Bannai Ei., Damerell R.M., “Tight spherical designs. I”, J. Math. Soc. Japan, 31 (1979), 199–207 | DOI | MR | Zbl

[12] Bannai Ei., Damerell R.M., “Tight spherical designs. II”, J. London Math. Soc. Ser. 2, 21 (1980), 13–30 | DOI | MR | Zbl

[13] Bannai Ei., Ito T., Algebraic combinatorics. I: Association schemes, Benjamin/Cummings, Menlo Park, CA, 1984 | MR | Zbl

[14] St. Petersburg Math. J., 16 (2005), 609–625 | DOI | MR | Zbl

[15] Bannai Ei., Sloane N.J.A., “Uniqueness of certain spherical codes”, Can. J. Math., 33 (1981), 437–449 | DOI | MR

[16] Bannai Et., “On antipodal Euclidean tight $(2e+1)$-designs”, J. Algebr. Comb., 24 (2006), 391–414 | DOI | MR | Zbl

[17] Bannai Et., “New examples of Euclidean tight $4$-designs”, Eur. J. Comb., 30 (2009), 655–667 | DOI | MR | Zbl

[18] Beth T., Jungnickel D., Lenz H., Design theory, Bibliogr. Inst., Mannheim, 1985 | MR | Zbl

[19] Bremner A., “A Diophantine equation arising from tight 4-designs”, Osaka J. Math., 16 (1979), 353–356 | MR | Zbl

[20] Brouwer A.E., Cohen A.M., Neumaier A., Distance-regular graphs, Springer, Berlin, 1989 | MR | Zbl

[21] Calderbank R., Kantor W.M., “The geometry of two-weight codes”, Bull. London Math. Soc., 18 (1986), 97–122 | DOI | MR | Zbl

[22] Cameron P.J., van Lint J.H., Designs, graphs, codes and their links, London Math. Soc. Stud. Texts, 22, Cambridge Univ. Press, Cambridge, 1991 | MR | Zbl

[23] Cameron P.J., Seidel J.J., “Quadratic forms over GF(2)”, Indag. Math., 35 (1973), 1–8 | DOI | MR

[24] Delsarte P., An algebraic approach to the association schemes of the coding theory, Thesis, Univ. Cathol. Louvain, Louvain-la-Neuve, 1973 | MR

[25] Delsarte P., “Association schemes and $t$-designs in regular semilattices”, J. Comb. Theory A, 20 (1976), 230–243 | DOI | MR | Zbl

[26] Delsarte P., “Pairs of vectors in the space of an association scheme”, Philips Res. Rep., 32 (1977), 373–411 | MR

[27] Delsarte P., Goethals J.M., Seidel J.J., “Bounds for systems of lines, and Jacobi polynomials”, Philips Res. Rep., 30 (1975), 91–105 | MR | Zbl

[28] Delsarte P., Goethals J.M., Seidel J.J., “Spherical codes and designs”, Geom. dedicata, 6 (1977), 363–388 | DOI | MR | Zbl

[29] Delsarte P., Seidel J.J., “Fisher type inequalities for Euclidean $t$-designs”, Linear Algebra Appl., 114–115 (1989), 213–230 | DOI | MR | Zbl

[30] Dukes P., Short-Gershman J., “Nonexistence results for tight block designs”, J. Algebr. Comb., 38 (2013), 103–119 | DOI | MR | Zbl

[31] Enomoto H., Ito N., Noda R., “Tight 4-designs”, Osaka J. Math., 16 (1979), 39–43 | MR | Zbl

[32] Hoggar S.G., “$t$-Designs in projective spaces”, Eur. J. Comb., 3 (1982), 233–254 | DOI | MR | Zbl

[33] Hughes D.R., “On $t$-designs and groups”, Amer. J. Math., 87 (1965), 761–778 | DOI | MR | Zbl

[34] Keevash P., The existence of designs, E-print, 2014, arXiv: 1401.3665 [math.CO]

[35] Kuperberg G., “Special moments”, Adv. Appl. Math., 34 (2005), 853–870 | DOI | MR | Zbl

[36] Kuperberg G., Lovett S., Peled R., Probabilistic existence of regular combinatorial structures, E-print, 2013, arXiv: 1302.4295 [math.CO]

[37] Levenshtein V.I., “Designs as maximum codes in polynomial metric spaces”, Acta appl. math., 29 (1992), 1–82 | DOI | MR | Zbl

[38] Li Z., Bannai Ei., Bannai Et., “Tight relative 2- and 4-designs on binary Hamming association schemes”, Graphs Comb., 30 (2014), 203–227 | DOI | MR | Zbl

[39] Martin W.J., “Mixed block designs”, J. Comb. Des., 6 (1998), 151–163 | 3.0.CO;2-E class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[40] Martin W.J., “Designs in product association schemes”, Des. Codes Cryptogr., 16 (1999), 271–289 | DOI | MR | Zbl

[41] Martin W.J., “Symmetric designs, sets with two intersection numbers, and Krein parameters of incidence graphs”, J. Comb. Math. Comb. Comput., 38 (2001), 185–196 | MR | Zbl

[42] McFarland R.L., “A family of difference sets in non-cyclic groups”, J. Comb. Theory A, 15 (1973), 1–10 | DOI | MR | Zbl

[43] St. Petersburg Math. J., 24 (2013), 485–491 | DOI | MR | Zbl

[44] Neumaier A., Combinatorial configurations in terms of distances: Memorandum 81-09, Dept. Math., Eindhoven Univ. Technol., Eindhoven, 1981 | MR

[45] Neumaier A., Seidel J.J., “Discrete measures for spherical designs, eutactic stars and lattices”, Indag. Math., 50 (1988), 321–334 | DOI | MR | Zbl

[46] Peterson C., “On tight 6-designs”, Osaka J. Math., 14 (1977), 417–435 | MR | Zbl

[47] Petrenyuk A.Ya., “Fisher's inequality for tactical configurations”, Math. Notes, 4 (1968), 742–746 | DOI

[48] Ray-Chaudhuri D.K., Wilson R.M., “On $t$-designs”, Osaka J. Math., 12 (1975), 737–744 | MR | Zbl

[49] Seymour P.D., Zaslavsky T., “Averaging sets: A generalization of mean values and spherical designs”, Adv. Math., 52 (1984), 213–240 | DOI | MR | Zbl

[50] Teirlinck L., “Non-trivial $t$-designs without repeated blocks exist for all $t$”, Discrete Math., 65 (1987), 301–311 | DOI | MR | Zbl

[51] Wallis W.D., “Construction of strongly regular graphs using affine designs”, Bull. Aust. Math. Soc., 4 (1971), 41–49 ; 5, 431 | DOI | MR | Zbl | DOI | MR | Zbl

[52] Woodall D.R., “Square $\lambda $-linked designs”, Proc. London Math. Soc. Ser. 3, 20 (1970), 669–687 | DOI | MR | Zbl

[53] Xiang Z., “A Fisher type inequality for weighted regular $t$-wise balanced designs”, J. Comb. Theory A, 119 (2012), 1523–1527 | DOI | MR | Zbl

[54] Zhu Y., Bannai E., Bannai E., “Tight relative 2-designs on two shells in Johnson association schemes”, Discrete Math., Submitted