# Universal Paralinguistic Speech Representations using Self-Supervised
Conformers

###### Abstract

Many speech applications require understanding aspects beyond the words being
spoken, such as recognizing emotion, detecting whether the speaker is wearing
a mask, or distinguishing real from synthetic speech. In this work, we
introduce a new state-of-the-art paralinguistic representation derived from
large-scale, fully self-supervised training of a 600M+ parameter Conformer-
based architecture. We benchmark on a diverse set of speech tasks and
demonstrate that simple linear classifiers trained on top of our time-averaged
representation outperform nearly all previous results, in some cases by large
margins. Our analyses of context-window size demonstrate that, surprisingly, 2
second context-windows achieve 98% the performance of the Conformers that use
the full long-term context. Furthermore, while the best per-task
representations are extracted internally in the network, stable performance
across several layers allows a single universal representation to reach near
optimal performance on all tasks.

Index Terms—  speech, representation learning, self-supervised learning,
paralinguistics, transformer

##  1 Introduction

Powerful representations of data are useful in a number of ways. They improve
model performance on small datasets by transferring data-driven insights from
larger datasets. The models that create representations can also be used as
pre-training for improved performance. If the model that generates the
representation is non-reversible, then the representations can unlock
applications in some privacy-sensitive scenarios. In this paper, we
significantly improve state-of-the-art representations for paralinguistic
speech tasks.

There are a number of promising data-driven speech representations. Some
directions include self-supervised contrastive learning [1, 2, 3], predictive
coding [4, 5], masked-unit prediction [6], multi-task learning [7], multimodal
coincidence [8, 9], and intermediate representations from a supervised task
[10, 11]. One of the most promising objectives for representation learning for
speech recognition was proposed in the recent Wav2Vec 2.0 [12] framework,
which combined Transformers [13] and a self-supervised contrastive learning
objective [5]. The Wav2Vec 2.0 training objective was subsequently combined
with more powerful Conformer architectures, producing large improvements in
semi-supervised speech recognition applications [14, 15, 16]. This paper
explores the use of these Conformer-based models to define fixed
representations for non-ASR speech analysis and paralinguistics tasks. To
fully evaluate the potential of these models, we evaluate several model sizes
and pretraining datasets combinations.

Recent work to establish a common benchmark has made it possible to directly
compare speech representations [1, 17]. In this work, we use the Non-Semantic
Speech Benchmark (NOSS) [1], a collection of publicly available non-semantic
speech tasks including speech emotion recognition, language identification,
and speaker identification. Following [18], we include masked speech detection
[19]. We also include three new tasks: synthetic speech detection [20], an
additional speech emotion recognition dataset [21], and dysarthria
classification [22]. Our work further establishes the usefulness of these
embeddings over classical paralinguistic features, and can be used to improve
other transfer-learning speech applications like voice imitation [23] and
personalized ASR [24].

Finally, our work adds to the growing evidence that Transformer-based models
outperform convolutional neural networks on many tasks [25]. In this paper, we
explore the impact of context window size on performance. We show that
2-second context windows are sufficient for nearly all tasks, but further
context truncation can lead to large losses in performance. Furthermore, we
analyzed the range of embeddings produced by the sequence of Conformer blocks
that define the encoder, demonstrating stable performance over a large portion
of the network regardless of architecture complexity. Using Centered Kernel
Alignment (CKA) analysis [26, 25], we further demonstrate that the
representations defined by this range of blocks are surprisingly similar, both
within and (to lesser degree) across architectures.

The main contributions of this paper are:

  1. 1.

Generate features for non-semantic speech tasks that set a new state-of-the-
art (SoTA) performance on 7/9 tasks using only time-averaged features and
linear classification models

  2. 2.

Analyze the performance versus context window size tradeoff, and show that
2-second context windows are sufficient

  3. 3.

Perform a more extensive embedding comparison than previously done, both in
terms of downstream tasks and embeddings compared. Using a per-example
analysis, we demonstrate that our embedding is strictly better than previous
ones

  4. 4.

Demonstrate that similarly-performing representations in different
architectures are similar in the CKA-sense

##  2 Conformer-Based Representations

Table 1: Comparison of models. Resnetish50 [10]. MobileNetv3 [27]. RNN-T [28]. EfficientNet [29]. Conformer [14]. AudioSet [30]. YT-U [16], LL is Libri-Light [31]. ∗“RA” stands for “relative attention.” Name | Architecture | Params |  | Training
---
data
| Labels
---
required
YAMNet [1] | MobileNetv1 | 3.7M | Audioset | Y
TRILL [1] | Resnetish50 | 24.5M | Audioset | N
FRILL [18] | MobileNetv3 | 10.1M | Audioset | N
COLA [2] | EfficientNetB0 | 4.0M | Audioset | N
ASR Emb [11] | RNN-T | 122M | - | Y
| Conformer XL
---
(No) RA∗ YT (LL)
Conformer | 608M |  | YT-U
---
(LL)
N
| Conformer XXL
---
YT (LL)
Conformer | 1.0B |  | YT-U
---
(LL)
N
Conformer G | Conformer | 8.0B | YT-U | N

###  2.1 Architectures

Each of our proposed paralinguistic representations is defined using a _speech
encoder_ comprised of a stack of convolution-augmented Transformer blocks
known as Conformers [14]. Each Conformer block inserts a small depthwise
separable convolutional module between the Transformer’s self-attention and
MLP modules, which has been shown to be highly beneficial to many recognition
applications. The input to this speech encoder is the output of a 3-layer
1-dimensional convolutional _feature encoder_ that is applied to log mel
spectrogram features. While the original spectrogram is sampled at 100 Hz, two
convolutional strides of two produce a vector time series sampled at 25 Hz, a
frame rate that is preserved throughout the entire speech encoder. The models
are trained using the Wav2Vec 2.0 contrastive loss [12]: we first extract
encoded features from the feature encoder and then use masked features as
inputs to the Conformer to create context vectors. These context vectors are
trained to agree with the target context vectors, obtained by applying a
linear layer to the initial encoded features, by a contrastive loss. Table 1
lists the various Conformer architectures considered in our evaluation. We
consider three Conformer encoder complexities defined in the original study
[16], including 608 million (24 layers/8 heads/1024D output), 1.0 billion (42
layers/8 heads/1024D output), and 8.0 billion parameters (36 layers/16
heads/3072D output). Also shown are corresponding details for five baseline
representations that we include in our evaluation. These cover a range of
model architectures, complexities, and training objectives.

###  2.2 Pre-training Datasets

We use two datasets for self-supervised training of the above architectures.
The first is YT-U, a 900k hour dataset [16] derived from YouTube. YT-U is
built by first randomly collecting 3 million hours of audio from “speech-
heavy” YouTube videos. The results are then segmented, and the non-speech
segments are removed to yield approximately 900k hours of unlabeled audio
data.

The second is Libri-Light [31], which contains 60k hours of audio derived from
open-source audio books in the LibriVox project. It is the largest publicly
available, unlabeled semi-supervised dataset to date.

##  3 Experiments

###  3.1 Tasks: The Non-Semantic Speech Benchmark (NOSS)

In order to fairly compare representations, we benchmark each representation
on the same 9 tasks (Table 2). Our tasks include most of the original NOSS
benchmark tasks [1], a mask-detection task used in representation benchmarking
in [18], a fake speech detection task [20], an additional speech emotion
recognition task [21], and a dysarthria classification task [22]. When a
single scalar is necessary (e.g. to compare embeddings), we aggregate over the
performances using the “Aggregate Embedding Score”, which is the average
accuracy of a model, averaged across tasks.

ASVSpoof2019: We introduce the ASVSpoof2019 [20] dataset as a new task in our
benchmark. This task measures a model’s ability to distinguish real from
synthetic speech. We use the Logical Access (LA) portion of this dataset. The
LA database contains bona fide and spoofed speech generated using 17 different
text-to-speech and voice conversion systems. The task is especially
challenging because spoofed speech in the test set is generated using
techniques not seen in training.

IEMOCAP: The Interactive Emotional Dyadic Motion Capture database [21] is an
acted, multimodal, and multispeaker database. We use the improvised scenarios
portion with categorical emotion labels. To compare fairly with previous SoTA
work [17], we only use the audio component and only 4 of the 10 labels (angry,
happy, neutral, and sad).

Euphonia: The Euphonia dataset [22] is a large dysarthric speech dataset. Our
task uses a 661 speaker subset of 29 identical phrases with manual dysarthria
labels from speech-language pathologists on their overall intelligibility
using a five-point Likert scale.

