A non-Schurian coherent configuration on 14 points exists. (English) Zbl 1367.05216
Summary: For a few decades the smallest known non-Schurian coherent configuration was the association scheme on 15 points, coming from a doubly regular tournament. Last year the second author, using a computer, enumerated all coherent configurations of order up to 15. A consequence of the enumeration is that all coherent configurations up to 13 points are Schurian and a unique non-Schurian rank 11 coherent configuration of order 14 exists. This coherent configuration has two fibers of sizes 6 and 8, and an automorphism group of order 24 isomorphic to \(\mathrm{SL}(2,3)\). We provide a computer free interpretation of this new object, relying on some simple interplay between group theoretical and combinatorial arguments.
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
Keywords:
coherent configuration; association scheme; centralizer algebra; automorphism group; Cayley graph; quaternion groupReferences:
| [1] | Bannai E., Ito T.: Algebraic Combinatorics. I: Association schemes. The Benjamin/Cummings Publishing, Menlo Park (1984). · Zbl 0555.05019 |
| [2] | Biggs N.: Algebraic Graph Theory, 2nd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1993). |
| [3] | Bose R.C., Shimamoto T.: Classification and analysis of partially balanced incomplete block designs with two associate classes. J. Am. Stat. Assoc. 47, 151-184 (1952). · Zbl 0048.11603 |
| [4] | Brouwer A.E., Cohen A.M., Neumaier A.: Distance-Regular Graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18. Springer-Verlag, Berlin (1989). · Zbl 0747.05073 |
| [5] | Cameron P.J.: Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge (1994). · Zbl 0806.05001 |
| [6] | Coxeter H.S.M.: Regular Complex Polytopes. Cambridge University Press, London (1974). · Zbl 0296.50009 |
| [7] | Coxeter H.S.M., Moser W.O.J.: Generators and Relations for Discrete Groups, 3rd edn. Springer-Verlag, New York (1972). Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 14. · Zbl 0239.20040 |
| [8] | Dixon J.D., Mortimer B.: Permutation Groups. Graduate Texts in Mathematics, vol. 163. Springer-Verlag, New York (1996). · Zbl 0951.20001 |
| [9] | Evdokimov S., Kovács I., Ponomarenko I.: Characterization of cyclic Schur groups. Algebra i Analiz 25(5), 61-85 (2013). · Zbl 1303.05213 |
| [10] | Faradžev I.A., Klin M.H.: Computer package for computations with coherent configurations. In: Proceedings of the ISSAC, pp. 219-223. ACM Press, Bonn (1991). · Zbl 0925.20006 |
| [11] | Faradžev I.A., Ivanov A.A., Klin M.H.: Galois correspondence between permutation groups and cellular rings (association schemes). Graphs Comb. 6(4), 303-332 (1990). · Zbl 0764.05099 |
| [12] | Faradžev I.A., Klin M.H., Muzichuk M.E.: Cellular rings and groups of automorphisms of graphs. In: Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Application (Soviet Seties), vol. 84, pp. 1-152. Kluwer Academic Publishers, Dordrecht (1994). · Zbl 0795.05073 |
| [13] | The GAP Group. GAP - Groups, Algorithms, and Programming, Version 4.4.12 (2008). |
| [14] | Hanaki A., Miyamoto I.: Classification of association schemes with 16 and 17 vertices. Kyushu J. Math. 52(2), 383-395 (1998). · Zbl 0914.05069 |
| [15] | Harary F.: Graph Theory. Addison-Wesley, Reading (1969). · Zbl 0182.57702 |
| [16] | Hardy G.H., Wright E.M.: An Introduction to the Theory of Numbers, 4th edn. Clarendon Press, Oxford (1960). · Zbl 0086.25803 |
| [17] | Higman D.G.: Coherent configurations. I. Rend. Sem. Mat. Univ. Padova 44, 1-25 (1970). · Zbl 0279.05025 |
| [18] | Higman D.G.: Strongly regular designs and coherent configurations of type \[\left[\begin{array}{ll} 3 \quad 2 \\ \quad \; 3 \\ \end{array}\right]\] <mtable columnspacing=”0.5ex“> <mtd columnalign=”left“> 3 <mspace width=”1em“/> 2 <mtd columnalign=”left“> <mspace width=”1em“/> <mspace width=”0.277778em“/> 3. Eur. J. Comb. <Emphasis Type=”Bold”>9(4), 411-422 (1988). · Zbl 0659.05033 |
| [19] | Hulpke A.: Constructing transitive permutation groups. J. Symb. Comput. 39(1), 1-30 (2005). · Zbl 1131.20003 |
| [20] | Kalužnin L.A., Beleckij P.M., Fejnberg V.Z.: Kranzprodukte. Teubner-Texte zur Mathematik [Teubner Texts in Mathematics], vol. 101. BSB B. G. Teubner Verlagsgesellschaft, Leipzig (1987) (with English, French and Russian summaries). · Zbl 0655.20019 |
| [21] | Klin M., Muzychuk M., Pech C., Woldar A., Zieschang P.-H.: Association schemes on 28 points as mergings of a half-homogeneous coherent configuration. Eur. J. Comb. 28(7), 1994-2025 (2007). · Zbl 1145.05056 |
| [22] | Klin M.Ch., Pöschel R., Rosenbaum K.: Angewandte Algebra für Mathematiker und Informatiker. Friedr. Vieweg & Sohn, Braunschweig (1988). Einführung in gruppentheoretisch-kombinatorische Methoden [Introduction to group-theoretical combinatorial methods]. · Zbl 0639.20001 |
| [23] | Klin M., Pech C., Reichard S., Woldar A., Ziv-Av M.: Examples of computer experimentation in algebraic combinatorics. Ars Math. Contemp. 3(2), 237-258 (2010). · Zbl 1227.05274 |
| [24] | Klin M.H., Reichard S.: Construction of small strongly regular designs. Tr. Inst. Mat. Mekh. 19(3), 164-178 (2013). |
| [25] | McKay B.D.: Nauty User’s Guide (version 1.5) (1990). |
| [26] | Miyamoto I., Hanaki A.: Classification of association schemes with small vertices. http://math.shinshu-u.ac.jp/ hanaki/as/ (2014). · Zbl 0957.05518 |
| [27] | Nagatomo, A., Shigezumi, J.: Coherent configurations with at most 13 vertices. http://researchmap.jp/mu45vd02h-1782674 (2009). |
| [28] | Pasechnik D.V.: Skew-symmetric association schemes with two classes and strongly regular graphs of type \[L_{2n-1}(4n-1)\] L2n-1(4n-1). Acta Appl. Math. 29(1-2), 129-138 (1992). Interactions between algebra and combinatorics. · Zbl 0760.05095 |
| [29] | Pöschel R.: Untersuchungen von \[SS\]-Ringen, insbesondere im Gruppenring von \[p\] p-Gruppen. Math. Nachr. 60, 1-27 (1974). · Zbl 0273.20005 |
| [30] | Schur I.: Zur theorie der einfach transitiven permutationsgruppen. Sitzungsber. Preuss. Akad. Wiss., Phys.-Math. Kl., pp. 598-623 (1933). · JFM 59.0151.01 |
| [31] | See K., Song S.Y.: Association schemes of small order. J. Stat. Plan. Inference 73(1-2), 225-271 (1998). R. C. Bose Memorial Conference (Fort Collins, CO, 1995). · Zbl 0935.05098 |
| [32] | Shrikhande S.S.: The uniqueness of the \[L_2\] L2 association scheme. Ann. Math. Stat. 30, 781-798 (1959). · Zbl 0086.34802 |
| [33] | Soicher L.H.: GRAPE: a system for computing with graphs and groups. In: Groups and Computation (New Brunswick, NJ, 1991). DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, vol. 11, pp. 287-291. American Mathematical Society, Providence (1993). · Zbl 0833.05071 |
| [34] | Weisfeiler B.: On Construction and Identification of Graphs. Lecture Notes in Mathematics, vol. 558. Springer, Berlin (1976). · Zbl 0366.05019 |
| [35] | Wielandt H.: Finite Permutation Groups. Translated from the German by R. Bercov. Academic Press, New York (1964). · Zbl 0138.02501 |
| [36] | Ziv-Av M.: Enumeration of coherent configurations of small orders (In preparation). · Zbl 1353.05005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
