The conjecture says that the chromatic symmetric function of any tree 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 -positivity is that 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 , , and with . For , let count edges whose component away from has order divisible by . Then
There is also a formula for the sum of two coefficients:
Here ranges over connected vertex sets of order such that every component of has order divisible by . Write for the number of components. Write for the total number of edges within these components whose deletion splits their component into two sets of orders divisible by . 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 colors, with , , and all other elementary functions zero. At the colors are the distinct roots of . For a tree of order rooted at , the sum of proper-coloring weights with root color is . The constant is a product over edges of if the subtree below that edge has order divisible by , and of otherwise. This follows recursively from
The colors as functions of are the roots of . At zero their derivatives are . Differentiate the weight of each coloring by singling out one vertex . Condition on the color of and root the tree there. This gives a contribution . Now and , giving (1).
Proof of (2). This time specialize and , with the other elementary functions zero. There are colors tending to the same nonzero roots as before and 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 . Colorings using only these colors therefore give the negative of (1) at the linear term.
As , divide the other colors by . They are the roots of up to by the same polynomial and the simplicity of these limiting roots. For colorings using these colors exactly at the vertex set , the weight sum factors into the two chromatic symmetric functions of and , evaluated on their respective color families. All edges crossing join distinct families. If , the contribution is by homogeneity. If , simultaneous rotation of the limiting small colors shows that the leading evaluation of is zero. The error is .
For , the coefficient contributed by the small colors is . It equals when 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 , again by rotation. For a component of order with internal edges splitting it into multiples of , the rooted-color formula gives the value . Multiplying over the components gives (2).
Matching forms for the coefficients using sizes two and three
Suppose is odd and has a matching missing a single vertex . Give vertices in the bipartition class of sign and the others sign . Use as root. Then
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 , so . In (2) with , the deletion of a vertex leaves components of even order exactly when and the mate of lie in the same component. That requires that the mate be the parent of . All other vertices are still matched. At the colors each even component with balanced bipartition contributes 2. The component containing the two unmatched vertices contributes if they lie in the same bipartition class, which happens exactly when . Deleting leaves a perfectly matched forest and gives . This proves (3).
If is even and has a perfect matching , there is a two-vertex formula:
This applies for . The pairs in are nonadjacent vertices whose connecting path starts and ends with edges of .
To see this, use three colors with and . Then , , , so the coefficient of is the left side. With no vertex colored , the term is . With just colored , exactly one component of has one unmatched vertex and it contributes a factor . The other components are balanced, giving the second term. With two vertices colored , they must be nonadjacent. At 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 . The component with both mates contributes if their bipartition classes differ and otherwise. The remaining components are balanced. There are components in total, giving (4).
An infinite family for Li's coefficient question
Problem 4.9 of Li asks if 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 from Proposition 5.2 of Tang, Wang, and Wang. It consists of a central vertex with two leaves, a pendant path of length from , and a neighbor of with one leaf and a pendant path of length . Path lengths count the vertices beyond the attaching vertex. The order is . The cited proposition proves that this tree has all connected partition types for and , including for every .
Match to one of its leaves, to its leaf, and the two even paths in consecutive pairs. The unmatched vertex is the second leaf of . In (3), and the other leaf of contribute each. The leaf of contributes . Along the length- path the downstairs endpoints of matching edges are in the positive class and contribute . Along the length- path they are in the negative class and contribute . Thus
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 . The lengths beyond the central vertex are , 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 with at least one edge. For each vertex of , put and choose a number of additional leaves. Make by replacing every edge of by a path of length and adjoining pendant leaves directly to . Suppose every and every vertex with has .
- There is an absolute constant such that is not -positive if there is at least one degree-four vertex and every . The constant is independent of .
- If the number of degree-four vertices is odd, the same conclusion holds for every .
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 colors with elementary functions , , and . Set for , , and . With the endpoints of a path of length fixed at colors , the sum of the weights on its interior vertices is . Directly attached leaves have weight sum when the adjacent vertex has color . Thus the weight at a vertex of is .
Put and . Expanding the determinant of the diagonal matrix minus a rank-one matrix gives
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 and the triangle inequality in the displayed polynomial. Equality on the unit circle forces . The three-color specialization is checked explicitly below. Set . The right and left eigenvectors are and , respectively, since . The left eigenvector multiplied by is the row . Write
The eigenprojection times is . On a compact neighborhood of either positive four-color specialization used below there are constants and with
For example, integrate the resolvent against on a fixed circle strictly between the other eigenvalues and 1 to bound the residual power. The color roots stay bounded, and keeps all away from zero. These estimates are uniform over permutations of the color roots.
For reference, with , differentiation of gives
Here , since . Using , , and , the other needed factors are
An absolute bound for odd parity
Use and . The characteristic polynomial of is . The two other eigenvalues have modulus , mutual distance greater than 1, and distances greater than 1 from the eigenvalue 1. The three colors satisfy , giving , and . The two other spectral projections, written by Lagrange interpolation in , each have norm at most 9. Thus the difference between and its rank-one limit is bounded by in row-sum norm.
The local factors for total degree at most three are in the order . The factors for total degree four with are for .
Root 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 , with a nonzero real and . Its sign is the product of the signs of the local factors in the corresponding subtree of .
Indeed, at a vertex , factor out the product of its child message scalars. The new conditional vector at is then . The product has at most three factors. Its leading scalar after the transfer to the parent is . The numerator differs from by at most . All vectors are invariant under conjugation combined with permuting the conjugate color labels, so the scalar is real. Its modulus exceeds , since and . The error in the message is bounded in norm by . Dividing by the modulus of the scalar gives an error less than when . These bounds also apply when the child product is empty. At the root the final sum uses , whose sign equals that of the root's local factor by the same product estimate. Hence the full specialization has sign , where is the number of degree-four vertices. Negative evaluation at these nonnegative elementary values precludes -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 -positivity using blocks of size two with at most one singleton. We may therefore assume all degree-four vertices have type or .
Use . The normalization implies , and the two degree-four factors simplify to
Choose one of these types that actually occurs. Set and choose for the first type or for the second. Determine 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 by and by . The vanishing factor has a simple zero at . Fix constants in (5) on a sufficiently small neighborhood along this curve.
Write , , and . Expanding (5) at each edge gives a sum over subsets where the error is used. The term for is . If is the set of vertices incident to edges of , the absolute value of any term is at most
with an absolute . 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 such vertices, each of degree at most four, so these bounds cost only a constant to the power .
Let be the vertices of the vanishing type, , and . At , contributions are possible only when , so . The other factors are bounded away from zero, allowing the omitted exposed factors in (6) to be charged by increasing the absolute constant. Since , this yields
once . At , all factors have modulus at least for some absolute . The contribution of the nonempty 's is bounded relative to the empty term by . The empty term has modulus at least , because each of the nonvanishing factors changes by a relative . If with a sufficiently large absolute , we have . These estimates give uniformly, including when grows.
On the other hand, if is -positive, the ratio of the values of each surviving monomial at and is at most , since the sum of its exponents is at most . The zero variables are the same at both points. The ratio of the positive normalization factors is also bounded. Consequently , 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 handles the bounded range of .