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

设为首页

收藏本站

网站地图 | English | 公务邮箱

读者指南

学术客户端

NSTL服务站

科技查新

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 ve&_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≥3

verflow="scroll"> m + 2 \geq 3

vertices (a class of signed graphs), started in Simson (2013) [49], by means of the non-symmetric Gram matrix ve&_eid=1-s2.0-S002437951600166X&_mathId=si2.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=28f17beda0cedc8e9e14850e3fd0e1c8">

verflow="scroll"> {ver accent="true"> G ˇ ver>}_{Δ} \in M_{m + 2} (Z)

of Δ, its symmetric Gram matrix ve&_eid=1-s2.0-S002437951600166X&_mathId=si3.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=624f31a8a16c7efe1da257a904ae7e8b">

verflow="scroll"> G_{Δ} : = \frac{1}{2} [{ver accent="true"> G ˇ ver>}_{Δ} + {ver accent="true"> G ˇ ver>}_{Δ}^{t r}] \in M_{m + 2} (\frac{1}{2} Z)

, the Gram quadratic form ve&_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→Z

verflow="scroll"> q_{Δ} : Z^{m + 2} \to Z

, and the Coxeter spectrum ve&_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_Δ⊂C

verflow="scroll"> {specc}_{Δ} \subset C

, i.e., the complex spectrum of the Coxeter matrix ve&_eid=1-s2.0-S002437951600166X&_mathId=si6.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=cee1250dc3ba5bd3d8d0eff0be0a2aef">

verflow="scroll"> {Cox}_{Δ} : = - {ver accent="true"> G ˇ ver>}_{Δ} \cdot {ver accent="true"> G ˇ ver>}_{Δ}^{- t r} \in Gl (m + 2, Z)

. In the present paper we study non-negative edge-bipartite graphs of corank two, in the sense that the symmetric Gram matrix ve&_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)

verflow="scroll"> G_{Δ} \in M_{m + 2} (Z)

of Δ is positive semi-definite of rank ve&_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≥1

verflow="scroll"> m \geq 1

. One of our aims is to get a complete classification of all connected corank-two loop-free edge-bipartite graphs Δ, with ve&_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≥3

verflow="scroll"> m + 2 \geq 3

vertices, up to the weak Gram ve&_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">Z

verflow="scroll"> Z

-congruence ve&_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Δ^′

verflow="scroll"> Δ \sim_{Z} Δ^{'}

, where ve&_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Δ^′

verflow="scroll"> Δ \sim_{Z} Δ^{'}

means that ve&_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_Δ⋅B

verflow="scroll"> G_{Δ^{'}} = B^{t r} \cdot G_{Δ} \cdot B

, for some ve&_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)

verflow="scroll"> B \in M_{m + 2} (Z)

such that ve&_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=±1

verflow="scroll"> \det B = \pm 1

. By one-vertex extensions of the simply laced Euclidean diagrams ve&_eid=1-s2.0-S002437951600166X&_mathId=si14.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=e4ccb0c6f2d0ed62b2acc6442e4a07e4">

verflow="scroll"> {ver accent="true"> A ˜ ver>}_{m}

, ve&_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≥1

verflow="scroll"> m \geq 1

, ve&_eid=1-s2.0-S002437951600166X&_mathId=si15.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=25f4f6bcbbf0345ddb8a09b233064209">

verflow="scroll"> {ver accent="true"> D ˜ ver>}_{m}

, ve&_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≥4

verflow="scroll"> m \geq 4

, ve&_eid=1-s2.0-S002437951600166X&_mathId=si17.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=663886cdbef833fc799896dee248f540">

verflow="scroll"> {ver accent="true"> E ˜ ver>}_{6}, {ver accent="true"> E ˜ ver>}_{7}, {ver accent="true"> E ˜ ver>}_{8}

, we construct a family of connected loop-free corank-two diagrams ve&_eid=1-s2.0-S002437951600166X&_mathId=si18.gif&_user=111111111&_pii=S002437951600166X&_rdoc=1&_issn=00243795&md5=60084ad51a3736d8b89b88fba2c5a079">

verflow="scroll"> {ver accent="true"> A ˜ ver>}_{m}^{(2)}, {ver accent="true"> D ˜ ver>}_{m}^{(2)}, {ver accent="true"> E ˜ ver>}_{6}^{(2)}, {ver accent="true"> E ˜ ver>}_{7}^{(2)}, {ver accent="true"> E ˜ ver>}_{8}^{(2)}

(called simply extended Euclidean diagrams) such that they classify all connected corank-two loop-free edge-bipartite graphs Δ, with ve&_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≥3

verflow="scroll"> m + 2 \geq 3

verflow="scroll"> Z

verflow="scroll"> Δ \sim_{Z} Δ^{'}

. 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 ve&_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">Δ^′

verflow="scroll"> Δ^{'}

, that is ve&_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">Z

verflow="scroll"> Z

-congruent with a simply laced Dynkin diagram ve&_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_Δ

verflow="scroll"> {Dyn}_{Δ}

(called the Dynkin type of Δ) such that Δ is a two-point extension ve&_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]]

verflow="scroll"> Δ^{'} [[u, w]]

of ve&_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">Δ^′

verflow="scroll"> Δ^{'}

along two roots ve&_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,w

verflow="scroll"> u, w

of the positive definite Gram form ve&_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→Z

verflow="scroll"> q_{Δ^{'}} : Z^{m} \to Z

. This yields a combinatorial algorithm ve&_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]]

verflow="scroll"> (Δ^{'}, u, w) \mapsto Δ^{'} [[u, w]]

allowing us to construct all connected corank-two loop-free edge-bipartite graphs Δ, with ve&_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≥3

verflow="scroll"> m + 2 \geq 3

vertices and ve&_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_Δ

verflow="scroll"> D = {Dyn}_{Δ}

, from the triples ve&_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)

verflow="scroll"> (Δ^{'}, u, w)

, where ve&_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">Δ^′

verflow="scroll"> Δ^{'}

is positive of the Dynkin type D , and ve&_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,w

verflow="scroll"> u, w

are roots of the positive definite Gram form ve&_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→Z

verflow="scroll"> q_{Δ^{'}} : Z^{m} \to Z

常见问题　|　交通位置　|　联系我们　|　OA远程办公

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700