Congruences of Edge-bipartite Graphs with Applications to Grothendieck Group Recognition. [Part 2], Coxeter Type Study

• Autorzy: Mróz A.

Identyfikatory

DOI

10.3233/FI-2016-1378

• Języki publikacji: EN

Abstrakty

EN

In this two parts article with the same main title we study a problem of Coxeter-Gram spectral analysis of edge-bipartite graphs (bigraphs), a class of signed graphs. We ask for a criterion deciding if a given bigraph Δ is weakly or strongly Gram-congruent with a graph. The problem is inspired by recent works of Simson et al. started in [SIAM J. Discr. Math. 27 (2013), 827-854], and by problems related to integral quadratic forms, bilinear lattices, representation theory of algebras, algebraic methods in graph theory and the isotropy groups of bigraphs. In this Part II we develop general combinatorial techniques, with the use of inflation algorithm discussed in Part I, morsifications and the isotropy group of a bigraph, and we provide a constructive solution of the problem for the class of all positive connected loop-free bigraphs. Moreover, we present an application of our results to Grothendieck group recognition problem: deciding if a given bilinear lattice is the Grothendieck group of some category. Our techniques are tested in a series of experiments for so-called Nakayama bigraphs, illustrating the applications in practice and certain related phenomena. The results show that a computer algebra technique and discrete mathematical computing provide important tools in solving theoretical problems of high complexity.

Słowa kluczowe

EN

bipartite graphs; grothendieck groups; Coxeter graphs; quadratic forms; graph theory; algorithms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 2
• Strony: 145--177
• Opis fizyczny: Bibliogr. 49 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] 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.
• [2] 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.
• [3] 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.
• [4] 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.
• [5] 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.
• [6] 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.
• [7] de la Peña JA. Algebras whose Coxeter polynomials are products of cyclotomic polynomials. Algebr Represent Theory. 2014;17(3):905–930. doi:10.1007/s10468-013-9424-0.
• [8] 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.
• [9] Happel D. Triangulated categories in the representation theory of finite dimensional algebras. vol. 119 of London Mathematical Society LNS. Cambridge University Press; 1988.
• [10] Mróz A. Congruences of edge-bipartite graphs with applications to Grothendieck group recognition I. Inflation algorithm revisited. Fund Inform. 2016;This issue.
• [11] Bocian R, Felisiak M, Simson D. Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups. J Comput Appl Math. 2014;259:815–827. doi:10.1016/j.cam.2013.07.013.
• [12] Felisiak M, Simson D. Applications of matrix morsifications to Coxeter spectral study of loop-free edgebipartite graphs. Discrete Appl Math. 2015;192:49–64. doi:10.1016/j.dam.2014.05.002.
• [13] 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.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] 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.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] 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.
• [24] 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.
• [25] 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.
• [26] 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.
• [27] 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.
• [28] 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.
• [29] 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.
• [30] Barot M, de la Peña JA. The Dynkin type of a non-negative unit form. Expo Math. 1999;17:339–348.
• [31] Drozd YA. Coxeter transformations and representations of partially ordered sets. Funkc Anal i Priložen. 1974;8:34–42. (in Russian).
• [32] 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).
• [33] 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.
• [34] Mróz A. Bigraph Congruences; 2015. Maple packages. http://www.mat.umk.pl/~amroz/projects/BigraphCongruences.zip.
• [35] 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.
• [36] Ringel CM. Tame algebras and integral quadratic forms. vol. 1099 of Lecture Notes in Math. Springer-Verlag, Berlin, Heidelberg, New York, Tokyo; 1984.
• [37] Meyer CD. Matrix Analysis and Applied Linear Algebra. Philadelphia, SIAM; 2000.
• [38] Mróz A. Coxeter energy of graphs. Linear Algebra Appl. 2016;506:279–307. doi:10.1016/j.laa.2016.05.037.
• [39] 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.
• [40] Gąsiorek M. Efficient computation of the isotropy group of a finite graphs: a combinatorial approach. In: 15th International Symposium on Symbolic and Numeric Algorithms for Scientic Computing (SYNASC 2013), Timisoara, Romania, 23-26 September 2013, Proceedings. IEEE Computer Society; 2013. p. 104–111. doi:10.1109/SYNASC.2013.21.
• [41] Gąsiorek M. Obliczenia symboliczne i algorytmy kombinatoryczne w spektralnej klasyfikacji skończonych zbiorów częściowo uporządkowanych; 2016. Ph.D. Thesis. University of Warsaw.
• [42] Happel D, Seidel U. Piecewise hereditary Nakayama algebras. Algebr Represent Theory. 2010;13(6):693–704. doi:10.1007/s10468-009-9169-y.
• [43] Assem I, Skowroński A. Iterated tilted algebras of type Ãn. Math Z. 1987;195:269–290.
• [44] Happel D. Iterated tilted algebras of affine type. Commun Algebra. 1987;15:29–45.
• [45] Happel D. A characterization of hereditary categories with tilting object. Invent Math. 2001;144(2):381–398.
• [46] Geigle W, Lenzing H. A class of weighted projective curves arising in representation theory of finite dimensional algebras. In: Singularities, representations of algebras, and vector bundles. vol. 1273 of Lecture Notes in Math. Springer; 1987. p. 265–297.
• [47] Assem I, Happel D. Generalized tilted algeras of type An. Comm Algebra. 1981;9(20):2101–2125.
• [48] Kussin D, Lenzing H, Meltzer H. Triangle singularities, ADE-chains, and weighted projective lines. Adv Math. 2013;237:194–251. doi:10.1016/j.aim.2013.01.006.
• [49] Zając K. Numeric algorithms for corank-two edge-bipartite graphs and their mesh geometries of roots. Fund Inform. 2016;In press.

Uwagi

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