检索结果-内蒙古大学图书馆

inflation algorithm for loop-free non-negative edge-bipartite graphs of corank at least two

LINEAR ALGEBRA AND ITS APPLICATIONS 2017年 524卷 109-152页

作者： Simson, Daniel Zajac, Katarzyna Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

We continue the study of finite connected loop-free edge bipartite graphs Delta, with m >= 3 vertices (a class of signed graphs), we started in Simson (2013) [48] and M. Gasiorek et al. (2016) [19] by means of the non-symmetric Gram matrix G(sic)Delta is an element of M-m (Z) of Delta, its symmetric Gram matrix G(Delta) := 1/2[G(sic)(Delta) + G(sic)(Delta)(tr)] is an element of M-m(1/2Z), and the Gram quadratic form q(Delta) : Z(m) -> Z. In particular, we study connected non negative edge-bipartite graphs Delta, with n + r >= 3 vertices of corank r >= 2, in the sense that the symmetric Gram matrix G(Delta) is an element of Mn+r(Z) of Delta is positive semi-definite of rank n >= 1. The edge-bipartite graphs Delta of corank r >= 2 are studied, up to the weak Gram Z-congruence Delta similar to z Delta', where Delta similar to z Delta' means that G(Delta') = B-tr . G(Delta) . B, for some B is an element of Mn+r(Z) such that det B = +/- 1. Our main result of the paper asserts that, given a connected edge-bipartite graph Delta with n + r >= 3 vertices of corank r >= 2, there exists a suitably chosen sequence t*(-) of the inflation operators of the form Delta' bar right arrow t(ab)(-)Delta' such that the composite operator Delta bar right arrow t*(-) Delta reduces Delta to a connected bigraph (D) over cap ((r))(n) such that Delta similar to z (D) over cap (n) ((r)) and (D) over cap ((r))(n) is one of the canonical r-vertex extensions (A) over cap ((r))(n), n >= 1, (D) over cap ((r))(n), n >= 4, (E) over cap ((r))(6), (E) over cap ((r))(7), and (E) over cap ((r))(8), with n + r vertices, of the simply laced Dynkin diagrams A(n), B-n, E-6, E-7, E-8, with n >= 1 vertices. The algorithm constructs also a matrix B is an element of Mn+r(Z), with det B = +/- 1, defining the weak Gram Z-congruence Delta similar to z (D) over cap ((r))(n), that is, satisfying the equation G((D) over capn(r)) = B-tr . G Delta . B. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Signed graph Edge-bipartite graph Corank Dynkin type Coxeter spectrum inflation algorithm Gram matrix

来源：评论

学校读者我要写书评

暂无评论

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

引用

FUNDAMENTA INFORMATICAE 2017年第4期153卷 367-398页

作者： Makuracki, Bartosz Simson, Daniel Zyglarski, Blazej Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

We continue the study of finite connected edge-bipartite graphs Delta, 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 G(Delta) is an element of M-n (Z) defining Delta, its symmetric Gram matrix G(Delta) : = 1/2 [G(Delta) + G(Delta)(tr)] is an element of M-n (1/2 Z), and the Gram quadratic form q Delta: Z(n) -> Z. In the present paper we study connected positive Cox-regular edge-bipartite graphs Delta, with n >= 2 vertices, in the sense that the symmetric Gram matrix G(Delta) is an element of M-n (Z) of Delta 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 Delta similar to(Z) Delta', where Delta similar to(Z) Delta' means that G(Delta') = B-tr . G(Delta) . B, for some B is an element of M-n (Z) such that det B = +/- 1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Delta with n >= 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph D-n is an element of {B-n;C-n;F-4;G(2) } with loops and a suitably chosen sequence t.(-) of the inflation operators of one of the types Delta' -> t(a)(-) Delta' and Delta' -> t(ab)(-) Delta' such that the composite operator Delta' -> t(.)(-) Delta reduces Delta to the bigraph D-n such that Delta similar to(Z) D-n and the bigraphs Delta, D-n have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B is an element of M-n (Z), with det B = +/- 1, defining the weak Gram Z-congruence Delta similar to(Z) D-n, that is, satisfying the equation GD(n) = B-tr . G(Delta) . B.

关键词： edge-bipartite graph Dynkin graph inflation algorithm Gram matrix unit quadratic form Coxeter spectrum isotropy group

来源：评论

学校读者我要写书评

暂无评论

A Framework for Coxeter Spectral Analysis of Edge-bipartite Graphs, their Rational Morsifications and Mesh Geometries of Root Orbits

引用

FUNDAMENTA INFORMATICAE 2013年第3期124卷 309-338页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci PL-87100 Torun Poland

Following the spectral Coxeter analysis of matrix morsifications for Dynkin diagrams, the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we continue our study of the category UBigr(n) of loop-free edge-bipartite (signed) graphs Delta, with n >= 2 vertices, by means of the Coxeter number c(Delta), the Coxeter spectrum specc(Delta) of Delta, that is, the spectrum of the Coxeter polynomial cox(Delta)(t) is an element of Z [t] and the Z-bilinear Gram form b(Delta) : Z(n) x Z(n) -> Z of Delta [SIAM J. Discrete Math. 27(2013)]. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. We show that the Coxeter spectral classification of connected edge-bipartite graphs Delta in UBigr(n) reduces to the Coxeter spectral classification of rational matrix morsifications A is an element of (M) over cap or (D Delta). for a simply-laced Dynkin diagram D Delta associated with Delta. Given Delta in UBigr(n), we study the isotropy subgroup Gl(n, Z)(Delta) of Gl(n, Z) that contains the Weyl group W-Delta and acts on the set (M) over cap or(Delta) of rational matrix morsifications A of Delta in such a way that the map A bar right arrow (specc(A), det A, c(Delta)) is Gl(n, Z)(Delta)-invariant. It is shown that, for n <= 6, specc(Delta) is the spectrum of one of the Coxeter polynomials listed in Tables 3.11-3.11(a) (we determine them by computer search using symbolic and numeric computation). The question, if two connected positive edge-bipartite graphs Delta,Delta' in UBigr n, with specc(Delta) = specc(Delta'), are Z-bilinear equivalent, is studied in the paper. The problem if any Z-invertible matrix A is an element of M-n (Z) is Z-congruent with its transpose A(tr) is also discussed.

关键词： edge-bipartite graph toroidal mesh algorithm inflation algorithm matrix morsification Dynkin diagram Coxeter spectrum Weyl group Euler bilinear form mesh geometry of root orbits toroidal mesh algorithm sand-glass tube

来源：评论

学校读者我要写书评

暂无评论

Toroidal algorithms for Mesh Geometries of Root Orbits of the Dynkin Diagram D₄

引用

FUNDAMENTA INFORMATICAE 2013年第3期124卷 339-364页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci PL-87100 Torun Poland

By applying symbolic and numerical computation and the spectral Coxeter analysis technique of matrix morsifications introduced in our previous paper [Fund. Inform. 124(2013)], we present a complete algorithmic classification of the rational morsifications and their mesh geometries of root orbits for the Dynkin diagram D-4. The structure of the isotropy group Gl(4, Z)(D4) of D-4 is also studied. As a byproduct of our technique we show that, given a connected loop-free positive edge-bipartite graph Delta, with n >= 4 vertices (in the sense of our paper [SIAM J. Discrete Math. 27(2013)]) and the positive definite Gram unit form (q Delta) : Z(n) -> Z, any positive integer d >= 1 can be presented as d = (q Delta)(v), with v is an element of Z(n). In case n = 3, a positive integer d >= 1 can be presented as d = (q Delta)(v), with v is an element of Z(n), if and only if d is not of the form 4(a) (16 . b + 14), where a and b are non-negative integers.

关键词： edge-bipartite graph toroidal mesh algorithm inflation algorithm matrix morsification Dynkin diagram Coxeter spectrum Weyl group Euler bilinear form mesh geometry of root orbits

来源：评论

学校读者我要写书评

暂无评论

A Coxeter spectral classification of positive edge-bipartite graphs II. Dynkin type D_n

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2021年 612卷 223-272页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 Torun Poland

We continue the Coxeter spectral study of finite positive edge-bipartite signed (multi)graphs Δ (bigraphs, for short), with n≥2 vertices started in Simson (2013) [44] and developed in Simson (2018) [49]. We do it by means of the non-symmetric Gram matrix GˇΔ∈Mn(Z) defining Δ, its Gram quadratic form qΔ:Zn→Z, v↦v⋅GˇΔ⋅vtr (that is positive definite, by definition), the complex spectrum speccΔ⊂S1:={z∈C,|z|=1} of the Coxeter matrix CoxΔ:=−GˇΔ⋅GˇΔ−tr∈Mn(Z), called the Coxeter spectrum of Δ, and the Coxeter polynomial coxΔ(t):=det⁡(t⋅E−CoxΔ)∈Z[t]. One of the aims of the Coxeter spectral analysis is to classify the connected bigraphs Δ with n≥2 vertices up to the ℓ-weak Gram Z-congruence Δ∼ℓZΔ′ and up to the strong Gram Z-congruence Δ≈ZΔ′, where Δ∼ℓZΔ′ (resp. Δ≈ZΔ′) means that det⁡GˇΔ=det⁡GˇΔ′ and GΔ′=Btr⋅GΔ⋅B (resp. GˇΔ′=Btr⋅GˇΔ⋅B), for some B∈Mn(Z) with det⁡B=±1, where GΔ:=12[GˇΔ+GˇΔtr]∈Mn(12Z).Here we study connected signed simple graphs Δ, with n≥2 vertices, that are positive, i.e., the symmetric Gram matrix GΔ∈Mn(12Z) of Δ is positive definite. It is known that every such a signed graph is ℓ-weak Gram Z-congruent with a unique simply laced Dynkin graph DynΔ∈{An,Dn,n≥4,E6,E7,E8}, called the Dynkin type of Δ. A classification up to the strong Gram Z-congruence Δ≈ZΔ′ is still an open problem and only partial results are known. In this paper, we obtain such a classification for the positive signed simple graphs Δ of Dynkin type Dn by means of the family of the signed graphs Dn(1)=Dn,Dn(2),…,Dn(rn) constructed in Section 2, for any n≥4, where rn=⌞n/2⌟. More precisely, we prove that any connected signed simple graph of Dynkin type Dn, with n≥4 vertices, is strongly Z-congruent with a signed graph Dn(s), for some s≤rn, and its Coxeter polynomial coxΔ(t) is of the form (ts+1)(tn−s+1). We do it by a matrix morsification type reduction to the classification of the conjugacy classes in the integral orthogonal group O(n,Z) of the integer orthogonal matrices C, with det⁡(E−C)=4.

关键词： Edge-bipartite graph Signed graph Dynkin type inflation algorithm Gram congruence Coxeter spectrum Quasi-Cartan matrix Integral quadratic form Matrix morsification

来源：评论

学校读者我要写书评

暂无评论

A COXETER-GRAM CLASSIFICATION OF POSITIVE SIMPLY LACED EDGE-BIPARTITE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第2期27卷 827-854页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci PL-87100 Torun Poland

Following the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we study the category UBigr(n) of loop-free edge-bipartite (signed) graphs Delta, with n >= 2 vertices, up to Z-congruences similar to(Z) and approximate to(Z) (defined in the paper), by means of the Gram matrix (sic)(Delta) is an element of M-n(Z), the Coxeter-Gram matrix Cox(Delta) = -(sic)(Delta) . (sic)(Delta)(-tr) is an element of M-n(Z), the spectrum specc(Delta) of Cox(Delta), the Coxeter polynomial cox Delta(t) is an element of Zleft perpendiculartright perpendicular, the Coxeter number c(Delta) >= 2, and the Z-bilinear Gram form b(Delta) : Z(n) x Z(n) -> Z of Delta. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. One of our aims is to compute the set CGpol(n)(+) of all polynomials cox(Delta)(t), with positive connected graphs Delta in UBigr(n), for all n >= 2, and to present a framework for a classification of graphs Delta in UBigr(n), up to the congruence approximate to(Z), by means of their Coxeter polynomials cox(Delta)(t) is an element of Z[t] and Coxeter spectra. In particular, the Coxeter spectral analysis question, whether the congruence Delta approximate to(Z) Delta' holds, for any pair of connected positive graphs Delta, Delta' is an element of UBigr(n) such that specc(Delta) = specc(Delta)', is studied in the paper. One of our main results contains an affirmative answer to the question and a description of the finite set CGpol(n)(+) for n <= 8. One of the tools we apply is an inflation algorithm Delta bar right arrow D Delta that associates with any connected positive graph Delta is an element of UBigr(n) a simply laced Dynkin diagram D Delta such that Delta similar to (Z) D Delta, and cox Delta(t) and c(Delta) coincide with the Coxeter polynomial cox(A)(t) and the Coxeter number c(A) of a matrix morsification A is an element of MorD(Delta) sub

关键词： edge-bipartite graph signed graphs Dynkin diagram Euclidean diagram mesh root system matrix morsification Coxeter-Gram polynomial inflation algorithm Coxeter spectral classification

来源：评论

学校读者我要写书评

暂无评论

Symbolic computation of strong Gram congruences for Cox-regular positive edge-bipartite graphs with loops

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2019年 573卷 90-143页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

The paper can be viewed as a second part of the author's paper (Simson (2018) [43]). Our main aim is to construct symbolic algorithms for the Coxeter spectral classification of a class of signed graphs (called edge-bipartite graphs), with n >= 2 vertices, we started in Simson (2013) [37] and Bocian et al. (2014) [6]. More precisely, we construct algorithms for the classification (up to the strong Gram Z-congruence Delta approximate to(Z) Delta') of all finite connected Cox-regular edge-bipartite graphs Delta with at least one loop (bigraphs, for short) that are positive in the sense that the associated symmetric Gram matrix G(Delta) = 1/2 (G(Delta) + G(Delta)(tr)) is an element of M-n (1/2Z) is positive definite, where G(Delta) is an element of M-n(Z) is the non-symmetric Gram matrix of Delta defined in Section 1 and Delta approximate to(Z) Delta' means that there is a Z-invertible matrix B is an element of M-n(Z) such that G(Delta') = B-tr . G(Delta) . B. We recall from [43] that every such a bigraph Delta, with a loop, is strongly Gram Z-congruent with a bigraph D-Delta, that is one of the positive Cox-regular bigraphs B-n, n >= 2, C-n, n >= 3, F-4, M-4, G(2) presented in Section 1. Here, by applying the geometry of mesh root system technique, we construct symbolic algorithms that compute the correspondence Delta bar right arrow D-Delta and the set (Delta)G1(n, Z)(D Delta) of all Z-invertible matrices B is an element of M-n(Z) defining the strong Gram Z-congruence Delta approximate to(Z) D-Delta, for any connected positive bigraph Delta, with n >= 2 vertices and at least one loop. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Unit form Symbolic algorithm Quasi-Cartan matrix inflation algorithm Edge-bipartite graph Dynkin graph Gram congruence Coxeter polynomial

