Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland. [email protected]
Correspondence:
[*]
Address for correspondence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland.
Note: [1] Supported by Polish Research Grant NCN 2011/03/B/ST1/00824.
Abstract: We continue the Coxeter spectral study of the category 𝒰ℬigrm of loop-free edge-bipartite (signed) graphs Δ, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Δ ∈ 𝒰ℬigrn + r of corank r ≥ 0, up to a pair of the Gram ℤ-congruences ∼ℤ and ≈ℤ, by means of the non-symmetric Gram matrix GˇΔ∈𝕄n+r(ℤ) of Δ, the symmetric Gram matrix GΔ:=12[GˇΔ+GˇΔtr]∈𝕄n+r(ℤ), the Coxeter matrix CoxΔ:=−GˇΔ⋅GˇΔ−tr∈𝕄n+r(ℤ) and its spectrum speccΔ ⊂ ℂ, called the Coxeter spectrum of Δ. One of the aims in the study of the category 𝒰ℬigrn + r is to classify the equivalence classes of the non-negative edge-bipartite graphs in 𝒰ℬigrn + r with respect to each of the Gram congruences ∼ℤ and ≈ℤ. In particular, the Coxeter spectral analysis question, when the strong congruence Δ≈ℤΔ′
holds (hence also Δ∼ℤΔ′
holds), for a pair of connected non-negative graphs Δ, Δ′ ∈ 𝒰ℬigrn + r such that speccΔ = speccΔ′, is studied in the paper. One of our main aims is an algorithmic description of a matrix B defining the Gram ℤ-congruences Δ≈ℤΔ′
and Δ∼ℤΔ′
, that is, a ℤ-invertible matrix B∈𝕄n+r(ℤ)
such that GˇΔ′=Btr⋅GˇΔ⋅B
and GΔ′=Btr⋅GΔ⋅B
, respectively. We show that, given a connected non-negative edge-bipartite graph Δ in 𝒰ℬigrn + r of corank r ≥ 0 there exists a simply laced Dynkin diagram D, with n vertices, and a connected canonical r-vertex extension D^:=D^(r) of D of corank r (constructed in Section 2) such that Δ~ℤD^. We also show that every matrix B defining the strong Gram ℤ-congruence Δ≈ℤΔ′ in 𝒰ℬigrn + r has the form B=CΔ⋅B¯⋅CΔ′−1, where CΔ,CΔ′∈Mn+r(ℤ) are fixed ℤ-invertible matrices defining the weak Gram congruences Δ~ℤD^ and Δ′~ℤD^ with an r-vertex extended graph D^, respectively, and B¯∈𝕄n+r(ℤ) is ℤ-invertible matrix lying in the isotropy group G1(n+r,ℤ)D^ of D^. Moreover, each of the columns k∈ℤn+r of B is a root of ℤ, i.e., k⋅GˇΔ⋅ktr=1. Algorithms constructing the set of all such matrices B are presented in case when r = 0. We essentially use our construction of a morsification reduction map ϕD^:UBigrD^→MorD^ that reduces (up to ≈ℤ) the study of the set 𝒰ℬigrD^ of all connected non-negative edge-bipartite graphs Δ in 𝒰ℬigrn + r such that Δ~ℤD^ to the study of G1(n+r,ℤ)D^-orbits in the set MorD^⊆G1(n+r,ℤ) of all matrix morsifications of the graph D^.
Keywords: signed graph, Gram congruence, Coxeter spectrum, symbolic algorithms, Coxeter-Dynkin type, isotropy group
