Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops

• Autorzy: Makuracki B. , Simson D. , Zyglarski B.

Identyfikatory

DOI

10.3233/FI-2017-1545

• Języki publikacji: EN

Abstrakty

EN

We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix Ğ_Δ ∊ M_n(Z) defining Δ, its symmetric Gram matrix G_Δ:=1/2[Ğ_Δ+Ğ^tr_Δ]∊ M_n(1/2Z), and the Gram quadratic form q_Δ : Zⁿ → Z. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix G_Δ∊ M_n(Z) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram Z-congruence Δ _~Z Δ', where Δ _~ZΔ' means that G_Δ' = B^tr.G_Δ .B, for some B ∊ M_n(Z) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph D_n ∊ {B_n, C_n, F₄, G₂} with loops and a suitably chosen sequence t-• of the inflation operators of one of the types Δ'↦t-_aΔ' and Δ'↦t-_abΔ' such that the composite operator Δ↦t-•Δ reduces Δ to the bigraph D_n such that Δ _~Z D_n and the bigraphs Δ, D_n have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∊ M_n(Z), with det B = ±1, defining the weak Gram Z-congruence Δ _~Z D_n, that is, satisfying the equation G_Dn= B^tr.G_Δ.B.

Słowa kluczowe

EN

Coxeter spectrum; Dynkin graph; edge-bipartite graph; gram matrix; inflation algorithm; isotropy group; unit quadratic form

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 4
• Strony: 367--398
• Opis fizyczny: Bibliogr. 56 poz.

Twórcy

autor

Makuracki B.

• 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

autor

Zyglarski B.

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

Bibliografia

