A Graph Theoretical Framework for the Strong Gram Classification of Non-negative Unit Forms of Dynkin Type 𝔸 n

• Autorzy: González Jiménez , Arturo Jesús

Identyfikatory

DOI

10.3233/FI-2021-2092

• Języki publikacji: EN

Abstrakty

EN

In the context of signed line graphs, this article introduces a modified inflation technique to study strong Gram congruence of non-negative (integral quadratic) unit forms, and uses it to show that weak and strong Gram congruence coincide among positive unit forms of Dynkin type An . The concept of inverse of a quiver is also introduced, and is used to obtain and analyze the Coxeter matrix of non-negative unit forms of Dynkin type An . With these tools, connected principal unit forms of Dynkin type An are also classified up to strong congruence.

Słowa kluczowe

EN

Integral quadratic form; Gram congruence; quiver; Dynkin type; Coxeter matrix; edge-bipartite graph; signed line graph

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 1
• Strony: 49--82
• Opis fizyczny: Bibliogr. 38 poz., rys.

Twórcy

autor

González Jiménez

• Instituto de Matemáticas, UNAM, Mexico

autor

Arturo Jesús

• Instituto de Matemáticas, UNAM, Mexico

Bibliografia

• [1] Aigner M. On the Linegraph of a Directed Graph, Math. Zeitschr. 1967. 102:56-61. doi:10.1007/BF01110285.
• [2] Barot M. A characterization of positive unit forms, Bol. Soc. Mat. Mexicana 1999. 5(1):87-93. ISSN:1405-213X, ID:124439229.
• [3] 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.
• [4] Barot M, Jiménez González JA, and de la Peña JA. Quadratic Forms: Combinatorics and Numerical Results, Algebra and Applications, Vol. 25 Springer Nature Switzerland AG 2018. ISBN-13:978-3030056261, 10:3030056260.
• [5] Barot M, and de la Peña JA. The Dynkin type of a non-negative unit form, Expo. Math. 1999. 17:339-348.
• [6] Barot M, and de la Peña JA. Root-induced integral quadratic forms, Linear Algebra Appl. 2006. 412(2):291-302. doi:10.1016/j.laa.2005.06.030.
• [7] Belardo F, Li Marzi EM, and Simi´c SK. Signed line graphs with least eigenvalue ´2: The star complement technique, Discrete Applied Mathematics 2016. 207:29-38. doi:10.1016/j.dam.2016.02.018.
• [8] Cameron PJ, Goethals JM, Seidel JJ, and Shult EE. Line graphs, Root Systems, and Elliptic Geometry, J. Algebra 1976. 43(1):305-327. doi:10.1016/0021-8693(76)90162-9.
• [9] Cavaleri M, D’Angelo D, and Donno A. Characterizations of line graphs in signed and gain graphs. 2021. arXiv:2101.09677v2 [math.CO]
• [10] Cvetkovi´c D, Rowlinson P, and Simi´c S. Spectral Generalizations of Line Graphs, On graphs with least eigenvalue ´2, Cambridge University Press, 2004. ISBN:9780511751752. doi:10.1017/CBO9780511751752.
• [11] Gąsiorek M, Simson D, and Zając K. Algorithmic computation of principal posets using Maple and Python. Algebra and Discrete Math. 2014. 17(1):33-69. URL http://dspace.nbuv.gov.ua/handle/123456789/152339.
• [12] Geller D, and Harary F. Arrow diagrams are line diagrams, SIAM J. Appl. Math., 1968. 16(6):1141-1145. URL https://www.jstor.org/stable/2099532.
• [13] Harary F, and Norman RZ. Some properties of line digraphs, Rend. Circ. Mat. Palermo 1961. 9:161-168. doi:10.1007/BF02854581.
• [14] Jiménez González JA. Incidence graphs and non-negative integral quadratic forms. Journal of Algebra 2018. 513:208-245. doi:10.1016/j.jalgebra.2018.07.020.
• [15] Jiménez González JA. Coxeter invariants for non-negative unit forms of Dynkin type An. 2020. arXiv:2010.09991v1 [math.CO].
• [16] Kosakowska J. Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform. 2012. 119(2):149-162, doi.org/10.3233/FI-2012-731.
• [17] Makuracki B, and Mróz A. Root systems and inflations of non-negative quasi-Cartan matrices, Linear Algebra Appl. 2019. 580:128-165. doi:10.1016/j.laa.2019.06.006.
• [18] Makuracki B, and Simson D. A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm, Discrete Appl. Math. 2019. 253:25-36. doi:10.1016/j.dam.2017.10.033.
• [19] Meyer CD. Matrix Analysis and Applied Linear Algebra. Philadelphia, SIAM, 2000. ISBN:9780898714548. doi:10.1137/1.9780898719512.
• [20] Ovsienko SA. Integral weakly positive forms, in: Schur Matrix Problems and Quadratic Forms (Russian), in: Inst. Mat. Akad. Nauk USSR, Preprint 78.25, 1978 pp. 3-17.
• [21] 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.
• [22] Simson D. Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebras 2011. 215(1):13-34. doi:10.1016/j.jpaa.2010.02.029.
• [23] 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.
• [24] Simson D. Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 2013. 123:447-490.
• [25] 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.
• [26] 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.
• [27] 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.
• [28] Simson D. A Coxeter spectral classification of positive edge-bipartite graphs I. Dynkin types Bn, Cn, F4, G2, E6, E7, E8. Linear Algebra Appl. 2018. 557:105-133. doi:10.1016/J.LAA.2018.07.013.
• [29] Simson D. A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices. Linear Algebra Appl., 2020. 586(3):190-238. doi:10.1016/j.laa.2019.10.015.
• [30] Simson D. A Coxeter spectral classification of positive edge-bipartite graphs II. Dynkin type Dn. Linear Algebra and its Applications 2021. 612:223-272. doi:10.1016/j.laa.2020.11.001.
• [31] Simson D. Weyl orbits of matrix morsifications and a Coxeter spectral classification of positive signed graphs and quasi-Cartan matrices of Dynkin type An. Preprint.
• [32] Simson D, and Zaj ˛ac K. 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.
• [33] von Höhne H-J. On weakly positive unit forms, Comment. Math. Helvetici 1988. 63:312-336. doi:10.1007/BF02566771.
• [34] Zaslavsky T. The geometry of root systems and signed graphs, Amer. Math. Monthly 1981. 88(2):88-105. doi:10.2307/2321133.
• [35] Zaslavsky T. Signed graphs, Discrete Applied Mathematics. North-Holland Publishing Company 1982. 4(1):47-74. doi:10.1016/0166-218X(82)90033-6.
• [36] Zaslavsky T. Line graphs of switching classes, Report of the XVIIIth O.S.U. Denison Maths Conference (Granville, Ohio, 1984), pp. 2-4. Dept. of Math., Ohio State Univ., Columbus, Ohio, 1984.
• [37] Zaslavsky T. Matrices in the theory of signed simple graphs, in: Advances in Discrete Mathematics and Applications: Mysore, 2008, in Ramanujan Math. Soc. Lect. Notes Ser., Vol. 13, Ramanujan Math. Soc., Mysore, 2010, pp. 207-229.
• [38] Zhang F. Matrix Theory: Basic Results and Techniques, 2nd Ed. Springer 1999. ISBN:978-1-4757-5797-2.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)