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

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 𝒰 ℬ i g r n of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category ℛ ℬ i g r n of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual ℤ-congruences ~_Z and ≈_Z. The positive graphs Δ in ℛ ℬ i g r n, with dotted loops, are studied by means of the complex Coxeter spectrum s p e c c Δ ⊂ ℂ, the irreducible mesh root systems of Dynkin types 𝔹 n , n ≥ 2 , ℂ n , n ≥ 3 , 𝔽 4 , 𝔾 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 Δ , Δ ′ ∈ ℛ ℬ i g r n such that spec c Δ = spec c Δ ′ and the numbers of loops in Δ and Δ′ coincide?” We do it by a reduction to the Coxeter spectral study of the G1 ( n , ℤ ) D-orbits in the set M o r D ⊂ 𝕄 n ( ℤ ) of matrix morsifications of a Dynkin diagram D = D Δ ∈ 𝒰 B i g 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 ℛ ℬ i g r n, for a fixed n ≥ 2, mesh algorithms for computing the set of all ℤ-invertible matrices B ∈ G1 ( n , ℤ ) definining the ℤ-congruence Δ ≈ ℤ Δ ', for positive graphs Δ , Δ ′ ∈ ℛ ℬ i g r n, with n ≥ 2 fixed, and mesh-type algorithms for the mesh root systems Γ ( R Δ • , Φ Δ ). 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 ≥ 2 , ℂ n , n ≥ 3 , 𝔽 4 , 𝔾 2. Moreover, we construct a unique Φ_D-mesh root system Γ ( R D • , Φ D ) for each of the Cox-regular edge-bipartite graphs ℬ n , n ≥ 2 , C n , n ≥ 3 , ℱ 4 , c a l 𝒢 2 of the type ℬ n , n ≥ 2 , ℂ n , n ≥ 3 , 𝔽 4 , 𝔾 2, respectively.

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