Construction of small strongly regular designs

Mikhail H. Klin   ; Sven Reichard

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 3, pp. 164-178

Résumé

We consider a particular class of coherent configurations, namely strongly regular designs (in the sense of D. G. Higman). We suggest to investigate these combinatorial structures from scratch and report first steps towards their systematical enumeration. This allows to take a fresh algebraic look on classical objects such as the Reye configuration.

Détail

Keywords: coherent configuration, strongly regular design
Mots-clés : association scheme, automorphism group, Reye configuration.

Bibliographie

[1] Babel L., Chuvaeva I. V., Klin M., Pasechnik D. V., Algebraic combinatorics in mathematical chemistry. Methods and algorithms. II. Program Implementation of the Weisfeiler–Leman algorithm, Technical Report TUM-M9701, Technische Universität München, München, 1997, 40 pp., arXiv: 1002.1921v1[math.CO]

[2] Bose R. C., “Strongly regular graphs, partial geometries and partially balanced designs”, Pacific J. Math., 13:2 (1963), 389–419 | DOI | MR | Zbl

[3] Brouwer A. E., Parameters of strongly regular graphs, [e-resource], URL: http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html

[4] Coherent Configurations with at most 13 vertices, [e-resource], URL: http://researchmap.jp/muprb160e-1782674

[5] Faradžev I. A., Klin M. H., “Computer package for computations with coherent configurations”, Proc. ISSAC-91, ACM Press, Bonn, 1991, 219–223 | Zbl

[6] Faradžev I. A., Klin M. H., Muzichuk M. E., “Cellular rings and groups of automorphisms of graphs”, Investigations in Algebraic Theory of Combinatorial Objects, eds. I. A. Faradžev, A. A. Ivanov, M. H. Klin, A. J. Woldar, Kluwer Acad. Pub., Dordrecht, 1994, 1–152 | MR | Zbl

[7] Fürer M., “Weisfeiler–Lehman refinement requires at least a linear number of iterations”, Automata, Languages and Programming, Lecture Notes in Comput. Sci., 2076, Springer, Berlin, 2001, 322–333 | DOI | MR | Zbl

[8] GAP Group, GAP – Groups, Algorithms, and Programming, Ver. 4.4.12, [e-resource], URL: , 2008 http://www.gap-system.org/

[9] Gol'fand Ja. Ju., Ivanov A. V., Klin M. H., “Amorphic association schemes”, Investigations in Algebraic Theory of Combinatorial Objects, eds. I. A. Faradžev, A. A. Ivanov, M. H. Klin, A. J. Woldar, Kluwer Acad. Pub., Dordrecht, 1994, 167–186 | DOI | MR

[10] Hanaki A., Miyamoto I., “Classification of association schemes of small order”, Discrete Math., 264 (2003), 75–80 | DOI | MR | Zbl

[11] Higman D. G., “Coherent algebras”, Linear Algebra Appl., 93 (1987), 209–239 | DOI | MR | Zbl

[12] Higman D. G., “Strongly regular designs and coherent configurations of type $[{3\atop\;}\,{2\atop3}]$”, European J. Combin., 9:4 (1988), 411–422 | DOI | MR | Zbl

[13] Hilbert D., Cohn-Vossen S., Anschauliche Geometrie, Reprint der 1932 Ausgabe, Springer-Verlag, Berlin, 1996, 358 pp. | Zbl

[14] Klin M., Muzychuk M., Pech C., Woldar A., Zieschang P.-H., “Association schemes on 28 points as mergings of a half-homogeneous coherent configuration”, European J. Combin., 28:7 (2007), 1994–2025 | DOI | MR | Zbl

[15] Klin M., Muzychuk M., Ziv-Av M., “Higmanian rank-5 association schemes on 40 points”, Michigan Math. J., 58:1 (2009), 255–284 | DOI | MR | Zbl

[16] Klin M., Pech C., Reichard S., Woldar A., Ziv-Av M., “Examples of computer experimentation in algebraic combinatorics”, Ars Math. Contemp., 3:2 (2010), 237–258 | MR | Zbl

[17] Klin M., Reichard S., Constructive enumeration and investigation of some families of small coherent configurations, preprint, Ben Gurion University, Beer Sheva, 2012, (Preliminary version)

[18] Klin M., Reichard S., Woldar A., “Siamese combinatorial objects via computer algebra experimentation”, Algorithmic Algebraic Combinatorics and Gröbner bases, Springer, Berlin, 2009, 67–112 | DOI | MR | Zbl

[19] Makhnev A. A., “Partial geometries, their extensions, and related graphs”, J. Math. Sci., 102:3 (2000), 4009–4017 | DOI | MR | Zbl

[20] McKay B. D., Nauty User Guide, Ver. 2.4, Australian National University, Canberra, 2009, 70 pp.

[21] Miyamoto I., Hanaki A., Classification of association schemes with small vertices, [e-resource], URL: http://kissme.shinshu-u.ac.jp/as/

[22] Nagatomo A., Classification of coherent configurations with at most 13 points, Master's thesis, Kyushu University, 2009 (Japanese)

[23] Neumaier A., “$t\frac12$-designs”, J. Combin. Theory. Ser. A, 28:3 (1980), 226–248 | DOI | MR | Zbl

[24] On Construction and Identification of Graphs, Lect. Notes Math., 558, ed. B. Weisfeiler, Springer, Berlin, 1976, 237 pp. | MR | Zbl

[25] Reye Th., “Die Hexaëder- und die Octaëder-Configurationen $(12^6,16^3)$”, Acta Math., 1:1 (1882), 97–108 | DOI | MR

[26] See K., Song S. Y., “Association schemes of small order”, J. Statist. Plann. Inference, 73:1–2, (R. C. Bose Memorial Conference. Fort Collins, CO, 1995) (1998), 225–271 | DOI | MR | Zbl

[27] Soicher L. H., The DESIGN package for GAP, Ver. 1.4, [e-resource], URL: , 2009 http://www.gap-system.org/Packages/design.html

[28] Soicher L. H., The GRAPE package for GAP, Ver. 4.3, [e-resource], URL: , 2006 http://www.gap-system.org/Packages/grape.html

[29] Weisfeiler B. Yu., Leman A. A., “A reduction of a graph to a canonical form and an algebra arising during this reduction”, Nauchno-Technicheskaya Informatsiya, 2:9 (1968), 12–16