来源：评论

学校读者我要写书评

暂无评论

A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2020年 586卷 190-238页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

With any symmetrizable integer Cartan matrix C is an element of SCar(n) subset of M-n(Z), a Z-invertible Coxeter matrix Cox(C) is an element of M-n(Z) is associated. We study such positive definite matrices up to a strong Gram Z-congruence C approximate to(Z) C' (defined in the paper by means of a 7G-invertible matrix B is an element of M-n(Z)) by means of the Dynkin type Dyne, the complex spectrum specc(C) subset of C of the Coxeter polynomial cox(C) (t) := det(tE - Cox(C)) is an element of Z[t] and the Coxeter type CtYP(C) = (specc(C),sw(C)) of C. We show that the strong Gram Z-congruence C approximate to(z) C' implies the equality Ctyp(C) = Ctyp(C)'. The inverse implication is an open problem studied in the paper. However, we prove the implication for positive definite symmetrizable integer Cartan matrices C, C' satisfying any of the following two conditions: (i) if n <= 9, the matrices C, C' are symmetric (i.e., sw(C) = sw(C), = 1) and Dyne is one of the simply laced Dynkin graphs A(n), n >= 1, D-n, n >= 4, E-6, E-7, E-8, and (ii) n >= 2, the matrices C, C' are not symmetric and Dyn(C) is one of the Dynkin signed graphs B-n, C-n, F-4, G(2). We do it by a reduction to an analogous problem for positive Cox-regular edge-bipartite graphs. Moreover, given n <= 9, we present a list of 60 pairwise non-congruent matrices in SCar(n) such that any positive definite irreducible symmetrizable integer Cartan matrix in M-n(Z), with n <= 9, is strongly Gram Z-congruent with a matrix of the list, see Theorem 4.3. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Symmetrizable integer Cartan matrix Integral quadratic form Edge-bipartite graph Dynkin graph Quasi-Cartan matrix inflation algorithm Gram congruence Coxeter spectrum

