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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si1.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=d6fbcf371b5830cac807f51417f7d4b9" title="Click to view the MathML source">m+2≥3class="mathContainer hidden">class="mathCode">$m+2\ge 3$ vertices (a class of signed graphs), started in Simson (2013) [49], by means of the non-symmetric Gram matrix class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si2.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=28f17beda0cedc8e9e14850e3fd0e1c8">class="imgLazyJSB inlineImage" height="20" width="112" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si2.gif">class="mathContainer hidden">class="mathCode">${\check{G}}_{\mathrm{\Delta }}\in {\mathbb{M}}_{m+2}(\mathbb{Z})$ of Δ, its symmetric Gram matrix class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si3.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=624f31a8a16c7efe1da257a904ae7e8b">class="imgLazyJSB inlineImage" height="22" width="236" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si3.gif">class="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si4.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=8a8ff4478dc51b497ea0d8ffceb14d9c" title="Click to view the MathML source">q_Δ:Z^m+2→Zclass="mathContainer hidden">class="mathCode">$q_{\mathrm{\Delta }}:{\mathbb{Z}}^{m+2}\to \mathbb{Z}$, and the Coxeter spectrum class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si5.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=8c68adabde7342e3161cd499e0dcfc0f" title="Click to view the MathML source">specc_Δ⊂Cclass="mathContainer hidden">class="mathCode">${\mathbf{specc}}_{\mathrm{\Delta }}\subset \mathbb{C}$, i.e., the complex spectrum of the Coxeter matrix class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si6.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=cee1250dc3ba5bd3d8d0eff0be0a2aef">class="imgLazyJSB inlineImage" height="22" width="257" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si6.gif">class="mathContainer hidden">class="mathCode">${\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si7.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=a0b236a1c14e8d4275d57f492c8ee71d" title="Click to view the MathML source">G_Δ∈M_m+2(Z)class="mathContainer hidden">class="mathCode">$G_{\mathrm{\Delta }}\in {\mathbb{M}}_{m+2}(\mathbb{Z})$ of Δ is positive semi-definite of rank class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si148.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=5071719696daec1c973ea4d388cb8500" title="Click to view the MathML source">m≥1class="mathContainer hidden">class="mathCode">$m\ge 1$. One of our aims is to get a complete classification of all connected corank-two loop-free edge-bipartite graphs Δ, with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si1.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=d6fbcf371b5830cac807f51417f7d4b9" title="Click to view the MathML source">m+2≥3class="mathContainer hidden">class="mathCode">$m+2\ge 3$ vertices, up to the weak Gram class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si119.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=bf2111f5c78ebfbf718d7127b8be4a89" title="Click to view the MathML source">Zclass="mathContainer hidden">class="mathCode">$\mathbb{Z}$-congruence class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si10.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=71575927ee505c4899655b122390b5eb" title="Click to view the MathML source">Δ∼_ZΔ^′class="mathContainer hidden">class="mathCode">$\mathrm{\Delta }{\sim }_{\mathbb{Z}}{\mathrm{\Delta }}^{\prime }$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si10.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=71575927ee505c4899655b122390b5eb" title="Click to view the MathML source">Δ∼_ZΔ^′class="mathContainer hidden">class="mathCode">$\mathrm{\Delta }{\sim }_{\mathbb{Z}}{\mathrm{\Delta }}^{\prime }$ means that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si11.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=61d95bde8838a12e60de43fc67701256" title="Click to view the MathML source">G_Δ^′=B^tr⋅G_Δ⋅Bclass="mathContainer hidden">class="mathCode">$G_{{\mathrm{\Delta }}^{\prime }}=B^{tr}\cdot G_{\mathrm{\Delta }}\cdot B$, for some class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si12.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=cfa48a78c80646ecc14f0fa818b80035" title="Click to view the MathML source">B∈M_m+2(Z)class="mathContainer hidden">class="mathCode">$B\in {\mathbb{M}}_{m+2}(\mathbb{Z})$ such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si13.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=9c4f137a6897b9c914b03d3b709e824b" title="Click to view the MathML source">det⁡B=±1class="mathContainer hidden">class="mathCode">$\det B=\pm 1$. By one-vertex extensions of the simply laced Euclidean diagrams class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si14.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=e4ccb0c6f2d0ed62b2acc6442e4a07e4">class="imgLazyJSB inlineImage" height="18" width="25" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si14.gif">class="mathContainer hidden">class="mathCode">${\tilde{\mathbb{A}}}_m$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si148.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=5071719696daec1c973ea4d388cb8500" title="Click to view the MathML source">m≥1class="mathContainer hidden">class="mathCode">$m\ge 1$, class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si15.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=25f4f6bcbbf0345ddb8a09b233064209">class="imgLazyJSB inlineImage" height="18" width="25" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si15.gif">class="mathContainer hidden">class="mathCode">${\tilde{\mathbb{D}}}_m$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si16.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=aa89c3743d35f1c03f2d15a2c6633d43" title="Click to view the MathML source">m≥4class="mathContainer hidden">class="mathCode">$m\ge 4$, class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si17.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=663886cdbef833fc799896dee248f540">class="imgLazyJSB inlineImage" height="19" width="71" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si17.gif">class="mathContainer hidden">class="mathCode">${\tilde{\mathbb{E}}}_6,{\tilde{\mathbb{E}}}_7,{\tilde{\mathbb{E}}}_8$, we construct a family of connected loop-free corank-two diagrams class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si18.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=60084ad51a3736d8b89b88fba2c5a079">class="imgLazyJSB inlineImage" height="21" width="171" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951600166X-si18.gif">class="mathContainer hidden">class="mathCode">${\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si1.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=d6fbcf371b5830cac807f51417f7d4b9" title="Click to view the MathML source">m+2≥3class="mathContainer hidden">class="mathCode">$m+2\ge 3$ vertices, up to the weak Gram class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si119.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=bf2111f5c78ebfbf718d7127b8be4a89" title="Click to view the MathML source">Zclass="mathContainer hidden">class="mathCode">$\mathbb{Z}$-congruence class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si10.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=71575927ee505c4899655b122390b5eb" title="Click to view the MathML source">Δ∼_ZΔ^′class="mathContainer hidden">class="mathCode">$\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si149.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=fb9bdfb932532ba9c863b2e623a01846" title="Click to view the MathML source">Δ^′class="mathContainer hidden">class="mathCode">${\mathrm{\Delta }}^{\prime }$, that is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si119.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=bf2111f5c78ebfbf718d7127b8be4a89" title="Click to view the MathML source">Zclass="mathContainer hidden">class="mathCode">$\mathbb{Z}$-congruent with a simply laced Dynkin diagram class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si20.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=1f802968c9b815edfa0dcdc1745dc534" title="Click to view the MathML source">Dyn_Δclass="mathContainer hidden">class="mathCode">${\mathrm{Dyn}}_{\mathrm{\Delta }}$ (called the Dynkin type of Δ) such that Δ is a two-point extension class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si21.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=25c162ac10c49dc59e5828fb3fad356a" title="Click to view the MathML source">Δ^′[[u,w]]class="mathContainer hidden">class="mathCode">${\mathrm{\Delta }}^{\prime }[[u,w]]$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si149.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=fb9bdfb932532ba9c863b2e623a01846" title="Click to view the MathML source">Δ^′class="mathContainer hidden">class="mathCode">${\mathrm{\Delta }}^{\prime }$ along two roots class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si22.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=851b854a79c140d25788ba25ca61935a" title="Click to view the MathML source">u,wclass="mathContainer hidden">class="mathCode">$u,w$ of the positive definite Gram form class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si23.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=81bdcc5ad8395bae831029b3de8fb94e" title="Click to view the MathML source">q_Δ^′:Z^m→Zclass="mathContainer hidden">class="mathCode">$q_{{\mathrm{\Delta }}^{\prime }}:{\mathbb{Z}}^m\to \mathbb{Z}$. This yields a combinatorial algorithm class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si24.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=8b40dc86789f67b2710ea487e778117b" title="Click to view the MathML source">(Δ^′,u,w)↦Δ^′[[u,w]]class="mathContainer hidden">class="mathCode">$({\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si1.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=d6fbcf371b5830cac807f51417f7d4b9" title="Click to view the MathML source">m+2≥3class="mathContainer hidden">class="mathCode">$m+2\ge 3$ vertices and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si170.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=9218e8a8268f28915ed15c6c31cc4012" title="Click to view the MathML source">D=Dyn_Δclass="mathContainer hidden">class="mathCode">$D={\mathrm{Dyn}}_{\mathrm{\Delta }}$, from the triples class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si26.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=3d41d9ad01d5d76b4c424e8cfa9c63bc" title="Click to view the MathML source">(Δ^′,u,w)class="mathContainer hidden">class="mathCode">$({\mathrm{\Delta }}^{\prime },u,w)$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si149.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=fb9bdfb932532ba9c863b2e623a01846" title="Click to view the MathML source">Δ^′class="mathContainer hidden">class="mathCode">${\mathrm{\Delta }}^{\prime }$ is positive of the Dynkin type D  , and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si22.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=851b854a79c140d25788ba25ca61935a" title="Click to view the MathML source">u,wclass="mathContainer hidden">class="mathCode">$u,w$ are roots of the positive definite Gram form class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951600166X&_mathId=si23.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=81bdcc5ad8395bae831029b3de8fb94e" title="Click to view the MathML source">q_Δ^′:Z^m→Zclass="mathContainer hidden">class="mathCode">$q_{{\mathrm{\Delta }}^{\prime }}:{\mathbb{Z}}^m\to \mathbb{Z}$.