A Framework for Coxeter Spectral Analysis of Edge-bipartite Graphs, their Rational Morsifications and Mesh Geometries of Root Orbits

• Autorzy: Simson D.
• Języki publikacji: EN

Abstrakty

EN

Following the spectral Coxeter analysis of matrix morsifications for Dynkin diagrams, the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we continue our study of the category UBigrn of loop-free edge-bipartite (signed) graphs ∆, with n > 2 vertices, by means of the Coxeter number oa, the Coxeter spectrum specc_∆ of ∆, that is, the spectrum of the Coxeter polynomial cox_∆(t) ∈ Z[t] and the Z-bilinear Gram form b_∆ : Zⁿ x Zⁿ →Z of ∆ [SIAM J. Discrete Math. 27(2013)]. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. We show that the Coxeter spectral classification of connected edge-bipartite graphs A in UBigrn reduces to the Coxeter spectral classification of rational matrix morsifications A ∈ Mor_D∆ for a simply-laced Dynkin diagram D∆ associated with ∆. Given ∆ in UBigr_n, we study the isotropy subgroup Gl(n, Z)_∆ of Gl(n, Z) that contains the Weyl group W∆. and acts on the set Mor_∆ of rational matrix morsifications A of ∆ in such a way that the map A → (specc_A, det A, c_∆) is Gl(n, Z)_∆-invariant. It is shown that, for n < 6, specc_∆ is the spectrum of one of the Coxeter polynomials listed in Tables 3.11-3.11(a) (we determine them by computer search using symbolic and numeric computation). The question, if two connected positive edge-bipartite graphs ∆, ∆' in UBigr_n, with specc_∆= specc_∆,, are Z-bilinear equivalent, is studied in the paper. The problem if any Z-invertible matrix A ∈ M_n(Z) is Z-congruent with its transpose Atr is also discussed.

Słowa kluczowe

EN

Coxeter spectrum; Dynkin diagram; edge-bipartite graph; inflation algorithm; matrix morsification; mesh geometry of root orbits; sand-glass tube; toroidal mesh algorithm; Weyl group

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 3
• Strony: 309--338
• Opis fizyczny: Bibliogr. 62 poz., wykr.

Twórcy

autor

Simson D.

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

Bibliografia