• [1] Abarca M. and Rivera D. Theoretical and algorithmic characterizations of positive definite symmetric quasi-Cartan matrices, Fund. Inform. 2016;149:241-261, doi:10.3233/FI-2016-1448.
• [2] Assem I, Simson D and Skowroński A. 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. ISBN:9780521586313.
• [3] Barot M, and de la Peña JA. The Dynkin type of a non-negative unit form, Exposition. Math. 1999;17:339–348.
• [4] Barot M, Geiss C, and Zelevinsky A. Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. 2006;73(3):545-564. doi:10.1112/S0024610706022769.
• [5] Bocian R, Felisiak M, and Simson D. Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups, J. Comp. Appl. Math. 2014;259:815–827. doi:10.1016/j.cam.2013.07.013.
• [6] Bondarenko VM, Futorny V, Klimchuk T, Sergeichuk VV, and Yusenko K. Systems of subspaces of a unitary space, Linear Algebra Appl. 2013;438:2561–2573. doi:10.1016/j.laa. 2012.10.038.
• [7] Bondarenko VM. and Stepochkina M.V. (Min, max)-equivalence of posets and nonnegative Tits forms, Ukrain. Mat. Zh. 2008;60:1157–1167. doi:10.1007/s11253-009-0147-7.
• [8] Dlab V. and Ringel CM. Indecomposable representations of graphs and algebras, Memoirs Amer. Math. Soc Vol. 173, 1976. URL urn:nbn:de:0070-bipr-26097.
• [9] Dowbor P. and Simson D. Quasi-Artin species and rings of finite representation type, J. Algebra 1980;63: 435-443.
• [10] Felisiak M. and Simson D. On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram An, Discrete Math. 2013;313:1358-1367. doi: 10.1016/j.disc.2013.02.003.
• [11] Felisiak M. and Simson D. Applications of matrix morsifications to Coxeter spectral study of loop-free edge-bipartite graphs, Discrete Appl. Math. 2015;192:49–64. doi:10.1016/j.dam.2014.05.002.
• [12] Gąsiorek M. Efficient computation of the isotropy group of a finite graph: a combinatorial approach, in: Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2013, IEEE CPS, Los Alamitos, Calif. [etc.], 2014, pp. 104–111, doi:10.1109/SYNASC.2013.21.
• [13] Gąsiorek M. and Simson D. A computation of positive one-peak posets that are Tits-sincere, Colloq. Math. 2012;127:83–103. doi:10.4064/cm127-1-6.
• [14] Gąsiorek M. Simson D. and Zając K. On corank two edge-bipartite graphs and simply extended Euclidean diagrams, SYNASC 2014, IEEE Computer Society, IEEE CPS, Tokyo, 2015, pp. 66–73. doi:10.1109/SYNASC.2014.17.
• [15] Gąsiorek M. Simson D. and Zając K. On Coxeter type study of non-negative posets using matrix morsifications and isotropy groups of Dynkin and Euclidean diagrams, Europ. J. Comb. 2015;48:127–142. doi:10.1016/j.ejc.2015.02.015.
• [16] Gąsiorek M. Simson D. and Zając K. A Gram classification of non-negative corank two loop-free edgebipartite graphs, Linear Algebra Appl. 2016;500:88–118. doi:10.1016/j.laa.2016.03.007.
• [17] Gąsiorek M. and Zając K. On algorithmic study of non-negative posets of corank at most two and their Coxeter-Dynkin types, Fund. Inform. 2015;139(4):347–367. doi:10.3233/FI-2015-1150.
• [18] Humphreys JE. Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics 9, Springer-Verlag, New York Heidelberg, Berlin, 1972. doi:10.1007/978-1-4612-6398-2.
• [19] Inohara T. Characterization of clusterability of signed graphs in terms of new combs balance of sentiments, Applied Math. and Comp. 2002;133:93-104. doi:10.1016/S0096-3003(01)00224-7.
• [20] Kaniecki M. Kosakowska J. Malicki P. and Marczak G. A horizontal mesh algorithm for a class of edgebipartite graphs and their matrix morsifications, Fund. Inform. 2015;136:345-379. doi:10.3233/FI-2016-1346.
• [21] Kaniecki M. Kosakowska J. Malicki P. and Marczak G. A horizontal mesh algorithm for posets with positive Tits form, Algebra and Discrete Math. 2016;22:240-261. URL http://mi.mathnet.ru/adm586.
• [22] Kasjan S. and Mróz A. Experiences in symbolic computations for matrix problems, in: Symbolic and Numeric Algorithms for Scientic Computing (SYNASC 2012), Timisoara, IEEE Computer Society, IEEE CPS, Los Alamitos, Calif. [etc.], 2012, pp. 39–44. doi:10.1109/SYNASC.2012.9.
• [23] Kasjan S. and Simson D. Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems, Fund. Inform. 2015;139(2):153–184. doi:10.3233/FI-2015-1230.
• [24] Kasjan S. and Simson D. Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, II. Application to Coxeter spectral analysis, Fund. Inform. 2015;139(2):185–209. doi:10.3233/FI-2012-1231.
• [25] Kasjan S. and Simson D. Algorithms for isotropy groups of Cox-regular edge-bipartite graphs, Fund. Inform. 2015;139:249-275. doi:10.3233/FI-2012-1234.
• [26] Kosakowska J. and Simson D. Hereditary coalgebras and representations of species, J. Algebra 2005;293:457–505.
• [27] Kosakowska J. Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform. 2012;119(2):149–162. doi:10.3233/FI-2012-731.
• [28] Lenzing H. and de la Peña JA. Spectral analysis of finite dimensional algebras and singularities, in: Trends in representation theory of algebras and related topics, ICRA XII, (ed. A. Skowroński), EMS Ser. Congr. Rep., Eur. Math. Soc., Zürich, 2008, pp. 541–588, doi:10.4171/062-1/13.
• [29] Marczak G. Polak A. and Simson D. P-critical integral quadratic forms and positive unit forms. An algorithmic approach, Linear Algebra Appl. 2010;433(11-12):1873–1888. doi:10.1016/j.laa. 2010.06.052.
• [30] Mróz A. On the computational complexity of Bongartz0s algorithm. Fund. Inform. 2013;123(3):317–329. doi:10.3233/FI-2013-813.
• [31] Mróz A. Coxeter energy of graphs, Linear Algebra Appl. 2016;506:279–307. doi:10.1016/j.laa.2016.05.037.
• [32] Mróz A. Congruences of edge-bipartite graphs with applications to Grothendieck group recognition I. Inflation algorithm revisited, Fund. Inform. 2016;146(2):121–144. doi:10.3233/FI-2016-1377.
• [33] Mróz A. Congruences of edge-bipartite graphs with applications to Grothendieck group recognition II. Coxeter type study, Fund. Inform. 2016;146(2):145–177. doi:10.3233/FI-2016-1378.
• [34] Mróz A. Effective nondeterministic positive definiteness test for unidiagonal integral matrices, in: Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016, IEEE CPS, Los Alamitos, Calif. [etc.], 2016, pp. 65–71. doi:10.1109/SYNASC.2016.023.
• [35] Mróz A, and de la Peña JA. Tubes in derived categories and cyclotomic factors of the Coxeter polynomial of an algebra, J. Algebra 2014;420:242–260. doi:10.1016/j.jalgebra.2014.08.017.
• [36] Mróz A, and de la Peña JA. Periodicity in bilinear lattices and the Coxeter formalism, Linear Algebra Appl. 2016;493:227–260. doi:10.1016/j.laa.2015.11.021.
• [37] Mróz A. and Zwara G. Combinatorial algorithms computing degenerations of modules of finite dimension. Fund. Inform. 2014;132(4):519–532. doi:10.3233/FI-2014-1057.
• [38] Nowak S. and Simson D. Locally Dynkin quivers and hereditary coalgebras whose left comodules are direct sums of finite dimensional comodules, Comm. Algebra, 2002;30:405–476.
• [39] Ovsienko SA. Integral weakly positive forms, in Schur Matrix Problems and Quadratic Forms, Inst. Mat. Akad. Nauk USSR, 1978, pp. 3–17, Preprint 78.25 (in Russian).
• [40] de la Peña JA. Algebras whose Coxeter polynomials are products of cyclotomic polynomials, Algebras and Repr. Theory, 2014;17(3): 905–930. doi:10.1007/s10468-013-9424-0.
• [41] de la Peña JA. On the Mahler measure of the Coxeter polynomial of algebra, Adv. Math. 2015;270:375–399. doi:10.1016/j.aim.2014.10.021.
• [42] Peng L. Intersection matrix Lie algebras and Ringel-Hall Lie algebras of tilted algebras, in "Representations of Algebras" ICRA-9, Vol. I (eds. D. Happel and Y. B. Zhang), Beiging Normal University Press, 2002, pp.98–108.
• [43] Simson D. Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets, Linear Algebra Appl. 2010;433(4):699–717. doi:10.1016/j.laa. 2010.03.04.
• [44] Simson D. Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fund. Inform. 2011;109(4):425–462. doi:10.3233/FI-2011-603.
• [45] Simson D. Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra 2011; 215(1):13–34. doi:10.1016/j.jpaa. 2010.02.029.
• [46] Simson D. A Coxeter-Gram classification of simply laced edge-bipartite graphs, SIAM J. Discr. Math. 2013;27(2):827–854. doi:10.1137/110843721.
• [47] Simson D. Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 2013;123(4):447–490. doi:10.3233/FI-2013-820.
• [48] Simson D. A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits, Fund. Inform. 2013;124(3):309–338. doi:10.3233/FI-2013-836.
• [49] Simson D. Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, I. Gram classification, Fund. Inform. 2016;145(1):19–48. doi:10.3233/FI-2016-1345.
• [50] Simson D. Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, II. Isotropy mini-groups, Fund. Inform. 2016;145(1):49–80. doi:10.3233/FI-2016-1346.
• [51] Simson D and Skowroński A. Elements of the Representation Theory of Associative Algebras. Volume 2. Tubes and Concealed Algebras of Euclidean type, London Math. Soc. Student Texts, Volume 71, Cambridge Univ. Press, Cambridge New York, 2007. URL https://doi.org/10.1017/CBO9780511619212.
• [52] D. Simson and K. Zając, Inflation algorithm for loop-free non-negative edge-bipartite graphs of corank at least two. Linear Algebra Appl. 2017;524:109-152, doi:10.1016/j.laa.2017.02.021.
• [53] Slodowy P. Beyond Kac-Moody Lie algebras, and inside, Canad. Math. Soc. Conf. Proc. 1988;5:361-371.
• [54] Zając K. Numeric algorithms for corank two edge-bipartite graphs and theirmesh geometries of roots. Fund. Inform. 2017;152:185–222. doi:10.3233/FI-2017-1518.
• [55] Zaslavsky T. Signed graphs, Discrete Appl. Math. 1982;4:47–74. URL http://dx.doi.org/10.1016/0166-218X(82)90033-6.
• [56] Zhang Y. Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 1989;17(10):2347–2362. URL http://dx.doi.org/10.1080/00927878908823853.