Table 2: Downstream evaluation datasets. ∗Results in our study used a subset of Voxceleb filtered according to YouTube’s privacy guidelines. Dataset | Target | Classes | Samples |  | Avg
---
length (s)
VoxCeleb∗ [32] | Speaker ID | 1,251 | 12,052 | 8.4
VoxForge [33] | Language ID | 6 | 176,438 | 5.8
| Speech
---
Commands[34]
Command | 12 | 100,503 | 1.0
| Masked
---
Speech [19]
Mask wearing | 2 | 36,554 | 1.0
ASVSpoof [20] |  | Synthetic
---
or not
2 | 121,461 | 3.2
Euphonia [22] | Dysarthria | 5 | 15,224 | 6.4
CREMA-D [35] | Emotion | 6 | 7,438 | 2.5
IEMOCAP [21] | Emotion | 4 | 5,531 | 4.5
SAVEE [36] | Emotion | 7 | 480 | 3.8
Table 3: Test performance on the NOSS Benchmark and extended tasks. “Prev SoTA” are arbitrarily complicated models, but all other rows are linear models on time-averaged input. †We use a filtered subset of Voxceleb1 according to YouTube’s privacy guidelines. We omit previous SoTA results on this dataset, since they used the entire dataset. ‡The Masked Speech task performance is reported using unweighted average recall [19] instead of accuracy. Also, test set labels are not available, so we report accuracy on the eval set. ∗∗ASVSpoof uses equal error rate [20]. #Euphonia is the only non-public dataset. We exclude it from aggregate scores. ††SAVEE is included in the table but not aggregate score, since its less than 1/10th the size of the next smallest dataset and results have high variance. ∗Audio and visual features used in previous SoTA. +Prev SOTA performed cross-fold validation. We hold out speakers M05 and F05 as test. ++YAMNet uses layer 10, as in [1]. §Best per-task results are compute by taking the model/layer with the best results of the dev set, and reporting those results on the test set. If the dev set performance is better but the test results are worse, “Best per-task” can be worse than “Best overall”.  Model |  Voxceleb1† | Voxforge |  | Speech
---
Commands
| Masked
---
Speech‡
| ASVSpoof
---
2019∗∗
Euphonia# | CREMA-D | IEMOCAP |  SAVEE††
Prev SoTA | - |  95.4 [37] |  97.9 [38] |  73.0 [39] |  5.11 [17] |  45.9 [11] |  74.0∗ [40] |  67.6+ [17] |  84.0∗ [36]
Baselines |  |  |  |  |  |  |  |  |
YAMNet++ [1] | 10.9 | 79.8 | 78.5 | 59.7 | 9.23 | 43.0 | 66.4 | 57.5 | 69.2
TRILL [1] | 12.6 | 84.5 | 77.6 | 65.2 | 7.46 | 48.1 | 65.7 | 54.3 | 65.0
FRILL [18] | 13.8 | 78.8 | 74.4 | 67.2 | 7.45 | 46.6 | 71.3 | 57.6 | 63.3
COLA [2] | 11.7 | 71.0 | 60.6 | 65.0 | 4.58 | 47.6 | 69.3 | 63.9 | 59.2
ASR Emb [11] | 5.2 | 98.9 | 96.1 | 54.4 | 11.2 | 54.5 | 71.8 | 65.4 | 85.0
Conformers |  |  |  |  |  |  |  |  |
Best per-task§ | 53.5 | 99.8 | 97.5 | 74.2 | 2.5 | 53.6 | 87.2 | 79.2 | 92.5
(model, layer #) | (XXL-YT, 25) | (G-YT, 19) | (CAP, 16) | (XL-LL RA, 5) | (CAP, 12) | (CAP, 13) | (G, 26) | (CAP, 15) | (CAP, 15)
| Best CAP per
---
task (layer #)
50.3 (11) | 99.7 (14) | 97.5 (16) | 73.4 (10) |  2.5 (12) | 53.6 (13) |  88.2§ (12) |  79.2 (15) | 92.5 (15)
| Best single
---
layer (CAP12)
51.0§ | 99.7 | 97.0 | 68.9 | 2.5 | 51.5 | 88.2§ | 75.0 | 81.7

###  3.2 Benchmark Results

For our first set of experiments, we compute embeddings from our speech
representation models (Table 1) and train simple models on the NOSS tasks
using the same methodology from [1]. For each pair of benchmark task and
embedding, we train and evaluate a number of simple linear classification
techniques (logistic regression, balanced logistic regression, linear
discriminant analysis) on top of clip-level average embeddings. We choose the
best performing classifier (as determined on dev set) and use it to report
test performance for that (task, embedding) pair.

Table 3 shows the results of the benchmark. Like recent studies we report the
performance of the best (model, layer) pair on a per-task basis. However, we
also aim to establish a single universal set of features that serve all
downstream tasks. Thus, we also evaluate all intermediate representations and
rank order them according to the Aggregate Embedding Quality on the dev set.
We then report performance on the test set in final line of Table 3. It comes
from layer 12/23 of the 600M parameter YT model, without relative attention.
We call this model “Conformer Applied to Paralinguistics,” or “CAP”, and we
refer to the best layer as “CAP12.” We note that this representation was
within 6% accuracy of the per-task best layer on 7 of 9 tasks. Figure 1 shows
how the aggregate embedding quality varies in this model across intermediate
layers.

Linear classifiers on Conformer representations set a new SoTA on 7/9 tasks:
The “best per-task” row in Table 3 shows the test set results on the
representations with the best dev-set performance. Linear models on these
representations set a new SoTA on 7 of the tasks, often outperforming far more
complex models. Furthermore, these linear models outperform previous SoTA
models that use more modalities than just speech (CREMA, SAVEE).

CAP12 significantly outperforms previous representations, especially on speech
emotion recognition: CAP12 outperforms every other non-Conformer
representation on every dataset we used with the lone exception of ”ASR Emb”
on SAVEE Especially noteworthy are the results on CREMA-D and IEMOCAP, where
CAP12 outperforms previous embeddings by 16% and 9% respectively.

CAP12 significantly outperforms previous single-model SoTA on ASVSpoof2019:
Linear models on averaged CAP12 would’ve been the best single-model entry in
the ASVSpoof2019 competition, and would’ve ranked 3rd overall [20].

Fig. 1: Upper) Aggregate NOSS score for “CAP.” X-axis is the network layer.
Different lines are different chunking values. Lower) Accuracy lost due to
smaller context windows. Error bars are 1 standard deviation. Each bar is a
mean over (models) x (layers) = 192 values. Fig. 2:  Each square is the
probability that Model Y correctly predicts an example given that Model X and
Model Y disagree on the prediction. The result is averaged over task. Each
task is an average over examples.

CAP12 is strictly better than other representations: Since aggregate
performance ignores patterns of errors, we investigate the agreement between
predictions made from different embeddings on a per-example basis. We see in
Figure 2 that when CAP12 and other embeddings disagree, CAP12 is correct on
32%-64% of the time. When they disagree, other embeddings are correct only
13%-23% of the time. This shows that with the exception of the supervised ASR
Embedding, it is relatively uncommon for other embeddings to be correct with
CAP12 is wrong.

###  3.3 Context window size

Our second experiment studies the role of context window size. Conformers,
like Transformers, use the entire audio clip to generate embeddings, while
CNN-based methods have fixed context-window sizes. To help understand how
essential the large context window is for performance, we feed finite-window-
sized inputs to the Conformer models, just like CNNs process input. We chunk
the audio into fixed length sub-clips (e.g. 1 second), and have the Conformer
model generate local embeddings independently. We then average over all local
representations and evaluate the quality of the embedding on each NOSS task.
We also average the loss in performance across models, tasks, and layers to
determine the average effect that finite-context windows have on downstream
performance. Results are shown in Figure 1.

2-second context windows are sufficient: The best-performing layer for 4 / 3 /
2 / 1 / 0.5 second context windows are 99% / 99% / 98% / 96% / 91% as accurate
as the entire context window, averaged across tasks. This result is a function
of the time-domain of the phenomena being studied, but is also a function of
the fact that the datasets we use are known to include the signal we care
about (average audio clips shown in Table 2).

Performance curves are stable across context window size: Figure 1 shows that
the Aggregate Embedding Quality curves are stable through many different
values of chunking. Furthermore, the best performing layer (according to dev)
is always layer 11 or 12.

###  3.4 Layerwise Analysis

Fig. 3: Upper) Aggregate NOSS score for 6 different Conformer models as a
function of layer index normalized to [0.0, 1.0] using (layer #) $/$ (# of
layers), where # of layers is different for different models. Middle) Linear
CKA scores between all pairs of layers: (left) within the Conformer XL YT
network and (right) across the top performing Conformer XL YT and XXL YT
networks. The colormap is truncated at 0.7 as is common to both images. Lower)
Mean attention distance: (left) the shortest attention head on every layer;
(right) all attention heads on 3 representative layers of the CAP model.

The comparable performance of CAP12 relative to the optimal per-task
embeddings identified in Table 3 suggests a high degree of representational
stability across layers and architectures evaluated. Thus, our final set of
experiments further probe the per-layer performance across layer and
architecture. Figure 3(upper) plots the aggregate NOSS performance as a
function of layer for each architecture, but where layer index is normalized
to a common [0, 1] scale. We observe an overall dependence on pretraining
dataset, with YouTube-trained models clearly outperforming LibriLight-trained
ones. However, within the YouTube models, we observe a surprisingly similar
performance trajectory as we move through the normalized network position.
Furthermore, for each of these models, we observe a wide performance plateau
in the second half of each network.

To test whether this behavior arises from representational similarity in the
models’ shared performance plateau, we apply linear Centered Kernel Alignment
(CKA) between pairs of layers both within and across networks, following the
methodology of a recent vision Transformer study [25]. Briefly, CKA computes a
$[0,1]$-valued similarity between two Gram matrices (using an arbitrary kernel
function, which we take to be linear) separately computed from two
representations over the same sample of input examples (see [26] for details).
Figure 3 (middle left) shows the pairwise layer similarity within the CAP
network. While each layer is most similar to its neighbors, we observe a large
block of similar layers in the second half of the network corresponding to the
performance plateau in Figure 3(upper). This indicates that the stable
downstream performance is indeed fueled by a stable representation across
these layers. While the overall similarity across XL and XXL networks is lower
in Figure 3(middle right), we again see a block of similar layers
corresponding to shared performance plateau. This indicates similar
characterization of paralinguistic properties in this stage of the network
regardless of total network depth.

Finally, in Figure 3 (lower right), we plot mean attention distances of self
attention layers to study how much temporal context each layer is aggregating
over. Following [25], we compute the mean attention distance as the attention
probability-weighted average temporal distance for each attention head, and
average over 1k clips from [31]. We observe that higher and lower layers
contain only global (long distance) attention heads, whereas middle layers
have a mix of local and global ones. Interestingly, there is a clear
correlation between the shortest attention distance on each layer (Figure 3
(lower left)) and its NOSS performance (Figure 3 (upper)), which suggests the
importance of local information for paralinguistic tasks.

##  4 Conclusion

In this paper, we introduce a class of Conformer-based self-supervised
representation for speech. These representations set a new state-of-the-art
performance on 7/9 paralinguistic speech tasks using only embeddings averaged
across time, and using only linear models on those embeddings. Furthermore,
these representations substantially outperform other speech representations
despite not using labels for training. Even though the models use the entire
context window to generate embeddings, we demonstrate that 2-second windows
give 98% the performance of the full context window, and that these
representations with 500ms context windows still outperform previous
representations. Finally, we show that Conformer models with different sized
architectures and different datasets, learn comparable representations at
similar parts of the network, indicating that our findings are fundamental to
the problem and not a superficial artifact.