来源：评论

学校读者我要写书评

暂无评论

Root systems and inflations of non-negative quasi-Cartan matrices

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2019年 580卷 128-165页

作者： Makuracki, Bartosz Mroz, Andrzej Nicolaus Copernicus Univ Ul Chopina 12-18 PL-87100 Torun Poland

Cartan matrices, quasi-Cartan matrices and associated integral quadratic forms and root systems play an important role in such areas like Lie theory, representation theory and algebraic graph theory. We study quasi-Cartan matrices by means of the inflation algorithm, an idea used in Ovsienko's classical proof of the classification of positive definite integral quadratic forms and recently applied in several other classification results. We prove that it is enough to perform linear number of inflations to reduce positive or non-negative principal quasi-Cartan matrix to its canonical form, i.e., to the Cartan matrix of a Dynkin or Euclidean diagram, respectively. Moreover, we show that in the positive case the length of every sequence of inflations has quadratic bound, and that the only other "natural" non-negative class having such universal bound is the class of so-called pos-sincerely principal quasi-Cartan matrices (and in this case the bound is linear). We obtain such low bounds by applying, among others, some new observations on the properties of the reduced root systems (in the sense of Bourbaki) associated with positive quasi-Cartan matrices. (C) 2019 Published by Elsevier Inc.

