论文标题
斯坦利色对称函数的根系变体
A rooted variant of Stanley's chromatic symmetric function
论文作者
论文摘要
理查德·斯坦利（Richard Stanley）定义了图形$ g $的色度对称函数$ x_g $，并询问是否有非同构树$ t $和$ u $，带有$ x_t = x_u $。我们研究了根顶的色度图的色度对称函数的变体，在其中我们要求root顶点使用或避免使用指定的颜色。我们介绍了这些根系色的多项式满足的组合身份和递归，解释它们与尖的色函数的关系和扎根的$ u $ $ polynomials，并证明了三个主要定理。首先，对于所有非空连接图$ g $，Stanley的多项式$ x_g（x_1，\ ldots，x_n）$在$ \ mathbb {q} [x_1，\ ldots，x_n] $中均可在所有足够大的$ n $中。对于根节点必须避免指定的颜色，我们的根部变体的结果相同。我们通过艾森斯坦标准的新型组合应用证明了不可约性。其次，我们证明了斯坦利的猜想的根本版本：当且仅当其生根的色多项式相等时，两个生根的树是同构作为根部图。实际上，我们证明了根系色多项式的单变量专业化（通过设置$ x_0 = x_1 = q $，$ x_2 = x_2 = x_3 = 1 $，而$ x_n = 0 $ for $ n> 3 $）已经区分了根的树。第三，我们通过提供对尖体功能的单一扩展的组合解释来回答帕沃斯基的问题。
Richard Stanley defined the chromatic symmetric function $X_G$ of a graph $G$ and asked whether there are non-isomorphic trees $T$ and $U$ with $X_T=X_U$. We study variants of the chromatic symmetric function for rooted graphs, where we require the root vertex to either use or avoid a specified color. We present combinatorial identities and recursions satisfied by these rooted chromatic polynomials, explain their relation to pointed chromatic functions and rooted $U$-polynomials, and prove three main theorems. First, for all non-empty connected graphs $G$, Stanley's polynomial $X_G(x_1,\ldots,x_N)$ is irreducible in $\mathbb{Q}[x_1,\ldots,x_N]$ for all large enough $N$. The same result holds for our rooted variant where the root node must avoid a specified color. We prove irreducibility by a novel combinatorial application of Eisenstein's Criterion. Second, we prove the rooted version of Stanley's Conjecture: two rooted trees are isomorphic as rooted graphs if and only if their rooted chromatic polynomials are equal. In fact, we prove that a one-variable specialization of the rooted chromatic polynomial (obtained by setting $x_0=x_1=q$, $x_2=x_3=1$, and $x_n=0$ for $n>3$) already distinguishes rooted trees. Third, we answer a question of Pawlowski by providing a combinatorial interpretation of the monomial expansion of pointed chromatic functions.
