Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops,I. Mesh Root Systems

Abstract

Abstract

This is the first part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category $𝒰ℬig{r}_n$ of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category $ℛℬig{r}_n$ of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual ℤ-congruences ~_Z and ≈_Z. The positive graphs Δ in $ℛℬig{r}_n$, with dotted loops, are studied by means of the complex Coxeter spectrum $spec{c}_{\Delta }\subset ℂ$, the irreducible mesh root systems of Dynkin types ${𝔹}_n,n\ge 2,{ℂ}_n,n\ge 3,{𝔽}_{\text{4}},{𝔾}_{\text{2}}$, the isotropy group Gl(n, ℤ)_Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490].

One of our aims of the paper is to study the Coxeter spectral analysis question: “Does the congruence Δ ≈_ℤ Δ′ hold, for any pair of connected positive graphs $\Delta ,{\Delta }^{\prime }\in ℛℬig{r}_n$ such that $\text{spec}{\text{c}}_{\Delta }=\text{spec}{\text{c}}_{{\Delta }^{\prime }}$ and the numbers of loops in Δ and Δ′ coincide?” We do it by a reduction to the Coxeter spectral study of the $\text{G1}(n,\mathbb{Z}{)}_D$-orbits in the set $Mo{r}_D\subset {𝕄}_n(\mathbb{Z})$ of matrix morsifications of a Dynkin diagram $D=D\Delta \in 𝒰Big{r}_n$ associated with Δ. In particular, we construct in the second part of the paper numeric algorithms for computing the connected positive edge-bipartite graphs Δ in $ℛℬig{r}_n$, for a fixed n ≥ 2, mesh algorithms for computing the set of all ℤ-invertible matrices B ∈ $\text{G1}(n,\mathbb{Z})$ definining the ℤ-congruence $\Delta {\approx }_{\mathbb{Z}}{\Delta }^{\text{'}}$, for positive graphs $\Delta ,{\Delta }^{\prime }\in ℛℬig{r}_n$, with n ≥ 2 fixed, and mesh-type algorithms for the mesh root systems $\Gamma (R_{\Delta }^{•},{\Phi }_{\Delta })$. In the first part of the paper we present an introduction to the study of Cox-regular edge-bipartite graphs Δ with dotted loops in relation with the irreducible reduced root systems and the Dynkin diagrams ${ℬ}_n,n\ge 2,{ℂ}_{n,}n\ge 3,{𝔽}_{\text{4}},{𝔾}_{\text{2}}$. Moreover, we construct a unique Φ_D-mesh root system $\Gamma (R_D^{•},{\Phi }_D)$ for each of the Cox-regular edge-bipartite graphs ${ℬ}_n,n\ge 2,C_n,n\ge 3,{ℱ}_4,cal{𝒢}_2$ of the type ${ℬ}_n,n\ge 2,{ℂ}_{n,}n\ge 3,{𝔽}_{\text{4}},{𝔾}_{\text{2}}$, respectively.

Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems.