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

Article type: Research Article

Authors: Kasjan, Stanisław^a | Simson, Daniel^{a; *; †}

Affiliations: [a] Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland. {skasjan,simson}@mat.umk.pl

Note: [*] The paper is supported by Polish Research Grant NCN 2011/03/B/ST1/00824

Note: [†] Address for correspondence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland.

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 𝒰ℬigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category ℛℬigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual ℤ-congruences ~Z and ≈Z. The positive graphs Δ in ℛℬigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ ⊂ℂ, 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 Δ, Δ′∈ℛℬigrn such that speccΔ=speccΔ′ 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 MorD ⊂ 𝕄n(ℤ) of matrix morsifications of a Dynkin diagram D=DΔ∈𝒰Bigrn associated with Δ. In particular, we construct in the second part of the paper numeric algorithms for computing the connected positive edge-bipartite graphs Δ in ℛℬigrn, for a fixed n ≥ 2, mesh algorithms for computing the set of all ℤ-invertible matrices B ∈ G1(n, ℤ) definining the ℤ-congruence Δ≈ℤΔ', for positive graphs Δ, Δ′∈ℛℬigrn, 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 Γ(RD•, ΦD) for each of the Cox-regular edge-bipartite graphs ℬn, n≥2, Cn, n≥3, ℱ4, cal𝒢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.

Keywords: Edge-bipartite graph, Dynkin diagram, morsification, Coxeter spectrum, Coxeter-Gram polynomial, mesh root system, mesh algorithm

DOI: 10.3233/FI-2015-1230

Journal: Fundamenta Informaticae, vol. 139, no. 2, pp. 153-184, 2015