论文标题
图形的非交叉粘结poset
The Noncrossing Bond Poset of a Graph
论文作者
论文摘要
分区晶格和非交叉分区晶格是组合学的对象进行了充分研究。在顶点集合$ \ {1,2，\ dots，n \} $上的图形$ g $，其债券晶格，$ l_g $，是分区晶格的子座，该子晶格是通过限制限制块的块诱导连接子g $的分区而形成的。在本文中，我们介绍了债券晶格的自然非交叉类似物，即$ nc_g $ $ nc_g $，通过限制限制在$ l_g $的非交叉分区而获得的。 非交叉分区晶格和键晶格都有许多不错的组合性能。我们表明，对于几个图形家庭，非交叉键盘也表现出这些特性。我们在图上介绍了简单的必要条件，以确保非交叉粘结poset是晶格。此外，对于几个图的家族，我们给出了Möbius函数和非交叉键Poset的特征多项式的组合描述。这些描述是根据图形的非破裂电路（NBC）集的非交叉类似物的角度来看，可以将其视为惠特尼（Whitney）的NBC定理的非交叉版本，用于色度多项式。我们还考虑了非交叉粘结poset的可壳性和超透明性，为两者提供了足够的条件。我们以一些开放的问题结尾。
The partition lattice and noncrossing partition lattice are well studied objects in combinatorics. Given a graph $G$ on vertex set $\{1,2,\dots, n\}$, its bond lattice, $L_G$, is the subposet of the partition lattice formed by restricting to the partitions whose blocks induce connected subgraphs of $G$. In this article, we introduce a natural noncrossing analogue of the bond lattice, the noncrossing bond poset, $NC_G$, obtained by restricting to the noncrossing partitions of $L_G$. Both the noncrossing partition lattice and the bond lattice have many nice combinatorial properties. We show that, for several families of graphs, the noncrossing bond poset also exhibits these properties. We present simple necessary and sufficient conditions on the graph to ensure the noncrossing bond poset is a lattice. Additionally, for several families of graphs, we give combinatorial descriptions of the Möbius function and characteristic polynomial of the noncrossing bond poset. These descriptions are in terms of a noncrossing analogue of non-broken circuit (NBC) sets of the graphs and can be thought of as a noncrossing version of Whitney's NBC theorem for the chromatic polynomial. We also consider the shellability and supersolvability of the noncrossing bond poset, providing sufficient conditions for both. We end with some open problems.
