Imprimitive cometric association schemes: Constructions and analysis
William J. Martin1
, Mikhail Muzychuk2
and Jason Williford3
1Department of Mathematical Sciences and Department of Computer Science, Worcester Polytechnic Institute, Worcester, Massachusetts USA
2Department of Computer Science and Mathematics, Netanya Academic College, Netanya, 42365 Israel
3Department of Mathematical Sciences, Worcester Polytechnic Institute, Worcester, Massachusetts USA
2Department of Computer Science and Mathematics, Netanya Academic College, Netanya, 42365 Israel
3Department of Mathematical Sciences, Worcester Polytechnic Institute, Worcester, Massachusetts USA
DOI: 10.1007/s10801-006-0043-2
Abstract
Dualizing the “extended bipartite double” construction for distance-regular graphs, we construct a new family of cometric (or Q-polynomial) association schemes with four associate classes based on linked systems of symmetric designs. The analysis of these new schemes naturally leads to structural questions concerning imprimitive cometric association schemes, some of which we answer with others being left as open problems. In particular, we prove that any Q-antipodal association scheme is dismantlable: the configuration induced on any subset of the equivalence classes in the Q-antipodal imprimitivity system is again a cometric association scheme. Further examples are explored.
Pages: 399–415
Keywords: keywords association scheme; cometric; $Q$-polynomial; imprimitive; spherical design; linked system of symmetric designs
Full Text: PDF
References
1. E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin-Cummings, Menlo Park, 1984.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
3. A.E. Brouwer, C.D. Godsil, J.H. Koolen, and W.J. Martin, “Width and dual width of subsets in metric and cometric association schemes,” J. Combin. Th. Ser. A 102 (2003), 255-271.
4. D. de Caen and E.R. van Dam, “Association schemes related to Kasami codes and Kerdock sets,” Des. Codes Cryptogr. 18 (1999), 89-102.
5. P.J. Cameron, “On groups with several doubly-transitive permutation representations,” Math. Z. 128 (1972), 1-14.
6. P.J. Cameron and J.J. Seidel, “Quadratic forms over GF(2),” Proc. Koninkl. Nederl. Akademie van Wetenschappen, Series A, Vol. 76 Indag. Math. 35 (1973), 1-8.
7. D. Cerzo and H. Suzuki, “On imprimitive Q-polynomial schemes of exceptional type,” Preprint, 2006.
8. E. van Dam, “Three-class association schemes,” J. Alg. Combin. 10(1) (1999), 69-107.
9. P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Repts. Suppl. 10 (1973).
10. P. Delsarte, J.-M. Goethals, and J.J. Seidel, “Spherical codes and designs,” Geom. Ded. 6 (1977), 363-388.
11. G.A. Dickie, “Q-polynomial structures for association schemes and distance-regular graphs,” Ph.D. Thesis, University of Wisconsin-Madison, 1995.
12. A.D. Gardiner, “Antipodal covering graphs,” J. Combin. Th. Ser. B 16 (1974), 255-273. Springer
13. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
14. R. Mathon, “The systems of linked 2-(16,6,2) designs,” Ars Comb. 11 (1981), 131-148.
15. A. Munemasa, “Spherical designs,” in Handbook of Combinatorial Designs (2nd ed.), C.J. Colbourn and J.H. Dinitz (eds.), CRC Press, Boca Raton, 2006, Section VI.54, pp. 637- 643.
16. R. Noda, “On homogeneous systems of linked symmetric designs,” Math. Z. 138 (1974), 15-20.
17. H. Suzuki, “Imprimitive Q-polynomial association schemes,” J. Alg. Combin. 7(2) (1998), 165- 180.
18. P. Terwilliger, “The subconstituent algebra of an association scheme I,” J. Alg. Combin. 1(4) (1992), 363-388.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
3. A.E. Brouwer, C.D. Godsil, J.H. Koolen, and W.J. Martin, “Width and dual width of subsets in metric and cometric association schemes,” J. Combin. Th. Ser. A 102 (2003), 255-271.
4. D. de Caen and E.R. van Dam, “Association schemes related to Kasami codes and Kerdock sets,” Des. Codes Cryptogr. 18 (1999), 89-102.
5. P.J. Cameron, “On groups with several doubly-transitive permutation representations,” Math. Z. 128 (1972), 1-14.
6. P.J. Cameron and J.J. Seidel, “Quadratic forms over GF(2),” Proc. Koninkl. Nederl. Akademie van Wetenschappen, Series A, Vol. 76 Indag. Math. 35 (1973), 1-8.
7. D. Cerzo and H. Suzuki, “On imprimitive Q-polynomial schemes of exceptional type,” Preprint, 2006.
8. E. van Dam, “Three-class association schemes,” J. Alg. Combin. 10(1) (1999), 69-107.
9. P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Repts. Suppl. 10 (1973).
10. P. Delsarte, J.-M. Goethals, and J.J. Seidel, “Spherical codes and designs,” Geom. Ded. 6 (1977), 363-388.
11. G.A. Dickie, “Q-polynomial structures for association schemes and distance-regular graphs,” Ph.D. Thesis, University of Wisconsin-Madison, 1995.
12. A.D. Gardiner, “Antipodal covering graphs,” J. Combin. Th. Ser. B 16 (1974), 255-273. Springer
13. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
14. R. Mathon, “The systems of linked 2-(16,6,2) designs,” Ars Comb. 11 (1981), 131-148.
15. A. Munemasa, “Spherical designs,” in Handbook of Combinatorial Designs (2nd ed.), C.J. Colbourn and J.H. Dinitz (eds.), CRC Press, Boca Raton, 2006, Section VI.54, pp. 637- 643.
16. R. Noda, “On homogeneous systems of linked symmetric designs,” Math. Z. 138 (1974), 15-20.
17. H. Suzuki, “Imprimitive Q-polynomial association schemes,” J. Alg. Combin. 7(2) (1998), 165- 180.
18. P. Terwilliger, “The subconstituent algebra of an association scheme I,” J. Alg. Combin. 1(4) (1992), 363-388.