Weighted association schemes, fusions, and minimal coherent closures. (English) Zbl 1332.05156
Author’s abstract: A weighted association scheme is a scheme with an edge weight function, which for our purposes will take values \(\pm 1\). When the scheme has a coherent fusion – a merging of classes resulting in another association scheme – the edge weights on the fusion scheme are inherited. The reverse process involves the coherent closure of a weighted scheme: the smallest coherent algebra containing the weighted adjacency matrices. The weight function applied to this closure is necessarily trivial, meaning constant on classes of the associated configuration. In this work there are two main objects of study: minimal rank coherent closures of strongly regular graphs with regular weights; and strongly regular graphs with regular weights which are obtained as fusions of association schemes with trivial regular weights. Both of these extend the work of D. Taylor on regular two-graphs and their interactions with strongly regular graphs. We obtain regular weights on strongly regular graphs with 125 and 256 vertices as fusions of rank 5 weighted schemes, and a family of rank 6, primitive, non-metric schemes which are minimal-rank closures of weighted lattice graphs. Our main result is the classification of these coherent closures of rank 4. They are imprimitive rank 4 association schemes, which have been studied generally by E. R. van Dam [J. Algebr. Comb. 10, No. 1, 69–107 (1999; Zbl 0929.05096)], and Y. Chang and T. Huang [Ann. Comb. 4, No. 3–4, 317–326 (2000; Zbl 0970.05044)].
Reviewer: Jack Koolen (Hefei)
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C12 | Distance in graphs |
| 05C22 | Signed and weighted graphs |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Keywords:
association scheme; coherent configuration; coherent closure; Weisfeiler-Lehman stabilization; regular weightReferences:
| [1] | Babel, L., Chuvaeva, I., Klin, M., Pasechnik, D.: Algebraic combinatorics in mathematical chemistry. Methods and algorithms. II. Program implementation of the Weisfeiler-Lehman algorithm. arXiv:1002.1921 [math.CO] |
| [2] | Bannai, E., Ito, T.: Algebraic Combinatorics. I: Association Schemes. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984) · Zbl 0555.05019 |
| [3] | Brouwer, A.: BCN tables. http://www.win.tue.nl/ aeb/drg/drgtables.html. Accessed 2012 |
| [4] | Brouwer, A.: Parameters of strongly regular graphs. http://www.win.tue.nl/ aeb/graphs/srg/srgtab.html. Accessed 2013 |
| [5] | Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989) · Zbl 0747.05073 |
| [6] | Cameron, P.J., van Lint, J.H.: Designs, Graphs, Codes and Their Links, London Mathematical Society Student Texts, vol. 22. Cambridge University Press, Cambridge and New York (1991) · Zbl 0743.05004 |
| [7] | Chang, Y., Huang, T.: Imprimitive association schemes of low ranks and Higmanian graphs. Ann. Comb. 4, 317-326 (2000) · Zbl 0970.05044 · doi:10.1007/PL00001283 |
| [8] | Conway, J.H., Curtis, R.T., Norton, S.P., Parker, R.A., Wilson, R.: Atlas of Finite Groups. Clarendon Press, Oxford (1985) · Zbl 0568.20001 |
| [9] | Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York (1993) · Zbl 0784.05001 |
| [10] | Hanaki, A., Miyamoto, I.: Classification of association schemes of small order. http://kissme.shinshu-u.ac.jp/as/. Accessed 2010-2011 · Zbl 1014.05073 |
| [11] | Higman, D.G.: Coherent configurations I: ordinary representation theory. Geom. Dedicata 4, 1-32 (1975) · Zbl 0333.05010 · doi:10.1007/BF00147398 |
| [12] | Higman, D.G.: Coherent configurations II: weights. Geom. Dedicata 5, 413-424 (1976) · Zbl 0353.05009 · doi:10.1007/BF00150773 |
| [13] | Higman, D.G.: Coherent algebras. Linear Algebra Appl. 93, 209-239 (1987) · Zbl 0618.05014 · doi:10.1016/S0024-3795(87)90326-0 |
| [14] | Higman, D.G.: Weights and \[t\] t-graphs. Algebra, groups and geometry. Bull. Soc. Math. Belg. Sér. A 42(3), 501-521 (1990) · Zbl 0787.05020 |
| [15] | Jørgensen, L.K., Klin, M.H.: Switching of edges in strongly regular graphs. I.: a family of partial difference sets on 100 vertices. Electron. J. Comb. 10, R17 (2003) · Zbl 1011.05063 |
| [16] | Klin, M., Munemasa, A., Muzychuk, M., Zieschang, P.H.: Directed strongly regular graphs obtained from coherent algebras. Linear Algebra Appl. 377, 83-109 (2004) · Zbl 1030.05119 · doi:10.1016/j.laa.2003.06.020 |
| [17] | 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), 19942025 (2007) · Zbl 1145.05056 · doi:10.1016/j.ejc.2006.08.010 |
| [18] | Maple 16.00: Maplesoft, a division of Waterloo Maple Inc., Waterloo, ON (2013) |
| [19] | Martin, W.J., Tanaka, H.: Commutative association schemes. Eur. J. Comb. 30, 1497-1524 (2009) · Zbl 1228.05317 · doi:10.1016/j.ejc.2008.11.001 |
| [20] | McKay, B.D., Spence, E.: Classification of regular two-graphs on 36 and 38 vertices. Australas. J. Comb. 24, 293-300 (2001) · Zbl 0979.05110 |
| [21] | Mesner, D.M.: Negative Latin Square Designs, NC Mimeo Series, vol. 410. Institute of Statistics, UNC. Chapel Hill, NC (1964) |
| [22] | Sankey, A.D.: Regular weights on strongly regular graphs. Ph.D. thesis, University of Michigan, Ann Arbor, MI (1992) · Zbl 0863.05084 |
| [23] | Sankey, A.D.: Regular weights of full rank on strongly regular graphs. Isr. J. Math. 95, 1-23 (1996) · Zbl 0863.05084 |
| [24] | Seidel, J.J.: A survey of two-graphs. In: Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I, pp. 481-511. Atti dei Convegni Lincei, No. 17. Accad. Naz. Lincei, Rome (1976) · Zbl 0352.05016 |
| [25] | Seidel, J.J.: More about two-graphs. In: Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), Annals of Discrete Mathematics, vol. 51, pp. 297-308. North-Holland, Amsterdam (1992) · Zbl 0764.05036 |
| [26] | Seidel, J.J., Taylor, D.E.: Two-graphs, a second survey. In: Algebraic Methods in Graph Theory, vols. I, II (Szeged, 1978), Colloquia Mathematica Societatis János Bolyai, vol. 25, pp. 689-711. North-Holland, Amsterdam (1981) · Zbl 0475.05073 |
| [27] | Stein, W.: Sage: Open Source Mathematical Software (Version 2.10.2). http://www.sagemath.org (2008) |
| [28] | Taylor, D.E.: Regular 2-graphs. Proc. Lond. Math. Soc. Ser. 3. 35(2), 257-274 (1977) · Zbl 0362.05065 |
| [29] | The GAP Group: Gap—Groups, Algorithms, and Programming (Version 4.6.4). http://www.gap-system.org (2013) |
| [30] | van Dam, E.R.: Three-class association schemes. J. Algebr. Comb. 10, 69-107 (1999) · Zbl 0929.05096 · doi:10.1023/A:1018628204156 |
| [31] | van Dam, E.R., Koolen, J.H., Tanaka, H.: Distance-regular graphs. https://sites.google.com/site/edwinrvandam/. Accessed Oct 2012 · Zbl 1335.05062 |
| [32] | Weisfeiler, B., Lehman, A.: Reduction of a graph to a canonical form and an algebra which appears in the process. NTI 9, 12-16 (1968) |
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.
