Wyniki wyszukiwania - BazTech

1

Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops

Makuracki B., Simson D., Zyglarski B.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 4

367--398

EN

We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix ĞΔ ∊ Mn(Z) defining Δ, its symmetric Gram matrix GΔ:=1/2[ĞΔ+ĞtrΔ]∊ Mn(1/2Z), and the Gram quadratic form qΔ : Zn → Z. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix GΔ∊ Mn(Z) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram Z-congruence Δ ~Z Δ', where Δ ~ZΔ' means that GΔ' = Btr.GΔ .B, for some B ∊ Mn(Z) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph Dn ∊ {Bn, Cn, F4, G2} with loops and a suitably chosen sequence t-• of the inflation operators of one of the types Δ'↦t-aΔ' and Δ'↦t-abΔ' such that the composite operator Δ↦t-•Δ reduces Δ to the bigraph Dn such that Δ ~Z Dn and the bigraphs Δ, Dn have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∊ Mn(Z), with det B = ±1, defining the weak Gram Z-congruence Δ ~Z Dn, that is, satisfying the equation GDn= Btr.GΔ.B.

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

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.