Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs

• Autorzy: Kasjan S. , Simson D.

Identyfikatory

DOI

10.3233/FI-2015-1234

• Języki publikacji: EN

Abstrakty

EN

This paper can be viewed as a third part of our paper [Fund. Inform. 2015, in press]. Following our Coxeter spectral study in [Fund. Inform. 123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category UBigr_n of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study a larger category RBigr_n of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigr_n, with dotted loops, are studied by means of the complex Coxeter spectrum specc_Δ ⊂ C, the irreduciblemesh root systems of Dynkin types B_n, n ≥ 2, C_n, n ≥ 3, F₄, G₂, the isotropy group G1(n, Z)_Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24]. Here we present combinatorial algorithms for constructing the isotropy groups G1(n,Z)_Δ. One of the aims of our three paper series is to develop computational tools for the study of the Zcongruence ~Z and the following Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' holds, for any pair of connected positive graphsΔ,Δ' ∈ RBigr_n such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ' coincide?". For this purpose, we construct in this paper a extended inflation algorithm Δ → DΔ, with DΔ ~Z Δ, that allows a reduction of the question to the Coxeter spectral study of the G1(n,Z)_D-orbits in the set Mor_D ⊂ M_n(Z) of matrix morsifications of the associated edge-bipartite Dynkin graph D = DΔ ∈ RBigrn. We also outline a construction of a numeric algorithm for computing the isotropy group G1(n,Z)_Δ of any connected positive edge-bipartite graph Δ in RBigr_n. Finally, we compute the finite isotropy group G1(n,Z)_D, for each of the Cox-regular edge-bipartite Dynkin graphs D.

Słowa kluczowe

EN

poset; Coxeter spectrum; Dynkin diagram; Coxeter-Dynkin type; isotropy group

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 3
• Strony: 249--275
• Opis fizyczny: Bibliogr. 45 poz., tab., wykr.

Twórcy

autor

Kasjan S.

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University ul. Chopina 12/18, 87-100 Toruń, Poland

autor

