Distinguishability and Linear Independence for $H$-Chromatic Symmetric Functions

Basic Information

• Paper ID: 2511.08665
• Title: Distinguishability and linear independence for $H$-chromatic symmetric functions
• Authors: Shao Yuan Lin, Laura Pierson
• Classification: math.CO (Combinatorics)
• Publication Date: November 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.08665

Abstract

This paper investigates $H$-chromatic symmetric functions $X_G^H$, which generalize classical chromatic symmetric functions (CSF) $X_G$ to track graph homomorphisms from graph $G$ to graph $H$. The research focuses on: (1) whether self-chromatic symmetric functions $X_G^G$ can distinguish different trees, verifying that all trees with up to 12 vertices can be distinguished; (2) proving that self-CSF distinguishes trees from non-trees (with only one exception); (3) analyzing power sum expansions for complete bipartite graphs and proving the $p$-monotonicity conjecture; (4) constructing multiple bases for symmetric function spaces using $H$-CSF; (5) introducing the concept of $H$-chromatic polynomials.

Research Background and Motivation

Problem Background

1. Generalization of Classical Chromatic Symmetric Functions: Stanley introduced chromatic symmetric functions $X_G$ in 1995, generalizing the chromatic polynomial of a graph to symmetric functions. Eagles et al. further generalized this in 2022 to $H$-chromatic symmetric functions $X_G^H$, defined as: $X_G^H(x_1, x_2, \ldots) := \sum_{f:G\to H} \sum_{\phi:V(H)\to\{1,2,\ldots,|V(H)|\}} \prod_{v\in V(G)} x_{\phi(f(v))}$ where $f$ is a graph homomorphism and $\phi$ is a vertex labeling.
2. Distinguishability Problem: A central question is the discriminative power of $H$-CSF as a graph invariant. For classical CSF, it is known that it cannot distinguish all graphs, but it is conjectured to distinguish all trees. For $H$-CSF, particularly the self-CSF $X_G^G$, its distinguishing capability remains unclear.

Research Significance

1. Graph Homomorphism Theory: Graph homomorphisms are fundamental concepts in combinatorics and theoretical computer science. $H$-CSF provides new tools for studying homomorphism structures.
2. Symmetric Function Theory: Investigating whether $H$-CSF can form bases for symmetric function spaces enriches the theory of symmetric functions.
3. Graph Invariants: Developing more refined graph invariants is important for graph isomorphism problems and graph classification.

Limitations of Existing Methods

