gpt 6 astra ultra attempt on Math-1064

Does the chromatic symmetric function distinguish between trees?

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph and let $x_1,x_2,\ldots$ be commuting indeterminates. A proper colouring by positive integers is a function $f:V\to\mathbb Z_{>0}$ with $f(u)\neq f(v)$ whenever $uv\in E$. Define the chromatic symmetric function by the formal sum \[ X_G(x_1,x_2,\ldots) =\sum_{f\text{ proper}}\prod_{v\in V}x_{f(v)}. \] This is a homogeneous symmetric function of degree $|V|$. Every particular monomial has a finite coefficient, so no convergence of the infinite sum is required. Its coefficient records the number of proper colourings with the corresponding sizes of colour classes.

A tree is a finite connected graph without a cycle. The question asks whether two nonisomorphic trees can have the same chromatic symmetric function. In its affirmative-distinguishability form, the target assertion is \[ X_T=X_{T'}\quad\Longrightarrow\quad T\cong T' \qquad\text{for all finite trees }T,T'. \] Equality means coefficientwise equality in the same indeterminates; isomorphism means a vertex bijection preserving adjacency. Equality automatically forces the trees to have the same order, by homogeneity. The question therefore concerns information beyond the number of vertices. Specializing the first $q$ variables to one and all others to zero counts proper $q$-colourings, but the full symmetric function retains the separate colour-class sizes discarded by that specialization.

Short English statement

Does the full chromatic symmetric function distinguish every pair of nonisomorphic finite trees?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and plan.

Martin, Morin and Wagner [R1] develop the power-sum expansion and extract several tree invariants from it, including substantially stronger results than the elementary families treated here. We use that expansion with a complete proof of the relevant coefficient interpretation, then test a tempting simplification: retaining only the component sizes arising from deletion of a single edge. This distinguishes paths, stars and double-stars, but an explicit pair shows why it cannot reconstruct all trees. No claim of novelty is made for these restricted results.

Recovering the edge-cut data.

Write $p_j=\sum_i x_i^j$ and $p_\lambda=\prod_jp_{\lambda_j}$ for a partition $\lambda$. For $F\subseteq E(G)$ let $\lambda(F)$ be the partition of $|V|$ formed by the component sizes of $(V,F)$, counting isolated vertices. Inclusion-exclusion over edges whose endpoints receive the same colour gives \[ X_G=\sum_{F\subseteq E(G)}(-1)^{|F|}p_{\lambda(F)}. \] Indeed, requiring every edge of $F$ to be monochromatic forces exactly each connected component of $(V,F)$ to be monochromatic. Its freely chosen colour contributes $p_j$ when that component has $j$ vertices. Inclusion-exclusion removes every colouring that violates properness. The argument is coefficientwise, so it needs no convergence assumption.

If $G=T$ is an $n$-vertex tree, every spanning subgraph is a forest, and therefore $|F|=n-\ell(\lambda(F))$. All contributions to a fixed power-sum coefficient have the same sign: \[ [p_\lambda]X_T=(-1)^{n-\ell(\lambda)} \#\{F\subseteq E(T):\lambda(F)=\lambda\}. \] Since the power sums are a basis over $\mathbb Q$, equality of symmetric functions gives equality of all these integers. Partitions with exactly two parts correspond precisely to deleting one edge of $T$. Thus $X_T$ determines the multiset of unordered component-size pairs produced by every single-edge deletion.

Three families that the data reconstruct.

For $n\ge3$, the number of cuts of type $(n-1,1)$ is the number of leaves. Deleting a leaf edge gives such a cut, and a singleton component can only arise this way. At $n=2$ the sole cut has two singleton sides, so the two leaves should instead be handled directly.

A tree of order $n\ge3$ with $n-1$ leaves is a star: its sole remaining vertex must be adjacent to every leaf. A tree with precisely two leaves is a path, since the degree sum gives \[ \#\{v:d(v)=1\}=2+\sum_{d(v)\ge3}(d(v)-2), \] so no vertex can branch. Hence $X_T$ determines these trees among all trees, not just among previously specified stars or paths.

For $n\ge4$, a tree with $n-2$ leaves has exactly two internal vertices. They are adjacent, because the path between them cannot have a leaf as an intermediate vertex. Let $a,b\ge1$ be their respective numbers of pendant neighbours. All edges except the central edge produce singleton cuts; the central edge produces $(a+1,b+1)$. The single-edge cut multiset therefore recovers the unordered pair $\{a,b\}$ and hence the double-star. This also includes the four-vertex path without ambiguity.

An explicit obstruction to reconstruction from these cuts alone.

On vertices $0,\ldots,6$, consider the two trees with edge sets \[ \begin{split} E(T_1)&=\{01,02,03,04,15,56\},\\ E(T_2)&=\{01,02,03,14,15,26\}. \end{split} \] Their degree multisets are respectively $(4,2,2,1,1,1,1)$ and $(3,3,2,1,1,1,1)$, so they are nonisomorphic. In both, the smaller component sizes obtained from deleting the six edges are $(1,1,1,1,2,3)$. Thus all two-part coefficients agree. The full symmetric functions do distinguish them: the coefficient of $p_{(3,2,2)}$ is zero for $T_1$ and one for $T_2$. For $T_2$, keeping exactly $03,14,15,26$ gives components $\{0,3\}$, $\{1,4,5\}$ and $\{2,6\}$. This is the unique such subset: leaves $4,5$ force the three-vertex component through $1$, then leaves $3,6$ force the two remaining pairs. In $T_1$, leaves $2,3,4$ would all need to be joined to $0$ to avoid singleton components, producing a component of size at least four. Hence its coefficient of this type is zero.

Verification and final status.

The reproducible script scripts/check_attempt_batch02_algebra_2026_10_01.py enumerates all $2^6$ subsets of each displayed edge set, computes their connected components including isolated vertices, and checks both the cut-profile collision and the stated power-sum coefficients exactly. The collision concerns a discarded part of the invariant; it is not a counterexample to the catalogue question. UNRESOLVED. The first remaining gap is to reconstruct a general tree from the full multiset of component-size partitions. The two-part projection has been shown insufficient by an actual pair, so a general proof must use interactions among multiple deleted edges.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3150 (OPG-36880), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Does the chromatic symmetric function distinguish between trees?. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/does_the_symmetric_chromatic_function_distinguish_trees.

• R1 Jeremy L. Martin, Matthew Morin and Jennifer D. Wagner, On distinguishing trees by their chromatic symmetric functions. Primary author-hosted paper, including the power-sum expansion and reconstruction results; checked 1 October 2026. https://jeremymartinmath.github.io/papers/CSFTree.pdf.