\documentclass[11pt]{article}

\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage[margin=1in]{geometry}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\id}{\operatorname{id}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\FF}{\mathbb{F}}

\title{A counterexample to ordering-independence for chromatic operators}
\author{GPT-5.6 Sol, prompted and edited by Darij Grinberg}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
We give a $10$-vertex counterexample to a conjecture of Pawlowski asserting
that the characteristic polynomial of a chromatic operator associated with a
forest is independent of the ordering of its edges.  The two operators already
have different traces of fifth powers.
% Instead of constructing the $10!$-dimensional regular
% representation, it uses the $42$ Specht representations of $S_{10}$; the
% largest matrix involved has size only $768\times768$.
\end{abstract}

\section{The question}

Let $n$ be a nonnegative integer, and write $[n]=\{1,2,\ldots,n\}$.  We
encode a simple graph $F$ on the vertex set $[n]$ by its edge set, so that every edge is a
$2$-element subset of $[n]$.  If
\[
  \pi=(e_1,e_2,\ldots,e_m)
\]
is a linear ordering of the edges of $F$, define%
\footnote{Pawlowski includes an overall factor of $n!$ in the definition of the
chromatic operator.  Since multiplication by this nonzero scalar does not
affect whether the characteristic polynomials associated with two edge
orderings are equal, we omit it here.}
\begin{equation}
  \mathbf a_{F,\pi}
  =\prod_{r=1}^{m}(1-t_{e_r})\in\ZZ[S_n],
  \label{eq:def-a}
\end{equation}
where $t_{\{i,j\}}=(i\ j)\in S_n$, and where the factors in
\eqref{eq:def-a} are multiplied from left to right in the order prescribed by
$\pi$.

The \emph{characteristic polynomial} of an element $x\in\QQ[S_n]$ means the
characteristic polynomial of left multiplication by $x$ on the regular module
$\QQ[S_n]$.  Pawlowski's conjecture~\cite[Conjecture~1(a)]{Paw22} asks the
following.

\medskip
\noindent
\emph{If $F$ is a forest, is the characteristic polynomial of
$\mathbf a_{F,\pi}$ independent of the edge ordering $\pi$?}
\medskip

We answer this question in the negative.

\section{The counterexample}

Let $F$ be the tree whose spine is
\[
  10-9-5-4-3-1,
\]
with the additional leaves $2$ and $7$ attached to $1$, the leaf $6$
attached to $3$, and the leaf $8$ attached to $4$.  Thus,
\begin{equation}
% \begin{split}
 E(F)=\{\{5,9\},\{9,10\},\{1,3\},\{4,5\},\{3,6\},
 % \\
        \{1,2\},\{3,4\},\{4,8\},\{1,7\}\}.
% \end{split}
% \label{eq:tree}
\end{equation}
For compactness, write $ij$ for the edge $\{i,j\}$.  Consider the two edge
orderings
\begin{align}
 \pi_1&=(59,9\,10,13,45,36,12,34,48,17),
 \label{eq:pi1}\\
 \pi_2&=(59,9\,10,17,36,34,13,12,45,48).
 \label{eq:pi2}
\end{align}
Put $\mathbf a_i=\mathbf a_{F,\pi_i}$ for $i\in\{1,2\}$.

\begin{theorem}
The elements $\mathbf a_1$ and $\mathbf a_2$ have different characteristic
polynomials.  Concretely,
\begin{equation}
  [\id]\mathbf a_1^5=323917419
  \qquad\text{and}\qquad
  [\id]\mathbf a_2^5=323917499,
  \label{eq:fifth-counts}
\end{equation}
where $[\id]x$ denotes the coefficient of the identity permutation in
$x\in\ZZ[S_{10}]$.
(This entails that the traces of $\mathbf a_1^5$ and $\mathbf a_2^5$
differ, because the trace of any element $\mathbf a \in \ZZ[S_n]$
acting on the regular representation of $S_n$ is $n! [\id] \mathbf a$.
And thus, the characteristic polynomials of $\mathbf a_1$ and $\mathbf a_2$
must differ as well.)
\end{theorem}

