Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: signed graph

Sortuj według:

Ogranicz wyniki do:

Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs. [Part 2], Isotropy Mini-groups

Simson D.

Fundamenta Informaticae

2016

Vol. 145, nr 1

49--80

In this two parts article with the same title we continue the Coxeter spectral study of the category UBigrm 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 Δ ∈ UBigrn+r of corank r ≥ 0, up to a pair of the Gram Z-congruences ;~z and ≈z, by means of the non-symmetric Gram matrix ĞΔ∈Mn+r(Z) of Δ, the symmetric Gram matrix GΔ:=1/2[ĞΔ+ĞΔ-tr]∈Mn+r(Z), the Coxeter matrix CoxΔ:[formula...], its spectrum speccΔ⊂C, called the Coxeter spectrum of Δ, and the Dynkin type DynΔ∈{An,Dn,E6,E7,E8} associated in Part 1 of this paper. One of the aims in the study of the category UBigrn+r is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigrn+r with respect to each of the Gram congruences ~Z and ≈Z. In particular, the Coxeter spectral analysis question, when the congruence Δ≈ZΔ′ holds (hence also Δ~ZΔ′ holds), for a pair of connected non-negative graphs Δ,Δ′∈uBigrn+rsuch that speccΔ=speccΔ′ and DynΔ=DynΔ′, is studied in the paper. One of our main aims in this Part 2 of the paper is to get an algorithmic description of a matrix B defining the strong Gram Z-congruence Δ≈ZΔ′, that is, a Z-invertible matrix B∈Mn+r(Z) such that [formula...]. We obtain such a description for a class of non-negative connected edge-bipartite graphs Δ∈uBigrn+r of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotropy mini-group ..., for a class of edge-bipartite graphs Δ∈uBigrn+r. Using the algorithms, we calculate the isotropy mini-groupGl(n,Z)D where D is any of the Dynkin bigraphs An, Bn, Cn, Dn, E6, E7, E8, F4, G2 and .D is any of the Euclidean graphs .[formula...].

Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs. [Part 1], A Gram Classification

Simson D.

Fundamenta Informaticae

2016

Vol. 145, nr 1

19--48

We continue the Coxeter spectral study of the category UBigrm 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 Δ ∈ UBigrn+r of corank r ≥ 0, up to a pair of the Gram Z-congruences ~ z and ≈z, by means of the non-symmetric Gram matrix GΔ∈ Mn+r(Z), the symmetric Gram matrix GΔ:=[formula..]..., the Coxeter matrix CoxΔ:=[formula...]... and its spectrum speccΔ ⊂ C, called the Coxeter spectrum of Δ. One of the aims in the study of the category UBigrn+r is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigrn+r with respect to each of the Gram congruences ~Z and ≈Z. In particular, the Coxeter spectral analysis question, when the strong congruence Δ≈ZΔ′ holds (hence also ΔZΔ′ holds), for a pair of connected non-negative graphs Δ, Δ′ ∈ UBigrn+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 Z-congruences Δ≈ZΔ′ and ΔZΔ′, that is, a Z-invertible matrix B∈Mn+r(Z) such that ..., respectively. We show that, given a connected non-negative edge-bipartite graph Δ in UBigrn+r of corank r ≥ 0 there exists a simply laced Dynkin diagram D, with n vertices, and a connected canonical r-vertex extension ... of D of corank r (constructed in Section 2) such that Δ~ZD. We also show that every matrix B defining the strong Gram Z-congruence Δ≈ZΔ′ in UBigrn+r has the form [formula...], where CΔ,CΔ′∈Mn+r(Z) are fixed Z-invertible matrices defining the weak Gram congruences Δ~Z ... and Δ′~ZD with an r-vertex extended graph ..., respectively, and B ∈Mn+r(Z) is Z-invertible matrix lying in the isotropy group ... Moreover, each of the columns k∈Zn+r of B is a root of Z, i.e., ... 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 ... that reduces (up to ≈Z) the study of the set UBigr... of all connected non-negative edge-bipartite graphs Δ in UBigrD such that ... to the study of G1(n+r,Z)D-orbits in the set MorD⊆G1(n+r,Z) of all matrix morsifications of the graph D.