A Gram classification of non-negative corank-two loop-free edge-bipartite graphs

详细信息    查看全文

• 作者：Marcin Gąsiorek ^{mgasiorek@mat.umk.pl" class="auth_mail" title="E-mail the corresponding author} ; Daniel Simson ; ^{simson@mat.umk.pl" class="auth_mail" title="E-mail the corresponding author} ; Katarzyna Zając ^{zajac@mat.umk.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C22 ; 05C50 ; 06A11 ; 15A63 ; 68R05 ; 68W30
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 July 2016
• 年：2016
• 卷：500
• 期：Complete
• 页码：88-118
• 全文大小：801 K

文摘

We continue the Coxeter spectral study of finite connected loop-free edge-bipartite graphs Δ, with m+2≥3$m+2\ge 3$ vertices (a class of signed graphs), started in Simson (2013) [49], by means of the non-symmetric Gram matrix ${\check{G}}_{\mathrm{\Delta }}\in {\mathbb{M}}_{m+2}(\mathbb{Z})$ of Δ, its symmetric Gram matrix $G_{\mathrm{\Delta }}:=\frac{1}{2}[{\check{G}}_{\mathrm{\Delta }}+{\check{G}}_{\mathrm{\Delta }}^{tr}]\in {\mathbb{M}}_{m+2}(\frac{1}{2}\mathbb{Z})$, the Gram quadratic form q_Δ:Z^m+2→Z$q_{\mathrm{\Delta }}:{\mathbb{Z}}^{m+2}\to \mathbb{Z}$, and the Coxeter spectrum specc_Δ⊂C${\mathbf{specc}}_{\mathrm{\Delta }}\subset \mathbb{C}$, i.e., the complex spectrum of the Coxeter matrix ${\mathrm{Cox}}_{\mathrm{\Delta }}:=-{\check{G}}_{\mathrm{\Delta }}\cdot {\check{G}}_{\mathrm{\Delta }}^{-tr}\in \mathrm{Gl}(m+2,\mathbb{Z})$. In the present paper we study non-negative edge-bipartite graphs of corank two, in the sense that the symmetric Gram matrix G_Δ∈M_m+2(Z)$G_{\mathrm{\Delta }}\in {\mathbb{M}}_{m+2}(\mathbb{Z})$ of Δ is positive semi-definite of rank m≥1$m\ge 1$. One of our aims is to get a complete classification of all connected corank-two loop-free edge-bipartite graphs Δ, with m+2≥3$m+2\ge 3$ vertices, up to the weak Gram Z$\mathbb{Z}$-congruence 05c4899655b122390b5eb" title="Click to view the MathML source">Δ∼_ZΔ^′$\mathrm{\Delta }{\sim }_{\mathbb{Z}}{\mathrm{\Delta }}^{\prime }$, where 05c4899655b122390b5eb" title="Click to view the MathML source">Δ∼_ZΔ^′$\mathrm{\Delta }{\sim }_{\mathbb{Z}}{\mathrm{\Delta }}^{\prime }$ means that G_Δ^′=B^tr⋅G_Δ⋅B$G_{{\mathrm{\Delta }}^{\prime }}=B^{tr}\cdot G_{\mathrm{\Delta }}\cdot B$, for some B∈M_m+2(Z)$B\in {\mathbb{M}}_{m+2}(\mathbb{Z})$ such that det⁡B=±1$\det B=\pm 1$. By one-vertex extensions of the simply laced Euclidean diagrams ${\tilde{\mathbb{A}}}_m$, m≥1$m\ge 1$, ${\tilde{\mathbb{D}}}_m$, m≥4$m\ge 4$, ${\tilde{\mathbb{E}}}_6,{\tilde{\mathbb{E}}}_7,{\tilde{\mathbb{E}}}_8$, we construct a family of connected loop-free corank-two diagrams ${\tilde{\mathbb{A}}}_m^{(2)},{\tilde{\mathbb{D}}}_m^{(2)},{\tilde{\mathbb{E}}}_6^{(2)},{\tilde{\mathbb{E}}}_7^{(2)},{\tilde{\mathbb{E}}}_8^{(2)}$ (called simply extended Euclidean diagrams) such that they classify all connected corank-two loop-free edge-bipartite graphs Δ, with m+2≥3$m+2\ge 3$ vertices, up to the weak Gram Z$\mathbb{Z}$-congruence 05c4899655b122390b5eb" title="Click to view the MathML source">Δ∼_ZΔ^′$\mathrm{\Delta }{\sim }_{\mathbb{Z}}{\mathrm{\Delta }}^{\prime }$. A structure of connected corank-two loop-free edge-bipartite graphs Δ is described. It is shown that every such Δ contains a connected positive edge-bipartite subgraph Δ^′${\mathrm{\Delta }}^{\prime }$, that is Z$\mathbb{Z}$-congruent with a simply laced Dynkin diagram Dyn_Δ${\mathrm{Dyn}}_{\mathrm{\Delta }}$ (called the Dynkin type of Δ) such that Δ is a two-point extension Δ^′[[u,w]]${\mathrm{\Delta }}^{\prime }[[u,w]]$ of Δ^′${\mathrm{\Delta }}^{\prime }$ along two roots u,w$u,w$ of the positive definite Gram form q_Δ^′:Z^m→Z$q_{{\mathrm{\Delta }}^{\prime }}:{\mathbb{Z}}^m\to \mathbb{Z}$. This yields a combinatorial algorithm (Δ^′,u,w)↦Δ^′[[u,w]]$({\mathrm{\Delta }}^{\prime },u,w)\mapsto {\mathrm{\Delta }}^{\prime }[[u,w]]$ allowing us to construct all connected corank-two loop-free edge-bipartite graphs Δ, with m+2≥3$m+2\ge 3$ vertices and c4012" title="Click to view the MathML source">D=Dyn_Δ$D={\mathrm{Dyn}}_{\mathrm{\Delta }}$, from the triples (Δ^′,u,w)$({\mathrm{\Delta }}^{\prime },u,w)$, where Δ^′${\mathrm{\Delta }}^{\prime }$ is positive of the Dynkin type D  , and u,w$u,w$ are roots of the positive definite Gram form q_Δ^′:Z^m→Z$q_{{\mathrm{\Delta }}^{\prime }}:{\mathbb{Z}}^m\to \mathbb{Z}$.