Graph Theoretical and Algorithmic Characterizations of Positive Definite Symmetric Quasi-Cartan Matrices

• Autorzy: Abarca M. , Rivera D.

Identyfikatory

DOI

10.3233/FI-2016-1448

• Języki publikacji: EN

Abstrakty

EN

A well known constructive proof for the ADE-classification of many mathematical objects, such as positive unit forms and their associated quasi-Cartan matrices, has lead to an Inflations Algorithm. However, this algorithm is not known to run in polynomial time. In this paper we use a so called flation transformation and show how its invariants can be used to characterize the Dynkin types A and D in the language of graph theory. Also, a polynomial-time algorithm for computing the Dynkin type is suggested.

Słowa kluczowe

EN

positive unit form; Dynkin-type; edge-bipartite graphs; combinatorial algorithms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 3
• Strony: 241--261
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Abarca M.

• Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

autor

Rivera D.

• Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

Bibliografia

• [1] Knapp AW. Lie Groups Beyond an Introduction. vol. 140 of Progress in Mathematics. 2nd ed. Birkhäuser; 2002. Available from: http://www.springer.com/book/978-0-8176-4259-4.
• [2] Barot M, Geiss C, Zelevinsky A. Cluster algebras of finite type and positive symmetrizable matrices. Journal of the London Mathematical Society. 2006;73(3):545–564. Available from: http://dx.doi.org/10.1112/S0024610706022769.
• [3] Barot M, Rivera D. Generalized Serre relations for Lie algebras associated with positive unit forms. Journal of Pure and Applied Algebra. 2007; 211:360–373. Available from: http://dx.doi.org/10.1016/j.jpaa.2007.01.008.
• [4] Ovsienko SA. Integer weakly positive forms. Schurian Matrix problems and quadratic forms. 1978; p. 3–17.
• [5] Ringel CM. Tame Algebras and Integral Quadratic Forms. vol. 1099 of Lecture Notes in Mathematics. Springer-Verlag Berlin Heidelberg; 1984. doi:10.1007/BFb0072870.
• [6] Gabriel P, Roiter AV. Representations of Finite-Dimensional Algebras. vol. 73 of Encyclopaedia of Mathematical Sciences. Springer; 1997. Available from: http://www.springer.com/book/978-3-540-53732-8.
• [7] Kosakowska J. Inflation Algorithms for Positive and Principal Edge-bipartite Graphs and Unit Quadratic Forms. Fundamenta Informaticae. 2012; 119(2):149–162. Available from: http://content.iospress.com/articles/fundamenta-informaticae/fi119-2-02.
• [8] Barot M. A characterization of positive unit forms. Boletín de la Sociedad Matemática Mexicana. 1999; 5:87–94.
• [9] Multiset. Encyclopedia of Mathematics; Available from: http://www.encyclopediaofmath.org/index.php?title=Multiset&oldid=37512.
• [10] Bondy A, Murty USR. Graph Theory. vol. 244 of Graduate Texts in Mathematics. Springer; 2008. Available from: http://www.springer.com/book/978-1-84628-969-9.
• [11] Hopcroft J, Tarjan R. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM. 1973; 16(6):372–378. doi:10.1145/362248.362272.
• [12] Barot M. A characterization of positive unit forms, part II. Boletín de la Sociedad Matemática Mexicana. 2001;7:13–22.
• [13] Ovsienko SA. Boundedness of roots of integral weakly positive forms. In: Representations and quadratic forms (Russian). Akad. Nauk Ukrain. SSR, Inst. Mat., Kiev; 1979. p. 106–123, 155.
• [14] Abarca M, Rivera D. Formas Cuadráticas Unitarias de tipo An: Un Enfoque Combinatorio. Programación Matemática y Software. 2014; 6(2):17–25. Available from: http://www.progmat.uaem.mx:8080/vol6nu2ar3.html.
• [15] Strang G. Linear Algebra and Its Applications. Brooks Cole; 2005. ISSN: 0024-3795.
• [16] Bareiss EH. Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation. 1968; 22(103):565–578. Available from: http://www.jstor.org/stable/2004533.
• [17] Yap C. Fundamental Problems in Algorithmic Algebra. Oxford University Press; 2000. Available from: http://cs.nyu.edu/yap/book/berlin/.
• [18] Skiena SS. The algorithm design manual: Text. vol. 1. Springer Science & Business Media; 1998. ISBN: 0387948600, 9780387948607.

Uwagi

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