Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops. [Part] 1, Mesh Root Systems

• Autorzy: Kasjan S. , Simson D.

Identyfikatory

DOI

10.3233/FI-2015-1230

• Języki publikacji: EN

Abstrakty

EN

This is the first 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 RBigrn 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 C, the irreducible mesh root systems of Dynkin types B_n, n ≥ 2, C_n, n ≥ 3, F4, G2, the isotropy group Gl(n;Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of the 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 Δ0 coincide?" We do it by a reduction to the Coxeter spectral study of the Gl(n, Z)D-orbits in the set MorD Mn(Z) of matrix morsifications of a Dynkin diagram D = DΔ ∊ UBigrn associated with Δ. In particular, we construct in the second part of the paper numeric algorithms for computing the connected positive edge-bipartite graphs Δ in RBigrn, 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 Δ;Δ' ∊ RBigrn, with n ≥ 2 fixed, and mesh-type algorithms for the mesh root systems Γ(RD Δ(RΔФΔ). In the first part of the paper we present an introduction to the study of Cox-regular edge-bipartite graphs Δ with dotted loops in relation with the irreducible reduced root systems and the Dynkin diagrams B_n, n ≥ 2, C_n, n ≥ 3, F₄, G₂. Moreover, we construct a unique ФD-mesh root system (RD,ФD) for each of the Cox-regular edge-bipartite graphs B_n, n ≥ 2, C_n, n ≥ 3, F₄, calG₂ of the type B_n, n ≥ 2, C_n, n ≥ 3, F₄, G₂, respectively. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems.

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: 153--184
• Opis fizyczny: Bibliogr. 63 poz., tab.

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] M. Barot and J. A. de la Peña, The Dynkin type of a non-negative unit form, Exposition. Math. 17(1999), 339–348.
• [3] R. Bautista and D. Simson, Torsionless modules over 1-Gorenstein `-hereditary artinian rings, Comm. Algebra 12(1984), 899–936.
• [4] 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.
• [5] 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.
• [6] 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/j.dam.2014.05.012.
• [7] S. Butler and J. Grout, A construction of cospectral graphs for the normalized Laplacian, Electronic J. Combin. 18(2011), #P231.
• [8] D. M. Cvetković, 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.
• [9] 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.
• [10] M. Felisiak and D. Simson, On computing mesh 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.
• [11] M. Felisiak and D. Simson, On Coxeter type classification of loop-free edge-bipartite graphs and matrix morsifications, SYNASC 2013, Timisoara, 2013, IEEE Post-Conference Proceedings, IEEE CPS Computer Society, IEEE CPS, Tokyo, 2013, pp. 115-118, doi: 10.1109//SYNASC.2013.22.
• [12] 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.
• [13] 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.
• [14] 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.
• [15] 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.
• [16] M. Gąsiorek, D. Simson, A computation of positive one-peak posets that are Tits-sincere, Colloq. Math. 127(2012), 83–103.
• [17] M. Gąsiorek, D. Simson and K. Zając, Algorithmic computation of principal posets using Maple and Python, Algebra and Discrete Math. 17(2013), No. 1, pp. 33–69.
• [18] 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..
• [19] 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.
• [20] M. F. Goodman, P. de la Harpe and V.F.R. Jones, Coxeter Graphs and Towers of Algebras, Math. Sci. Res. Inst. Publ. 14, Springer-Verlag, New York-Berlin-Heidelberg, 1989.
• [21] J. P. Gram, On Raekkeudviklinger bestemte ved Hjaelp of de mindste Kvadraters Methode, Kopenhavne, 1879.
• [22] D. Happel, Triangulated categories in the representation theory of finite dimensional algebras, London Math. Soc. Lecture Notes Series, Vol. 119, 1988.
• [23] H. J. von Höhne, On weakly positive unit forms, Comment Math. Helvetici 63(1988), 312–336.
• [24] M. Hazewinkel, W. Hesselink, D. Siersma and F. D Veldkamp, The ubiquity of Coxeter-Dynkin diagrams, New Archief voor Wiskunde (3) 25(1977), 257-307.
• [25] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics 9, Springer-Verlag, New York Heidelberg, Berlin, 1972.
• [26] T. Inohara, Characterization of clusterability of signed graphs in terms of newcombs balance of sentiments, Applied Math. and Comp. 133( 2002), 93-104.
• [27] 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.
• [28] 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. 2015, in press, this volume.
• [29] S. Kasjan and D. Simson, Algorithms for isotropy groups of Cox-regular edge-bipartite graphs, Fund. Inform. 2015, in press.
• [30] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra and Discrete Math. 4 (2008), 49-79.
• [31] 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.
• [32] S. A. Krugliak and I. V. Livinskyi, Regular orthoscalar representations of the extended Dynkin graphe E8 and _-algebra associated with it, Ukrain. Math. Zh. 62(2010), 1213-1233.
• [33] J. Kunegis, Spectral analysis of signed graphs for clustering, prediction, and visualization, In SDM SIAM 2010, pp. 559-570.
• [34] 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´nski), Series of Congress Reports, European Math. Soc. Publishing House, Zürich, 2008, pp. 541–588.
• [35] 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.
• [36] A. Mróz, On the computational complexity of Bongartz0s algorithm, Fund. Inform. 123(2013), 317–329.
• [37] 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.
• [38] 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.
• [39] 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.
• [40] 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.
• [41] C. M. Ringel, Tame Algebras and Integral Quadratic Forms, Lecture Notes in Math., Vol. 1099, Springer–Verlag, Berlin–Heidelberg–New York-Tokyo, 1984.
• [42] 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.
• [43] V. V. Sergeichuk, Canonical matrices for linear matrix problems, Linear Algebra Appl. 317(2000), 53–102.
• [44] D. Simson, Socle reductions and socle projective modules, J Algebra 103(1986), 16–68.
• [45] D. Simson, A reduction functor, tameness, and Tits form for a class of orders, J. Algebra 174(1995), 439–452.
• [46] D. Simson, Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories, Colloq. Math. 115(2009), 259–295.
• [47] 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.
• [48] 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.
• [49] 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.
• [50] D. Simson, A Coxeter-Gram classification of simply laced edge-bipartite graphs, SIAM J. Discr. Math. 27(2013), 827-854; doi: 10.1137/110843721.
• [51] 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.
• [52] 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.
• [53] 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.
• [54] 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.
• [55] D. Simson and A. Skowro´nski, Elements of the Representation Theory of Associative Algebras, Volume 2. Tubes and Concealed Algebras of Euclidean Type, London Math. Soc. Student Texts 71, Cambridge Univ. Press, Cambridge-New York, 2007.
• [56] D. Simson and M.Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83(2008), 389–410.
• [57] D. Simson and K. Zaja˛c, A framework for Coxeter spectral classification of finite posets and their mesh geometries of roots, Int. J. Math. Math. Sci. 2013, Article ID 743734, 22 pages, doi: 10.1155/2013/743734.
• [58] R. Steinberg, Conjugacy Classes in Algebraic Groups, Lecture Notes in Math., Vol. 366, Springer–Verlag, Berlin–Heidelberg–New York-Tokyo, 1974.
• [59] R. Steinberg, On the desingularization of the unipotent varieties, Invent. Math. 36(1976), 209-224.
• [60] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4(1982), 47–74.
• [61] Y. Zhang, Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 17(1989), 2347-2362..
• [62] Y. Zhang, The structure of stable components, Canad. J. Math., 43 (1991), 652–672, doi: 10.4153/CJM-1991-038-1.
• [63] http://www.gap-system.org/Gap3/gap3.html