×

zbMATH — the first resource for mathematics

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.

MSC:
05E30 Association schemes, strongly regular graphs
20B99 Permutation groups
PDF BibTeX XML Cite
Full Text: DOI
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, (), 1447-1541 · Zbl 0846.05042
[5] 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
[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 · Zbl 1207.05022
[9] Bannai, E.; Ito, T., Algebraic combinatorics. I, (1984), 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
[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, ()
[13] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, () · Zbl 0747.05073
[14] Handbook of incidence geometry, () · 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)
[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, (), 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
[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
[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
[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
[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
[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, (), 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 · 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, (), 32-38, (in Russian)
[40] Y.Y. Gol’fand, M.H. Klin, N.L. Naimark, The structure of S-rings over \(\mathbb{Z}_{2^m}\), XVI All Union Algebraic Conference, Part 2, (Leningrad 1981), LOMI, 1981, 195-196 (in Russian)
[41] 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
[43] 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
[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, (), 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
[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
[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)
[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, (), 405-434
[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
[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}\) isomorphism technique, The 10th Annual ACM Symposium on the Theory of Computing, 1978, 51-58 · 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) · 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. 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
[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, (), 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, ()
[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
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.