Wyniki wyszukiwania - BazTech

1

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

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

2

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

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.

3

On Algorithmic Study of Non-negative Posets of Corank at Most Two and their Coxeter-Dynkin Types

Gąsiorek M., Zając K.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 4

347--367

EN

Here we study the connected posets I that are non-negative of corank one or two, in the sense that the symmetric Gram matrix 1/2 (CI + Citr) ∊ Mn(Q) is positive semi-definite of corank one or two, where CII ∊ Mn(Z) is the incidence matrix of I. We study such posets I by means of the Dynkin type DynI and the Coxeter polynomial coxI (t) := det(t.E - CoxI) ∊ Z[t], where CoxI := CI + CItr ∊ Mn(Z) is the Coxeter matrix of I. Among other results, we develop an algorithmic technique that allows us to compute a complete list of such posets I, with |I| ≤ 16, their Dynkin types DynI, and the Coxeter polynomials coxI(t) ∊Z[t]. We prove that, given a pair of such connected posets I and J, the incidence matrices CI and CJ are Z-congruent if and only if coxI (t) = coxJ (t) and DynI = DynJ

4

Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 3

249--275

EN

This paper can be viewed as a third part of our paper [Fund. Inform. 2015, in press]. Following our Coxeter spectral study in [Fund. Inform. 123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study a larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ ⊂ C, the irreduciblemesh root systems of Dynkin types Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, the isotropy group G1(n, Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24]. Here we present combinatorial algorithms for constructing the isotropy groups G1(n,Z)Δ. One of the aims of our three paper series is to develop computational tools for the study of the Zcongruence ~Z and the following Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' holds, for any pair of connected positive graphsΔ,Δ' ∈ RBigrn such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ' coincide?". For this purpose, we construct in this paper a extended inflation algorithm Δ → DΔ, with DΔ ~Z Δ, that allows a reduction of the question to the Coxeter spectral study of the G1(n,Z)D-orbits in the set MorD ⊂ Mn(Z) of matrix morsifications of the associated edge-bipartite Dynkin graph D = DΔ ∈ RBigrn. We also outline a construction of a numeric algorithm for computing the isotropy group G1(n,Z)Δ of any connected positive edge-bipartite graph Δ in RBigrn. Finally, we compute the finite isotropy group G1(n,Z)D, for each of the Cox-regular edge-bipartite Dynkin graphs D.