## References

  * [1] J. Shor _et al._ , “Towards learning a universal non-semantic representation of speech,” in _Interspeech_ , 2020, pp. 140–144.
  * [2] A. Saeed _et al._ , “Contrastive learning of general-purpose audio representations,” in _ICASSP_ , 2021, pp. 3875–3879.
  * [3] A. Jansen _et al._ , “Unsupervised learning of semantic audio representations,” in _ICASSP_. IEEE, 2018, pp. 126–130.
  * [4] Y.-A. Chung _et al._ , “An Unsupervised Autoregressive Model for Speech Representation Learning,” in _Interspeech_ , 2019, pp. 146–150.
  * [5] A. van den Oord _et al._ , “Representation learning with contrastive predictive coding,” 2019.
  * [6] W. Hsu _et al._ , “Hubert: Self-supervised speech representation learning by masked prediction of hidden units,” _CoRR_ , vol. abs/2106.07447, 2021\. [Online]. Available: https://arxiv.org/abs/2106.07447
  * [7] S. Pascual _et al._ , “Learning Problem-Agnostic Speech Representations from Multiple Self-Supervised Tasks,” in _Interspeech_ , 2019, pp. 161–165.
  * [8] R. Arandjelovic _et al._ , “Look, listen and learn,” in _ICCV_. IEEE Computer Society, 2017, pp. 609–617.
  * [9] A. Jansen _et al._ , “Coincidence, categorization, and consolidation: Learning to recognize sounds with minimal supervision,” in _ICASSP_. IEEE, 2020, pp. 121–125.
  * [10] S. Hershey _et al._ , “Cnn architectures for large-scale audio classification,” in _ICASSP_ , 2017.
  * [11] S. Venugopalan _et al._ , “Comparing Supervised Models and Learned Speech Representations for Classifying Intelligibility of Disordered Speech on Selected Phrases,” in _Interspeech_ , 2021, pp. 4843–4847.
  * [12] A. Baevski _et al._ , “wav2vec 2.0: A framework for self-supervised learning of speech representations,” in _NeurIPS_ , vol. 33, 2020, pp. 12 449–12 460.
  * [13] A. Vaswani _et al._ , “Attention is all you need,” in _NeurIPS_ , I. Guyon _et al._ , Eds., vol. 30, 2017.
  * [14] A. Gulati _et al._ , “Conformer: Convolution-augmented transformer for speech recognition,” in _Interspeech_. ISCA, 2020, pp. 5036–5040.
  * [15] Y. Zhang _et al._ , “Pushing the limits of semi-supervised learning for automatic speech recognition,” 2020.
  * [16] ——, “BigSSL: Exploring the frontier of large-scale semi-supervised learning for automatic speech recognition,” 2021.
  * [17] S. wen Yang _et al._ , “SUPERB: Speech Processing Universal PERformance Benchmark,” in _Proc. Interspeech 2021_ , 2021, pp. 1194–1198.
  * [18] J. Peplinski _et al._ , “FRILL: A Non-Semantic Speech Embedding for Mobile Devices,” in _Interspeech_ , 2021.
  * [19] B. Schuller _et al._ , “The INTERSPEECH 2020 Computational Paralinguistics Challenge: Elderly emotion, Breathing & Masks,” in _INTERSPEECH_ , 2020.
  * [20] M. Todisco _et al._ , “ASVspoof 2019: Future horizons in spoofed and fake audio detection,” in _Interspeech_ , 2019, pp. 1008–1012.
  * [21] C. Busso _et al._ , “IEMOCAP: Interactive emotional dyadic motion capture database,” _Language Resources and Evaluation_ , vol. 42, pp. 335–359, 12 2008.
  * [22] R. L. MacDonald _et al._ , “Disordered Speech Data Collection: Lessons Learned at 1 Million Utterances from Project Euphonia,” in _Interspeech_ , 2021, pp. 4833–4837.
  * [23] Y. Jia _et al._ , “Transfer learning from speaker verification to multispeaker text-to-speech synthesis,” in _NeurIPS_ , S. Bengio _et al._ , Eds., vol. 31, 2018.
  * [24] J. Shor _et al._ , “Personalizing ASR for dysarthric and accented speech with limited data,” _Interspeech_ , Sep 2019.
  * [25] M. Raghu _et al._ , “Do Vision Transformers see like convolutional neural networks?” 2021.
  * [26] S. Kornblith _et al._ , “Similarity of neural network representations revisited,” in _ICML_. PMLR, 2019, pp. 3519–3529.
  * [27] A. Howard _et al._ , “Searching for mobilenetv3,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 1314–1324.
  * [28] Y. He _et al._ , “Streaming end-to-end speech recognition for mobile devices,” in _ICASSP_ , 05 2019, pp. 6381–6385.
  * [29] M. Tan _et al._ , “EfficientNet: Rethinking model scaling for convolutional neural networks,” in _ICML_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri _et al._ , Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 6105–6114.
  * [30] J. F. Gemmeke _et al._ , “Audio set: An ontology and human-labeled dataset for audio events,” in _ICASSP_. IEEE, 2017, pp. 776–780.
  * [31] J. Kahn _et al._ , “Libri-Light: A benchmark for ASR with limited or no supervision,” in _ICASSP_ , 2020, pp. 7669–7673.
  * [32] A. Nagrani _et al._ , “Voxceleb: a large-scale speaker identification dataset,” in _INTERSPEECH_ , 2017.
  * [33] K. MacLean, “Voxforge,” _Ken MacLean.[Online]. Available: http://www.voxforge.org/home.[Acedido em 2012]_ , 2018.
  * [34] P. Warden, “Speech Commands: A Dataset for Limited-Vocabulary Speech Recognition,” _ArXiv e-prints_ , Apr. 2018.
  * [35] H. Cao _et al._ , “CREMA-D: Crowd-sourced emotional multimodal actors dataset,” _IEEE transactions on affective computing_ , vol. 5, pp. 377–390, 2014.
  * [36] S. Haq _et al._ , “Speaker-dependent audio-visual emotion recognition.” in _AVSP_ , 2009, pp. 53–58.
  * [37] Sarthak _et al._ , “Spoken language identification using convnets,” in _Ambient Intelligence_ , I. Chatzigiannakis _et al._ , Eds. Springer International Publishing, 2019, pp. 252–265.
  * [38] D. Seo _et al._ , “Wav2KWS: Transfer learning from speech representations for keyword spotting,” _IEEE Access_ , vol. 9, pp. 80 682–80 691, 2021.
  * [39] J. Szep _et al._ , “Paralinguistic Classification of Mask Wearing by Image Classifiers and Fusion,” in _Interspeech_ , 2020, pp. 2087–2091.
  * [40] E. Ghaleb _et al._ , “Multimodal and temporal perception of audio-visual cues for emotion recognition,” in _2019 8th International Conference on Affective Computing and Intelligent Interaction (ACII)_. IEEE, 2019, pp. 552–558.


#  $q$-chromatic polynomials

Esme Bajo  Department of Mathematics, UC Berkeley<EMAIL_ADDRESS>,
Matthias Beck  Department of Mathematics, San Francisco State University
<EMAIL_ADDRESS>and  Andrés R. Vindas-Meléndez  Departments of Mathematics
UC Berkeley & Harvey Mudd College<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We introduce and study a $q$-version of the chromatic polynomial of a given
graph $G=(V,E)$, namely,

$\chi_{G}^{\lambda}(q,n)\ :=\sum_{\begin{subarray}{c}\text{proper
colorings}\\\ c\,:\,V\to[n]\end{subarray}}q^{\sum_{v\in V}\lambda_{v}c(v)},$

where $\lambda\in\mathbb{Z}^{V}$ is a fixed linear form. Via work of Chapoton
(2016) on $q$-Ehrhart polynomials, $\chi_{G}^{\lambda}(q,n)$ turns out to be a
polynomial in the $q$-integer $[n]_{q}$, with coefficients that are rational
functions in $q$. Additionally, we prove structural results for
$\chi_{G}^{\lambda}(q,n)$ and exhibit connections to neighboring concepts,
e.g., chromatic symmetric functions and the arithmetic of order polytopes. We
offer a strengthened version of Stanley’s conjecture that the chromatic
symmetric function distinguishes trees, which leads to an analogue of
$P$-partitions for graphs.

We thank Farid Aliniaeifard, Logan Crew, Serkan Hoşten, Brendan McKay,
Alejandro Morales, Rosa Orellana, Bruce Sagan, Richard Stanley, and Ole
Warnaar for helpful discussions about this work and pointers to the
literature. Andrés R. Vindas-Meléndez is supported by the NSF under Award
DMS-2102921.

##  1\. Introduction

The _chromatic polynomial_ of a graph $G=(V,E)$,

$\chi_{G}(n)\ :=\ \\#\\{c:V\to[n]\,:\,c(v)\neq c(w)\text{ if }vw\in E\\}\,,$

where $[n]:=\\{1,2,\dots,n\\}$, is a famous and much-studied enumerative
invariant of $G$. We introduce and study the following refinement: given
$\lambda:=(\lambda_{1},\lambda_{2},\dots,\lambda_{|V|})\in\mathbb{Z}^{V}$, let

$\chi_{G}^{\lambda}(q,n)\ :=\sum_{\begin{subarray}{c}\text{proper
colorings}\\\ c\,:\,V\to[n]\end{subarray}}q^{\sum_{v\in V}\lambda_{v}c(v)}.$

Naturally, $\chi_{G}^{\lambda}(1,n)=\chi_{G}(n)$. On the other hand, consider
Stanley’s _chromatic symmetric function_ [21]