• [1] I. Assem, D. Simson and A. Skowronski, 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] K.T. Balinska and S.K Simic, The nonregular, bipartite, integral graphs with maximum degree four, Discrete Math. 236(2001), 13-24.
• [3] M. Barot, A characterization of positive unit forms, II, Bol. Soc. Mat. Mexicana (3) 7(2001), 13-22.
• [4] M. Barot and J.A. de la Pena, The Dynkin type of a non-negative unit form, Expo. Math. 17(1999), 339-348. 
• [5] R. Bautista and D. Simson, Torsionless modules over 1-Gorenstein ^-hereditary artinian rings, Comm. Algebra 12 (1984), 899-936.
• [6] G. Belitskii and V. V. Sergeichuk, Complexity of matrix problems, Linear Algebra Appl. 361(2003), 203-222.
• [7] I. N. Bernstein, I. M. Gelfand and V. A. Ponomarev, Coxeter functors and Gabriel’s theorem, Uspiehi Mat. Nauk, 28(1973), 19-33. (in Russian); English translation in Russian Math. Surveys, 28(1973), 17-32.
• [8] V. M. Bondarenko, Minimax isomorphism algorithm and primitive posets, Algebra and Discrete Math. 12(2011), no. 2,31-37.
• [9] V. M. Bondarenko and M. V. Stepochkina, On posets of width two with positive Tits form, Algebra and Discrete Math. 2(2005), no. 2, 20-35.
• [10] V. M. Bondarenko and M. V. Stepochkina, On finite posets of inj-finite type and their Tits form, Algebra and Discrete Math. 2(2006), 17-21.
• [11] R.A. Brualdi and D. M. Cvetkovic, A Combinatorial Approach to Matrix Theory and its Application, CRS Press (Boca Raton), 2008.
• [12] D. M. Cvetkovic, P. Rowlinson and S. Simic, An Introduction to the Theory of Graph Spectra, London Math. Soc. Student Texts 75, Cambridge Univ. Press, Cambridge-New York, 2010.
• [13] M. DeVos, J. Ebrahimi, M. Ghebleh, L. Goddyn, B. Mohar, R. Neserasr, Circular coloring the plane, SIAM J. Discrete Math. 21(2007), 461-465 (electronic).
• [14] P. Dowbor and D. Simson, Quasi-Artin species and rings of finite representation type, J. Algebra 63 (1980), 435-443.
• [15] P. Draxler, J. A. Drozd, N. S. Golovachtchuk, S. A. Ovsienko, M. Zeldych, Towards the classification of sincere weakly positive unit forms, Europ. J. Comb. 16 (1995), 1-16.
• [16] J. A. Drozd, Coxeter transformations and representations of partially ordered sets, Funkc. Anal. i Prilozen. 8(1974), 34-42 (in Russian).
• [17] J. A. Drozd and V. V. Kirichenko, Finite Dimensional Algebras, Springer-Verlag, Berlin, 1994.
• [18] Z. Dvorak and B. Mohar, Spectral radius of finite and infinite planar graphs and graphs of bounded genus, J. Comb. Theory, Ser. B, 100(2010), 729-739.
• [19] M. Felisiak, Computer algebra technique for Coxeter spectral study of edge-bipartite graphs and matrix modifications of Dynkin type An, Fund. Inform. 2013, to appear.
• [20] M. Felisiak and D. Simson, Experiences in computing mesh root systems for Dynkin diagrams using Maple and C++, Proc. 13th Intern. Symposium on Symbolic and Numeric Algorithms, SYNASC11, Timisoara, 2011, IEEE Post-Conference Proceedings, IEEE CPS Computer Society, IEEE CPS, Tokyo, 2011, pp. 83-86.
• [21] M. Felisiak and D. Simson, On computing mesh root systems and the isotropy group for simply-laced Dynkin diagrams, Proc. 14th Intern. Symposium on Symbolic and Numeric Algorithms, SYNASC12, Timisoara, 2012, IEEE Post-Conference Proceedings, IEEE CPS Computer Society, IEEE CPS, Tokyo, 2012, pp. 91-97.
• [22] M. Felisiak and D. Simson, On combinatorial algorithms computing mesh root systems and matrix modifications for the Dynkin diagram An, Discrete Math. 313(2013), 1358-1367, doi: 10.1016.disc.2013.02.003.
• [23] M. Gasiorek 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.
• [24] M. Gasiorek and D. Simson, A computation of positive one-peak posets that are Tits-sincere, Colloq. Math. 127(2012), 83-103, DOI: 10.4064//cm127-1-6.
• [25] P. Gabriel and A. V. Roiter, Representations ofFinite Dimensional Algebras, Algebra VIII, Encyclopaedia of Math. Sc., Vol. 73, Springer-Verlag, Berlin, Heidelberg, New York, 1992.
• [26] M. Grzecza, S. Kasjan and A. Mroz, Tree matrices and a matrix reduction algorithm of Belitskii, Fund. Inform. 117(2012), 253-279, doi: 10.3233/FI-2012-713.
• [27] Y. Han and D. Zhao, Superspecies and their representations, J. Algebra 321(2009), 3668-3680.
• [28] R.A. Horn and V. V. Sergeichuk, Congruences of a square matrix and its transpose, Linear Algebra Appl. 389(2004), 347-353.
• [29] H.-J. von Hohne, On weakly positive unit forms, Comment Math. Helvetici 63(1988), 312-336.
• [30] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics 29, Cambridge Univ. Press, 1990.
• [31] S. Kasjan and D. Simson, Tame prinjective type and Tits form of two-peak posets, I, J. Pure Appl. Algebra 106(1996), 307-330;
• [32] S. Kasjan and D. Simson, Tame prinjective type and Tits form of two-peak posets, II, J. Algebra 187 (1997), 71-96.
• [33] K. Kawarabayashi and B. Mohar, Star coloring and acyclic coloring of locally planar graphs, SIAM J. Discrete Math. 24( 2010), 56-71.
• [34] A. Kisielewicz and M. Szykuła, Rainbow induced subgraphs in proper vertex colorings, Fund. Inform. 111(2011), 437-451, doi: 10.3233/FI-2011-572.
• [35] 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.
• [36] P. Lakatos, Additive functions on trees, Colloq. Math. 89(2001), 135-145.
• [37] H. Lenzing and J.A de la Pena, Spectral analysis of finite dimensional algebras and singularities, In: Trends in Representation Theory of Algebras and Related Topics, ICRA XII, (ed. A. Skowroriski), Series of Congress Reports, European Math. Soc. Publishing House, Zurich, 2008, pp. 541-588.
• [38] P. Leszczyliski and K. Stencel, Update propagator for joint scalable storage, Fund. Inform. 119(2012), 337355, doi: 10.3233//FI-2012-741.
• [39] 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.
• [40] A. Mroz, On the computational complexity of Bongartz's algorithm, Fund. Inform. 123(2013), 317-329.
• [41] 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.
• [42] Pu Zhang and C. Xiao-Wu, Comodules of Uq(sl2) and modules of SLq(2) via quiver methods, J. Pure Appl. Algebra 211(2007), 862-876.
• [43] A. Polak and D. Simson, One-peak posets with almost P-critical Tits form and a spectral Coxeter classification using computer algebra tools, Europ. J. Comb. 2013, to appear.
• [44] 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.
• [45] V. V. Sergeichuk, Canonical matrices for linear matrix problems, Linear Algebra Appl. 317(2000), 53-102.
• [46] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space Categories, Algebra, Logic and Applications, Vol. 4, Gordon & Breach Science Publishers, 1992.
• [47] D. Simson, A reduction functor, tameness and Tits form for a class of orders, J. Algebra 174(1995), 430-452.
• [48] D. Simson, On Corner type Endo-Wild algebras, J. Pure Appl. Algebra 202 (2005), 118-132.
• [49] D. Simson, Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories, Colloq. Math. 115(2009), 259-295.
• [50] 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.
• [51] 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.
• [52] 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.
• [53] 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.
• [54] D. Simson, A Coxeter-Gram classification of simply-laced edge-bipartite graphs, SIAM J. Discrite Math. 27(2013), in press.
• [55] D. Simson, Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4, Fund. Inform. 124(2013), 89-114, doi 10.3233I-2013-836.
• [56] D. Simson and A. Skowromki, 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.
• [57] D. Simson and M. Wojewodzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83(2008), 389-410.
• [58] D. Simson and K. Zajac, An inflation algorithm and a toroidal mesh algorithm for edge-bipartite graphs, Electronic Notes in Discrete Mathematics, 2013, 6 pp. in press.
• [59] K. Szymiczek, Bilinear Algebra: An Introduction to the Algebraic Theory of Quadratic Forms, Algebra, Logic and Applications, Vol. 7, Gordon & Breach Science Publishers, 1997.
• [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] http://www.gap-system.org/Gap3/gap3.html