The first five identity coefficients are as follows.
\begin{center}
\begin{tabular}{c@{\qquad}r@{\qquad}r}
\toprule
$k$ & $[\id]\mathbf a_1^k$ & $[\id]\mathbf a_2^k$\\
\midrule
$1$ & $1$         & $1$\\
$2$ & $65$        & $65$\\
$3$ & $7922$      & $7922$\\
$4$ & $1417045$   & $1417045$\\
$5$ & $3239174\textbf{19}$ & $3239174\textbf{99}$\\
\bottomrule
\end{tabular}
\end{center}

Before giving the verification, we record two elementary reductions.

\begin{lemma}[Subword interpretation]
Let $w=(t_1,t_2,\ldots,t_m)$ be any word of transpositions, and put
\[
  a_w=(1-t_1)(1-t_2)\cdots(1-t_m).
\]
For every nonnegative integer $k$, the coefficient $[\id]a_w^k$ is the
number of subwords of the concatenated word $w^k$ whose product is the
identity.  In particular,
\begin{equation}
  0\leq [\id]a_w^k\leq 2^{mk}.
  \label{eq:subword-bound}
\end{equation}
\end{lemma}

\begin{proof}
Expand the $mk$ factors in $a_w^k$.  Choosing either $1$ or the transposition
term from each factor is the same as choosing a subword of $w^k$.  A chosen
subword of length $r$ has coefficient $(-1)^r$.  If its product is the
identity, then $r$ is even, since every transposition is odd.  Hence every
identity subword contributes $+1$, and there is no cancellation.  This proves
both assertions.
\end{proof}

\begin{lemma}[Fourier inversion at the identity]\label{lem:fourier}
For each partition $\lambda\vdash n$, let $\rho^\lambda$ be the corresponding
irreducible representation of $S_n$, and let $f^\lambda$ be its dimension.
Then every $x\in\QQ[S_n]$ satisfies
\begin{equation}
 n![\id]x
 =\sum_{\lambda\vdash n}f^\lambda
   \tr\!\left(\rho^\lambda(x)\right).
 \label{eq:fourier}
\end{equation}
\end{lemma}

\begin{proof}
The left-hand side is the trace of left multiplication by $x$ on the regular
module $\QQ[S_n]$.  The regular module decomposes as
\[
  \QQ[S_n]\cong\bigoplus_{\lambda\vdash n}
       (S^\lambda)^{\oplus f^\lambda}.
\]
Taking traces gives \eqref{eq:fourier}.
\end{proof}

Applying \eqref{eq:fourier} avoids the $10!$-dimensional regular
representation.  There are only $42$ partitions of $10$, and
the largest possible dimension of an irreducible representation
of $S_{10}$ is $\max_{\lambda\vdash10}f^\lambda=768$.
Thus, when computing the identity coefficient $[\id]x$ of an
element $x\in\QQ[S_n]$ using Lemma~\ref{lem:fourier}, we only
need to deal with matrices of size at most $768\times768$
(namely, the matrices $\rho^\lambda(x)$). Moreover, if $x$ is
a $k$-th power $a^k$ of some $a \in \QQ[S_n]$, then
$\rho^\lambda(x) = \rho^\lambda(a^k) = (\rho^\lambda(a))^k$,
so that we need not compute $x$ itself but can get by with
computing the $k$-th power of the matrix $\rho^\lambda(a)$.
This makes the coefficients $[\id]\mathbf a_1^5$ and
$[\id]\mathbf a_2^5$ realistically computable. 

Here is the complete SageMath code that performs this
computation.  It uses Sage's built-in graph,
partition, permutation, matrix, and Specht-representation functionality.

\begin{verbatim}
"""
Exact SageMath verification of a counterexample to Pawlowski's
ordering-independence conjecture for chromatic operators.

Run with:
    sage pawlowski_counterexample.sage

The computation uses all 42 Specht representations of S_10, not the
10!-dimensional regular representation.  Its largest matrix is 768 by 768.
"""

from sage.all import *
from sage.combinat.symmetric_group_representations import \
    SymmetricGroupRepresentations

n = 10

# The tree is the path 10-9-5-4-3-1, with leaves 2 and 7 at 1,
# leaf 6 at 3, and leaf 8 at 4.
order_1 = [
    (5, 9), (9, 10), (1, 3), (4, 5), (3, 6),
    (1, 2), (3, 4), (4, 8), (1, 7),
]
order_2 = [
    (5, 9), (9, 10), (1, 7), (3, 6), (3, 4),
    (1, 3), (1, 2), (4, 5), (4, 8),
]
edges = set(order_1)