$X_{G}(x_{1},x_{2},\ldots)\ :=\sum_{\begin{subarray}{c}\text{proper
colorings}\\\
c:V\to\mathbb{Z}_{>0}\end{subarray}}x_{1}^{\\#c^{-1}(1)}x_{2}^{\\#c^{-1}(2)}\cdots$

(so that $X_{G}(1,1,\dots,1,0,0,\dots)=\chi_{G}(n)$ ). Its _principal
evaluation_ (sometimes referred to as the _principal specialization_)

(1) $X_{G}(q,q^{2},\ldots,q^{n},0,0,\ldots)\
=\sum_{\begin{subarray}{c}\text{proper colorings}\\\
c:V\to[n]\end{subarray}}q^{\sum_{v\in V}c(v)}\ =\ \chi_{G}^{\mathbf{1}}(q,n)$

is the special case $\lambda=\mathbf{1}\in\mathbb{Z}^{V}$, i.e., $\lambda$ is
a vector whose entries are all 1. In fact, $\chi_{G}^{\mathbf{1}}(q,n)$ was
also the subject of [13]. We think of $X_{G}(x_{1},x_{2},\ldots)$ and
$\chi_{G}^{\lambda}(q,n)$ as (quite) different generalizations of the
chromatic polynomial, which meet in (1) and still generalize $\chi_{G}(n)$.

Our first result says that $\chi_{G}^{\lambda}(q,n)$ has a polynomial
structure whose coefficients are rational functions in $q$, in the following
sense:

######  Theorem 1.

There exists a unique polynomial
$\widetilde{\chi}_{G}^{\lambda}(q,x)\in\mathbb{Q}(q)[x]$ such that

$\widetilde{\chi}_{G}^{\lambda}(q,[n]_{q})\ =\ \chi_{G}^{\lambda}(q,n),$

where $[n]_{q}:=\frac{1-q^{n}}{1-q}$.

We thus call $\widetilde{\chi}_{G}^{\lambda}(q,x)$ (and sometimes, by a slight
abuse of nomenclature, $\chi_{G}^{\lambda}(q,n)$) the _$q$ -chromatic
polynomial_ of $G$ with respect to $\lambda$. Our main goal is to initiate the
study of this polynomial.

######  Example 1.

Consider the path $P_{2}$ with $2$ vertices. The following table shows
$\widetilde{\chi}_{G}^{\lambda}(q,x)$ and $\chi_{G}^{\lambda}(q,n)$ for
$\lambda=(1,1)$ and $(1,2)$.

$\lambda$ $\widetilde{\chi}_{P_{2}}^{\lambda}(q,x)$
$\chi_{P_{2}}^{\lambda}(q,n)$ (1,1)
$\displaystyle{\frac{2q^{2}}{q+1}x^{2}+\frac{-2q^{2}}{q+1}x}$
$\displaystyle{q^{2}\left(\left(\frac{1-q^{n}}{1-q}\right)^{2}-\left(\frac{1-q^{2n}}{1-q^{2}}\right)\right)}$
(1,2)
$\displaystyle{\frac{q^{5}+q^{4}-2q^{3}}{q^{3}+2q^{2}+q+1}x^{3}+\frac{-q^{5}+2q^{4}+5q^{3}}{q^{3}+2q^{2}+q+1}x^{2}+\frac{-3q^{3}}{q^{2}+q+1}x}$
$\displaystyle{q^{3}\left(\frac{1-q^{n}}{1-q}\,\frac{1-q^{2n}}{1-q^{2}}-\frac{1-q^{3n}}{1-q^{3}}\right)}$

Note that the chromatic polynomial $\chi_{P_{2}}(n)=n^{2}-n$ appears for
$q=1$.

There are several motivations to study $\chi_{G}^{\lambda}(q,n)$ and
$\widetilde{\chi}_{G}^{\lambda}(q,x)$. Their definition and basic structure
mirror Chapoton’s study of $q$-Ehrhart polynomials [4] and, in fact, Theorem 1
follows from Chapoton’s work and the interplay of chromatic and order
polynomials, as we will show in Section 2 below. On the graph-theoretic side,
Stanley famously conjectured that $X_{G}(x_{1},x_{2},\ldots)$ distinguishes
trees; this conjecture has been checked for trees with $\leq 29$ vertices
[11], but remains open in general. The literature contains several variations
of Stanley’s chromatic symmetric function; some references on those different
variations include [8, 17, 10, 16, 1]. We particularly point out recent work
of Crew and Spirkl [6] who introduced a weighted form of the chromatic
symmetric function (and so $\chi_{G}^{\lambda}(q,n)$ is a special evaluation,
with the weights given by $\lambda$) and of Loehr and Warrington [14] who
conjectured, more strongly, that the principal evaluation (1) distinguishes
trees; they confirmed this conjecture for all trees with $\leq 17$ vertices.
We offer the following further strengthening, which we have checked for all
trees with $\leq 16$ vertices.

######  Conjecture 1.

The leading coefficient of the $q$-chromatic polynomial
$\widetilde{\chi}_{G}^{\mathbf{1}}(q,x)$ distinguishes trees.

Section 3 of this paper contains several further structural results for
$q$-chromatic polynomials: deletion–contraction musings (Theorems 8 and 9), a
combinatorial reciprocity theorem (Theorem 10), and a formula for
$\widetilde{\chi}_{G}^{\lambda}(q,x)$ in terms of the Möbius function of the
flats of the given graph (Theorem 11). We mostly concentrate on results on the
polynomial $\widetilde{\chi}_{G}^{\lambda}(q,x)$; there are further structural
results on the enumeration function $\chi_{G}^{\lambda}(q,n)$ that are direct
consequences of their counterparts on the (weighted) chromatic symmetric
function side.

In Section 4 we give several formulas for
$\widetilde{\chi}_{G}^{\mathbf{1}}(q,x)$. One of them naturally suggests an
analogue of Stanley’s $P$-partitions [18], moving from posets to graphs: we
introduce and study $G$-partitions in Section 5 and show that Conjecture 1 is
equivalent to saying that $G$-partitions distinguish trees.

##  2\. $q$-Ehrhart Polynomials

Chapoton [4] introduced a weighted generalization of the Ehrhart polynomial of
a _lattice polytope_ $P\subseteq\mathbb{R}^{d}$ (i.e., $P$ is the convex hull
of finitely many integer lattice points in $\mathbb{Z}^{d}$). We briefly
sketch this theory and its application to order polytopes, which in turn
allows us to exhibit a connection to $q$-chromatic polynomials.

Let $\lambda:\mathbb{Z}^{d}\to\mathbb{Z}$ be a linear form, and define

$\operatorname{ehr}_{P}^{\lambda}(q,n)\ :=\sum_{m\in
nP\cap\mathbb{Z}^{d}}q^{\lambda(m)}.$

The classical Ehrhart polynomial [7] is the specialization
$\operatorname{ehr}_{P}^{\lambda}(1,n)$. Chapoton proved that there is a
polynomial
$\widetilde{\operatorname{ehr}}_{P}^{\lambda}(x)\in\mathbb{Q}(q)[x]$, such
that

(2) $\widetilde{\operatorname{ehr}}_{P}^{\lambda}([n]_{q})\ =\
\operatorname{ehr}_{P}^{\lambda}(q,n)\,.$

We refer to $\widetilde{\operatorname{ehr}}_{P}^{\lambda}(x)$ as the
$q$-Ehrhart polynomial with respect to $\lambda$. We often denote the linear
form $\lambda$ as a vector
$(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}^{d}$, where
$\lambda_{j}=\lambda(e_{j})$.

Parallel to the classical case, structural results for
$\operatorname{ehr}_{P}^{\lambda}(q,n)$ follow from studying the _$q$ -Ehrhart
series_

(3) $\operatorname{Ehr}_{P}^{\lambda}(q,z)\ :=\ \sum_{n\geq
0}\operatorname{ehr}_{P}^{\lambda}(q,n)\,z^{n}.$

Chapoton [4] showed that (3) can be written as a rational function whose
denominator consists of factors $1-q^{j}z$, where $j=\lambda(v)$ for a vertex
$v$ of $P$. Furthermore, Chapoton proved the reciprocity theorem

(4) $(-1)^{\dim(P)}\,\widetilde{\operatorname{ehr}}^{\lambda}_{P}(q,[-n]_{q})\
=\
\widetilde{\operatorname{ehr}}^{\lambda}_{P^{\circ}}\left(\tfrac{1}{q},[n]_{\frac{1}{q}}\right),$

where $P^{\circ}$ denotes the (relative) interior of $P$. The case $q=1$ in
(4) recovers the classical Ehrhart–Macdonald reciprocity theorem [15, 2].

Given a poset $\Pi=([d],\preceq)$, the _order polytope_ $\mathcal{O}(\Pi)$ is
the lattice polytope

$\mathcal{O}(\Pi)\ :=\ \left\\{(x_{1},\ldots,x_{d})\in[0,1]^{d}:\,x_{i}\leq
x_{j}\text{ if }i\preceq j\right\\}.$

Order polytopes were introduced by Stanley [20]; they contain much information
about a given poset and have provided important examples in polyhedral
geometry.

Since all vertices of $\mathcal{O}(\Pi)$ are $0/1$-vectors,
$\operatorname{Ehr}^{\lambda}_{\mathcal{O}(\Pi)}(q,z)$ can be written as a
rational function with factors $1-q^{j}z$ in the denominator where $j$ is a
sum of some of the entries of $\lambda$. This yields the following corollary,
which we record for future purposes.

######  Lemma 2.

Let $\Lambda:=\lambda_{1}+\lambda_{2}+\dots+\lambda_{d}$. The coefficients of
$[\Lambda]_{q}!\,\widetilde{\operatorname{ehr}}^{\lambda}_{\mathcal{O}(\Pi)}(x)$
are polynomials in $q$.

Kim and Stanton [12, Corollary 9.7] gave the following (equivalent) formulas
for the case when $\lambda=\mathbf{1}$:

$\displaystyle\operatorname{Ehr}^{\mathbf{1}}_{\mathcal{O}(\Pi)}(q,z)\ $
$\displaystyle=\
\frac{\displaystyle\sum_{\sigma\in\mathcal{L}(\Pi)}q^{\operatorname{comaj}(\sigma)}z^{\operatorname{des}(\sigma)}}{(1-z)(1-qz)\cdots(1-q^{d}z)}$
(5) $\displaystyle\operatorname{ehr}^{\mathbf{1}}_{\mathcal{O}(\Pi)}(q,n)\ $
$\displaystyle=\sum_{\sigma\in\mathcal{L}(\Pi)}q^{\operatorname{comaj}(\sigma)}\left[{n+d-\operatorname{des}(\sigma)\atop
d}\right]_{q},$

where $\mathcal{L}(\Pi)$ is the set of linear extensions of $\Pi$ and, writing
a given linear extension $\sigma$ as a permutation of $[d]$, and 111Here we
fix a natural labeling of $\Pi$, i.e., an order-preserving bijection
$\Pi\to[d]$. The permutation corresponding to a given linear extension
$\sigma$ can be read off from this labeling. Unfortunately, there are two
different (and conflicting) definitions of the comajor index in the
literature: the one we use here, and the sum of the ascent positions.

$\operatorname{Des}(\sigma):=\\{j:\,\sigma(j+1)<\sigma(j)\\},$
$\operatorname{des}(\sigma):=|\operatorname{Des}(\sigma)|,\text{ and}$
$\operatorname{comaj}(\sigma):=\sum_{j\in\operatorname{Des}(\sigma)}(d-j).$

See [2, Chapter 6] for details on the interplay of linear extensions of a
poset, their descent statistics, and the arithmetic of order polytopes.

Given a graph $G$, let $\mathcal{A}(G)$ denote the set of acyclic orientations
of $G$; each acyclic orientation $\rho$ naturally induces a poset, which we
denote $\Pi_{\rho}$. There is a well-known connection (essentially going back
to [19]) between the chromatic polynomial of a given graph $G$ and the Ehrhart
polynomials of the order polytopes of the acyclic orientations of $G$. In the
language of $q$-chromatic polynomials and $q$-Ehrhart polynomials, it reads as
follows.

######  Lemma 3.

The $q$-chromatic polynomial with respect to $\lambda$ equals

$\chi_{G}^{\lambda}(q,n)\
=\sum_{\rho\in\mathcal{A}(G)}\operatorname{ehr}_{\mathcal{O}(\Pi_{\rho})^{\circ}}^{\lambda}(q,n+1)\,.$

###### Proof.

We follow the philosophy of inside-out polytopes [3]. Let $d=|V|$. We may
interpret each $n$-coloring of the vertices of $G$ is a lattice point in the
$(n+1)$st dilate of the open unit cube $(0,1)^{d}$ (where the $j$th coordinate
is the color of vertex $j$). Furthermore, every proper $n$-coloring of $[d]$
is a lattice point that is not contained in the graphical hyperplane
arrangement

(6) $\mathcal{H}_{G}\ :=\ \left\\{x_{i}=x_{j}:\,ij\in E\right\\}.$

The regions of $(0,1)^{d}\setminus\mathcal{H}_{G}$ are precisely the open
order polytopes $\mathcal{O}(\Pi_{\rho})^{\circ}$ for $\rho$ an acyclic
orientation of $G$. That is, each proper coloring $c$ of $G$ induces an
acyclic orientation $\rho_{c}$ of $G$, where the edge $ij$ is oriented from
$i$ to $j$ if $c(i)<c(j)$ and from $j$ to $i$ if $c(j)<c(i)$. Therefore,

$\displaystyle\chi_{G}^{\lambda}(q,n)\ =\sum_{\begin{subarray}{c}\text{proper
colorings}\\\
c:[d]\to[n]\end{subarray}}q^{\lambda_{1}c(1)+\cdots+\lambda_{d}c(d)}\ $
$\displaystyle=\sum_{\rho\in\mathcal{A}(G)}\
\sum_{\mathbf{c}\in(n+1)\mathcal{O}(\Pi_{\rho})^{\circ}\cap\mathbb{Z}^{d}}q^{\lambda_{1}c_{1}+\cdots+\lambda_{d}c_{d}}$
$\displaystyle=\sum_{\rho\in\mathcal{A}(G)}\operatorname{ehr}_{\mathcal{O}(\Pi_{\rho})^{\circ}}^{\lambda}(q,n+1)\,.\qed$

######  Lemma 4.

Suppose $f(x)$ and $g(x)$ are polynomials with coefficients that are rational
functions in $q$ such that

$f([n]_{q})\ =\ g([n]_{q})\qquad\text{ for all }\ n\in\mathbb{Z}_{>0}\,.$

Then $f(x)=g(x)$.

###### Proof.

By our assumptions, the polynomial $f(x)-g(x)\in\mathbb{Q}(q)[x]$ has
infinitely many zeros and so must be the zero polynomial. ∎

Together with Chapoton’s result (2), Lemmas 3 and 4 prove Theorem 1. In fact,
we can see more, namely, that the analogue of Lemma 2 holds also for
$q$-chromatic polynomials.

######  Corollary 5.

Let $\Lambda:=\lambda_{1}+\lambda_{2}+\dots+\lambda_{d}$. The coefficients of
$[\Lambda]_{q}!\,\widetilde{\chi}^{\lambda}_{G}(x)$ are polynomials in $q$.

The case $\lambda=\mathbf{1}$ is particularly nice because we can employ (5).

######  Corollary 6.

For any graph $G=(V,E)$,

$\chi^{\mathbf{1}}_{G}(q,n)\ =\sum_{\rho\in\mathcal{A}(G)}\
\sum_{\sigma\in\mathcal{L}(\Pi_{\rho})}q^{\binom{d+1}{2}-\operatorname{comaj}{\sigma}}\left[n+\operatorname{des}{\sigma}\atop
d\right]_{q}\,.$

###### Proof.

We apply (4) and (5):

$\operatorname{ehr}^{\mathbf{1}}_{\mathcal{O}(\Pi_{\rho})^{\circ}}(q,n)\ =\
(-1)^{d}\operatorname{ehr}^{\mathbf{1}}_{\mathcal{O}(\Pi_{\rho})}(\tfrac{1}{q},-n)\
=\sum_{\sigma\in\mathcal{L}(\Pi_{\rho})}q^{\binom{d+1}{2}-\operatorname{comaj}{\sigma}}\left[n+\operatorname{des}{\sigma}-1\atop
d\right]_{q},$

and so Lemma 3 finishes the proof. ∎

We record a few consequences of the last corollary.

######  Corollary 7.

Let $G=([d],E)$ and express $\chi^{\mathbf{1}}_{G}(q,n)$ in the form

$\chi^{\mathbf{1}}_{G}(n)\ =\ \sum_{j\geq 0}\beta_{j}(q)\left[n+j\atop
d\right]_{q}\,.$

  1. (1)

Each $\beta_{i}(q)$ is a polynomial in $q$ with nonnegative coefficients.

  2. (2)

$\beta_{0}(q)=|\mathcal{A}(G)|\,q^{\binom{d+1}{2}}$; in particular, if $G$ is
a tree then $\beta_{0}(q)=2^{d-1}q^{\binom{d+1}{2}}$.

  3. (3)

The largest value $i$ for which $\beta_{i}(q)\neq 0$ is $d-\xi$ where $\xi$ is
the chromatic number of $G$. Moreover,

$\beta_{d-\xi}(q)\ =\sum_{\begin{subarray}{c}\text{proper colorings}\\\
c:V\to\xi\end{subarray}}q^{\sum_{v\in V}c(v)}.$

######  Remark 1.

Corollary 6 gives another way of realizing the largest value $j$ for which
$\beta_{j}(q)\neq 0$, namely, as the maximal number $m$ of descents in a
linear extension of a poset induced by an acyclic orientation of $G$.
Therefore, the chromatic number of $G$ is equal to $d-m$, which is one more
than the minimal number of ascents in a linear extension of a poset induced by
an acyclic orientation of $G$. This fact is known as the
Gallai–Hasse–Roy–Vitaver Theorem (see, e.g., [5, Theorem 7.17]).

We also remark that $\beta_{d-\xi}(q)$ distinguishes between some trees as the
next example illustrates.

######  Example 2.

Let $T_{1}$ be the path of length 3 and let $T_{2}$ be the star with degree
sequence $(3,1,1,1)$. We compute

$\displaystyle\chi^{\mathbf{1}}_{T_{1}}(q,n)\ $ $\displaystyle=\
8q^{10}\left[{n\atop 4}\right]_{q}+(4q^{9}+6q^{8}+4q^{7})\left[{n+1\atop
4}\right]_{q}+2q^{6}\left[{n+2\atop 4}\right]_{q}$
$\displaystyle\chi^{\mathbf{1}}_{T_{2}}(q,n)\ $ $\displaystyle=\
8q^{10}\left[{n\atop 4}\right]_{q}+(5q^{9}+4q^{8}+5q^{7})\left[{n+1\atop
4}\right]_{q}+(q^{7}+q^{5})\left[{n+2\atop 4}\right]_{q}.$

In particular, $\chi^{\mathbf{1}}_{T_{1}}(q,2)=2q^{6}$ while
$\chi^{\mathbf{1}}_{T_{2}}(q,2)=q^{7}+q^{5}$. However, the coefficient
$\beta_{d-2}(q)$ is not enough to distinguish all non-isomorphic trees on $d$
vertices.

##  3\. The structure of $q$-chromatic polynomials

As with the classic chromatic polynomial, the $q$-chromatic polynomial
satisfies a deletion–contraction relation. Naturally, this strongly relates to
the deletion–contraction formula for Crew–Spirkl’s weighted version of the
chromatic symmetric function [6, Lemma 2].

######  Theorem 8.

Suppose $G=([d],E)$ is a graph,
$\lambda=(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}^{d}$, and $e=12\in E$.
Then

$\chi_{G}^{\lambda}(q,n)\ =\ \chi_{G\setminus
e}^{\lambda}(q,n)-\chi_{G/e}^{(\lambda_{1}+\lambda_{2},\lambda_{3},\ldots,\lambda_{d})}(q,n)\,.$

###### Proof.

As usual, we observe that the proper $n$-colorings of $G$ are precisely the
proper $n$-colorings $c$ of $G\setminus e$ that satisfy the additional
condition $c(1)\neq c(2)$. Therefore, we may count them by counting all proper
$n$-colorings $c$ of $G\setminus e$ and then removing all such colorings $c$
for which $c(1)=c(2)$:

$\displaystyle\chi_{G}^{\lambda}(q,n)\ $
$\displaystyle=\sum_{\begin{subarray}{c}\text{proper colorings}\\\
c:[d]\to[n]\text{ of
}G\end{subarray}}q^{\lambda_{1}c(1)+\cdots+\lambda_{d}c(d)}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{proper colorings}\\\
c:[d]\to[n]\text{ of }G\setminus
e\end{subarray}}q^{\lambda_{1}c(1)+\cdots+\lambda_{d}c(d)}-\sum_{\begin{subarray}{c}\text{proper
colorings}\\\ c:[d]\to[n]\text{ of }G\setminus e\\\ \text{where
}c(1)=c(2)\end{subarray}}q^{\lambda_{1}c(1)+\cdots+\lambda_{d}c(d)}$
$\displaystyle=\ \chi_{G\setminus
e}^{\lambda}(q,n)-\chi_{G/e}^{(\lambda_{1}+\lambda_{2},\lambda_{3},\ldots,\lambda_{d})}(q,n)\,.\qed$

