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

Article type: Research Article

Authors: Abarca, M. | Rivera, D.^{*; †}

Affiliations: [a] 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. {asma,darivera}@uaem.mx

Correspondence: [*] Address for correspondence: Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos; Av. Universidad 1001, Cuernavaca, Mor. Mexico.

Note: [†] The authors gratefully acknowledge the support of CONACyT (Grant 156667).

Abstract: A well known constructive proof for the 𝔸𝔻𝔼-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 𝔸 and 𝔻 in the language of graph theory. Also, a polynomial-time algorithm for computing the Dynkin type is suggested.

Keywords: Positive unit forms, Dynkin-type, edge-bipartite graphs, combinatorial algorithms

DOI: 10.3233/FI-2016-1448

Journal: Fundamenta Informaticae, vol. 149, no. 3, pp. 241-261, 2016