Simson D.

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University ul. Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [1] I. Assem, D. Simson and A. Skowroński, Elements of the Representation Theory of Associative Algebras, Volume 1. Techniques of Representation Theory, London Math. Soc. Student Texts 65, Cambridge Univ. Press, Cambridge-New York, 2006.
• [2] R. Bautista and D. Simson, Torsionless modules over 1-Gorenstein ℓ-hereditary artinian rings, Comm. Algebra 12(1984), 899–936.
• [3] R. Bocian, M. Felisiak and D. Simson, Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups, J. Comp. Appl. Math. 259(2014), 815-827, doi:10.1016/j.cam.2013.07.013.
• [4] V. M. Bondarenko, V. Futorny, T. Klimchuk, V.V. Sergeichuk and K. Yusenko, Systems of subspaces of a unitary space, Linear Algebra Appl. 438(2013), 2561-2573, doi: 10.1016/j.laa. 2012.10.038.
• [5] V. Bugaenko, Y. Cherniavsky, T. Nagnibeda, and R. Shwartz, Weighted Coxeter graphs and generalized geometric representations of Coxeter groups, Discrete Applied Mathematics, 2015, in press, doi:10.1016/dam.2014.05.012.
• [6] D. M. Cvetkovi´c, P. Rowlinson and S. K. Simić, An Introduction to the Theory of Graph Spectra, London Math. Soc. Student Texts 75, Cambridge Univ. Press, Cambridge-New York, 2010.
• [7] M. Felisiak, Computer algebra technique for Coxeter spectral study of edge-bipartite graphs and matrix morsifications of Dynkin type An, Fund. Inform. 125(2013), 21-49.
• [8] M. Felisiak and D. Simson, On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram An, Discrete Math. 313(2013), 1358-1367, doi: 10.1016/j.disc.2013.02.003.
• [9] M. Felisiak and D. Simson, Applications of matrix morsifications to Coxeter spectral study of loop-free edge-bipartite graphs, Discrete Appl. Math. 2015, in press , doi: 10.1016/dam.2014.05.002.
• [10] M. Gąsiorek, Efficient computation of the isotropy group of a finite graph: a combinatorial approach, SYNASC 2013, IEEE Computer Society, IEEE CPS, Tokyo, 2014, pp. 104-111.
• [11] M. Gąsiorek and D. Simson, One-peak posets with positive Tits quadratic form, their mesh translation quivers of roots, and programming in Maple and Python, Linear Algebra Appl. 436(2012), 2240–2272, doi:10.1016/j.laa. 2011.10.045.
• [12] M. Gąsiorek, D. Simson and K. Zając, Algorithmic computation of principal posets using Maple and Python, Algebra Discrete Math. 17(2013), No. 1, 33–69.
• [13] M. Gąsiorek, D. Simson and K. Zając, On Coxeter type study of non-negative posets using matrix morsifications and isotropy groups of Dynkin and Euclidean diagrams, Europ. J. Comb. 2015, in press, doi:10.1016/j.ejc.2015.02.15.
• [14] J. P. Gram, On Raekkeudviklinger bestemte ved Hjaelp of de mindste Kvadraters Methode, Kopenhavne, 1879.
• [15] H. J. von Höhne, On weakly positive unit forms, Comment. Math. Helvetici 63(1988), 312–336.
• [16] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics 9, Springer-Verlag, New York Heidelberg, Berlin, 1972.
• [17] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics 29, Cambridge Univ. Press, 1990.
• [18] T. Inohara, Characterization of clusterability of signed graphs in terms of newcombs balance of sentiments, Applied Math. and Comp. 133( 2002), 93-104.
• [19] M. Kaniecki, J. Kosakowska, P. Malicki, and G. Marczak, A horizontal mesh algorithm for a class of edgebipartite graphs and their matrix morsifications, Fund. Inform. 136(2015), 345-379.
• [20] S. Kasjan and D. Simson, Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems, Fund. Inform. 127(2015), in press, doi: 10.3233/FI-2015-1194
• [21] S. Kasjan and D. Simson, Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, II. Application to Coxeter spectral analysis, Fund. Inform. 127(2015), in press, doi:10.3233/FI-2015-1195
• [22] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra Discrete Math. 4 (2008), 49-79.
• [23] J. Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform. 119(2012), 149-162, doi: 10.3233/FI-2012-731.
• [24] S. A. Krugliak and I. V. Livinskyi, Regular orthoscalar representations of the extended Dynkin grapheE8 and ∗-algebra associated with it, Ukrain. Math. Zh. 62(2010), 1213-1233.
• [25] J. Kunegis, Spectral analysis of signed graphs for clustering, prediction, and visualization, In SDM SIAM 2010, pp. 559-570.
• [26] G. Marczak, A. Polak and D. Simson, P-critical integral quadratic forms and positive unit forms. An algorithmic approach, Linear Algebra Appl. 433(2010), 1873–1888; doi: 10.1016/j.laa. 2010.06.052.
• [27] A. Mróz, On the computational complexity of Bongartz′s algorithm, Fund. Inform. 123(2013), 317–329.
• [28] A. Mróz and J. A. de la Peña, Tubes in derived categories and cyclotomic factors of Coxeter polynomials of an algebra, J. Algebra 420(2014), 242-260.
• [29] S. Nowak and D. Simson, Locally Dynkin quivers and hereditary coalgebras whose left comodules are direct sums of finite dimensional comodules, Comm. Algebra 30(2002), 405–476.
• [30] J. A. de la Peña, Algebras whose Coxeter polynomials are products of cyclotomic polynomials, Algebras and Repr. Theory 17(2014), 905-930, doi.10.1007/s10468-013-9424-0.
• [31] C. M. Ringel, Tame Algebras and Integral Quadratic Forms, Lecture Notes in Math., Vol. 1099, Springer–Verlag, Berlin–Heidelberg–New York-Tokyo, 1984.
• [32] M. Sato, Periodic Coxeter matrices and their associated quadratic forms, Linear Algebra Appl. 406(2005), 99–108; doi: 10.1016/j.laa. 2005.03.036.
• [33] D. Simson, Socle reductions and socle projective modules, J Algebra 103(1986), 16–68.
• [34] D. Simson, Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets, Linear Algebra Appl. 433(2010), 699–717; doi: 10.1016/j.laa. 2010.03.04.
• [35] D. Simson, Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra 215(2011), 13–34, doi: 10.1016/j.jpaa. 2010.02.029.
• [36] D. Simson, Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fund. Inform. 109(2011), 425–462, doi: 10.3233/FI-2011-603.
• [37] D. Simson, A Coxeter-Gram classification of simply laced edge-bipartite graphs, SIAM J. Discr. Math. 27(2013), 827-854; doi: 10.1137/110843721.
• [38] D. Simson, Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 123(2013), 447-490., doi: 10.3233/FI-2013-820.
• [39] D. Simson, A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits, Fund. Inform. 124(2013), 309-338, doi: 10.3233/FI-2013-836.
• [40] D. Simson, Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4, Fund. Inform. 124(2013), 339-364, doi: 10.3233/FI-2013-837
• [41] D. Simson, Tame-wild dichotomy of Birkhoff type problems for nilpotent linear operators, J. Algebra 424(2015), 254-293, doi: 10.10.1016/jalgebra.2014.11.008.
• [42] D. Simson andM.Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83(2008), 389–410.
• [43] A. P. Wojda, A condition for a graph to contain k-maching, Discrete Math. 276(2004), 375–378.
• [44] Y. Zhang, Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 17(1989), 2347-2362.
• [45] Y. Zhang, The structure of stable components, Canad. J. Math., 43 (1991), 652–672, doi: 10.4153/CJM-1991-038-1.