We observe that a similar computation enables us to express any $q$-chromatic
polynomial (for general $\lambda$ with positive entries) as a linear
combination of $q$-chromatic polynomials with $\lambda=\mathbf{1}$, via a
repeated expansion–addition process as follows. If $G=([d],E)$ is a graph and
$\lambda=(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}_{\geq 0}^{d}$ with
$\lambda_{1}\geq 2$, split the vertex $1$ into two vertices $1^{\prime}$ and
$1^{\prime\prime}$ with weights $\lambda_{1}-1$ and $1$, respectively. Create
the expansion graph $\exp(G,e)$ of $G$ at $1$ with vertex set
$\\{1^{\prime},1^{\prime\prime},2,\ldots,d\\}$ and edge set

$\\{1^{\prime}i,1^{\prime\prime}i:\,i\in\\{2,\ldots,d\\}\text{ such that
}1i\in E\\}\cup\\{ij:\,i,j\in\\{2,\ldots,d\\}\text{ such that }ij\in E\\}\,,$

and let the addition graph $\operatorname{add}(G,e)$ of $G$ at $1$ be
$\text{exp}(G,e)$ with an edge added between the new vertices $1^{\prime}$ and
$1^{\prime\prime}$. Then

$\chi_{G}^{\lambda}(q,n)\ =\
\chi_{\text{exp}(G,e)}^{(\lambda_{1}-1,1,\lambda_{2},\ldots,\lambda_{d})}(q,n)-\chi_{\text{add}(G,e)}^{(\lambda_{1}-1,1,\lambda_{2},\ldots,\lambda_{d})}(q,n)\,.$

By repeatedly applying this process, we obtain the following result:

######  Theorem 9.

If $G=([d],E)$ is a graph and
$\lambda=(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}_{\geq 0}^{d}$, then
there exist graphs $H_{1},\ldots,H_{\ell}$ on $\lambda_{1}+\cdots+\lambda_{d}$
vertices and integers $k_{1},\ldots,k_{\ell}$ such that

$\chi_{G}^{\lambda}(q,n)\ =\
\sum_{i=1}^{\ell}k_{i}\,\chi^{\mathbf{1}}_{H_{i}}(q,n)\,.$

Our next result extends Stanley’s famous reciprocity theorem for the chromatic
polynomial to the $q$-setting. A (not necessarily proper) coloring $c$ of a
graph $G$ is _compatible_ with an acyclic orientation $\rho$ of $G$ if $c$
(weakly) increases along oriented edges. Stanley [19] proved that
$|\chi_{G}(-n)|$ equals the number of pairs of an $n$-coloring and a
compatible acyclic orientation of $G$. In particular, $|\chi_{G}(-1)|$ equals
the number of acyclic orientations of $G$. This generalizes as follows.

######  Theorem 10.

Given a graph $G=(V,E)$ and $\lambda\in\mathbb{Z}^{V}$, let
$\Lambda:=\sum_{v\in V}\lambda_{v}$. Then

$(-1)^{|V|}q^{\Lambda}\,\widetilde{\chi}^{\lambda}_{G}\left(\tfrac{1}{q},[-n]_{\frac{1}{q}}\right)\
=\sum_{(c,\rho)}q^{\sum_{v\in V(G)}\lambda_{v}c(v)},$

where the sum is over all pairs of an $n$-coloring $c$ and a compatible
acyclic orientation $\rho$.

######  Example 3.

For $\lambda=\mathbf{1}$, the path on 2 vertices has $q$-chromatic polynomial

$\widetilde{\chi}^{\mathbf{1}}_{P_{2}}(q,x)\ =\
\frac{2q^{2}x^{2}-2q^{2}x}{1+q}\,.$

Therefore,

$(-q)^{2}\,\widetilde{\chi}^{\mathbf{1}}_{P_{2}}(\tfrac{1}{q},x)\ =\
q^{2}\,\frac{2q^{-2}x^{2}-2q^{-2}x}{1+q^{-1}}\ =\ \frac{2qx^{2}-2qx}{1+q}$

and so, e.g.,

$(-q)^{2}\,\widetilde{\chi}^{\mathbf{1}}_{P_{2}}(\tfrac{1}{q},-q-q^{2})\ =\
\frac{2q(-q-q^{2})^{2}-2q(-q-q^{2})}{1+q}\ =\ 2q^{4}+2q^{3}+2q^{2}.$

Indeed, this sums $q^{\sum c(v)}$ for the six pairs of 2-colorings and
compatible acyclic orientations.

###### Proof of Theorem 10.

Let $d:=|V|$. We apply Chapoton’s reciprocity result (4) to Lemma 3:

$\displaystyle(-1)^{d}\,\widetilde{\chi}^{\lambda}_{G}(q,[-n]_{q})\ $
$\displaystyle=\sum_{\rho\in
A(G)}(-1)^{d}\,\widetilde{\operatorname{ehr}}^{\lambda}_{\mathcal{O}(\Pi_{\rho})^{\circ}}(q,[-n+1]_{q})$
$\displaystyle=\sum_{\rho\in
A(G)}(-1)^{d}\,\widetilde{\operatorname{ehr}}^{\lambda}_{\mathcal{O}(\Pi_{\rho})}\left(\tfrac{1}{q},[n-1]_{\frac{1}{q}}\right).$

Therefore,

$\displaystyle(-1)^{d}\,\widetilde{\chi}^{\lambda}_{G}\left(\tfrac{1}{q},[-n]_{\frac{1}{q}}\right)\
$ $\displaystyle=\sum_{\rho\in
A(G)}(-1)^{d}\,\widetilde{\operatorname{ehr}}^{\lambda}_{\mathcal{O}(\Pi_{\rho})}(q,[n-1]_{q})$
(7) $\displaystyle=\sum_{\rho\in
A(G)}\operatorname{ehr}^{\lambda}_{\mathcal{O}(\Pi_{\rho})}(q,n-1)\,.$

