Congruences of Edge-bipartite Graphs with Applications to Grothendieck Group Recognition. [Part 1], Inflation Algorithm Revisited

• Autorzy: Mróz A.

Identyfikatory

DOI

10.3233/FI-2016-1377

• Języki publikacji: EN

Abstrakty

EN

We study edge-bipartite graphs (bigraphs), a class of signed graphs, by means of the inflation algorithm which relies on performing certain elementary transformations on a given bigraph Δ, or equivalently, on the associated integral quadratic form q_Δ: Zⁿ → Z, preserving Gram Z-congruence. The ideas are inspired by classical results of Ovsienko and recent studies of Simson started in [SIAM J. Discr. Math. 27 (2013), 827-854], concerning classifications of integral quadratic and bilinear forms, and their Coxeter spectral analysis. We provide few modifications of the inflation algorithm and new estimations of its complexity for positive and principal loop-free bigraphs. We discuss in a systematic way the behavior and computational aspects of inflation techniques. As one of the consequences we obtain relatively simple proofs of several interesting properties of quadratic forms and their roots, extending known facts. On the other hand, the results are a first step of a solution of a variant of Grothendieck group recognition, a difficult combinatorial problem arising in representation theory of finite dimensional algebras and their derived categories, which we discuss in Part II of this two parts article with the same main title.

Słowa kluczowe

EN

congruences; grothendieck groups; bipartite graphs; algorithms; inflation; quadratic forms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 2
• Strony: 121--144
• Opis fizyczny: Bibliogr. 47 poz., rys., tab.

Twórcy

autor

Mróz A.

