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

Abstract

We describe combinatorial algorithms that compute the Dynkin type (resp. Euclidean type) of any positive (resp. principal) unit quadratic form q : $\mathbb{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.