论文标题
通过Tutte多项式证明了分层树的重量多项式的身份
Proving identities on weight polynomials of tiered trees via Tutte polynomials
论文作者
论文摘要
a {\ it s层图} $ g =（v，e）$带有$ m $ tiers是一个简单的图表，带有$ v \ subseteq \ brk {n} $，其中$ \ brk {n} = \ {1,2，\ {1,2，\ cdots，n \ cdots，n \} $，以及$ t $ t $ t $ t $ t $ br} $ v> v'$，然后$ t（v）> t（v'）$附近的$ v'$ in $ g $ in $ v'$ in $ g $。对于任何有序分区$ p =（p_1，p_2，\ cdots，p_m）$ $ n $的$，令$ \ sett_p $表示带有顶点$ \ brk {n} $的一组分层树，并用map $ t：$ t：\ brk {n}对于所有$ i = 1,2，\ ldots，m $。对于\ sett_p $中的任何$ t \，令$ k_t $表示完整的分层图，其顶点集和分层映射与$ t $相同。如果$ k_t $的边缘是按其终点订购的，那么$ t $的重量$ w（t）$是$ t $的外部活动，即$ k_t $，即，e（k_ {t}）\ setminus e（t）$ e $ e $ e $ e $ e $ e $ e $ n unique $ t in Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique the Unique ccyp the $ e（t）。令$ p_p（q）= \ sum_ {t \ in \ sett_ {p}} q^{w（t）} $。 Dugan，Glennon，Gunnells和Steingrímsson[J。组合。理论，Ser。 A 164（2019）pp。24-49]要求提供任何置换$π$ $ 1,2，\ cdots，m $，werr $π（p）= p_ {π（1）}，p_ {π（2）}，\ cdots，p_ {π（m）}）$。在本文中，我们将通过应用Tutte多项式来证明这种身份的扩展。此外，我们还提供了身份的证明$ p _ {（1，p_1，p_2）}（q）= p _ {（p_1+1，p_2+1）}（q）$ via tutte polynomials。
A {\it tiered graph} $G=(V,E)$ with $m $ tiers is a simple graph with $V\subseteq \brk{n}$, where $\brk{n}=\{1,2,\cdots,n\}$, and with a surjective map $t$ from $V$ to $\brk{m}$ such that if $v$ is a vertex adjacent to $v'$ in $G$ with $v>v'$, then $t(v) >t(v')$. For any ordered partition $p=(p_1,p_2,\cdots,p_m)$ of $n$, let $\sett_p$ denote the set of tiered trees with vertex set $\brk{n}$ and with a map $t: \brk{n}\rightarrow \brk{m}$ such that $|t^{-1}(i)|=p_i$ for all $i=1,2,\ldots,m$. For any $T\in \sett_p$, let $K_T$ denote the complete tiered graph whose vertex set and tiering map are the same as those of $T$. If the edges of $K_T$ are ordered lexicographically by their endpoints, then the weight $w(T)$ of $T$ is the external activity of $T$ in $K_T$, i.e., the number of edges $e\in E(K_{T})\setminus E(T)$ such that $e$ is the least element in the unique cycle determined by $T\cup e$. Let $P_p(q)=\sum_{T\in \sett_{p}}q^{w(T)}$. Dugan, Glennon, Gunnells and Steingrímsson [J. Combin. Theory, Ser. A 164 (2019) pp. 24-49] asked for an elementary proof of the identity $P_p(q)=P_{π(p)}(q)$ for any permutation $π$ of $1,2,\cdots,m$, where $π(p)=p_{π(1)},p_{π(2)},\cdots,p_{π(m)})$. In this article, we will prove an extension of this identity by applying Tutte polynomials. Furthermore, we also provide a proof of the identity $P_{(1,p_1,p_2)}(q)=P_{(p_1+1,p_2+1)}(q)$ via Tutte polynomials.
