Permutation group approach to association schemes. (English) Zbl 1228.05311
Summary: We survey the modern theory of schemes (coherent configurations). The main attention is paid to the schurity problem and the separability problem. Several applications of schemes to constructing polynomial-time algorithms, in particular, graph isomorphism tests, are discussed.
References:
| [1] | Albert, A. A., Quasigroups. I, Trans. Amer. Math. Soc., 54, 3, 507-519 (1943) · Zbl 0063.00039 |
| [2] | Arad, Z.; Fisman, E.; Muzychuk, M., Generalized table algebras, Israel J. Math., 114, 29-60 (1999) · Zbl 0952.20009 |
| [3] | Babai, L., On the order of uniprimitive permutation groups, Ann. Math., 113, 553-568 (1981) · Zbl 0485.20002 |
| [4] | Babai, L., Automorphism groups, isomorphism, reconstruction, (Handbook Of Combinatorics, vol. 2 (1995), Elsevier Science), 1447-1541 · Zbl 0846.05042 |
| [5] | L. Babel, Computing coherent configurations, Technische Universität München, TUM-M0204, März 2002; L. Babel, Computing coherent configurations, Technische Universität München, TUM-M0204, März 2002 |
| [6] | L. Babel, I.V. Chuvaeva, M. Klin, D.V. Pasechnik, Algebraic combinatorics in mathematical chemistry II. Program implementation of the Weisfeiler-Leman algorithm, Technische Universität München, TUM-M9701, Januar 1997; L. Babel, I.V. Chuvaeva, M. Klin, D.V. Pasechnik, Algebraic combinatorics in mathematical chemistry II. Program implementation of the Weisfeiler-Leman algorithm, Technische Universität München, TUM-M9701, Januar 1997 |
| [7] | Bagherian, J.; Ponomarenko, I.; Rahnamai Barghi, A., On cyclotomic schemes over finite near-fields, J. Algebraic Combin., 27, 173-185 (2008) · Zbl 1194.05168 |
| [8] | E. Bannai, E. Bannai, A survey on spherical designs and algebraic combinatorics on spheres, this volume; E. Bannai, E. Bannai, A survey on spherical designs and algebraic combinatorics on spheres, this volume · Zbl 1207.05022 |
| [9] | Bannai, E.; Ito, T., Algebraic combinatorics. I (1984), Benjamin/Cummings: Benjamin/Cummings Menlo Park, CA · Zbl 0555.05019 |
| [10] | O. Bastert, New ideas for canonically computing graph algebras, Technische Universität München, TUM-M9803, Juni 1998; O. Bastert, New ideas for canonically computing graph algebras, Technische Universität München, TUM-M9803, Juni 1998 |
| [11] | Berlekamp, E. R., Factoring polynomials over large finite fields, Math. Comp., 24, 713-735 (1970) · Zbl 0247.12014 |
| [12] | Beth, T.; Jungnickel, D.; Dieter, H., Design theory, (Encyclopedia of Mathematics and Its Applications, 69 (1999), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0945.05004 |
| [13] | Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (Ergebnisse der Mathematik und ihrer Grenzgebiete (1989), Springer-Verlag: Springer-Verlag 3. Folge, 18. Berlin etc.) · Zbl 0747.05073 |
| [14] | Handbook of incidence geometry, (Buekenhout, F., Buildings and foundations (1995), North-Holland: North-Holland Amsterdam) · Zbl 0821.00012 |
| [15] | Cai, J. Y.; Fürer, M.; Immerman, N., An optimal lower bound on the number of variables for graph identification, Combinatorica, 12, 389-410 (1992) · Zbl 0785.68043 |
| [16] | Cameron, P. J., On groups with several doubly-transitive permutation representations, Math. Z., 128, 1-14 (1972) · Zbl 0227.20001 |
| [17] | Enomoto, H., Strongly regular graphs and finite permutation groups of rank 3, J. Math. Kyoto Univ., 11, 381-397 (1971) · Zbl 0226.20004 |
| [18] | S. Evdokimov, Schurity and separability of association schemes, Thesis (2004) (in Russian); S. Evdokimov, Schurity and separability of association schemes, Thesis (2004) (in Russian) |
| [19] | Evdokimov, S. A., Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis, Zapiski Nauchnykh Seminarov POMI, 176, 104-117 (1989), (Prepublication in 1986). English translation: J. Soviet Math. 59 (3) (1992) 842-849 · Zbl 0703.11070 |
| [20] | Evdokimov, S., Factorization of polynomials over finite fields in subexponential time under GRH, (Algorithmic number theory (Ithaca, NY, 1994). Algorithmic number theory (Ithaca, NY, 1994), Lecture Notes in Comput. Sci., 877 (1994), Springer: Springer Berlin), 209-219 · Zbl 0829.11065 |
| [21] | Evdokimov, S.; Karpinski, M.; Ponomarenko, I., On a new high dimensional Weisfeiler-Leman algorithm, J. Algebraic Combin., 10, 29-45 (1999) · Zbl 0936.05070 |
| [22] | Evdokimov, S.; Ponomarenko, I., Normal cyclotomic schemes over a finite commutative ring, Algebra and Analysis, 19, 59-85 (2007), English translation: St. Petersburg Math. J. 19 (2008), 911-929 · Zbl 1206.13029 |
| [23] | Evdokimov, S.; Ponomarenko, I., On primitive cellular algebras, Zapiski Nauchnykh Seminarov POMI, 256, 38-68 (1999), English translation: J. Math. Sci., New York, 107 (5) (2001) 4172-4191 · Zbl 0979.16017 |
| [24] | Evdokimov, S.; Ponomarenko, I., Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, Algebra and Analysis, 14, 2, 11-55 (2002), English translation: St. Petersburg Math. J. 14 (2) (2003) 189-221 · Zbl 1056.20001 |
| [25] | Evdokimov, S.; Ponomarenko, I., Two inequalities for the parameters of a cellular algebra, Zapiski Nauchnykh Seminarov POMI, 240, 82-95 (1997), English translation: J. Math. Sci., New York 96 (5) (1999) 3496-3504 · Zbl 0960.20006 |
| [26] | Evdokimov, S.; Ponomarenko, I., On highly closed cellular algebras and highly closed isomorphisms, European. J. Combin., 6 (1999), #R18 · Zbl 0911.05061 |
| [27] | Evdokimov, S.; Ponomarenko, I., On a family of Schur rings over a finite cyclic group, Algebra and Analysis, 13, 3, 139-154 (2001), English translation: St. Petersburg Math. J. 13 (3) (2002) 441-451 · Zbl 1067.20005 |
| [28] | Evdokimov, S.; Ponomarenko, I., Separability number and schurity number of coherent configurations, Electron. J. Combin., 7 (2000), #R31 · Zbl 0939.05087 |
| [29] | S. Evdokimov, I. Ponomarenko, Schemes of a finite projective plane and their extensions, accepted in Algebra and Analysis, (2008). PDMI Preprint, 14 (2007), 1-34; S. Evdokimov, I. Ponomarenko, Schemes of a finite projective plane and their extensions, accepted in Algebra and Analysis, (2008). PDMI Preprint, 14 (2007), 1-34 |
| [30] | Evdokimov, S.; Ponomarenko, I., On the geometric graph isomorphism problem, J. Pure Appl. Algebra, 117-118, 253-276 (1997) · Zbl 0871.68141 |
| [31] | Evdokimov, S.; Ponomarenko, I., Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica, 19, 321-333 (1999) · Zbl 0932.05064 |
| [32] | Evdokimov, S.; Ponomarenko, I., Recognizing and isomorphism testing circulant graphs in polynomial time, Algebra and Analysis, 15, 6, 1-34 (2003), English translation: St. Petersburg Math. J. 15 (6) (2004) 813-835 · Zbl 1061.05045 |
| [33] | Evdokimov, S.; Ponomarenko, I.; Tinhofer, G., Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Math., 225, 149-172 (2000) · Zbl 0962.05041 |
| [34] | Evdokimov, S. A.; Ponomarenko, I. N.; Vershik, A. M., Algebras in Plancherel duality and algebraic combinatorics, Funct. Anal. Appl., 31, 4, 34-46 (1997) · Zbl 0917.16006 |
| [35] | Faradžev, I. A.; Klin, M. H.; Muzychuk, M. E., Cellular rings and groups of automorphisms of graphs, (Faradžev, I. A., Investigations In Algebraic Theory Of Combinatorial Objects (1994), Kluwer Acad. Publ: Kluwer Acad. Publ Dordrecht), 1-152 · Zbl 0795.05073 |
| [36] | I.A. Faradz˘ev, M.H. Klin, Computer package for computations with coherent configurations, Proc. Conf. ISSAC-91. Bonn, July 1991; I.A. Faradz˘ev, M.H. Klin, Computer package for computations with coherent configurations, Proc. Conf. ISSAC-91. Bonn, July 1991 · Zbl 0925.20006 |
| [37] | Friedland, S., Coherent algebras and the graph isomorphism problem, Discrete Appl. Math., 25, 73-98 (1989) · Zbl 0704.05023 |
| [38] | Goldbach, R. W.; Claasen, H. L., Cyclotomic schemes over finite rings, Indag. Math. (N.S.), 3, 301-312 (1992) · Zbl 0780.05059 |
| [39] | Gol’fand, J. Y.; Klin, M. H., Amorphic cellular rings I, (Investigations in Algebraic Theory of Combinatorial Objects, VNIISI (1985), Institute for System Studies: Institute for System Studies Moscow), 32-38, (in Russian) · Zbl 0717.20002 |
| [40] | Y.Y. Gol’fand, M.H. Klin, N.L. Naimark, The structure of S-rings over \(\mathbb{Z}_{2^m} \); Y.Y. Gol’fand, M.H. Klin, N.L. Naimark, The structure of S-rings over \(\mathbb{Z}_{2^m} \) |
| [41] | M. Grohe, Isomorphism testing for embeddable graphs through definability, Proc. of the 32nd ACM Ann. Symp. on Theory of Computing, 2000, 63-72; M. Grohe, Isomorphism testing for embeddable graphs through definability, Proc. of the 32nd ACM Ann. Symp. on Theory of Computing, 2000, 63-72 · Zbl 1296.05134 |
| [42] | A. Hanaki, Elementary functions for association schemes on GAP, 2007 http://kissme.shinshu-u.ac.jp/as/gap/association_scheme.pdf; A. Hanaki, Elementary functions for association schemes on GAP, 2007 http://kissme.shinshu-u.ac.jp/as/gap/association_scheme.pdf |
| [43] | A. Hanaki, I. Miyamoto, Classification of association schemes with small vertices, published on web http://kissme.shinshu-u.ac.jp/as/; A. Hanaki, I. Miyamoto, Classification of association schemes with small vertices, published on web http://kissme.shinshu-u.ac.jp/as/ · Zbl 0957.05518 |
| [44] | A. Heinze, M. Klin, Loops, Latin Squares and Strongly Regular Graphs: An algorithmic approach via Algebraic Combinatorics, 2008; A. Heinze, M. Klin, Loops, Latin Squares and Strongly Regular Graphs: An algorithmic approach via Algebraic Combinatorics, 2008 |
| [45] | Higman, D. G., Coherent configurations 1, Rend. Mat. Sem. Padova, 44, 1-25 (1970) · Zbl 0279.05025 |
| [46] | Higman, D. G., Coherent algebras, Linear Algebra Appl., 93, 209-239 (1987) · Zbl 0618.05014 |
| [47] | Higman, D. G., Strongly regular designs and coherent configurations of type \([\begin{matrix} 3 \& 2 \\ \& 3 \end{matrix}]\), European J. Combin., 9, 411-422 (1988) · Zbl 0659.05033 |
| [48] | Higman, D. G., Invariant relations, coherent configurations and generalized polygons, (Combinatorics (Proc. Advanced Study Inst., Breukelen, 1974), Part 3: Combinatorial group theory. Combinatorics (Proc. Advanced Study Inst., Breukelen, 1974), Part 3: Combinatorial group theory, Math. Centre Tracts, 57 (1974), Math. Centrum: Math. Centrum Amsterdam), 27-43 · Zbl 0366.05018 |
| [49] | Higman, D. G., Characterization of families of rank 3 permutation groups by the subdegree I, II, Arch. Math., 21, 151-156 (1970), 353-361 · Zbl 0245.20003 |
| [50] | Hirasaka, M., On quasi-thin association schemes with odd number of points, J. Algebra, 240, 665-679 (2001) · Zbl 0969.05069 |
| [51] | Hirasaka, M.; Muzychuk, M., On quasi-thin association schemes, J. Combin. Theory, A98, 17-32 (2002) · Zbl 0994.05149 |
| [52] | M.-D.A. Huang, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM Symp. on Theory of Computing (STOC) New York, (1985), 121-130; M.-D.A. Huang, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM Symp. on Theory of Computing (STOC) New York, (1985), 121-130 |
| [53] | Ishibashi, H.; Ito, T.; Yamada, M., Terwilliger algebras of cyclotomic schemes and jacobi sums, European J. Combin., 20, 397-410 (1999) · Zbl 0944.05101 |
| [54] | G. Ivanyos, On the combinatorics of Evdokimov’s deterministic factorization method, Draft preprint, 1997; G. Ivanyos, On the combinatorics of Evdokimov’s deterministic factorization method, Draft preprint, 1997 |
| [55] | M.Kh. Klin, The axiomatics of cellular rings, Investigations in the algebraic theory of combinatorial objects, 6-32, Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, 1985 (in Russian); M.Kh. Klin, The axiomatics of cellular rings, Investigations in the algebraic theory of combinatorial objects, 6-32, Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, 1985 (in Russian) · Zbl 0639.00001 |
| [56] | Klin, M.; Muzychuk, M.; Pech, C.; Woldar, A.; Zieschang, P.-H., Association schemes on 28 points as mergings of a half-homogeneous coherent configurations, European J. C., 28, 1994-2025 (2007) · Zbl 1145.05056 |
| [57] | Klin, M. Kh.; Pöschel, R., The König problem, the isomorphism problem for cyclic graphs and the method of Schur rings, (Algebraic Methods in Graph Theory. vol. 1, 2 (Szeged, 1978). Algebraic Methods in Graph Theory. vol. 1, 2 (Szeged, 1978), Colloq. Math. Soc. János Bolyai, 25 (1981), North-Holland: North-Holland Amsterdam, New York), 405-434 · Zbl 0416.05044 |
| [58] | Lagarias, J. C.; Montgomery, H. L.; Odlyzko, A. M., A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math., 54, 271-296 (1979) · Zbl 0401.12014 |
| [59] | Leman, A. A., On automorphisms of certain classes of graphs, Avtomat. Telemeh., 2, 75-82 (1970), English translation: Automat. Remote Control (1970) 235-242 · Zbl 0214.51302 |
| [60] | Lenstra, H. W., Finding isomorphisms between finite fields, Math. Comp., 56, 329-347 (1991) · Zbl 0709.11072 |
| [61] | Leon, J. S., An algorithm for computing the automorphism group of a hadamard matrix, J. Combin. Theory, A27, 289-306 (1979) · Zbl 0435.20002 |
| [62] | Lidl, R.; Niedereiter, H., Introduction To Finite Fields And Their Applications (1986), Cambridge University Press · Zbl 0629.12016 |
| [63] | McConnel, R., Pseudo-ordered polynomials over a finite field, Acta Arith., 8, 127-151 (1963) · Zbl 0113.01604 |
| [64] | Mesner, D. M.; Bhattacharya, P., Association schemes on triples and a ternary algebra, J. Combin. Theory, A55, 204-234 (1990) · Zbl 0761.05098 |
| [65] | Metsch, K., A characterization of grassmann graphs, European J. Combin., 16, 639-644 (1995) · Zbl 0836.05066 |
| [66] | G.L. Miller, On the \(n^{\log n}\); G.L. Miller, On the \(n^{\log n}\) · Zbl 1282.68192 |
| [67] | Muzychuk, M., A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc., 88, 1-41 (2004) · Zbl 1045.05052 |
| [68] | Muzychuk, M., On the isomorphism problem for cyclic combinatorial objects, Discrete Math., 197-198, 589-606 (1999) · Zbl 0938.05005 |
| [69] | M. Muzychuk, I. Ponomarenko, Schur rings, European J. Combin., in this issue (doi:10.1016/j.ejc.2008.11.006; M. Muzychuk, I. Ponomarenko, Schur rings, European J. Combin., in this issue (doi:10.1016/j.ejc.2008.11.006 · Zbl 1195.20003 |
| [70] | Muzychuk, M.; Zieschang, P.-H., On association schemes all elements of which have valency 1 or 2, Discrete Math, 308, 3097-3103 (2008) · Zbl 1145.05057 |
| [71] | Nomura, K., Spin models and bose-mesner algebras, European J. Combin., 20, 691-700 (1999) · Zbl 0936.05089 |
| [72] | Passman, D., Permutation Groups (1968), W. A. Benjamin, Inc.: W. A. Benjamin, Inc. New York, Amsterdam · Zbl 0179.04405 |
| [73] | Pöschel, P., Untersuchungen von S-ringen insbesondere im gruppenring von \(p\)-gruppen, Math. Nachr., 60, 1-27 (1974) · Zbl 0273.20005 |
| [74] | L. Rónyai, Factoring polynomials over finite fields, Proc. 28th IEEE Symp. on Foundations of Computer Science (FOCS) New York, (1987), 132-137; L. Rónyai, Factoring polynomials over finite fields, Proc. 28th IEEE Symp. on Foundations of Computer Science (FOCS) New York, (1987), 132-137 |
| [75] | Smith, J. D.H., Association schemes, superschemes, and relations invariant under permutation groups, European J. Combin., 15, 285-291 (1994) · Zbl 0796.05097 |
| [76] | Spielman, D., Faster isomorphism testing of strongly regular graphs, (Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, 1996, Philadelphia, PA (1996), ACM: ACM New York), 576-584 · Zbl 0915.05104 |
| [77] | Terwilliger, P., The subconstituent algebra of an association scheme, J. Algebraic Combin., 1, Part I, 363-388 (1992), (Part II) 2 (1993), 73-103; (Part III) 2 (1993), 177-210 · Zbl 0785.05089 |
| [78] | On construction and identification of graphs, (Weisfeiler, B., Lecture Notes in Math., 558 (1976)) · Zbl 0366.05019 |
| [79] | Weisfeiler, B. Ju.; Leman, A. A., Reduction of a graph to a canonical form and an algebra which appears in the process, NTI, Ser.2, 9, 12-16 (1968) |
| [80] | H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969; H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969 |
| [81] | Zieschang, P.-H., Homogeneous coherent configurations as generalized groups and their relationship to buildings, J. Algebra, 178, 677-709 (1995) · Zbl 0843.51017 |
| [82] | Zieschang, P.-H., The exchange condition for association schemes, Israel J. Math., 151, 357-380 (2006) · Zbl 1154.05062 |
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.
