Inflation Algorithms for Positive and Principal Edge-bipartite Graphs and Unit Quadratic Forms

Article type: Research Article

Authors: Kosakowska, Justyna

Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland, [email protected]

Note: [] Address for correspondence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland Partially supported by Grant UMK 403-M

Abstract: We describe combinatorial algorithms that compute the Dynkin type (resp. Euclidean type) of any positive (resp. principal) unit quadratic form q : $\mathbb{N}$n → $\mathbb{N}$ and of any positive (resp. principal) edge-bipartite connected graph Δ. The study of the problem is inspired by applications of the algorithms in the representation theory, in solving a class of Diophantine equations, in the study of mesh geometries of roots, in the spectral analysis of graphs, and in the Coxeter-Gram classification of edge-bipartite graphs.

Keywords: edge-bipartite graphs, Dynkin graphs, Euclidean graphs, quadratic forms, equivalence of quadratic forms, combinatorial algorithms

DOI: 10.3233/FI-2012-731

Journal: Fundamenta Informaticae, vol. 119, no. 2, pp. 149-162, 2012