Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops [Part] 2. Application to Coxeter Spectral Analysis

• Autorzy: Kasjan S. , Simson D.

Identyfikatory

DOI

10.3233/FI-2015-1231

• Języki publikacji: EN

Abstrakty

EN

This is a second part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827- 854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n = 2 vertices, we study here the 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 RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ C, the irreducible mesh root systems of Dynkin types B_n, n = 2, C_n, n = 3, F₄, G₂, the isotropy group Gl(n, Z)_Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of our two part paper is to study the Coxeter spectral analysis question: "Does the congruence Δ Z Δ' hold, for any pair of connected positive graphs Δ,Δ' ∊ RBigrn such that speccΔ = speccΔ' and the numbers of loops in ΔandΔ' coincide?"We do it by a reduction to the Coxeter spectral study of the Gl(n, Z)D-orbits in the set MorD C Mn(Z) of matrix morsifications of a Dynkin diagram D = DΔ ∊ UBigrn associated with Δ. In this second part, we construct numeric algorithms for computing the connected positive edge-bipartite graphs Δ in RBigr_n, for a fixed n = 2, mesh algorithms for computing the set of all Z-invertible matrices B ∊ Gl(n, Z) definining the Z-congruenceΔ Z Δ', for positive graphsΔ,Δ' ∊ RBigr_n, with n geq2 fixed, and mesh-type algorithms for the mesh root systems Γ(R·_Δ,Φ_Δ). We also present a classification and a structure type results for positive Cox-regular edge-bipartite graphs Δ with dotted loops.

Słowa kluczowe

EN

edge-bipartite graph; Dynkin diagram; morsification; Coxeter spectrum; Coxeter-Gram polynomial; mesh root system; mesh algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 2
• Strony: 185--209
• Opis fizyczny: Bibliogr. 47 poz.

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´nski, 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] 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.
• [6] M. Felisiak and D. Simson, On computingmesh root systems and the isotropy group for simply-laced Dynkin diagrams, SYNASC12, Timisoara, 2012, IEEE Post-Conference Proceedings, IEEE Computer Society, IEEE CPS, pp. 91-97,Washington-Tokyo, 2012.
• [7] 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.
• [8] 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.
• [9] 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.
• [10] 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.
• [11] M. Gąsiorek and D. Simson, A computation of positive one-peak posets that are Tits-sincere, Colloq. Math. 127(2012), 83–103.
• [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, pp. 33–69.
• [13] M. Gąsiorek, D. Simson and K. Zając, Structure and a Coxeter-Dynkin type classification of corank two non-negative posets, Linear Algebra Appl. 469(2015), 76-113, doi: 10.1016/j.laa. 2014.11.003.
• [14] 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.
• [15] M. Gąsiorek and K. Zając, On algorithmic study of non-negsative posets of corank at most two and their Coxeter-Dynkin types, Fund. Inform. 137(2015), in press.
• [16] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics 9, Springer-Verlag, New York Heidelberg, Berlin, 1972.
• [17] T. Inohara, Characterization of clusterability of signed graphs in terms of newcombs balance of sentiments, Applied Math. and Comp. 133( 2002), 93-104.
• [18] 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.
• [19] 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. 2015, in press, this volume.
• [20] S. Kasjan and D. Simson, Algorithms for isotropy groups of Cox-regular edge-bipartite graphs, Fund. Inform. 2015, to appear.
• [21] B. Klemp and D. Simson, Schurian sp-representation-finite right peak PI-rings and their indecomposable socle projective modules, J. Algebra 131 (1990), 390–468.
• [22] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra and 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] J. Kunegis, Spectral analysis of signed graphs for clustering, prediction, and visualization, In SDM SIAM 2010, pp. 559-570.
• [25] H. Lenzing and J.A. de la Peña, Spectral analysis of finite dimensional algebras and singularities, In: Trends in Representation Theory of Algebras and Related Topics, ICRA XII, (ed. A. Skowroński), Series of Congress Reports, EuropeanMath. Soc. Publishing House, Zürich, 2008, pp. 541–588.
• [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] J. A. de la Peña, On the Mahler measure of the Coxeter polynomial of an algebra, Adv. Math. 270(2015), 375-399.
• [32] A. Polak and D. Simson, Coxeter spectral classification of almost TP-critical one-peak posets using symbolic and numeric computations, Linear Algebra Appl. 445 (2014) 223–255, doi10.1016/j.laa.2013.12.018.
• [33] C. M. Ringel, Tame Algebras and Integral Quadratic Forms, Lecture Notes in Math., Vol. 1099, Springer–Verlag, Berlin–Heidelberg–New York-Tokyo, 1984.
• [34] V. V. Sergeichuk, Canonical matrices for linear matrix problems, Linear Algebra Appl. 317(2000), 53–102.
• [35] D. Simson, Socle reductions and socle projective modules, J Algebra 103(1986), 16–68.
• [36] D. Simson, A reduction functor, tameness, and Tits formfor a class of orders, J. Algebra 174(1995), 439–452.
• [37] 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.
• [38] 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.
• [39] 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.
• [40] D. Simson, A Coxeter-Gram classification of simply laced edge-bipartite graphs, SIAM J. Discr. Math. 27(2013), 827-854; doi: 10.1137/110843721.
• [41] 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.
• [42] 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.
• [43] 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.
• [44] 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.
• [45] D. Simson andM.Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83(2008), 389–410.
• [46] Y. Zhang, Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 17(1989), 2347-2362.
• [47] Y. Zhang, The structure of stable components, Canad. J. Math., 43 (1991), 652–672, doi: 10.4153/CJM-1991-038-1.