# Elementary checks on the input.
assert set(order_2) == edges
G = Graph(list(edges))
assert G.vertices(sort=True) == list(range(1, n + 1))
assert G.is_tree()

K = QQ


def transposition(i, j):
    """Return (i j) as a Sage permutation in one-line notation."""
    w = list(range(1, n + 1))
    w[i - 1], w[j - 1] = w[j - 1], w[i - 1]
    return Permutation(w)


# Load Sage's integral Specht models.  The identity
#
#   n! [1]x = sum_{lambda |- n} f^lambda tr(rho^lambda(x))
#
# is the decomposition of the regular character.
representations = SymmetricGroupRepresentations(
    n, "specht", ring=K, cache_matrices=False
)
# regular_traces will be a list of traces of A1^k and A2^k
# on the regular representation of S_n, for all
# k \in {1, 2, 3, 4, 5}, where A1 and A2 are the actions
# of the two products of 1 - t's in the two orders.
regular_traces = [[K.zero() for _ in range(6)] for _ in range(2)]
dimensions = [] # will be the list of the dimensions f^\lambda

for lam in Partitions(n):
    rho = representations(lam) # the Specht module for partition lam

    # Compute each transposition matrix only once for this partition.
    T = {e: rho(transposition(*e)) for e in edges}
    d = next(iter(T.values())).nrows() # the dimension of rho
    dimensions.append(d)
    I = identity_matrix(K, d)

    def chromatic_operator(order): # action of order-operator on rho
        A = I
        for e in order:
            A = A * (I - T[e])
        return A

    A = [chromatic_operator(order_1), chromatic_operator(order_2)]
    for which in range(2):
        power = A[which]
        for k in range(1, 6):
            regular_traces[which][k] += K(d) * power.trace()
            if k < 5:
                power = power * A[which]

# Sanity checks on the irreducible dimensions.
assert len(dimensions) == Partitions(n).cardinality() == 42
assert max(dimensions) == 768
assert sum(d^2 for d in dimensions) == factorial(n)

# Divide the regular trace by 10! to obtain the identity coefficient.
# All computations are exact over QQ.
coefficients = []
for which in range(2):
    row = []
    for k in range(1, 6):
        residue = regular_traces[which][k] / K(factorial(n))
        row.append(QQ(residue))
    coefficients.append(row)

expected = [
    [1, 65, 7922, 1417045, 323917419],
    [1, 65, 7922, 1417045, 323917499],
]
assert coefficients == expected

print("identity coefficients for order 1:", coefficients[0])
print("identity coefficients for order 2:", coefficients[1])
print("difference of fifth coefficients:",
      coefficients[1][4] - coefficients[0][4])

\end{verbatim}

The output is
\begin{verbatim}
identity coefficients for order 1: [1, 65, 7922, 1417045, 323917419]
identity coefficients for order 2: [1, 65, 7922, 1417045, 323917499]
difference of fifth coefficients: 80
\end{verbatim}
This proves \eqref{eq:fifth-counts}.

Finally, for any $x\in\QQ[S_{10}]$, the trace of its left-regular action is
$10![\id]x$.  Hence
\[
 \tr(L_{\mathbf a_2}^5)-\tr(L_{\mathbf a_1}^5)
 =10!\cdot80=290304000\neq0.
\]
Two endomorphisms with the same characteristic polynomial have equal traces
of all powers.  Therefore $L_{\mathbf a_1}$ and $L_{\mathbf a_2}$ have
different characteristic polynomials, as claimed.

\begin{remark}
For a faster certificate that only disproves equality, one may work over
finite fields whose characteristic is larger than $10$.
However, in the SageMath version used for this computation, the Specht-representation
implementation did not work over the desired finite fields, so we used
exact rational arithmetic instead.
\end{remark}

\begin{thebibliography}{1}

\bibitem[Paw22]{Paw22}
Brendan Pawlowski,
\emph{Chromatic symmetric functions via the group algebra of $S_n$},
Algebraic Combinatorics \textbf{5} (2022), no.~1, 1--20;
\href{https://arxiv.org/abs/1802.05470}{arXiv:1802.05470}.

\end{thebibliography}

\end{document}