The integer lattice points in $(n-1)\mathcal{O}(\Pi_{\rho})$ can be
interpreted as colorings of $G$ using the color set
$\\{0,1,\ldots,n-1\\}$ that are compatible with $\rho$, and so (7) equals

$\sum_{(c,\rho)}q^{\sum_{v\in V(G)}\lambda_{v}(c(v)-1)}.\qed$

We conclude this section with one more way of computing $q$-chromatic
polynomials. A _flat_ of a given graph $G=(V,E)$ is a subset $S\subseteq E$
such that for any edge $e\notin S$, the subgraph $(V,S)$ has strictly more
connected components than $(V,S\cup\\{e\\})$. Geometrically, the intersection
$H_{S}$ of the hyperplanes of the graphical arrangement $\mathcal{H}_{G}$ in
(6) corresponding to $S$ form a flat of $\mathcal{H}_{G}$. Let $P(S)$ be the
collection of vertex sets of the connected components induced by $S$, and for
$W\subseteq V$ and $\lambda\in\mathbb{Z}_{\geq 0}^{V}$, let

$\Lambda_{W}:=\sum_{v\in W}\lambda_{v}\,.$

The flats of $G$ form a poset (in fact, a lattice), whose Möbius function
helps us compute, again via inside-out polytopes [3] (see also [2, Chapter
7]), that

$\displaystyle\chi^{\lambda}_{G}(q,n)\ =\sum_{\text{flats }S\subseteq
E}\mu(\varnothing,S)\operatorname{ehr}^{\lambda}_{(0,1)^{V}\cap H_{S}}(n+1)\ $
$\displaystyle=\sum_{\text{flats }S\subseteq E}\mu(\varnothing,S)\prod_{C\in
P(S)}q^{\Lambda_{C}}[n]_{q^{\Lambda_{C}}}$ $\displaystyle=\
q^{\Lambda_{V}}\sum_{\text{\rm flats }S\subseteq
E}\mu(\varnothing,S)\prod_{C\in P(S)}[n]_{q^{\Lambda_{C}}}\,.$

In particular, for a tree $T=(V,E)$,

$\chi^{\lambda}_{T}(q,n)\ =\ q^{\Lambda_{V}}\sum_{S\subseteq
E}(-1)^{|S|}\prod_{C\in P(S)}[n]_{q^{\Lambda_{C}}}\,.$

These formulas can be viewed as analogues of [21, Theorem 2.5], where Stanley
proves an expression for the chromatic symmetric function in the power sum
basis.

Next, we employ the following trick from [4]: for integers $n\geq 0$ and
$k\geq 1$,

$\left.\frac{1-(1+qx-x)^{k}}{1-q^{k}}\right|_{x=[n]_{q}}=\ [n]_{q^{k}}\,.$

This yields the following formulas for $q$-chromatic polynomials.

######  Theorem 11.

Given a graph $G=(V,E)$ and $\lambda\in\mathbb{Z}^{V}$,

$\widetilde{\chi}^{\lambda}_{G}(q,x)\ =\ q^{\Lambda_{V}}\sum_{\text{\rm flats
}S\subseteq E}\mu(\varnothing,S)\prod_{C\in
P(S)}\frac{1-(1+qx-x)^{\Lambda_{C}}}{1-q^{\Lambda_{C}}}\,.$

In particular, for a tree $T=(V,E)$,

$\widetilde{\chi}^{\lambda}_{T}(q,x)\ =\ q^{\Lambda_{V}}\sum_{S\subseteq
E}(-1)^{|S|}\prod_{C\in
P(S)}\frac{1-(1+qx-x)^{\Lambda_{C}}}{1-q^{\Lambda_{C}}}\,.$

######  Remark 2.

In the following section, we will study the leading coefficient of this
polynomial and see that it appears to distinguish trees. This is certainly not
true of all other coefficients. For example, we can see that any tree on $d$
vertices with the same total vertex weight $\Lambda_{V}$ has the same linear
coefficient (and the same constant 0, like the ordinary chromatic polynomial).
Since

$\frac{1-(1+(q-1)x)^{\Lambda_{C}}}{1-q^{\Lambda_{C}}}\ =\
\frac{-\Lambda_{C}(q-1)x-\binom{\Lambda_{C}}{2}(q-1)^{2}x^{2}-\cdots}{1-q^{\Lambda_{C}}}\,,$

the only linear terms of $\widetilde{\chi}$ come from edge subsets $S$ that
result in 1 connected component; for trees $T$, the only such set is $S=E$.
Thus, for a tree, the linear coefficient is determined only by $d$ and
$\Lambda_{V}$.

######  Example 4.

Theorem 11 suggests highly structured formulas for certain families of graphs;
we exercise this for the path $P_{k}$ on $k$ vertices when
$\lambda=\mathbf{1}$, in analogy with the chromatic symmetric function [22,
Exercise 7.47(k)].

$\widetilde{\chi}^{\mathbf{1}}_{P_{k}}(q,x)\ =\ q^{k}\sum_{S\subseteq
E}(-1)^{|S|}\prod_{C\in P(S)}\frac{1-(1+qx-x)^{|C|}}{1-q^{|C|}}\ =\
(-q)^{k}\sum_{S\subseteq E}\prod_{C\in P(S)}\Phi(q,x,|C|),$

where

$\Phi(q,x,j)\ :=\ -\frac{1-(1+qx-x)^{j}}{1-q^{j}}$

and we used the fact that (for a tree) $|S|+|P(S)|=|E|+1$. The subsets of $E$
(for the path $P_{k}$) are in one-to-one correspondence with the compostions
(i.e., ordered partitions) of $k$, with parts given by the sizes of the sets
in $P(S)$. Thus

$\sum_{k\geq 1}\widetilde{\chi}^{\mathbf{1}}_{P_{k}}(q,x)\,t^{k}\ =\
\sum_{k\geq 1}\sum_{S\subseteq E}\prod_{C\in P(S)}\Phi(q,x,|C|)\,(-qt)^{k}\ =\
\sum_{\mu}\prod_{m\in P(\mu)}\Phi(q,x,m)\,(-qt)^{|\mu|},$

where the sum is over all compositions $\mu$, we collect the parts of $\mu$ in
the multiset $P(\mu)$, and $|\mu|$ is the sum of the parts of $\mu$.

######  Example 5.

The analogous computation for the star $S_{k+1}$ on $k+1$ vertices gives

$\widetilde{\chi}^{\mathbf{1}}_{S_{k+1}}(q,x)\ =\ (-q)^{k+1}\sum_{S\subseteq
E}\prod_{C\in P(S)}\Phi(q,x,|C|)\ =\
(-q)^{k+1}\sum_{j=0}^{k}\binom{k}{j}\Phi(q,x,j+1)\,(-x)^{k-j}$

and so

$\displaystyle\sum_{k\geq
0}\widetilde{\chi}^{\mathbf{1}}_{S_{k+1}}(q,x)\,t^{k+1}\ $ $\displaystyle=\
\sum_{k\geq
0}\sum_{j=0}^{k}\binom{k}{j}\Phi(q,x,j+1)\,(-x)^{k-j}\,(-qt)^{k+1}$
$\displaystyle=\ -qt\sum_{j\geq 0}\Phi(q,x,j+1)\,(-x)^{-j}\sum_{k\geq
j}\binom{k}{j}(xqt)^{k}$ $\displaystyle=\ -qt\sum_{j\geq
0}\Phi(q,x,j+1)\,(-x)^{-j}\,\frac{(xqt)^{j}}{(1-xqt)^{j+1}}$ $\displaystyle=\
\sum_{j\geq 0}(-1)^{j+1}\Phi(q,x,j+1)\left(\frac{qt}{1-xqt}\right)^{j+1}.$

##  4\. The Leading Coefficient of a $q$-chromatic Polynomial

We now focus our attention on the leading coefficient $c^{\lambda}_{T}(q)$ of
$\widetilde{\chi}^{\lambda}_{T}(q,n)$ stemming from Theorem 11.

######  Corollary 12.

Given a tree $T=(V,E)$ and $\lambda\in\mathbb{Z}^{V}$, the leading coefficient
of $\widetilde{\chi}^{\lambda}_{T}(q,n)$ equals

$c^{\lambda}_{T}(q)\ =\ (-1)^{|V|}(q^{2}-q)^{\Lambda_{V}}\sum_{S\subseteq
E}\prod_{C\in P(S)}\frac{1}{1-q^{\Lambda_{C}}}\,.$

In particular,

$[\Lambda_{V}]_{q}!\ c^{\lambda}_{T}(q)\ =\
q^{\Lambda_{V}}(-1)^{|V|+\Lambda_{V}}\sum_{S\subseteq
E}(1-q)^{\Lambda_{V}-\kappa(S)}\frac{[\Lambda_{V}]_{q}!}{\prod_{C\in
P(S)}[\Lambda_{C}]_{q}}$

(where $\kappa(S)$ denotes the number of components of the subgraph induced by
$S$) is visibly a polynomial in $q$, as the fraction is a $q$-multinomial
coefficient times a polynomial.

######  Remark 3.

Deletion–contraction extends to $c^{\lambda}_{T}(q)$, and we provide a formula
here which might be helpful for computations. Let $l$ be a leaf of $T$ and

$\displaystyle A\ $ $\displaystyle:=\ \left\\{S\subset E:l\notin e\text{ for
all }e\in S\right\\}$ $\displaystyle B\ $ $\displaystyle:=\ \left\\{S\subset
E:l\in e\text{ for for some }e\in S\right\\}.$

Let $T^{\prime}=(V^{\prime},E^{\prime})$ be the tree with $l$ deleted; we will
denote the number of connected components induced by $S\subseteq E^{\prime}$
by $\kappa^{\prime}(S)$. We further define $\lambda^{\prime}$ to be the vector
$\lambda$ with $l$th entry removed, and $\lambda^{+}$ to stem from $\lambda$
where we add $\lambda_{l}$ to the entry corresponding to the neighbor of $l$,
with corresponding notation $\Lambda^{+}_{W}$ for $W\subseteq E^{\prime}$.
Then

$\sum_{S\in
A}(1-q)^{\Lambda_{V}-\kappa(S)}\frac{[\Lambda_{V}]_{q}!}{\prod_{C\in
P(S)}[\Lambda_{C}]_{q}}\ =\
(1-q)^{\lambda_{l}-1}\frac{[\Lambda_{V}]_{q}!}{[\lambda_{l}]_{q}\,[\Lambda_{V^{\prime}}]_{q}!}\sum_{S\subseteq
E^{\prime}}(1-q)^{\Lambda_{V^{\prime}}-\kappa^{\prime}(S)}\frac{[\Lambda_{V^{\prime}}]_{q}!}{\prod_{C\in
P(S)}[\Lambda_{C}]_{q}}$

and

$\sum_{S\in
B}(1-q)^{\Lambda_{V}-\kappa(S)}\frac{[\Lambda_{V}]_{q}!}{\prod_{C\in
P(S)}[\Lambda_{C}]_{q}}\ =\ \sum_{S\subseteq
E^{\prime}}(1-q)^{\Lambda^{+}_{V^{\prime}}-\kappa^{\prime}(S)}\frac{[\Lambda^{+}_{V^{\prime}}]_{q}!}{\prod_{C\in
P(S)}[\Lambda^{+}_{C}]_{q}}\,.$

