Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups

作者:

Highlights:

摘要

We develop algorithmic techniques for the Coxeter spectral analysis of the class UBigrn of connected loop-free positive edge-bipartite graphs Δ with n≥2 vertices (i.e., signed graphs). In particular, we present numerical and graphical algorithms allowing us a computer search in the study of such graphs Δ by means of their Gram matrix ǦΔ, the (complex) spectrum speccΔ⊆C of the Coxeter matrix CoxΔ:=−ǦΔ⋅ǦΔ−tr, and the geometry of Weyl orbits in the set MorDΔ of matrix morsifications A∈Mn(Z) of a simply laced Dynkin diagram DΔ∈{An,Dn,E6,E7,E8} associated with Δ and mesh root systems of type DΔ. Our algorithms construct the Coxeter–Gram polynomials coxΔ(t)∈Z[t] and mesh geometries of root orbits of small connected loop-free positive edge-bipartite graphs Δ. We apply them to the study of the following Coxeter spectral analysis problem: Does the Z-congruence Δ≈ZΔ′ hold (i.e., the matrices ǦΔ and ǦΔ′ are Z-congruent), for any pair of connected positive loop-free edge-bipartite graphs   Δ,Δ′ in UBigrn such that speccΔ=speccΔ′? The problem if any square integer matrix A∈Mn(Z) is Z-congruent with its transpose Atr is also discussed. We present a solution for graphs in UBigrn, with n≤6.

论文关键词:Edge-bipartite graph,Matrix morsification,Dynkin diagram,Coxeter polynomial,Mesh geometry of roots,Computer algorithm

论文评审过程:Received 13 February 2013, Revised 30 April 2013, Available online 31 July 2013.

论文官网地址:https://doi.org/10.1016/j.cam.2013.07.013

Back to Top