Dahlberg–She–van Willigenburg conjecture

The conjecture says that the chromatic symmetric function XTX_T of any tree TT with a vertex of degree at least four has a negative elementary-basis coefficient. It appears as Conjecture 6.1 of Dahlberg, She, and van Willigenburg. The problem remains open in the sources checked.

Wolfgang's necessary condition for ee-positivity is that TT admits a connected partition of every type. Barth and Fournier and Tom exclude degree at least five and degree four with no leaf neighbor. Zheng and Tom exclude four-legged spiders. Tang, Wang, and Wang recently excluded all caterpillars of maximum degree four. Li formulates coefficient tests and related questions.

Coefficients using one part size with a single exception

Let d≥2d\ge2, 1≤r<d1\le r\lt d, and n=jd+rn=jd+r with j≥1j\ge1. For v∈V(T)v\in V(T), let gd(v)g_d(v) count edges whose component away from vv has order divisible by dd. Then

[eredj]XT=(−1)j∑v∈V(T)(1−d)gd(v).[e_r e_d^j]X_T=(-1)^j\sum_{v\in V(T)}(1-d)^{g_d(v)}. \tag{1}

There is also a formula for the sum of two coefficients:

[ed+redj−1]XT+[eredj]XT=r∑S(−1)j−c(S)−h(S)dc(S)(d−1)h(S).[e_{d+r}e_d^{j-1}]X_T+[e_re_d^j]X_T =r\sum_{S}(-1)^{j-c(S)-h(S)}d^{c(S)}(d-1)^{h(S)}. \tag{2}

Here SS ranges over connected vertex sets of order rr such that every component of T−ST-S has order divisible by dd. Write c(S)c(S) for the number of components. Write h(S)h(S) for the total number of edges within these components whose deletion splits their component into two sets of orders divisible by dd. Formula (2) evaluates the signed connected-partition sum in Li's Corollary 4.3 via divisibility of single-edge splits.

Proof of (1). Specialize to dd colors, with ed=1e_d=1, er=te_r=t, and all other elementary functions zero. At t=0t=0 the colors xix_i are the distinct roots of xd=(−1)d−1x^d=(-1)^{d-1}. For a tree of order kk rooted at ww, the sum of proper-coloring weights with root color xix_i is CwxikC_w x_i^k. The constant CwC_w is a product over edges of d−1d-1 if the subtree below that edge has order divisible by dd, and of −1-1 otherwise. This follows recursively from

