A Horizontal Mesh Algorithm for a Class of Edge-bipartite Graphs and their Matrix Morsifications

• Autorzy: Kaniecki M. , Kosakowska J. , Malicki P. , Marczak G.

Identyfikatory

DOI

10.3233/FI-2015-1162

• Języki publikacji: EN

Abstrakty

EN

We construct a horizontal mesh algorithm for a study of a special type of mesh root systems of connected positive loop-free edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense of [SIAM J. Discrete Math. 27 (2013), 827–854] and [Fund. Inform. 124 (2013), 309-338]. Given such a loop-free edge-bipartite graph Δ, with the non-symmetric Gram matrix ˇGΔ ∈ M_n(Z) and the Coxeter transformation Φ_A : Zⁿ → Zⁿ defined by a quasi-triangular matrix morsification A ∈ Mn(Z) of Δ satisfying a non-cycle condition, our combinatorial algorithm constructs a Φ_A-mesh root system structure Γ(R_Δ,Φ_A) on the finite set of all Φ_A-orbits of the irreducible root system R_Δ := {v ∈ Zⁿ; v · ˇG_Δ · v^tr = 1}. We apply the algorithm to a graphical construction of a Φ_I - mesh root system structure Γ(R_I ,Φ_I ) on the finite set of ΦI -orbits of roots of any poset I with positive definite Tits quadratic form bqI : Z^I → Z.

Słowa kluczowe

EN

combinatorial algorithm; edge-bipartite graph; Dynkin diagram; root system; mesh translation quiver; quadratic form; Coxeter polynomial

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 4
• Strony: 345--379
• Opis fizyczny: Bibliogr. 45 poz., rys., tab.

Twórcy

autor

Kaniecki M.

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

autor

Kosakowska J.

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

autor

Malicki P.

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

autor

Marczak G.

• 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. Auslander, I. Reiten and S. Smalø, Representation Theory of Artin Algebras, Cambridge Studies in Advanced Mathematics 36, Cambridge University Press, 1995.
• [3] M. Barot, A characterization of positive unit forms, II, Bol. Soc. Mat. Mexicana (3) 7 (2001), 13–22.
• [4] M. Barot, D. Kussin and H. Lenzing, The Lie algebra associated to a unit form, J. Algebra 296 (2007), 1–17.
• [5] M. Barot and J. A. de la Peña, The Dynkin type of a non-negative unit form, Expositiones Mathematicae 17 (1999), 339–348.
• [6] 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.
• [7] K. Bongartz, A criterion for finite representation type, Math. Ann. 269 (1984), 1–12.
• [8] S. Brenner, Unfoldings of algebras, Proc. London Math. Soc. (3) 62 (1991), 242–274.
• [9] P. Dräxler, Yu. A. Drozd, N. S. Golovachtchuk, S. A. Ovsienko and M. Zeldych, Towards the classification of sincere weakly positive unit forms, Europ. J. Combinatorics 16 (1995), 1–16.
• [10] 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.
• [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. 98–101.
• [12] M. Felisiak and D. Simson, On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram n, 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] P. Gabriel and A. V. Roiter, Representations of Finite Dimensional Algebras, in: Algebra VIII, Encyclopaedia of Math. Sci., vol. 73, Springer-Verlag, 1992.
• [15] M. Gąsiorek and D. Simson, One-peak posets with positive Tits quadratic form, their mesh quivers of roots, and programming in Maple and Python, Linear Algebra Appl. 436 (2012), 2240–2272.
• [16] M. Gąsiorek and D. Simson, A computation of positive one-peak posets that are Tits sincere, Colloq. Math. 127 (2012), 83–103.
• [17] M. Grzecza, S. Kasjan and A. Mróz, Tree matrices and a matrix reduction algorithm of Belitskii, Fund. Inform. 117 (2012), 253–279.
• [18] M. Grześkowiak, Algorithms for relatively cyclotomic primes, Fund. Inform. 125 (2013), 161–181.
• [19] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Springer-Verlag, New York-Heilderberg-Berlin, 1972.
• [20] M. Kaniecki, J. Kosakowska, P. Malicki and G. Marczak, An application of a horizontal mesh algorithm to posets, preprint 2014.
• [21] S. Kasjan and J. A. de la Peña, Constructing the preprojective components of an algebra, J. Algebra 179 (1996), 793–807.
• [22] S. Kasjan and D. Simson, A subbimodule reduction, a peak reduction functor and tame prinjective type, Bull. Pol. Acad, Sci. 45 (1997) 89–107,
• [23] S. Kasjan and D. Simson, Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, Fund. Inform. 2015, to appear,
• [24] A. Kisielewicz and M. Szykuła, Rainbow induced subgraphs in proper vertex colorings, Fund. Inform. 111 (2011), 437–451.
• [25] J. Kosakowska, A classification of two-peak sincere posets of finite prinjective type and their sincere prinjective representations, Colloq. Math. 87 (2001), 27–77.
• [26] J. Kosakowska, A specialization of prinjective Ringel-Hall algebra and the associated Lie algebra, Acta Mathematica Sinica, English Series, 24 (2008), 1687–1702.
• [27] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra and Discrete Math. 4 (2008), 49–79.
• [28] J. Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform. 119 (2012), 149–162.
• [29] J. Kosakowska and D. Simson, On Tits form and prinjective representations of posets of finite prinjective type, Comm. Algebra, 26 (1998), 1613–1623.
• [30] H. Lenzing, Coxeter transformations associated with finite dimensional algebras, in: Progress in Math., vol. 173, Birkhäsuer Verlag, Basel, 1999, pp. 287–308.
• [31] A. Mróz, On the computational complexity of Bongartz′s algorithm, Fund. Inform. 123 (2013), 317–329.
• [32] C. M. Ringel, Tame Algebras and Integral Quadratic Forms, Lecture Notes in Math. 1099, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1984.
• [33] M. Sato, Periodic Coxeter matrices and their associated quadratic forms, Linear Algebra Appl. 406 (2005), 99–108.
• [34] D. Simson, Representation types of the category of subprojective representations of a finite poset over K[t]/(tm) and a solution of a Birkhoff type problem, J. Algebra 311(2007), 1–30
• [35] D. Simson, Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories, Colloq. Math. 115 (2009), 259–295.
• [36] D. Simson, Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets, Linear Algebra Appl. 433 (2010), 699–717.
• [37] D. Simson, Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra 215 (2011), 13–34.
• [38] D. Simson, Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fund. Inform. 109 (2011), 425–462.
• [39] D. Simson, Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 123 (2013), 447–490.
• [40] D. Simson, A Coxeter-Gram classification of positive simply laced edge-bipartite graphs, SIAM J. Discrete Math. 27 (2013), 827–854.
• [41] 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.
• [42] D. Simson, Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4, Fund. Inform. 124 (2013), 339–364.
• [43] D. Simson and M.Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83 (2008), 389–410.
• [44] D. Simson and K. Zając, A framework for Coxeter spectral classification of finite posets and their mesh geometries of roots, Intern. J. Math. Mathematical Sciences, Volume 2013, Article ID 743734, 22 pages.
• [45] Y. Zhang, Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 17 (1989), 2347–2362.