1. Limitations of Classical CSF: It is known that different graphs can have the same CSF (e.g., Stanley's example).
2. Unknowns about $H$-CSF: Eagles et al. proposed several conjectures that remain unresolved, including:
   • Whether self-CSF distinguishes all trees
   • The $p$-monotonicity of $\omega(X_G^H)$
   • Whether $H$-CSF for fixed $H$ (non-complete graphs) can construct bases

Core Contributions

1. Distinguishing Power of Self-CSF:
   • Proves that self-CSF distinguishes trees from non-trees, with only the exception $X_{P_3}^{P_3} = X_{K_1\sqcup K_2}^{K_1\sqcup K_2}$
   • Verifies computationally using Sage that all trees with up to 12 vertices can be distinguished by self-CSF
   • Proves that self-CSF determines the number of legs in spider graphs and the degree sequence in caterpillar graphs
2. Power Sum Expansion Theory:
   • Proves that when $H=S_{n+1}$ (star graph) and $n$ is sufficiently large, $\omega(X_G^{S_{n+1}})$ is $p$-monotone
   • Provides explicit power sum expansion formulas for $H=K_{2,n}$ and $H=K_{m,n}$
3. Construction of Symmetric Function Bases:
   • Proves that self-CSF of complete multipartite graphs form a basis for $\Lambda$
   • Constructs multiple methods for $H$-CSF to form bases for $\Lambda^n$ with fixed $H$ (non-complete graphs)
   • Proves that for $n\geq 12$, fixed $G$ (even allowing loops) cannot construct a basis for $\Lambda^n$
4. $H$-Chromatic Polynomials:
   • Defines $H$-chromatic polynomial $\chi_G^H(k) := X_G^H(1^k)$ and proves it is indeed a polynomial
   • Provides explicit formulas and studies its relationship with $H$-CSF

Detailed Methodology

Task Definition

Study the following properties of $H$-chromatic symmetric functions $X_G^H$:

• Input: Two graphs $G$ and $H$
• Output: Symmetric function $X_G^H \in \Lambda$
• Objective: Analyze the distinguishing capability, algebraic structure, and combinatorial meaning of $X_G^H$

Core Methodology

1. Self-CSF Analysis Method

Endomorphism Analysis for Bipartite Graphs (Proposition 2.2.1): For a connected bipartite graph $G$ with bipartition $V(G) = V_k \sqcup V_{n-k}$, by analyzing coefficients $[m^n_{n-k,k-\ell+1,1^{\ell-1}}]X_G^G$ one can recover the first $k$ terms of the star sequence, namely $\sum_{v\in V(G)} \binom{\deg(v)}{\ell}$.

Key Technical Innovation:

• Exploits the property that graph homomorphisms must preserve bipartite structure
• Uses inclusion-exclusion principle to compute specific types of homomorphisms
• Establishes direct connections between monomial coefficients and graph structure parameters

2. Power Sum Expansion Technique

Star Graph Case (Lemma 3.1.2): For $H=S_{n+1}$, when $n$ is sufficiently large: $X_G^{S_{n+1}} = \sum_{(b_1,\ldots,b_\ell)\in\{1,2\}^\ell} n! \sum_{j=k_1^{b_1}+\cdots+k_\ell^{b_\ell}}^{|V(G)|} (-1)^{j-(k_1^{b_1}+\cdots+k_\ell^{b_\ell})} p_{j,1^{|V(G)|-j}} \cdots$

$p$-Monotonicity Proof Strategy:

1. Express power sum coefficients as sums over bipartite partitions of connected components
2. Apply the $\omega$ map: $\omega(p_\lambda) = (-1)^{|\lambda|-\ell(\lambda)}p_\lambda$
3. Prove that all nonzero coefficients have the same sign $(-1)^{k_2^1+\cdots+k_2^\ell}$

3. Basis Construction Method

Complete Multipartite Graph Basis (Proposition 4.1.1): Proves that $\{X_{K_\lambda}^{K_\lambda} : \lambda \vdash n\}$ forms a basis for $\Lambda$ by:

• Observing that the shortest monomial length in $X_{K_\lambda}^{K_\lambda}$ is $\ell(\lambda)$
• Establishing a triangular transition matrix with the monomial basis $\{m_\lambda\}$

Basis Construction for Fixed $H$ (Proposition 4.2.2): When $H$ is a disjoint union of cliques with at least one clique of size $\geq 3$, one can construct a basis by:

• For each $\lambda$, constructing $G_\lambda$ as a disjoint union of complete multipartite graphs
• Using strict control of monomial lengths to establish triangularity

Technical Innovations

1. Type Analysis Framework: Introduces the concept of "homomorphisms of type $\lambda$," i.e., homomorphisms whose preimage sizes form partition $\lambda$, providing a unified combinatorial interpretation.
2. Refined Application of Inclusion-Exclusion: In power sum expansions, not only considers which vertices are used but also how they are labeled, deriving precise coefficient formulas.
3. Spectral Radius Approximation (Proposition 2.4.10): For spider graph $T_\lambda$, proves $|\text{End}(T_\lambda)| = 2^{\ell(\lambda)}\rho^{n-1}(\|x_0\|_{\ell(\lambda)}^{\ell(\lambda)}\|x_0\|_1^{e(\lambda)}\|x_1\|_1^{o(\lambda)} + \cdots) + o(\rho^{n-1})$ where $\rho$ is the spectral radius and $x$ is the eigenvector.
4. Dimension Arguments: By projecting to the length-2 monomial subspace, proves the non-existence of bases for fixed $G$ (Proposition 4.3.1).

Experimental Setup

Computational Tools

• Sage Mathematical Software: Used for computing $H$-CSF and verifying conjectures
• Implementation Details: Authors provide Sage function implementations in a GitHub repository

Verification Scope

1. Tree Distinguishability (Proposition 2.3.1):
   • Verified all trees with 10-12 vertices
   • For cases with computation timeout, used automorphism group size and sum of squared degrees as auxiliary criteria
   • Specially handled two 12-vertex spider graphs $T_1$ and $T_2$
2. Basis Existence (§4.2):
   • Computed $p_H(n)$ (proportion of graphs $H$ that allow basis construction) for $n=3,4,5,6$
   • Results: $p_H(2)=0.5, p_H(3)=0.5, p_H(4)\approx 0.636, p_H(5)\approx 0.794, p_H(6)\approx 0.885$

Numerical Evidence

Tables show the trend of $p_H(n)$ growth with $n$, suggesting $p_H(n)\to 1$ as $n\to\infty$, though the growth rate remains undetermined.

Experimental Results

Main Results

1. Self-CSF Distinguishes Trees:
   • ✓ All non-isomorphic trees with 12 vertices can be distinguished by self-CSF
   • ✓ Self-CSF distinguishes trees from non-trees (except for $P_3$ and $K_1\sqcup K_2$)
   • ✓ Self-CSF determines the number of connected components in forests (except for the same exception)
2. Power Sum Monotonicity:
   • ✓ For $H=S_{n+1}$, when $n\geq k_1^1+\cdots+k_\ell^1$, $\omega(X_G^{S_{n+1}})$ is $p$-monotone
   • ✓ All $p_{\lambda}$ terms (with $\ell(\lambda)=m$) in $\omega(X_G^{K_{m,n}})$ have the same sign
3. Basis Construction:
   • ✓ Self-CSF of complete multipartite graphs form a basis for $\Lambda$
   • ✓ Multiple choices of $H$ (including $n$-cliques, disjoint unions of cliques, paths with loops, etc.) allow construction of bases for $\Lambda^n$
   • ✗ Certain $H$ (e.g., disjoint unions with few edges, $K_n$ with deleted edges) do not allow basis construction
   • ✗ For $n\geq 12$, fixed $G$ cannot construct a basis (even allowing loops)

Key Theorems

Proposition 2.3.2 (Distinguishing Trees from Non-Trees): If $T$ is a tree and $X_T^T = X_G^G$, then $G$ is also a tree, except when $T=P_3$ and $G=K_1\sqcup K_2$.

Proof Sketch:

1. Prove $G$ must be bipartite using monomial length
2. Analyze edge count relationship: $|E(G)| \cdot 2^{\kappa(G)} = (n-1) \cdot 2$
3. Derive $\kappa(G)\leq 2$ and verify only the special case $n=3$ is exceptional

Proposition 3.1.1 ($p$-Monotonicity): When $n\geq k_1^1+\cdots+k_\ell^1$, all $p$-coefficients of $\omega(X_G^{S_{n+1}})$ have the same sign.

Proposition 4.3.1 (Impossibility for Fixed $G$): For $n\geq 12$, there do not exist a graph $G$ and a collection of graphs $\{H_\lambda\}$ such that $\{X_{H_\lambda}^G\}$ spans $\Lambda^n$.

Case Studies

Example 2.1.3 (Graphs with Same CSF but Different Self-CSF): Stanley's two 5-vertex graphs have the same CSF, but:

• Left graph has 8 automorphisms (can swap two triangles, flip each triangle)
• Right graph has only 2 automorphisms (can only swap two diagonal vertices)
• Therefore $[m_1^5]X_{\text{left}}^{\text{left}} = 8 \neq 2 = [m_1^5]X_{\text{right}}^{\text{right}}$

Example 6.1.6 ($H$-Chromatic Polynomial): For $H=C_4$ (4-cycle) and $G$ a bipartite tree (with partition sizes $a,b$): $\chi_G^H(k) = 16k(k-1) + (2^{a+2}+2^{b+2}-16)k(k-1)(k-2) + (2^{a+b+1}-2^{a+2}-2^{b+2}+8)k(k-1)(k-2)(k-3)$

Related Work

Chromatic Symmetric Function Theory

1. Stanley (1995): Introduced classical CSF $X_G$, proved $\omega(X_G)$ is $p$-positive
2. Cho & van Willigenburg (2016): Constructed chromatic bases, proved CSF spans $\Lambda^n$
3. Crew & Spirkl (2020, 2021): Developed weighted CSF theory and complete multipartite graph bases

$H$-CSF Theory

1. Eagles et al. (2022): Introduced $H$-CSF, proposed several conjectures:
   • Self-CSF distinguishes trees
   • $p$-monotonicity
   • Basis existence problems
2. Advances in This Paper:
   • Partially proved the tree distinguishability conjecture (up to 12 vertices)
   • Proved $p$-monotonicity under sufficiently large $H$ conditions
   • Systematically answered questions about basis construction possibilities

Graph Homomorphism Theory

1. Bonato & Prałat (2009): Cores and endomorphisms of random graphs
2. Erdős & Rényi (1963): Asymptotically almost all graphs are asymmetric
3. This paper uses these results to prove most graph pairs have the same self-CSF (Corollary 2.1.2)

Spectral Graph Theory

1. Oliveira et al. (2018): Spectral radius ordering of spider graphs
2. This paper applies spectral methods to endomorphism counting (Proposition 2.4.10)

Conclusions and Discussion

Main Conclusions

1. Distinguishing Capability: Self-CSF exhibits strong distinguishing power on trees and forests, supporting the conjecture of Eagles et al.
2. Algebraic Structure: Power sum expansions have good properties in the complete bipartite graph case, and $p$-monotonicity holds under appropriate conditions.
3. Basis Theory: $H$-CSF can form bases for symmetric function spaces, but requires careful choice of $H$ or $G$.
4. Polynomial Generalization: $H$-chromatic polynomials are natural generalizations of chromatic polynomials, containing richer information.

Limitations

1. Computational Complexity:
   • Computing $X_T^T$ for high-degree trees may timeout ($|\text{End}(T)| \geq d^d$ for vertices of degree $d$)
   • Limits verification capability for larger trees
2. Condition Requirements:
   • $p$-monotonicity requires $H$ to be "sufficiently large" ($|V(H)|\geq k_1^1+\cdots+k_\ell^1$)
   • Basis construction imposes strict structural requirements on $H$
3. Exceptional Cases:
   • $X_{P_3}^{P_3} = X_{K_1\sqcup K_2}^{K_1\sqcup K_2}$ is unique but important
   • Suggests complete characterization may require handling small graphs specially
4. Unresolved Problems:
   • Complete tree distinguishability conjecture remains unproven (only verified up to 12 vertices)
   • Basis existence for fixed $G$ with $n=8$ to $11$ undetermined
   • Asymptotic behavior of $p_H(n)$ undetermined

Future Directions

1. Open Problems (Explicitly Stated in Paper):
   • Question 2.4.11: Does self-CSF distinguish all sufficiently large spider graphs?
   • Question 4.2.9: Complete characterization of which $H$ allow constructing bases for $\Lambda^{|V(H)|}$
   • Question 4.2.10: Asymptotic behavior of $p_H(n)$ (conjectured $p_H(n)\to 1$)
   • Question 4.3.6: Can fixed $G$ construct bases for $n=8$ to $11$?
   • Question 6.2.1: For given $H$, which graphs have the same $\chi_G^H$ but different $X_G^H$?
2. Methodological Extensions:
   • Generalize spectral methods to broader tree families
   • Develop more efficient $H$-CSF computation algorithms
   • Explore relationships between $H$-CSF and other graph invariants
3. Theoretical Deepening:
   • Study combinatorial interpretations of $H$-CSF
   • Establish deletion-contraction relations for $H$-chromatic polynomials
   • Explore applications of $H$-CSF to graph isomorphism problems

In-Depth Evaluation

Strengths

1. Solid Theoretical Contributions:
   • Systematically advances multiple conjectures proposed by Eagles et al.
   • Provides complete proofs and counterexamples
   • Establishes new theoretical frameworks (e.g., type analysis, spectral methods)
2. Methodological Innovation:
   • Cleverly combines combinatorial, algebraic, and spectral methods
   • Refined application of inclusion-exclusion techniques
   • Concise and powerful dimension arguments
3. Sufficient Computational Verification:
   • Large-scale verification using Sage
   • Provides reproducible code
   • Numerical evidence supports theoretical conjectures
4. Clear Presentation:
   • Well-organized structure, progressing from specific to general
   • Abundant examples and illustrations
   • Clearly marked open problems

Weaknesses

1. Computational Limitations:
   • Tree verification only up to 12 vertices (limited by computational capacity)
   • Some results require "sufficiently large" assumptions without explicit bounds
2. Exception Handling:
   • The exception $P_3$ and $K_1\sqcup K_2$ appears repeatedly across multiple theorems
   • While authors acknowledge this, lacks deeper explanation for why this is the only exception
3. Systematicity of Basis Construction:
   • Construction in Proposition 4.2.2 is quite technical
   • Lacks unified characterization conditions
   • Computation of $p_H(n)$ only up to $n=6$
4. Insufficient Application Discussion:
   • Primarily focuses on theoretical properties
   • Lacks discussion of applications of $H$-CSF to practical graph theory problems

Impact

1. Academic Contribution:
   • Significantly advances $H$-CSF theory
   • Provides new perspective for symmetric function theory
   • Establishes deep connections between graph homomorphisms and symmetric functions
2. Methodological Value:
   • Spectral methods in combinatorial counting can be generalized
   • Type analysis framework applicable to other graph invariants
3. Openness:
   • Proposes multiple explicit open problems
   • Points directions for future research
   • Provides reproducible computational tools

Applicable Scenarios

1. Theoretical Research:
   • Graph homomorphism theory
   • Symmetric function theory
   • Algebraic combinatorics
2. Computational Applications:
   • Graph invariant computation
   • Graph classification and recognition
   • Symmetry analysis in combinatorial optimization
3. Educational Use:
   • Demonstrates integrated application of combinatorial, algebraic, and spectral methods
   • Provides rich examples and computational instances

References

Key references include:

1. Stanley (1995): "A symmetric function generalization of the chromatic polynomial of a graph" - Pioneering work introducing chromatic symmetric functions
2. Eagles et al. (2022): "H-chromatic symmetric functions" - Direct predecessor of this paper, proposing main conjectures
3. Cho & van Willigenburg (2016): "Chromatic bases for symmetric functions" - Theory of chromatic bases
4. Crew & Spirkl (2020, 2021): Work on weighted CSF and complete multipartite graph bases
5. Godsil & Royle (2001): "Algebraic Graph Theory" - Standard reference for spectral graph theory

Overall Assessment: This is a high-quality theoretical paper in combinatorics that makes substantial advances in $H$-chromatic symmetric function theory. The authors systematically address multiple questions posed by predecessors, employing diverse and profound proof techniques with sufficient computational verification. While certain results require technical assumptions and the main conjecture remains incompletely resolved, the paper establishes a solid foundation for future research in this field. Particularly noteworthy are the authors' clear articulation of open problems and candid discussion of limitations.