∑h≠ixhℓ={(d−1)xiℓ,d∣ℓ,−xiℓ,d∤ℓ.\sum_{h\ne i}x_h^\ell = \begin{cases} (d-1)x_i^\ell,& d\mid\ell,\\ -x_i^\ell,& d\nmid\ell . \end{cases}

The colors as functions of tt are the roots of xd+(−1)rtxd−r+(−1)d=0x^d+(-1)^r t x^{d-r}+(-1)^d=0. At zero their derivatives are (−1)r+1xi1−r/d(-1)^{r+1}x_i^{1-r}/d. Differentiate the weight of each coloring by singling out one vertex vv. Condition on the color of vv and root the tree there. This gives a contribution (−1)r+1Cv∑ixin−r/d(-1)^{r+1}C_v\sum_i x_i^{n-r}/d. Now Cv=(−1)n−1−gd(v)(d−1)gd(v)C_v=(-1)^{n-1-g_d(v)}(d-1)^{g_d(v)} and xin−r=(−1)j(d−1)x_i^{n-r}=(-1)^{j(d-1)}, giving (1).

Proof of (2). This time specialize ed=1e_d=1 and ed+r=te_{d+r}=t, with the other elementary functions zero. There are dd colors tending to the same nonzero roots as before and rr colors tending to zero. At zero the derivative at each nonzero root is the negative of the corresponding derivative in the proof of (1), by implicit differentiation of xd+r+(−1)dxr+(−1)d+rt=0x^{d+r}+(-1)^dx^r+(-1)^{d+r}t=0. Colorings using only these dd colors therefore give the negative of (1) at the linear term.

As t→0+t\to0^+, divide the other rr colors by t1/rt^{1/r}. They are the roots of yr=(−1)r−1y^r=(-1)^{r-1} up to O(td/r)O(t^{d/r}) by the same polynomial and the simplicity of these limiting roots. For colorings using these colors exactly at the vertex set SS, the weight sum factors into the two chromatic symmetric functions of T[S]T[S] and T−ST-S, evaluated on their respective color families. All edges crossing SS join distinct families. If |S|>r|S|>r, the contribution is o(t)o(t) by homogeneity. If 0<|S|<r0\lt|S|\lt r, simultaneous rotation of the limiting small colors shows that the leading evaluation of XT[S]X_{T[S]} is zero. The error is O(t(|S|+d)/r)=o(t)O(t^{(|S|+d)/r})=o(t).

For |S|=r|S|=r, the coefficient contributed by the small colors is [er]XT[S][e_r]X_{T[S]}. It equals rr when T[S]T[S] is connected and vanishes otherwise. This follows from the power-sum expansion for a tree and multiplicativity over components. Each remaining component contributes zero unless its order is divisible by dd, again by rotation. For a component of order dj′dj' with h′h' internal edges splitting it into multiples of dd, the rooted-color formula gives the value d(−1)j′−1−h′(d−1)h′d(-1)^{j'-1-h'}(d-1)^{h'}. Multiplying over the components gives (2).

Matching forms for the coefficients using sizes two and three

Suppose nn is odd and TT has a matching missing a single vertex uu. Give vertices in the bipartition class of uu sign +1+1 and the others sign −1-1. Use uu as root. Then

[e3e2(n−3)/2]XT=−1+2deg(u)+∑w≠uwmatchedtoitsparentσ(w)2deg(w).[e_3 e_2^{(n-3)/2}] X_T = -1+2^{\deg(u)} +\sum_{\substack{w\ne u\\w\ \mathrm{matched\ to\ its\ parent}}}\sigma(w)2^{\deg(w)}. \tag{3}

The independent check of the earlier Li counterexample uses the corresponding two-color deletion calculation. The matching in (3) identifies exactly which vertices contribute, without enumerating their deletion forests. The two-color specialization has XT(y,z)=(yz)(n−1)/2(y+z)X_T(y,z)=(yz)^{(n-1)/2}(y+z), so [e1e2(n−1)/2]XT=1[e_1e_2^{(n-1)/2}]X_T=1. In (2) with r=1,d=2r=1,d=2, the deletion of a vertex w≠uw\ne u leaves components of even order exactly when uu and the mate of ww lie in the same component. That requires that the mate be the parent of ww. All other vertices are still matched. At the colors i,−ii,-i each even component with balanced bipartition contributes 2. The component containing the two unmatched vertices contributes −2-2 if they lie in the same bipartition class, which happens exactly when σ(w)=−1\sigma(w)=-1. Deleting uu leaves a perfectly matched forest and gives 2deg(u)2^{\deg(u)}. This proves (3).

If nn is even and TT has a perfect matching MM, there is a two-vertex formula:

[e32e2(n−6)/2]XT=n−∑w2deg(w)−1+∑{u,v}∈𝒫(−1)dist(u,v)−12deg(u)+deg(v)−1.[e_3^2 e_2^{(n-6)/2}]X_T = n-\sum_{w}2^{\deg(w)-1} +\sum_{\{u,v\}\in\mathcal P}(-1)^{\operatorname{dist}(u,v)-1} 2^{\deg(u)+\deg(v)-1}. \tag{4}

This applies for n≥6n\ge6. The pairs in 𝒫\mathcal P are nonadjacent vertices whose connecting path starts and ends with edges of MM.

To see this, use three colors z,y1,y2z,y_1,y_2 with y1+y2=−zy_1+y_2=-z and y1y2=1+z2y_1y_2=1+z^2. Then e1=0e_1=0, e2=1e_2=1, e3=z+z3e_3=z+z^3, so the coefficient of z2z^2 is the left side. With no vertex colored zz, the term is 2(1+z2)n/22(1+z^2)^{n/2}. With just ww colored zz, exactly one component of T−wT-w has one unmatched vertex and it contributes a factor y1+y2=−zy_1+y_2=-z. The other deg(w)−1\deg(w)-1 components are balanced, giving the second term. With two vertices u,vu,v colored zz, they must be nonadjacent. At z=0z=0 their two mates must lie in the same component or the product of the two-color evaluations is zero. This is exactly the path condition in 𝒫\mathcal P. The component with both mates contributes 22 if their bipartition classes differ and −2-2 otherwise. The remaining components are balanced. There are deg(u)+deg(v)−1\deg(u)+\deg(v)-1 components in total, giving (4).

An infinite family for Li's coefficient question

Problem 4.9 of Li asks if [e3e2(n−3)/2]XT[e_3e_2^{(n-3)/2}]X_T is always negative for an odd-order tree of maximum degree four with connected partitions of every type. The 31-vertex result in this collection already answers it in the negative, including the non-spider reading. Its source audit records an earlier spider counterexample from the work of Horňák–Woźniak and Zheng. The following calculation extends the non-spider obstruction to an infinite family.

Use the non-spider caterpillar GaG_a from Proposition 5.2 of Tang, Wang, and Wang. It consists of a central vertex vv with two leaves, a pendant path of length a−2a-2 from vv, and a neighbor ww of vv with one leaf and a pendant path of length aa. Path lengths count the vertices beyond the attaching vertex. The order is 2a+32a+3. The cited proposition proves that this tree has all connected partition types for a≡2mod4a\equiv2\bmod 4 and gcd(2a+3,15)=1\gcd(2a+3,15)=1, including a=60t+10a=60t+10 for every t≥0t\ge0.

Match vv to one of its leaves, ww to its leaf, and the two even paths in consecutive pairs. The unmatched vertex uu is the second leaf of vv. In (3), uu and the other leaf of vv contribute 22 each. The leaf of ww contributes −2-2. Along the length-aa path the downstairs endpoints of matching edges are in the positive class and contribute 2a−22a-2. Along the length-(a−2)(a-2) path they are in the negative class and contribute −2a+6-2a+6. Thus

[e3e2a]XGa=−1+2+2−2+(2a−2)+(−2a+6)=5.[e_3 e_2^{a}]X_{G_a}= -1+2+2-2+(2a-2)+(-2a+6)=5.

This also explains why the connected-partition information and this particular coefficient can both pass while the chromatic symmetric function has a negative coefficient elsewhere. The general conjecture still requires a sign obstruction for degree-four trees beyond the families already excluded.

The proposed odd-order reduction in Li's Problem 4.8 also fails. Horňák and Woźniak, Table 2 list the arbitrarily vertex-decomposable spider with arm orders (2,5,31,57)(2,5,31,57). The lengths beyond the central vertex are (1,4,30,56)(1,4,30,56), so this degree-four tree has even order 92. It has exactly one leaf adjacent to its center.

Trees with branching vertices separated by long paths

Take a tree HH with at least one edge. For each vertex vv of HH, put kv=degH(v)k_v=\deg_H(v) and choose a number ℓv\ell_v of additional leaves. Make TT by replacing every edge ee of HH by a path of length LeL_e and adjoining ℓv\ell_v pendant leaves directly to vv. Suppose every kv+ℓv≤4k_v+\ell_v\le4 and every vertex with kv+ℓv=4k_v+\ell_v=4 has ℓv≥1\ell_v\ge1.

  • There is an absolute constant CC such that XTX_T is not ee-positive if there is at least one degree-four vertex and every Le≥Clog|V(T)|L_e\ge C\log|V(T)|. The constant is independent of HH.
  • If the number of degree-four vertices is odd, the same conclusion holds for every Le≥150L_e\ge150.

This uses color transfer along paths, as in Tang, Wang, and Wang, together with the rank-one limit of that transfer. The logarithmic statement also handles even numbers of degree-four vertices by evaluating at an interior zero of one local factor.

Transfer and local factors

Use mm colors xix_i with elementary functions e1=0e_1=0, e2,…,em≥0e_2,\ldots,e_m\ge0, and ∑j=2m(j−1)ej=1\sum_{j=2}^m(j-1)e_j=1. Set Kij=1K_{ij}=1 for i≠ji\ne j, Kii=0K_{ii}=0, D=diag(xi)D=\operatorname{diag}(x_i) and P=KDP=KD. With the endpoints of a path of length LeL_e fixed at colors i,ji,j, the sum of the weights on its interior vertices is (PLe−1K)ij(P^{L_e-1}K)_{ij}. Directly attached leaves have weight sum −xi-x_i when the adjacent vertex has color ii. Thus the weight at a vertex of HH is xi(−xi)ℓvx_i(-x_i)^{\ell_v}.

Put R(z)=∏i(z+xi)R(z)=\prod_i(z+x_i) and J(z)=∑ixi/(z+xi)J(z)=\sum_i x_i/(z+x_i). Expanding the determinant of the diagonal matrix minus a rank-one matrix gives

det(zI−P)=R(z)(1−J(z))=zm−∑j=2m(j−1)ejzm−j.\det(zI-P)=R(z)(1-J(z))=z^m-\sum_{j=2}^m(j-1)e_jz^{m-j}.

In the specializations below, the eigenvalue 1 is simple and all other eigenvalues have modulus less than 1. For the four-color specialization this follows from strict positivity of e2,e3,e4e_2,e_3,e_4 and the triangle inequality in the displayed polynomial. Equality on the unit circle forces z=1z=1. The three-color specialization is checked explicitly below. Set bi=1/(1+xi)b_i=1/(1+x_i). The right and left eigenvectors are bib_i and xibix_i b_i, respectively, since J(1)=1J(1)=1. The left eigenvector multiplied by KK is the row b⊤b^\top. Write

Fk,ℓ=∑ixi(−xi)ℓbik,B2=F2,0.F_{k,\ell}=\sum_i x_i(-x_i)^\ell b_i^k,\qquad B_2=F_{2,0}.

The eigenprojection times KK is bb⊤/B2b b^\top/B_2. On a compact neighborhood of either positive four-color specialization used below there are constants M<∞M\lt \infty and 0<ρ<10\lt \rho\lt 1 with

B2PL−1K=bb⊤+EL,∥EL∥∞≤MρL.B_2P^{L-1}K=b b^\top+E_L,\qquad \|E_L\|_\infty\le M\rho^{L}. \tag{5}

For example, integrate the resolvent (zI−P)−1(zI-P)^{-1} against zL−1z^{L-1} on a fixed circle strictly between the other eigenvalues and 1 to bound the residual power. The color roots stay bounded, and R(1)>0R(1)>0 keeps all 1+xi1+x_i away from zero. These estimates are uniform over permutations of the color roots.

For reference, with B=R(1)B=R(1), differentiation of 1−J(z)=det(zI−P)/R(z)1-J(z)=\det(zI-P)/R(z) gives

F1,0=1,F2,0=∑jj(j−1)ejB,F3,0=∑jj(j−1)2ej2B.F_{1,0}=1,\qquad F_{2,0}=\frac{\sum_j j(j-1)e_j}{B},\qquad F_{3,0}=\frac{\sum_j j(j-1)^2 e_j}{2B}.

Here R′(1)=(m−1)BR'(1)=(m-1)B, since ∑jjej=B\sum_j j e_j=B. Using xibi=1−bix_i b_i=1-b_i, e1=0e_1=0, ∑ixi2=−2e2\sum_i x_i^2=-2e_2 and ∑ixi3=3e3\sum_i x_i^3=3e_3, the other needed factors are

F1,1=1,F2,1=F2,0−1,F1,2=1−2e2,F3,1=F3,0−F2,0,F2,2=F2,0−2,F1,3=1−2e2−3e3.F_{1,1}=1,\quad F_{2,1}=F_{2,0}-1,\quad F_{1,2}=1-2e_2,\quad F_{3,1}=F_{3,0}-F_{2,0},\quad F_{2,2}=F_{2,0}-2,\quad F_{1,3}=1-2e_2-3e_3 .

An absolute bound for odd parity

Use m=3m=3 and e2=e3=1/3e_2=e_3=1/3. The characteristic polynomial of PP is (z−1)(z2+z+2/3)(z-1)(z^2+z+2/3). The two other eigenvalues have modulus 2/3\sqrt{2/3}, mutual distance greater than 1, and distances greater than 1 from the eigenvalue 1. The three colors satisfy xi3+xi/3−1/3=0x_i^3+x_i/3-1/3=0, giving |xi|<0.9|x_i|\lt0.9, ∥P∥∞<2\|P\|_\infty\lt 2 and ∥b∥∞≤10\|b\|_\infty\le10. The two other spectral projections, written by Lagrange interpolation in PP, each have norm at most 9. Thus the difference between PtP^t and its rank-one limit is bounded by 18(2/3)t/218(2/3)^{t/2} in row-sum norm.

The local factors for total degree at most three are 1,8/5,7/5,1,3/5,1/31,8/5,7/5,1,3/5,1/3 in the order (1,0),(2,0),(3,0),(1,1),(2,1),(1,2)(1,0),(2,0),(3,0),(1,1),(2,1),(1,2). The factors for total degree four with ℓ≥1\ell\ge1 are −1/5,−2/5,−2/3-1/5,-2/5,-2/3 for (3,1),(2,2),(1,3)(3,1),(2,2),(1,3).

Root HH at any vertex. For a child with a path to its parent, the message to the parent is the vector of sums of coloring weights conditional on the parent's color, excluding the weight of the parent. We prove that each message can be written a(b+δ)a(b+\delta), with a nonzero real aa and ∥δ∥∞≤10−6\|\delta\|_\infty\le10^{-6}. Its sign is the product of the signs of the local factors in the corresponding subtree of HH.

Indeed, at a vertex vv, factor out the product of its child message scalars. The new conditional vector at vv is then Ui=xi(−xi)ℓv∏w(bi+δw,i)U_i=x_i(-x_i)^{\ell_v}\prod_w(b_i+\delta_{w,i}). The product has at most three factors. Its leading scalar after the transfer to the parent is b⊤U/B2b^\top U/B_2. The numerator differs from Fkv,ℓvF_{k_v,\ell_v} by at most 3⋅10⋅3⋅112⋅10−6<0.13\cdot10\cdot 3\cdot 11^2\cdot10^{-6}\lt0.1. All vectors are invariant under conjugation combined with permuting the conjugate color labels, so the scalar is real. Its modulus exceeds 1/161/16, since B2=8/5B_2=8/5 and |Fkv,ℓv|≥1/5|F_{k_v,\ell_v}|\ge1/5. The error in the message is bounded in norm by 18(2/3)(Le−1)/2⋅2⋅11318(2/3)^{(L_e-1)/2}\cdot 2\cdot 11^3. Dividing by the modulus of the scalar gives an error less than 10−610^{-6} when Le≥150L_e\ge150. These bounds also apply when the child product is empty. At the root the final sum uses ∑iUi\sum_i U_i, whose sign equals that of the root's local factor by the same product estimate. Hence the full specialization has sign (−1)s(-1)^s, where ss is the number of degree-four vertices. Negative evaluation at these nonnegative elementary values precludes ee-positivity.

A logarithmic bound for either parity

If a vertex has three directly attached leaves and total degree four, the tree has no matching covering all but at most one vertex. Wolfgang's connected-partition test then excludes ee-positivity using blocks of size two with at most one singleton. We may therefore assume all degree-four vertices have type (3,1)(3,1) or (2,2)(2,2).

Use m=4m=4. The normalization implies e2+2e3+3e4=1e_2+2e_3+3e_4=1, and the two degree-four factors simplify to

F3,1=−e2+6e4B,F2,2=−2e2+4e4B.F_{3,1}=\frac{-e_2+6e_4}{B},\qquad F_{2,2}=\frac{-2e_2+4e_4}{B}.

Choose one of these types that actually occurs. Set e4=1/30e_4=1/30 and choose e2=6e4e_2=6e_4 for the first type or e2=2e4e_2=2e_4 for the second. Determine e3e_3 by the normalization. These values are strictly positive. At this point the chosen local factor vanishes, the other does not vanish, and all factors for degree at most three are positive by the formulas above. Perturb e2e_2 by τ\tau and e3e_3 by −τ/2-\tau/2. The vanishing factor has a simple zero at τ=0\tau=0. Fix constants in (5) on a sufficiently small neighborhood along this curve.

Write N=|V(T)|N=|V(T)|, L=mineLeL=\min_e L_e, and Y(τ)=B2(τ)|E(H)|XT(e(τ))Y(\tau)=B_2(\tau)^{|E(H)|}X_T(e(\tau)). Expanding (5) at each edge gives a sum over subsets A⊆E(H)A\subseteq E(H) where the error is used. The term for A=⌀A=\varnothing is ∏vFkv,ℓv(τ)\prod_v F_{k_v,\ell_v}(\tau). If V(A)V(A) is the set of vertices incident to edges of AA, the absolute value of any term is at most

(M1ρL)|A|∏v∉V(A)|Fkv,ℓv(τ)|(M_1\rho^L)^{|A|}\prod_{v\notin V(A)}|F_{k_v,\ell_v}(\tau)| \tag{6}

with an absolute M1M_1. Every unexposed vertex contributes its exact local factor. At the exposed vertices, each color and each incident factor is bounded on the fixed neighborhood. There are at most 2|A|2|A| such vertices, each of degree at most four, so these bounds cost only a constant to the power |A||A|.

Let SS be the vertices of the vanishing type, s=|S|≥1s=|S|\ge1, and U=∏v∉S|Fkv,ℓv(0)|U=\prod_{v\notin S}|F_{k_v,\ell_v}(0)|. At τ=0\tau=0, contributions are possible only when V(A)⊇SV(A)\supseteq S, so |A|≥s/2|A|\ge s/2. The other factors are bounded away from zero, allowing the omitted exposed factors in (6) to be charged by increasing the absolute constant. Since |E(H)|≤N|E(H)|\le N, this yields

|Y(0)|≤2U(M2NρL)s/2|Y(0)|\le 2U(M_2N\rho^L)^{s/2}

once M2NρL<1/2M_2N\rho^L\lt1/2. At τ=1/N\tau=1/N, all factors have modulus at least c/Nc/N for some absolute c>0c>0. The contribution of the nonempty AA's is bounded relative to the empty term by (1+M3N2ρL)N−1(1+M_3N^2\rho^L)^N-1. The empty term has modulus at least c1U(c2/N)sc_1 U(c_2/N)^s, because each of the nonvanishing factors changes by a relative O(1/N)O(1/N). If L≥ClogNL\ge C\log N with a sufficiently large absolute CC, we have ρL≤N−6\rho^L\le N^{-6}. These estimates give |Y(0)|/|Y(1/N)|=o(1)|Y(0)|/|Y(1/N)|=o(1) uniformly, including when ss grows.

On the other hand, if XTX_T is ee-positive, the ratio of the values of each surviving monomial at τ=1/N\tau=1/N and τ=0\tau=0 is at most (1+C1/N)N(1+C_1/N)^N, since the sum of its exponents is at most NN. The zero variables are the same at both points. The ratio of the positive normalization factors B2|E(H)|B_2^{|E(H)|} is also bounded. Consequently 0<Y(1/N)≤C2Y(0)0\lt Y(1/N)\le C_2Y(0), which contradicts the estimates. All constants can be taken uniformly since there are just two choices of the vanishing type. Increasing the constant in the lower bound on LL handles the bounded range of NN.