Wyniki wyszukiwania - Biblioteka Nauki

1

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

100%

Simson D.

Fundamenta Informaticae

|

2016

|

tom Vol. 145, nr 1

19--48

EN

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.

2

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

100%

Simson D.

Fundamenta Informaticae

|

2016

|

tom Vol. 145, nr 1

49--80

EN

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...].

3

A Graph Theoretical Framework for the Strong Gram Classification of Non-negative Unit Forms of Dynkin Type 𝔸 n

100%

González J. , Arturo J.

Fundamenta Informaticae

|

2021

|

tom Vol. 184, nr 1

49--82

EN

In the context of signed line graphs, this article introduces a modified inflation technique to study strong Gram congruence of non-negative (integral quadratic) unit forms, and uses it to show that weak and strong Gram congruence coincide among positive unit forms of Dynkin type An . The concept of inverse of a quiver is also introduced, and is used to obtain and analyze the Coxeter matrix of non-negative unit forms of Dynkin type An . With these tools, connected principal unit forms of Dynkin type An are also classified up to strong congruence.

4

Coxeter Invariants for Non-negative Unit Forms of Dynkin Type A

84%

Jiménez González J. A.

Fundamenta Informaticae

|

2022

|

tom Vol. 185, nr 3

221--246

EN

Two integral quadratic unit forms are called strongly Gram congruent if their upper triangular Gram matrices are ℤ-congruent. The paper gives a combinatorial strong Gram invariant for those unit forms that are non-negative of Dynkin type r (for r ≥ 1), within the framework introduced in [Fundamenta Informaticae 184(1):49–82, 2021], and uses it to determine all corresponding Coxeter polynomials and (reduced) Coxeter numbers.