查看更多>>摘要：One of the main aims of the paper is to develop the mesh geometry technique for corank-two edge-bipartite graphs Δ with n+2≥3 vertices, and the mesh algorithms introduced in [30,33] and successfully studied in our recent article [42]. We introduce and study the concept of a self-duality of mesh geometries Γ(R?Δ,ΦΔ) viewed as ΦΔ-mesh translation quivers. We show how self-dualities of mesh geometries Γ(R?Δ,ΦΔ) and the mesh geometry technique is applied to an affirmative algorithmic solution of so called Horn-Sergeichuk type problem [9, Problem 4.3] on the self-congruency of square integer matrices A∈Mn+2(Z), for the class of non-symmetric Gram matrices A=GˇΔ of corank-two loop-free edge-bipartite graphs Δ, with n+2≤6 vertices. More precisely, we show that each of the mesh geometries Γ(R?Δ,ΦΔ) is self-dual, we construct its dual form Γ(R?Δ,ΦΔ)op=Γ(R?Δ,ΦΔ?1) isomorphic with Γ(R?Δ,ΦΔ), and we construct a canonical self-duality isomorphism fΔ:Γ(R?Δ,ΦΔ)→Γ(R?Δ,ΦΔ)op of mesh translation quivers. Using the self-duality fΔ we construct combinatorial algorithms such that, given a square Gram matrix A=GˇΔ∈Mn+2(Z) of Δ lying in this class, they are able to compute a Z-invertible matrix B∈Mn+2(Z) that coincide with its inverse B?1 and defines the congruence of A with Atr, i.e., the equation Atr=Btr?A?B is satisfied. An idea of our solution is outlined in Section 8 of our recent article [42], where among others two of our 13 algorithms solving the problem are constructed. The remaining 11 algorithms are constructed in the present article. We do it by means of the structure of the standard self-dual ΦΔ-mesh translation quiver Γ(R?Δ,ΦΔ) (called a geometry) canonically associated with Δ, consisting of ΦΔ-meshes of ΦΔ-orbits OΔ(w) of vectors w∈R?Δ?Zn+2, where ΦΔ:Zn+2→Zn+2 is the Coxeter transformation of Δ. We construct in the paper such self-dual ΦΔ-mesh geometry Γ(R?Δ,ΦΔ), for each of the corank-two loop-free edge-bipartite graphs Δ, with n+2≤6 vertices.
NSTL
Elsevier