• Centro de Investigación en Matemáticas, A.C., Jalisco S/N, Col. Valenciana CP: 36023 Guanajuato, Gto, Mexico
• Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [1] Simson D. A Coxeter-Gram classification of positive simply laced edge-bipartite graphs. SIAM J Discrete Math. 2013;27(2):827–854. doi:10.1137/110843721.
• [2] Kasjan S, 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.
• [3] Barot M, de la Peña JA. The Dynkin type of a non-negative unit form. Expo Math. 1999;17:339–348.
• [4] Ovsienko SA. Integral weakly positive forms. In: Schur Matrix Problems and Quadratic Forms. vol. 78.25. Inst. Mat. Akad. Nauk USSR, Kiev; 1978. p. 3–17. (in Russian).
• [5] Barot M. A characterization of positive unit forms. Bol Soc Mat Mexicana. 1999;5(3):87–93.
• [6] Barot M. A characterization of positive unit forms. II. Bol Soc Mat Mexicana. 2001;7(3):13–22.
• [7] von Höhne HJ. On weakly positive unit forms. Comment Math Helv. 1988;63:312–336.
• [8] von Höhne HJ, de la Peña JA. Isotropic vectors of non-negative integral quadratic forms. Eur J Combin. 1998;19(5):621–638. doi:10.1006/eujc.1998.0217.
• [9] Dräxler P, Drozd YA, Golovachtchuk NS, Ovsienko SA, Zeldych M. Towards the classification of sincere weakly positive unit forms. Eur J Combin. 1995;16(1):1–16. doi:10.1016/0195-6698(95)90084-5.
• [10] 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.
• [11] Zając K. Numeric algorithms for corank-two edge-bipartite graphs and their mesh geometries of roots. Fund Inform. 2016; In press.
• [12] Kasjan S, 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-2015-1231.
• [13] Kasjan S, Simson D. Algorithms for isotropy groups of Cox-regular edge-bipartite graphs. Fund Inform. 2015;139(3):249–275. doi:10.3233/FI-2015-1234.
• [14] Gąsiorek M, Simson D, Zając K. Structure and a Coxeter-Dynkin type classification of corank two nonnegative posets. Linear Algebra Appl. 2015;469:76–113. doi: 10.1016/j.laa.2014.11.003.
• [15] Gąsiorek M, Simson D, Zając K. On Coxeter type study of non-negative posets using matrix morsifications and isotropy groups of Dynkin and Euclidean diagrams. Eur J Combin. 2015;48:127–142. doi:10.1016/j.ejc.2015.02.015.
• [16] Bondarenko VM, Stepochkina MV. Description of posets critical with respect to the nonnegativity of the quadratic Tits form. Ukr Math J+. 2009;61(5):611–624. doi:10.1007/s11253-009-0245-6.
• [17] Drozd YA. Coxeter transformations and representations of partially ordered sets. Funkc Anal i Priložen. 1974;8:34–42. (in Russian).
• [18] 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-520.
• [19] 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.
• [20] Simson D. Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4. Fund Inform. 2013;124(3):339–364. doi:10.3233/FI-2013-837.
• [21] Simson D. Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, I. A Gram classification. Fund Inform. 2016;145(1):19–48. doi:10.3233/FI-2016-1345.
• [22] Mróz A. Congruences of edge-bipartite graphs with applications to Grothendieck group recognition II. Coxeter type study. Fund Inform. 2016;This issue.
• [23] de la Peña JA. Coxeter transformations and the representation theory of algebras. In: Finite Dimensional Algebras and Related Topics, NATO ASI Series C: Mathematical and Physical Sciences. vol. 424. Kluwer Academic Publishers, Dordrecht; 1994. p. 223–253.
• [24] Lenzing H. Coxeter transformations associated with finite dimensional algebras. In: Computational Methods for Representations of Groups and Algebras. Progress in Mathematics. vol. 173. Birkhäser-Verlag, Basel-Boston; 1999. p. 287–308.
• [25] Lenzing H, de la Peña JA. Spectral analysis of finite dimensional algebras and singularities. In: Trends in Representation Theory of Algebras and Related Topics, ed. A. Skowroński. EMS Publishing House, Zürich; 2008. p. 541–588.
• [26] Lenzing H. A K-theoretical study of canonical algebras. In: Representations of algebras, Seventh International Conference, Cocoyoc (Mexico) 1994 (eds R. Bautista et al.), CMS Conference Proceedings. vol. 18. American Mathematical Society, Providence, R.I.; 1996. p. 433–454.
• [27] Mróz A. Coxeter energy of graphs. Linear Algebra Appl. 2016;506:279–307. doi:10.1016/j.laa.2016.05.037.
• [28] Mróz A, 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.
• [29] Mróz A, 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.
• [30] 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.
• [31] Happel D, Seidel U. Piecewise hereditary Nakayama algebras. Algebr Represent Theory. 2010;13(6):693–704. doi:10.1007/s10468-009-9169-y.
• [32] Dowbor P, Meltzer H, Mróz A. An algorithm for the construction of exceptional modules over tubular canonical algebras. J Algebra. 2010;323(10):2710–2734. doi:10.1016/j.jalgebra.2009.12.027.
• [33] Dowbor P, Meltzer H, Mróz A. Parametrizations for integral slope homogeneous modules over tubular canonical algebras. Algebr Represent Theory. 2014;17(1):321–356. doi:10.1007/s10468-012-9386-7.
• [34] Dowbor P, Meltzer H, Mróz A. An algorithm for the construction of parametrizing bimodules for homogeneous modules over tubular canonical algebras. Algebr Represent Theory. 2014;17(1):357–405. doi:10.1007/s10468-013-9430-2.
• [35] Dowbor P, Mróz A. On the normal forms of modules with respect to parametrizing bimodules. J Algebra. 2014;402:219–257. doi:10.1016/j.jalgebra.2013.12.001.
• [36] Grzecza M, Kasjan S, Mróz A. Tree matrices and a matrix reduction algorithm of Belitskii. Fund Inform. 2012;118(3):253–279. doi:10.3233/FI-2012-713.
• [37] Kasjan S, Mróz A. Experiences in symbolic computations for matrix problems. In: 14th International Symposium on Symbolic and Numeric Algorithms for Scientic Computing (SYNASC 2012), Timisoara, Romania, 26-29 September 2012, Proceedings. IEEE Computer Society; 2012. p. 39–44. doi:10.1109/SYNASC.2012.9.
• [38] Mróz A. On the multiplicity problem and the isomorphism problem for the four subspace algebra. Comm Algebra. 2012;40(6):2005–2036. doi:10.1080/00927872.2011.570830.
• [39] Mróz A. On the computational complexity of Bongartz’s algorithm. Fund Inform. 2013;123(3):317–329. doi:10.3233/FI-2013-813.
• [40] Mróz A, Zwara G. Combinatorial algorithms for computing degenerations of modules of finite dimension. Fund Inform. 2014;132(4):519–532. doi:10.3233/FI-2014-1057.
• [41] Assem I, Simson D, Skowroński A. Elements of the Representation Theory of Associative Algebras, 1: Techniques of Representation Theory. vol. 65 of London Math. Soc. Student Texts. Cambridge Univ. Press, Cambridge - New York; 2006.
• [42] Ringel CM. Tame algebras and integral quadratic forms. vol. 1099 of Lecture Notes in Math. Springer-Verlag, Berlin, Heidelberg, New York, Tokyo; 1984.
• [43] 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.
• [44] Meyer CD. Matrix Analysis and Applied Linear Algebra. Philadelphia, SIAM; 2000.
• [45] Gąsiorek M, Simson D, Zając K. A Gram classification of non-negative corank-two loop-free edge-bipartite graphs. Linear Algebra Appl. 2016;500:88–118. doi:10.1016/j.laa.2016.03.007.
• [46] Humphreys JE. Introduction to Lie Algebras and Representation Theory. Springer-Verlag, New York, Heidelberg, Berlin; 1980. Third Printing, Revised.
• [47] Mróz A. Bigraph Congruences; 2015. Maple packages. http://www.mat.umk.pl/~amroz/projects/BigraphCongruences.zip.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).

Dedicated to Professor Piotr Dowbor on the occasion of his 60th birthday.