Thus,

$\displaystyle[\Lambda_{V}]_{q}!\ c^{\lambda}_{T}(q)\ $ $\displaystyle=\
q^{\Lambda_{V}}(-1)^{|V|+\Lambda_{V}}(1-q)^{\lambda_{l}-1}\frac{[\Lambda_{V}]_{q}!}{[\lambda_{l}]_{q}\,[\Lambda_{V^{\prime}}]_{q}!}\sum_{S\subseteq
E^{\prime}}(1-q)^{\Lambda_{V^{\prime}}-\kappa^{\prime}(S)}\frac{[\Lambda_{V^{\prime}}]_{q}!}{\prod_{C\in
P(S)}[\Lambda_{C}]_{q}}$
$\displaystyle\qquad+q^{\Lambda_{V}}(-1)^{|V|+\Lambda_{V}}\sum_{S\subseteq
E^{\prime}}(1-q)^{\Lambda^{+}_{V^{\prime}}-\kappa^{\prime}(S)}\frac{[\Lambda^{+}_{V^{\prime}}]_{q}!}{\prod_{C\in
P(S)}[\Lambda^{+}_{C}]_{q}}$ $\displaystyle=\
q^{\lambda_{l}}(q-1)^{\lambda_{l}-1}\frac{[\Lambda_{V}]_{q}!}{[\lambda_{l}]_{q}\,[\Lambda_{V^{\prime}}]_{q}!}\left([\Lambda_{V^{\prime}}]_{q}!\
c^{\lambda^{\prime}}_{T^{\prime}}(q)\right)-\left([\Lambda^{+}_{V^{\prime}}]_{q}!\
c^{\lambda^{+}}_{T^{\prime}}(q)\right).$

Again, the fraction is a polynomial (via a $q$-binomial coefficient).

We now further focus on the case $\lambda=\mathbf{1}$. Corollaries 6 and 12
give the following two (quite different) expressions for the leading
coefficient.

######  Corollary 13.

Given a tree $T=(V,E)$ on $d$ vertices, the leading coefficient of
$\widetilde{\chi}^{\mathbf{1}}_{T}(q,n)$ equals

$\displaystyle c^{\mathbf{1}}_{T}(q)\ $ $\displaystyle=\
(q-q^{2})^{d}\sum_{S\subseteq E}\prod_{C\in P(S)}\frac{1}{1-q^{\Lambda_{C}}}$
$\displaystyle=\
\frac{1}{[d]_{q}!}\sum_{(\rho,\sigma)}q^{d+\operatorname{maj}{\sigma}},$

where the sum ranges over all pairs of acyclic orientations $\rho$ of $T$ and
linear extensions $\sigma$ of the poset induced by $\rho$.

###### Proof.

The first formula follows directly from Corollary 12. The second follows from
Corollary 6. The $q$-binomial coefficient in Corollary 6 can be expressed in
terms of the $q$-integers via

$\displaystyle\left[n+\operatorname{des}{\sigma}\atop d\right]_{q}$
$\displaystyle=\
\frac{[n+\operatorname{des}{\sigma}]_{q}\cdots[n]_{q}\cdots[n+\operatorname{des}{\sigma}-(d-1)]_{q}}{[d]_{q}!}$
$\displaystyle=\
\frac{1}{[d]_{q}!}\left(q^{\operatorname{des}{\sigma}}[n]_{q}+[\operatorname{des}{\sigma}]_{q}\right)\cdots[n]_{q}\cdots\left(\frac{[n]_{q}-[\operatorname{asc}{\sigma}]_{q}}{q^{\operatorname{asc}{\sigma}}}\right)$

(since $(d-1)-\operatorname{des}{\sigma}=\operatorname{asc}{\sigma}$, the
number of ascents of $\sigma$ ), which gives

$c^{\mathbf{1}}_{T}(q)\ =\
\frac{1}{[d]_{q}!}\sum_{\rho\in\mathcal{A}(G)}\sum_{\sigma\in\mathcal{L}(\Pi_{\rho})}q^{\binom{d+1}{2}+\binom{\operatorname{des}{\sigma}+1}{2}-\binom{\operatorname{asc}{\sigma}+1}{2}-\operatorname{comaj}{\sigma}}\,.$

Using the relation $\operatorname{asc}\sigma+\operatorname{des}\sigma=d-1$
again, the exponent simplifies to

$\binom{d+1}{2}+\binom{\operatorname{des}{\sigma}+1}{2}-\binom{\operatorname{asc}{\sigma}+1}{2}-\operatorname{comaj}{\sigma}\
=\ d+\operatorname{maj}{\sigma}\,.\qed$

In Corollary 13, the latter expression for $c^{\mathbf{1}}_{T}(q)$ illustrates
that $\frac{1}{q^{d}}\,[d]_{q}!\,c^{\mathbf{1}}_{T}(q)$ is a polynomial in $q$
with nonnegative coefficients. We provide this expression for all non-
isomorphic trees on $d=6$ vertices in Figure 1.

$\displaystyle T$ |  $\displaystyle\frac{[d]_{q}!}{q^{d}}\,c^{\mathbf{1}}_{T}(q)$
---|---
|
$2q^{12}+8q^{11}+18q^{10}+36q^{9}+62q^{8}+78q^{7}+102q^{6}+102q^{5}+106q^{4}+80q^{3}+62q^{2}+32q+32$
|
$q^{13}+q^{12}+10q^{11}+16q^{10}+41q^{9}+57q^{8}+81q^{7}+95q^{6}+108q^{5}+100q^{4}+83q^{3}+59q^{2}+36q+32$
|
$4q^{12}+8q^{11}+18q^{10}+42q^{9}+58q^{8}+78q^{7}+92q^{6}+110q^{5}+98q^{4}+82q^{3}+58q^{2}+40q+32$
|
$2q^{12}+9q^{11}+20q^{10}+34q^{9}+65q^{8}+77q^{7}+96q^{6}+104q^{5}+107q^{4}+76q^{3}+62q^{2}+36q+32$
|
$q^{13}+3q^{12}+11q^{11}+18q^{10}+39q^{9}+60q^{8}+78q^{7}+87q^{6}+110q^{5}+101q^{4}+79q^{3}+59q^{2}+42q+32$
|
$q^{14}+9q^{12}+9q^{11}+20q^{10}+39q^{9}+60q^{8}+72q^{7}+81q^{6}+112q^{5}+99q^{4}+79q^{3}+58q^{2}+49q+32$
Figure 1. A table of the leading coefficients of the $q$-chromatic polynomials
of the non-isomorphic trees on $d=6$ vertices.

######  Example 6.

Continuing Example 4, we return to the path $P_{k}$ on $k$ vertices. Corollary
12 gives

$c^{\mathbf{1}}_{P_{k}}(q)\ =\ (q-q^{2})^{k}\sum_{S\subseteq E}\prod_{C\in
P(S)}\frac{1}{1-q^{|C|}}$

and thus

$\sum_{k\geq 1}c^{\mathbf{1}}_{P_{k}}(q)\,t^{k}\ =\ \sum_{k\geq
1}\sum_{S\subseteq E}\prod_{C\in
P(S)}\frac{1}{1-q^{|C|}}\left((q-q^{2})\,t\right)^{k}\ =\
\sum_{\mu}\prod_{m\in
P(\mu)}\frac{1}{1-q^{m}}\left((q-q^{2})\,t\right)^{|\mu|},$

where again the sum is over all compositions $\mu$.

######  Example 7.

Continuing Example 5 along similar lines, we compute for the star

$c^{\mathbf{1}}_{S_{k+1}}(q)\ =\
(q-q^{2})^{k+1}\sum_{j=0}^{k}\binom{k}{j}\frac{1}{(1-q^{j+1})(1-q)^{k-j}}\ =\
q^{k+1}\sum_{j=0}^{k}\binom{k}{j}\frac{(1-q)^{j+1}}{1-q^{j+1}}$

and so

$\sum_{k\geq 0}c^{\mathbf{1}}_{S_{k+1}}(q)\,t^{k+1}\ =\ \sum_{j\geq
0}\frac{(1-q)^{j+1}}{1-q^{j+1}}\sum_{k\geq j}\binom{k}{j}(qt)^{k+1}\ =\
\sum_{j\geq 0}\frac{1}{1-q^{j+1}}\left(\frac{qt(1-q)}{1-qt}\right)^{j+1}$

is a classical Lambert series.

######  Remark 4.

Corollary 13 immediately distinguishes stars from all other trees: the largest
possible major index one can obtain from a tree is from the linear extension
$[1,d,d-1,\ldots,3,2]$, and the only tree that realizes this is the star (with
acyclic orientation where all edges point out from center). Consequently, the
degree of $[d]_{q}!\,c^{\mathbf{1}}_{T}(q)$ for a star is strictly larger than
that of any other tree with the same number of vertices.

##  5\. $G$-partitions

The second formula in Corollary 13 is reminiscent of Stanley’s $P$-partitions
[18] and organically suggests an extension of that concept to graphs. We first
review the part of Stanley’s theory that we will need.

Given a poset $\Pi=([d],\preceq)$, a _strict $\Pi$-partition_ of
$n\in\mathbb{Z}_{>0}$ is a tuple $\mathbf{m}\in\mathbb{Z}_{>0}^{d}$, such
that222 Our definition differs from Stanley’s inequalities, but the
methodology is the same.

$\sum_{j=1}^{d}m_{j}=n\qquad\text{ and }\qquad m_{j}<m_{k}\ \text{ whenever }\
j\prec k\,.$

Let $p_{\Pi}(n)$ denote the number of strict $\Pi$-partitions of $n$, with
accompanying generating function

$P_{\Pi}(q):=\sum_{n>0}p_{\Pi}(n)\,q^{n}.$

Then by [2, Exercise 6.23],

(8) $P_{\Pi}(q)\ =\
\frac{q^{d}\sum_{\sigma\in\mathcal{L}(\Pi)}\prod_{j\in\operatorname{Asc}\sigma}q^{d-j}}{(1-q)(1-q^{2})\cdots(1-q^{d})}\
=\ \frac{q^{d}\sum_{\sigma\in\mathcal{L}(\Pi)}q^{\operatorname{maj}\sigma^{\rm
op}}}{(1-q)(1-q^{2})\cdots(1-q^{d})},$

where $\operatorname{Asc}\sigma$ denotes the ascent set of $\sigma$, and we
define $\sigma^{\rm op}(j):=\sigma(d+1-j)$. Note that we compute ascents and
descents as in Section 2: we fix some natural labeling of $\Pi$, i.e., an
order-preserving bijection $\Pi\to[d]$. The permutation corresponding to a
given linear extension $\sigma$ can be read off from this labeling. Viewing a
poset as an (acyclic) directed graph, the following definition gives the
natural analogue for an undirected graph.

Let $G=(V,E)$ be a graph. A _$G$ -partition_333 We follow the (somewhat
misleading) nomenclature of Stanley—in general, neither $P$\- nor
$G$-partitions are partitions, rather they are _compositions_ , i.e., ordered
partition of a given integer $n$.  of $n\in\mathbb{Z}_{>0}$ is a tuple
$\mathbf{m}\in\mathbb{Z}_{>0}^{V}$, such that