关键词： Quasi-Cartan matrix inflation algorithm Edge-bipartite graph Gram congruence Coxeter matrix Integral quadratic form Dynkin diagram Euclidean diagram Root system

来源：评论

学校读者我要写书评

暂无评论

A Coxeter spectral classification of positive edge-bipartite graphs I. Dynkin types B_n, C_n, F₄, g₂, E₆, E₇, E₈

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2018年 557卷 105-133页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

We develop a computational technique for classification of a class of signed graphs (called edge-bipartite graphs), we started in Simson (2013) [42] and Bocian et al. (2014) [6]. Here we mainly study finite positive Cox-regular edge-bipartite graphs Delta (bigraphs, for short), with n >= 2 vertices, by means of the non-symmetric Gram matrix G(Delta) is an element of M-n(Z) defining Delta, and the complex spectrum specc(Delta)subset of S-1:= {z is an element of C, vertical bar z vertical bar = 1} of the Coxeter matrix Cox(Delta) := -G(Delta).G(Delta)(-tr) is an element of M-n,(Z), called the Coxeter spectrum of Delta. The bigraph Delta is said to be positive if the symmetric Gram matrix G(Delta) = 1/2 (G(Delta) + G(Delta)(tr)) is an element of M-n(Z) is positive definite. Our aim is to classify such edge-bipartite graphs, up to the strong Gram Z-congruence Delta approximate to z Delta', where Delta approximate to z Delta' means that G(Delta)', = B-tr .G(Delta).B, for some B is an element of M-n(Z) with det B = +/- 1. Our main result of the paper asserts that, given a pair Delta Delta' of Cox-regular connected positive edge-bipartite graphs with at least one loop, there is a congruence Delta approximate to z Delta' if and only if specc(Delta) = specc(Delta), and det G(Delta) = det G(Delta),. Moreover, given n >= 2, we present a list of five types of pairwise non-congruent bigraphs such that any Cox-regular connected positive bigraph with a loop and n >= 2 vertices is strongly Z-congruent with a bigraph of the list. Our main idea used in the proof is a reduction of the classification problem to the problem of computing the orbits of a finite set Mors(n) subset of M-n(Z) of integer matrix morsifications of the antichain S-n, consisting of n vertices, with respect to the right Gram action (A, B) bar right arrow A(*)B: = B(tr)A.B of the integral orthogonal group O(n, Z) on Mors(n). The computational technique developed in the paper allows also to construct a symbolic algo

关键词： Integral quadratic form Edge-bipartite graph Dynkin graph Quasi-Cartan matrix inflation algorithm Gram congruence Coxeter spectrum

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：