$\sum_{v\in V}m_{v}=n\qquad\text{ and }\qquad m_{v}\neq m_{w}\ \text{ whenever
}\ vw\in E\,.$

Let $p_{G}(n)$ denote the number of $G$-partitions of $n$, with accompanying
generating function $P_{G}(q):=\sum_{n>0}p_{G}(n)\,q^{n}$.

######  Theorem 14.

Let $G$ be a graph on $d$ vertices. Then

$\displaystyle P_{G}(q)\ $ $\displaystyle=\
\frac{q^{d}\sum_{(\rho,\sigma)}q^{\operatorname{maj}\sigma^{\rm
op}}}{(1-q)(1-q^{2})\cdots(1-q^{d})}$ $\displaystyle=\
\frac{q^{\binom{d+1}{2}}\sum_{(\rho,\sigma)}q^{-\operatorname{maj}\sigma}}{(1-q)(1-q^{2})\cdots(1-q^{d})}\,,$

where each sum ranges over all pairs of acyclic orientations $\rho$ of $G$ and
linear extensions $\sigma$ of the poset induced by $\rho$.

###### Proof.

Since every $G$-partition is a $\Pi_{\rho}$-partition for exactly one acyclic
orientation $\rho$ of $G$ (and, conversely, every $\Pi_{\rho}$-partition is a
$G$-partition),

$p_{G}(n)\ =\sum_{\rho\in\mathcal{A}(G)}p_{\Pi_{\rho}}(n)$

and so (8) gives the first formula:

$P_{G}(q)\ =\
\frac{q^{d}\sum_{\rho\in\mathcal{A}(G)}\sum_{\sigma\in\mathcal{L}(\Pi_{\rho})}q^{\operatorname{maj}\sigma^{\rm
op}}}{(1-q)(1-q^{2})\cdots(1-q^{d})}\,.$

To see the second formula, we note that each $\rho\in\mathcal{A}(G)$ has a
partner orientation $\overline{\rho}\in\mathcal{A}(G)$ in which the direction
of each edge is reversed. A linear extension
$\sigma\in\mathcal{L}(\Pi_{\rho})$ has the corresponding linear extension
$\overline{\sigma}\in\mathcal{L}(\Pi_{\overline{\rho}})$ defined via

$\overline{\sigma}(j)\ :=\ d+1-\sigma(d+1-j)\ =\ d+1-\sigma^{\rm op}(j)\,.$

In particular, $j\in\operatorname{Des}(\sigma^{\rm op})$ if and only if
$j\in\operatorname{Asc}(\overline{\sigma})$, and so

$\sum_{(\rho,\sigma)}q^{\operatorname{maj}\sigma^{\rm op}}\ =\
\sum_{(\overline{\rho},\overline{\sigma})}q^{\binom{d}{2}-\operatorname{maj}\overline{\sigma}}\,.\qed$

This yields a third equation that can be added to the ones in Corollary 13.

######  Corollary 15.

Given a tree $T=(V,E)$ on $d$ vertices, the leading coefficient of
$\widetilde{\chi}^{\mathbf{1}}_{T}(q,n)$ equals

$c^{\mathbf{1}}_{T}(q)\ =\ (-1)^{d}q^{d}\,P_{G}\left(\tfrac{1}{q}\right).$

We can now see Remark 4 through this new lens: the star graph on $d$ vertices
is unique with $p_{G}(d+1)=1$. More generally, Corollary 15 implies that
Conjecture 1 is equivalent to the following.

######  Conjecture 2.

The $G$-partition function $p_{G}(n)$ distinguishes trees.

We conclude by making note of the connection between $G$-partitions and the
_stable principal evaluation_ $X_{G}(q,q^{2},q^{3},\ldots)$ of the chromatic
symmetric function. Namely, from first principles we can see that

$P_{G}(q)\ =\ X_{G}(q,q^{2},q^{3},\ldots)\,.$

This yields one final equation for the leading coefficient that can be added
to the ones in Corollary 13.

######  Corollary 16.

Given a tree $T=(V,E)$ on $d$ vertices, the leading coefficient of
$\widetilde{\chi}^{\mathbf{1}}_{T}(q,n)$ equals

$c^{\mathbf{1}}_{T}(q)\ =\
(-1)^{d}q^{d}\,X_{G}\left(\tfrac{1}{q},\tfrac{1}{q^{2}},\tfrac{1}{q^{3}},\dots\right).$

That is, when we express the principal evaluation of the chromatic symmetric
function as a polynomial in the $q$-integers, the stable principal evaluation
appears in its leading coefficient.

##  6\. Open Questions

From our construction of $\widetilde{\chi}^{\lambda}_{T}(q,n)$ for general
$\lambda$, a natural weakening of Conjecture 1 (that is perhaps easier to
prove) arises.

######  Conjecture 3.

For any pair of non-isomorphic trees $S$ and $T$ on $d$ vertices, there exists
a vector $\lambda=(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}_{>0}$ such
that $\chi_{S}^{\lambda}(q,n)\neq\chi_{T}^{\lambda}(q,n)$.

Another line of open questions emerges concerning the coefficients of the
$q$-chromatic polynomial. The classical chromatic polynomial $\chi_{G}(n)$ is
very well studied, and many of its coefficients have nice combinatorial
interpretations. Can we generalize these to
$\widetilde{\chi}^{\mathbf{1}}_{G}(q,n)$? For example:

  1. (1)

The second coefficient of $\chi_{G}(n)$ is (negative) the number of edges of
$G$. Can we refine this to a $q$ version, i.e., does the second coefficient of
$\widetilde{\chi}^{\mathbf{1}}_{G}(q,n)$ count the number of edges of $G$, but
graded by some property of the edges?

  2. (2)

Can the same be done for the linear coefficient which, in the classical case,
counts the number of acyclic orientations with a unique sink at one fixed
vertex? (This is not interesting for trees by Remark 2, but could be
interesting for general graphs.)

  3. (3)

The coefficients of $\chi_{G}(n)$ are alternating. Can we show that the
coefficients of $\widetilde{\chi}^{\mathbf{1}}_{G}(q,n)$ are “strongly
alternating,” in the sense that the coefficient of $x^{j}$ in
$[d]_{q}!\cdot\widetilde{\chi}^{\mathbf{1}}_{G}(q,x)$ is a polynomial in $q$
with either all positive or all negative coefficients (depending on the parity
of $d-j$)?

Finally, as we mentioned in the introduction, there are further structural
results and questions that stem from viewing $\chi_{G}^{\lambda}(q,n)$ as an
evaluation of a (weighted) chromatic symmetric function. It is then natural to
ask if there is anything to be gained by zeroing in on the polynomial
$\widetilde{\chi}^{\lambda}_{G}(q,x)$; for example:

  1. (4)

Is there some (interesting) variant of the $(3+1)$-free Conjecture of Stanley
and Stembridge [23] for $\widetilde{\chi}^{\lambda}_{G}(q,x)$?

  2. (5)

There exist variants of Whitney’s Broken-Circuit Theorem for weighted
chromatic symmetric functions; see [6, Lemma 3] and [9, Theorem 6.8]. Do they
give rise to a meaningful broken-circuit result for the coefficients of
$\widetilde{\chi}^{\lambda}_{G}(q,x)$?

##  7\. Funding

## References

  * [1] José Aliste-Prieto, Anna de Mier, and José Zamora, _On the smallest trees with the same restricted $U$-polynomial and the rooted $U$-polynomial_, Discrete Math. 344 (2021), no. 3, 9 pages, Id 112255\.
  * [2] Matthias Beck and Raman Sanyal, _Combinatorial reciprocity theorems: An invitation to enumerative geometric combinatorics_ , Graduate Studies in Mathematics, vol. 195, American Mathematical Society, Providence, RI, 2018.
  * [3] Matthias Beck and Thomas Zaslavsky, _Inside-out polytopes_ , Adv. Math. 205 (2006), no. 1, 134–162.
  * [4] Frédéric Chapoton, _$q$ -analogues of Ehrhart polynomials_, Proc. Edinb. Math. Soc. (2) 59 (2016), no. 2, 339–358.
  * [5] Gary Chartrand and Ping Zhang, _Chromatic graph theory_ , Discrete Math. Appl. (Boca Raton), Boca Raton, FL: Chapman & Hall/CRC, 2009.
  * [6] Logan Crew and Sophie Spirkl, _A deletion-contraction relation for the chromatic symmetric function_ , Eur. J. Comb. 89 (2020), 19 pages, Id/No 103143.
  * [7] Eugène Ehrhart, _Sur les polyèdres rationnels homothétiques à $n$ dimensions_, C. R. Acad. Sci. Paris 254 (1962), 616–618.
  * [8] David D. Gebhard and Bruce E. Sagan, _A chromatic symmetric function in noncommuting variables_ , J. Algebr. Comb. 13 (2001), no. 3, 227–255.
  * [9] Darij Grinberg, _Generalized whitney formulas for broken circuits in ambigraphs and matroids_ , (2023), 99 pages, Preprint (arXiv:1604.03063).
  * [10] Takahiro Hasebe and Shuhei Tsujie, _Order quasisymmetric functions distinguish rooted trees_ , J. Algebr. Comb. 46 (2017), no. 3-4, 499–515.
  * [11] Simon Heil and Caleb Ji, _On an algorithm for comparing the chromatic symmetric functions of trees_ , Australas. J. Comb. 75 (2019), 210–222.
  * [12] Jang Soo Kim and Dennis Stanton, _On $q$-integrals over order polytopes_, Adv. Math. 308 (2017), 1269–1317.
  * [13] Martin Loebl, _Chromatic polynomial, $q$-binomial counting and colored Jones function_, Adv. Math. 211 (2007), no. 2, 546–565.
  * [14] Nicholas A. Loehr and Gregory S. Warrington, _A rooted variant of Stanley’s chromatic symmetric function_ , Discrete Math. 347 (2024), no. 3, Paper No. 113805, 18 pages.
  * [15] Ian G. Macdonald, _Polynomials associated with finite cell-complexes_ , J. London Math. Soc. (2) 4 (1971), 181–192.
  * [16] Brendan Pawlowski, _Chromatic symmetric functions via the group algebra of $S_{n}$_, Algebr. Comb. 5 (2022), no. 1, 1–20.
  * [17] John Shareshian and Michelle L. Wachs, _Chromatic quasisymmetric functions_ , Adv. Math. 295 (2016), 497–551.
  * [18] Richard P. Stanley, _Ordered structures and partitions_ , American Mathematical Society, Providence, R.I., 1972, Memoirs of the American Mathematical Society, No. 119.
  * [19] by same author, _Acyclic orientations of graphs_ , Discrete Math. 5 (1973), 171–178.
  * [20] by same author, _Two poset polytopes_ , Discrete & Computational Geometry 1 (1986), no. 1, 9–23.
  * [21] by same author, _A symmetric function generalization of the chromatic polynomial of a graph_ , Adv. Math. 111 (1995), no. 1, 166–194.
  * [22] by same author, _Enumerative combinatorics. Vol. 2_ , second ed., Cambridge Studies in Advanced Mathematics, vol. 208, Cambridge University Press, Cambridge, 2024, With an appendix by Sergey Fomin.
  * [23] Richard P. Stanley and John R. Stembridge, _On immanants of Jacobi–Trudi matrices and permutations with restricted position_ , J. Combin. Theory Ser. A 62 (1993), no. 2, 261–279.