In this paper we show that if $(X,\mathcal{A})$ is a measurable space and if $Y$ is a topological model of a Lawvere theory $\mathcal{T}$ equipped with $\mathcal{B}$ the Borel $\sigma$-algebra on $Y$, then the set of $\mathcal{B}$-measurable functions from $X$ to $Y$, $\operatorname{Meas}(X,Y)$, is a set-theoretic model of $\mathcal{T}$. As a corollary we give short proofs of the facts that the set of real-valued measurable functions on a measurable space $X$ is a ring and the set of complex-valued measurable functions from $X$ to $\mathbb{C}$ is a ring.

Primary 28E15; Secondary 18C10, 18C40

§ INTRODUCTION

Without much exaggeration, measure theory is as important to modern analysis as the theory of modules is to modern algebra. It is a fundamental tool in functional analysis, statistics, representation theory, harmonic analysis, geometric group theory, and even in number theory. In fact any time a question can be phrased in terms of volumes it probably has a formulation or approach using measure-theoretic tools. However, while measure theory itself is mostly applied in analytic contexts due to its relationship with integration, there is a very set-theoretic algebraic flavour in the foundations and many of the basic results for measure theory. Despite this, it is often an arduous journey for many algebraically-minded graduate students to work through many of the basic measure-theoretic results needed for representation theory and number theory.

In this paper, however, we show that this difficulty need not be the case. We prove a categorical-algebraic result that gives, if the mathematician writing the proof is willing to be brief and lean on some “apply Theorem $xyz$ to $\Tcal_{\Ring}$ with the observation...” in their writing, a one-sentence proof of the fact that for any measurable set $(X,\Acal)$ the set $\Meas(X,\R;\text{Borel})$ of Borel measurable functions is a ring. The trade-off here is that we use some categorical algebraic concepts and prove a much stronger statement using Lawvere theories in order to avoid the analytic perspective and provide a structural proof indicating exactly what is used to prove that $\Meas(X,\R;\text{Borel})$ is a ring. However, this gives an $\epsilon$-free method for proving algebraic properties of sets of measurable functions with values in $\R$.

§.§ The Structure of the Paper

In Section <ref> we give a short review of some of the basics of measurable spaces. Because there are many good textbook accounts of measure theory in the literature, we focus instead on when our measurable space $(X,\Acal)$ is the Borel algebra of a topological space $X$. Section <ref> gives a quick review of (infinitary) Lawvere theories following the construction of [3]. The focus we give is more on definitions and examples than in proving and providing general theorems. Finally in Section <ref> we prove the main theorem of our paper, presented below, and then the following two corollaries.

Let $\Tcal$ be a Lawvere theory and let $Y$ be a topological model of $\Tcal$, i.e., $Y \in \Tcal(\Top)_0$. Then if $(X, \Acal)$ is a measurable space, the set

\[
\Meas(X,Y;\Bcal_X) = \lbrace f:X \to Y \; | \; f\,\text{is}\,\Bcal_Y\textnormal{-measurable}\rbrace
\]

is an object in $\Tcal(\Set)_0$.

Let $R$ be a topological ring. Then for any measurable space $(X,\Acal)$ the set $\Meas(X,R;\Bcal_{R})$ is a ring. In particular, the real-measurable functions $\Meas(X,\R;\Bcal_{\R})$ and complex-measurable functions $\Meas(X,\C;\Bcal_{\C})$ are rings.

Let $G$ be a topological group and let $(X,\Acal)$ be any measurable space. Then $\Meas(X,G;\Bcal_{G})$ is a group. In particular, for any local field $F$ the set $\Meas(X,\operatorname{GL}_n(F);\Bcal_{\operatorname{GL}_n(F)})$ is a group.

§.§ Acknowledgments

This work was supported by an AARMS postdoctoral fellowship.

§ A REVIEW OF MEASURE THEORY FOR TOPOLOGICAL SPACES

In this short section we review some of the basics of measure theory regarding measurable spaces and $\sigma$-algebras. Most of this section is simply review of what is explained in more detail in many textbooks in the literature (cf. [4], [5], [8], [9], for instance), but we present it primarily because, in my opinion, Example <ref> and the interaction between uncountably infinite topological spaces and measure theory are not as well-known as they likely should be.

Let $X$ be a set and let $\Pcal X$ denote the power set

\[
\Pcal X := \lbrace S \; | \; S \subseteq X \rbrace
\]

of $X$. Then a $\sigma$-algebra on $X$ is a subset $\Acal \subseteq \Pcal X$ for which:

* We have that $X \in \Acal$.

* If $A \in \Acal$, then $A^c := X \setminus A \in \Acal$;

* If $I$ is a countable index set and if $\lbrace A_i \; | \; i \in I \rbrace \subseteq \Acal$ then

\[
\bigcup_{i \in I} A_i \in \Acal.
\]

A measurable space is a pair $(X,\Acal)$ where $X$ is a set and $\Acal$ is a $\sigma$-algebra on $X$.

Of course the definition of a measurable space is geometrically motivated; it allows us to axiomitize which pieces of a set $X$ can have measured volume and gives us inference rules for what we can say about how these sets must behave. The first axiom says that if we can measure the volume of a piece $A \subseteq X$ then we can measure the volume of the complement of $A$, while the second rule says that if we can measure the volume of countably many pieces $A_i \subseteq X$ then we can measure the volume of the compositum $\cup_{i \in I} A_i$. Another important way to describe the geometry of a set $X$ is through a topology on $X$, which we now describe.

A topological space is a pair $(X,\Tcal)$ where $X$ is a set and $\Tcal \subseteq \Pcal X$ is a set of subsets we declare to be open such that:

* $\emptyset, X \in \Tcal$;

* For any set $I$, if $\lbrace U_i \; | \; i \in I, U_i \in \Tcal \rbrace \subseteq \Tcal$ then

\[
\bigcup_{i \in I} U_i \in \Tcal.
\]

* For any finite collection $U_1, \cdots, U_n \in \Tcal$, there is a $U \in \Tcal$ for which

\[
\bigcap_{i=1}^{n} U_i^{c} = U^c.
\]

An important consequence of the definition of a $\sigma$-algebra is that such a set is closed with respect to countable intersections of its members. This allows us to deduce the following proposition which tells us that $\sigma$-algebras are topologies on countable sets.

Let $(X,\Acal)$ be a countable measure space. Then $\Acal$ is a topology on $X$.

With this in mind it is tempting to think that $\sigma$-algebras give rise to topologies on sets, but sadly it is relatively well-known that this need not be the case. However, as this is not as well-known as it should be, we present the example below to illustrate this fact.

Let $X$ be an uncountably infinite set and let $\Acal \subseteq \Pcal(X)$ be the $\sigma$-algebra of countable or cocountable subsets of $X$, i.e.,

\[
\Acal := \lbrace Y \subseteq X \; : \; \lvert Y \rvert \leq \aleph_0\,\text{or}\,\lvert Y^c \rvert \leq \aleph_0 \rbrace.
\]

It is routine and tedious to check that $\Acal$ is a $\sigma$-algebra on $X$. To see that it does not generate a topology on $X$ note that since the set $\lbrace x \rbrace \subseteq X$ for each $x \in X$, $\Acal$ contains every singleton point of $X$ and so must be the discrete topology if it is a topology. However, as $\Acal$ contains no uncountable set with uncountable complement this is impossible and so $\Acal$ cannot be a topology on $X$.

§ A REVIEW OF LAWVERE THEORIES

In this section we give a short review of Lawvere theories, their basic notions, and some examples. Lawvere theories are generalizations and formalizations of algberiac theories (as they appear in universal algbera and logic; cf. ) and give us a language to discuss and the infinitary Lawvere theories we allow in this paper even provide a way to discuss algebraic objects that have infinitely many operations. We follow <cit.>, which contains an expository account of Lawvere theories in detail, and formalize the notion of Lawvere theories as certain limit sketches; other equivalent formalizations are given in [2], [6], and [1], among other sources. Of course, it is an important theorem of Linton (cf. [7] for the usual reference and [3] for a self-contained explicit and direct proof) that there is an equivalence of categories

\[
\Lawvere \simeq \Monad(\Set).
\]

While we will not need more than a basic definition of Lawvere theories in this paper, we present some examples in this short section so that we can firmly ground our intuition in the sort of examples which are likely to be most familiar.

An infintary Lawvere theory is a pair $(\Lcal, X)$ where $\Lcal$ is a locally small category with all $\Set$-indexed products and $X$ is a distinguished object of $\Lcal$ such that for all objects $Y$ of $\Lcal$ there exists a set $I$ and an isomorphism

\[
Y \cong \prod_{i \in I} X = X^I
\]

in $\Lcal$.

Because of the nature of a Lawvere theory $(\Lcal, X)$ described above, to describe functors $F:\Lcal \to \Cscr$ it suffices to define $F$ on the objects $X^I$ for all sets $I$ and on all morphisms between all $X^I$ and $X^J$.

We say that a Lawvere theory $(\Lcal,X)$ is finitary if for any index sets $I, J$ we have that

\[
\Lcal(X^I, X^J) \cong \left(\colim_{\substack{E \subseteq I \\ E\,\text{finite}}} \Lcal(X^E,X)\right)^I.
\]

The (finitary) Lawvere theory of groups is the category $\Tcal_{\Grp}$ where we define the obejcts to be given by:

* For every index set there is an object $G^I$. The distinguished object is $G := G^{[0]}$ where $[0] = \lbrace 0 \rbrace$. We also write $\top := G^{\emptyset}$.

We define the morphisms to be generated by making sure that each $G^I$ is a product indexed by $I$ together with some extra morphisms

* $1_G:\top \to G$

* $\inv:G \to G$

* $\mu:G \times G \to G$

which satisfy the diagrams

\[
\begin{tikzcd}
G \ar[r]{}{\cong} \ar[d, swap]{}{\cong} \ar[drr, equals]{}{} & G \times \top \ar[r]{}{\id_G \times 1_G} &  G \times G \ar[d]{}{\mu} \\
\top \times G \ar[r, swap]{}{1_G \times \id_G} & G \times G \ar[r, swap]{}{\mu} & G
\end{tikzcd}
\]

\[
\begin{tikzcd}
(G \times G) \times G \ar[rr]{}{\mu \times \id_G} \ar[d, swap]{}{\cong} & & G \times G \ar[d]{}{\mu} \\
G \times (G \times G) \ar[dr, swap]{}{\id_G\times \mu} & & G \\
&  G \times G \ar[ur, swap]{}{\mu}
\end{tikzcd}
\]

\[
\begin{tikzcd}
G \ar[r]{}{\Delta} \ar[dr, swap, dashed]{}{!_G} & G \times G \ar[rr, shift left = .5ex]{}{\inv \times \id_G} \ar[rr, swap, shift right = .5ex]{}{\id_G\times \inv} & & G \times G \ar[d]{}{\mu} \\
& \top \ar[rr, swap]{}{1_G} & & G
\end{tikzcd}
\]

The (finitary) Lawvere theory of (associative unital) rings is the category $\Tcal_{\Ring}$ where we define the obejcts to be given by:

* For every index set there is an object $G^I$. The distinguished object is $R := R^{[0]}$ where $[0] = \lbrace 0 \rbrace$. We also write $\top := R^{\emptyset}$.

We define the morphisms to be generated by making sure that each $R^I$ is a product indexed by $I$ together with some extra morphisms

* $0_R:\top \to R$

* $1_R:\top \to R$

* $\negg:R \to R$

* $\alpha:R \times R \to R$

* $\mu:R \times R \to R$

which satisfy the diagrams

\[
\begin{tikzcd}
R \ar[r]{}{\cong} \ar[d, swap]{}{\cong} \ar[drr, equals]{}{} & R \times \top \ar[r]{}{\id_R \times 1_R} &  R \times R \ar[d]{}{\mu} \\
\top \times R \ar[r, swap]{}{1_R \times \id_R} & R \times R \ar[r, swap]{}{\mu} & R
\end{tikzcd}
\]

\[
\begin{tikzcd}
(R \times R) \times R \ar[rr]{}{\mu \times \id_R} \ar[d, swap]{}{\cong} & & R \times R \ar[d]{}{\mu} \\
R \times (R \times R) \ar[dr, swap]{}{\id_R\times \mu} & & R \\
&  R \times R \ar[ur, swap]{}{\mu}
\end{tikzcd}
\]

\[
\begin{tikzcd}
R \ar[r]{}{\cong} \ar[d, swap]{}{\cong} \ar[drr, equals]{}{} & R \times \top \ar[r]{}{\id_R \times 0_R} &  R \times R \ar[d]{}{\alpha} \\
\top \times R \ar[r, swap]{}{0_R \times \id_R} & R \times R \ar[r, swap]{}{\alpha} & R
\end{tikzcd}
\]

\[
\begin{tikzcd}
(R \times R) \times R \ar[rr]{}{\alpha \times \id_R} \ar[d, swap]{}{\cong} & & R \times R \ar[d]{}{\alpha} \\
R \times (R \times R) \ar[dr, swap]{}{\id_R\times \alpha} & & R \\
&  R \times R \ar[ur, swap]{}{\alpha}
\end{tikzcd}
\]

\[
\begin{tikzcd}
R \ar[r]{}{\Delta} \ar[dr, swap, dashed]{}{!_G} & R \times R \ar[rr, shift left = .5ex]{}{\negg \times \id_R} \ar[rr, swap, shift right = .5ex]{}{\id_R\times \negg} & & R \times R \ar[d]{}{\alpha} \\
& \top \ar[rr, swap]{}{0_R} & & R
\end{tikzcd}
\]

and diagrams expressing left and right distributivity of multiplication and addition:

\[
\begin{tikzcd}
R \times (R \times R) \ar[d, swap]{}{\Delta} \ar[rrr]{}{\id_R\times \alpha} &  & & R \times R \ar[d]{}{\mu} \\
(R \times R) \times (R \times R) \ar[d, swap]{}{\cong} & (R \times R) \times (R \times R) \ar[r, swap]{}{\mu \times \mu} & R \times R \ar[r]{}{\alpha} & R \\
R \times (R \times R) \times R \ar[r, swap]{}{\id_R \times \text{switch} \times \id_R} & R \times (R \times R) \times R \ar[u, swap]{}{\cong}
\end{tikzcd}
\]

\[
\begin{tikzcd}
(R \times R) \times R \ar[d, swap]{}{\Delta} \ar[rrr]{}{\alpha \times \id_R} & & & R \times R \ar[d]{}{\mu} \\
(R \times R) \times (R \times R) \ar[d, swap]{}{\cong} & (R \times R) \times (R \times R) \ar[r]{}{\mu \times \mu}& R \times R \ar[r, swap]{}{\alpha} & R  \\
R \times (R \times R) \times R \ar[r, swap]{}{\id_R \times \text{switch} \times \id_R} & R \times (R \times R) \times R \ar[u, swap]{}{\cong}	\end{tikzcd}
\]

Let $\Cscr$ be a category and let $(\Lcal,X)$ be a Lawvere theory. A $\Cscr$-model of $\Lcal$ is a product-preserving functor $M:\Lcal \to \Cscr$. In this case we call $M(X)$ the underlying object of the model. Moreover, the category of all such models is the category

\[
\Lcal(\Cscr) := [\Lcal,\Cscr]_{\text{prod}}
\]

of product-preserving functors $\Lcal \to \Cscr$ and their natural transformations.

If $(\Lcal,X)$ is a Lawvere theory then:

* A $\Set$-valued model of $\Lcal$ is often called “an $\Lcal$” by abuse of notation (just as we call models of $\Tcal_{\Grp}$ in $\Set$ groups, $\Tcal_{\Ring}$ in $\Set$ rings, etc.). There are  equivalences of categories $\Tcal_{\Grp}(\Set) \simeq \Grp$ and $\Tcal_{\Ring}(\Set) \simeq \Ring$ which follow immediately after unwinding the definitions of everything in sight.

* A $\Top$-valued model of $\Lcal$ is a topological model of $\Lcal$. Classical examples of this include topological groups (models of $\Tcal_{\Grp}$) and topological rings (models of $\Tcal_{\Ring}$). However, topological fields are not examples of $\Top$-valued models of a Lawvere theory because the theory of fields is not a Lawvere theory.

* If $K$ is a field and if $\Cscr = \Var_{/\Spec K}$ is the category of $K$-varieties then $\Lcal(\Var_{/\Spec K})$ is the category of $K$-variety models of $\Lcal$. When $\Lcal = \Tcal_{\Grp}$, $\Lcal(\Var_{/\Spec K}) = \Tcal_{\Grp}(\Var_{/\Spec K})$ is the category of algebraic groups over $K$ (which is a category whose objects occupy an area of central importance in the Langlands Programme and in algebraic geometry).

§ PUTTING IT ALL TOGETHER: BOREL MEASURES

We now discuss some topological measure theory before proceeding to prove our main theorem. This material is relatively well-known, so we will mostly focus on giving a quick description in order to get to show how topological models of Lawvere theories and Borel algebras interact.

Let $X$ be a topological space. We define the Borel algebra on $X$, $\Bcal_X$, to be the $\sigma$-algebra generated by the open subsets $U \subseteq X$.

Let $X$ be a topological space. We say that a $\sigma$-algebra $\Acal$ on $X$ is a Borel algebra if for any open set $U \subseteq X$, $U \in \Acal$.

From the definition it is immediate that if $X$ is a topological space then we can describe the Borel algebra $\Bcal_X$ by

\[
\Bcal_X := \bigcap_{\substack{\Acal\,\text{is a}\, \sigma\text{-algebra} \\ \Acal\,\text{is a Borel algebra}}} \Acal.
\]

This follows more or less immediately from the description of $\Bcal_X$ being generated by the open sets of $X$.

Let $X$ be a topological space. The Borel algebra $\Bcal_X$ on $X$ admits the description

\[
\Bcal_X = \inf\left\lbrace \Acal \; | \; \Acal\,\textnormal{is a}\;\sigma\textnormal{-algebra}, U \in \Acal, U \subseteq X\,\textnormal{open} \right\rbrace
\]

in the power set $\Pscr(X)$ regarded as a Boolean algebra with respect to the subset order $\subseteq$.

With this terminology we can now develop the theory of Borel measurable functions in order to derive our main result. These are the measurable functions $f:X \to Y$ where $Y$ is a topological space which interact in a compatible way with the topology on $Y$.

Let $Y$ be a topological space and let $(X,\Acal)$ be a measurable space. We then say that $f:X \to Y$ is Borel measurable (or $\Bcal_Y$-measurable if we need to emphasize the space $Y$) if and only if for all $B \in \Bcal_Y$ we have $f^{-1}(B) \in \Acal$.

This leads to a standard but helpful set-theoretic lemma.

If $(X,\Acal)$ is a measurable space and if $f:X \to Y$ is a function of sets then

\[
\Bcal := \left\lbrace B \subseteq Y \; | \; f^{-1}(B) \in \Acal \right\rbrace
\]

is a $\sigma$-algebra on $Y$.

We proceed with the observations that for any arbitrary family $\lbrace B_i \; | \; i \in I, B_i \subseteq Y \rbrace$ of subsets,

\[
f^{-1}\left(\bigcup_{i \in I} B_i\right) = \lbrace x \in X \; | \; \exists\,i \in I.\,f(x) \in B_i \subseteq Y \rbrace = \bigcup_{i \in I} f^{-1}(B_i)
\]

and dually

\[
f^{-1}\left(\bigcap_{i \in I} B_i\right) = \bigcap_{i \in I}f^{-1}(B_i).
\]

Thus if we have any countable collection of sets $B_n \subseteq Y$ for which $f^{-1}(B_n) \in \Acal$ for all $n \in \N$ we get that

\[
f^{-1}\left(\bigcup_{n \in \N}B_n\right) = \bigcup_{n \in \N} f^{-1}(B_n) \in \Acal
\]

\[
f^{-1}\left(\bigcap_{n \in \N}B_n\right) = \bigcap_{n \in \N}f^{-1}\left(B_n\right) \in \Acal
\]

because $\Acal$ is a $\sigma$-algebra and each of $f^{-1}(B_n) \in \Acal$.

To verify that $\Bcal$ is closed under complements, note that $f^{-1}(Y) = X$ and $f^{-1}(S \setminus T) = f^{-1}(S) \setminus f^{-1}(T)$ for any $S, T \subseteq Y$. Then if $B \in \Bcal$ we get that, because $\Acal$ is a $\sigma$-algebra,

\[
f^{-1}(B^c) = f^{-1}(Y \setminus B) = f^{-1}(Y) \setminus f^{-1}(B) = X \setminus f^{-1}(B) = f^{-1}(B)^c \in \Acal.
\]

Thus $f^{-1}(B)^c \in \Bcal$ and so $\Bcal$ is a $\sigma$-algebra.

We now can establish some basic properties about the Borel measurability of continuous functions and how these functions post-compose with other Borel measurable functions.

Let $X$ and $Y$ be topological spaces and regard $X$ as a measurable space by equipping it with its Borel measure $\Bcal_{X}$. If $f:X \to Y$ is a continuous function of topological spaces then $f$ is Borel measurable.

Since $f$ is continuous, for every open set $V \subseteq Y$ we have that $f^{-1}(V) \subseteq X$ is open and so $f^{-1}(V) \in \Bcal_X$ as well. However, this then implies that every open $V \subseteq Y$ open we get that

\[
f^{-1}(V) \in \lbrace U \subseteq Y \; | \; f^{-1}(U) \in \Bcal_X \rbrace =: \Ccal.
\]

Because $\Ccal$ is a $\sigma$-algebra by Lemma <ref> which contains every open set of $Y$, we see that $\Bcal_Y \subseteq \Ccal$ by Proposition <ref>. However, this implies that for any $A \in \Bcal_X$ we have $f^{-1}(A) \in \Bcal_X$ and so $f$ is Borel measurable.

Let $(X,\Acal)$ be a measurable space and let $Y$ and $Z$ be topological spaces equipped with their corresponding Borel $\sigma$-algebras $\Bcal_Y$ and $\Bcal_Z$. Then if $f:X \to Y$ is $\Bcal_Y$-measurable and if $g:Y \to Z$ is $\Bcal_Z$-measurable, the composite $g \circ f:X \to Z$ is $\Bcal_Z$-measurable.

Let $V \subseteq Z$ with $Z \in \Bcal_Z$; it now suffices to show that

\[
(g \circ f)^{-1}(Z) = f^{-1}(g^{-1}(V))
\]

is contained in $\Acal$. However, as $g$ is $\Bcal_Z$-measurable, $g^{-1}(V) \in \Bcal_Y$. Similarly, as $f$ is $\Bcal_Y$-measurable, $f^{-1}(g^{-1}(V)) \in \Acal$. Thus

\[
f^{-1}\left(g^{-1}(V)\right) = (g \circ f)^{-1}(V) \in \Acal
\]

and so $g \circ f$ is $\Bcal_Z$-measurable.

Let $(X,\Acal)$ be a measurable space and let $Y$ and $Z$ be topological spaces equipped with their corresponding Borel algebras $\Bcal_Y$ and $\Bcal_Z$. Then  if $g:Y \to Z$ is a continuous function the composite function $g \circ f:X \to Z$ is $\Bcal_Z$-measurable.

Apply Lemma <ref> to derive that $g$ is Borel-measurable and then use Proposition <ref>.

We now have two last technical ingredients to provide. These show the Borel measurabliity of situations we'll find ourselves in when studying the measurability of topological models of a Lawvere theory $\Lcal$.

Let $(X,\Acal)$ be a measurable space, let $I$ be an index set, and let

\[
\left\lbrace f_i:X \to Y \; | \; i \in I \right\rbrace
\]

be a collection of functions which are all $\Bcal_Y$-measurable. If $F:X \to Z^I$ is the map given by

\[
f(x) := \big(f_i(x)\big)_{i \in I}
\]

then $f$ is $\Bcal_{Y^I}$-measurable.

Because $Y^I$ is the categorical product of $Y$ taken $I$-many times and carries the product topology, $Y^I$ has basis of open sets

\[
\Bscr := \left\lbrace \prod_{i \in I} U_i \; : \; U_i \subseteq Y\,\text{open}, U_i \ne Y\,\text{for all but finitely many}\,i \right\rbrace.
\]

Similarly, because the Borel $\sigma$-algebra $\Bcal_{Y^I}$ is generated by the opens of $Y^I$ and the open sets of $Y^I$ are generated by those in $\Bscr$ it suffices to prove that for any basic open $U = \prod_{i \in I} U_i$ in $\Bscr$, $f^{-1}(V) \in \Acal$. However, we now note that

\begin{align*}
f^{-1}\left(\prod_{i \in I} U_i\right) &= \left\lbrace x \in X \; : \; (f_i(x))_{i \in I} \in \prod_{i  \in I} U_i \right\rbrace = \left\lbrace x \in X \; | \; \forall\,i\in I.\,f_i(x)\in U_i\right\rbrace \\
&= \bigcap_{i \in I} f_i^{-1}(U_i).
\end{align*}

Because $U$ is a basic open in $Y^I$, at most finitely many of the $U_i$ satisfy $U_i \ne Y$. But then because $f_i^{-1}(Y) = X$, the intersection above is a finite intersection

\[
f^{-1}\left(\prod_{i \in I} U_i\right) = \bigcap_{U_i \ne Y} f_i^{-1}(U_i);
\]

moreover since each $U_i$ is open and each $f_i$ is $\Bcal_Y$-measurable, $f_i^{-1}(U_i) \in \Acal$. But then, as finite intersections are countable, it follows that

\[
f^{-1}\left(\prod_{i \in I} U_i\right) = \bigcap_{U_i \ne Y} f_i^{-1}(U_i) \in \Acal
\]

and so $f$ is Borel measurable.

The lemma above says in categorical terms that if we have a collection of $\Bcal_Y$-measurable morphisms

\[
\left\lbrace f_i:X \to Y \; | \; i \in I \right\rbrace
\]

then the pairing map

\[
\langle f_i \rangle_{i \in I}:X \to Y^I
\]

is $\Bcal_{Y^I}$-measurable.

Let $(X,\Acal)$ be a measurable space, let $Y$ be a topological space, let $I$ be an index set. If

\[
\lbrace f_i:X \to Y \; | \; i \in I \rbrace
\]

is a collection of $\Bcal_Y$-indexed functions and $g:Y^I \to Y$ is a $\Bcal_Y$-measurable function, then the function $h:X \to Y$ given by $h = g \circ \langle f_i \rangle_{i \in I}$ is $\Bcal_Y$-measurable.

Simply apply Lemma <ref> and Proposition <ref> to the composition $h = g \circ \langle f_i \rangle_{i \in I}$.

Combining these tools together allows us to prove our main theorem: the collection of Borel-measurable functions from a measurable space $(X,\Acal)$ into a topological model of a Lawvere theory $\Lcal$ gives rise to a set-theoretic model of $\Lcal$.

Let $\Tcal$ be a Lawvere theory and let $Y$ be a topological model of $\Tcal$, i.e., $Y \in \Tcal(\Top)_0$. Then if $(X, \Acal)$ is a measurable space, the set

\[
\Meas(X,Y;\Bcal_X) = \lbrace f:X \to Y \; | \; f\,\text{is}\,\Bcal_Y\textnormal{-measurable}\rbrace
\]

is an object in $\Tcal(\Set)_0$.

Because $Y$ is a topological model of $\Tcal$, we write

\[
\underline{Y}:\Tcal \to \Top
\]

for the corresponding functor and specify that $\underline{Y}(D) = Y$ for $D$ the distinguished object of $\Tcal$. To show that $\Meas(X,Y;\Bcal_Y)$ is a model of $\Tcal$ in $\Set$, we define

\[
\underline{\Meas(X,Y;\Bcal_Y)}:\Tcal \to \Set
\]

as follows:

* For objects $D^I$ for index sets $I$, we define

\[
\underline{\Meas(X,Y;\Bcal_Y)}(D^I) := \Meas(X,Y^{I};\Bcal_{Y^I}).
\]

* For morphisms $\phi:D^I \to D^J$ in $\Tcal$, we define

\[
\underline{\Meas(X,Y;\Bcal_Y)}(D^I) \to \underline{\Meas(X,Y;\Bcal_{Y})}(D^J)
\]

to be the function

\[
\Meas(X,Y^I;\Bcal_{Y^I}) \to \Meas(X,Y^{J};\Bcal_{Y^J})
\]

given by $f \mapsto \underline{Y}(\varphi) \circ f$.

That this is a functor is a straightforward check from definition and Remark <ref>, while the fact that the assignment on morphisms is well-defined follows from Proposition <ref>. To see that it is product preserving, let $I$ be a set and assume that for all $i \in I$ there is a map $f_i:Z \to \Meas(X,Y;\Bcal_Y)$. Consider the functions $p_i:\Meas(X,Y^{I};\Bcal_{Y^I}) \to \Meas(X,Y;\Bcal_Y)$ given by post-composition by the projection maps $\pi_i:Y^I \to Y$; these are the maps we must show play the role of projections. We define a map $f:Z \to \Meas(X,Y^{I};\Bcal_{Y^I})$ by, for each $z \in Z$, letting $f(z)$ be the function $X \to Y^I$ given by the pairing $\langle f_i(z) \rangle_{i \in I}$. It then follows by construction that for all $i \in I$

\[
p_i \circ f = \pi_i \circ \langle f_i \rangle_{i \in I} = f_i
\]

so the diagram

\[
\begin{tikzcd}
Z \ar[d, swap]{}{f} \ar[dr]{}{f_i} \\
\Meas(X,Y^I;\Bcal_{Y^I}) \ar[r, swap]{}{p_i} & \Meas(X,Y;\Bcal_{Y})
\end{tikzcd}
\]

commutes. The fact that $f$ is unique follows from the fact that each pairing map $\langle f_i(z) \rangle_{i \in I}$ is induced by the universal property of the (Cartesian) product. Thus $\Meas(X,Y^I;\Bcal_{Y^I}) \cong \Meas(X,Y;\Bcal_{Y})^I$ and so the functor $\underline{\Meas(X,Y;\Bcal_{Y})}:\Tcal \to \Set$ is product-preserving. Consequently $\Meas(X,Y;\Bcal_{Y})$ is a set-theoretic model of the Lawvere theory $\Tcal$.

The usefulness of this theorem is exemplified by following straightforward algebraic proofs of the corollaries below (which are in particular of use in functional analysis, representation theory, harmonic analysis, and number theory).

Let $R$ be a topological ring. Then for any measurable space $(X,\Acal)$ the set $\Meas(X,R;\Bcal_{R})$ is a ring. In particular, the real-measurable functions $\Meas(X,\R;\Bcal_{\R})$ and complex-measurable functions $\Meas(X,\C;\Bcal_{\C})$ are rings.

Since rings are set-theoretic models of the Lawvere theory $\Tcal_{\Ring}$ of rings described in Example <ref> and topological rings are topological models of $\Tcal_{\Ring}$, we simply apply Theorem <ref> to the set $\Meas(X,R;\Bcal_{R})$. The final statements follow from the fact that $\R$ and $\C$ are topological rings.

Let $G$ be a topological group and let $(X,\Acal)$ be any measurable space. Then $\Meas(X,G;\Bcal_{G})$ is a group. In particular, for any local field $F$ the set $\Meas(X,\operatorname{GL}_n(F);\Bcal_{\operatorname{GL}_n(F)})$ is a group.

This follows mutatis mutandis to the proof of Corollary <ref> save with the Lawvere theory $\Tcal_{\Ring}$ replaced with the Lawvere theory $\Tcal_{\Grp}$ of groups as described in Example <ref>. The final statement of the corollary follows from the fact that because $F$ is a local field $\operatorname{GL}_n(F)$ naturally inherits the structure of a topological group from the topology on $F$.

[1]
J. Adámek and J. Rosický, Locally presentable and accessible
categories, London Mathematical Society Lecture Note Series, vol. 189,
Cambridge University Press, Cambridge, 1994. 1294136

[2]
M. Barr and C. Wells, Toposes, triples and theories, Repr. Theory
Appl. Categ. (2005), no. 12, x+288, Corrected reprint of the 1985 original
[MR0771116]. 2178101

[3]
M. Brandenburg, Large limit sketches and topological space objects,
2021, Available at <arxive.org/abs/2106.11115>.

[4]
J.B. Conway, A course in abstract analysis, Graduate studies in
mathematics, American Mathematical Society, 2012.

[5]
J. L. Doob, Measure theory, Graduate Texts in Mathematics, vol. 143,
Springer-Verlag, New York, 1994. 1253752

[6]
M. Hyland and J. Power, The category theoretic understanding of
universal algebra: Lawvere theories and monads, Computation, meaning, and
logic: articles dedicated to Gordon Plotkin, Electron. Notes Theor.
Comput. Sci., vol. 172, Elsevier Sci. B. V., Amsterdam, 2007, pp. 437–458.

[7]
F. E. J. Linton, An outline of functorial semantics, Sem. on Triples
and Categorical Homology Theory (ETH, Zürich, 1966/67), Lecture
Notes in Math., No. 80, Springer, Berlin-New York, 1969, pp. 7–52.

[8]
T. Tao, An introduction to measure theory, Graduate Studies in
Mathematics, vol. 126, American Mathematical Society, Providence, RI, 2011.

[9]
M.E. Taylor, Measure theory and integration, Graduate studies in
mathematics, American Mathematical Soc., 2006.


# The Amazing Chromatic Polynomial

Bruce E. Sagan
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
(
Key Words: acyclic orientation, chromatic polynomial, hyperplane arrangement,
increasing tree, Möbius function, partially ordered set
AMS subject classification (2010): 05-02 (Primary) 05C05, 05C32, 06A07
(Secondary) )

###### Abstract

Let $G$ be a combinatorial graph with vertices $V$ and edges $E$. A proper
coloring of $G$ is an assignment of colors to the vertices such that no edge
connects two vertices of the same color. These are the colorings considered in
the famous Four Color Theorem. It turns out that the number of proper
colorings of $G$ using $t$ colors is a polynomial in $t$, called the chromatic
polynomial of $G$. This polynomial has many wonderful properties. It also has
the surprising habit of appearing in contexts which, a priori, have nothing to
do with graph coloring. We will survey three such instances involving acyclic
orientations, hyperplane arrangements, and increasing forests. In addition,
connections to symmetric functions and algebraic geometry will be mentioned.

##  1 Introduction

We begin at the beginning with some basic definitions. Let ${\mathbb{N}}$ and
${\mathbb{P}}$ be the nonnegative and positive integers, respectively. Given
$n\in{\mathbb{N}}$ we will use the notation $[n]=\\{1,2,\ldots,n\\}$ for the
interval of the first $n$ positive integers.

A (combinatorial) graph is $G=(V,E)$ where $V$ is a finite set of vertices and
$E$ is a set of edges, each edge connecting a pair of distinct vertices. If
edge $e$ goes between vertices $u$ and $v$ then we write $e=uv$ or $e=vu$ and
call $u,v$ the endpoints of $e$. Alternatively, we say that $u$ and $v$ are
adjacent. As an example, on the left in Figure 1 we have a graph $G$ with
vertex set $V=\\{u,v,w,x\\}$ and edge set $E=\\{uv,ux,vx,vw\\}$.

Given a set $S$, a coloring of $G$ by $S$ is a function $\kappa:V\rightarrow
S$. Figure 1 displays colorings of $G$ using the set $S=[3]$. For example, the
coloring in the middle has $\kappa(v)=\kappa(x)=1$ and
$\kappa(u)=\kappa(w)=2$. (A coloring function need not be surjective.) We say
that a coloring $\kappa$ is proper if each edge $e=uv$ of $G$ we have
$\kappa(u)\neq\kappa(v)$. Returning to Figure 1 we see that the middle
coloring is not proper since $e=vx$ has $\kappa(v)=\kappa(x)$. But it is easy
to check that the coloring $\kappa^{\prime}$ on the right is proper.

$G$$x$$w$$u$$v$

$\kappa$$1$$2$$2$$1$

$\kappa^{\prime}$$1$$2$$2$$3$

Figure 1: A graph and two colorings

Proper colorings are the subject of the famous Four Color Theorem. If $S$ is a
finite set then we use $\\#S$ or $|S|$ for the cardinality of $S$. The
chromatic number of $G$, denoted $\chi(G)$, is the minimum $\\#S$ such that
there exists a proper coloring $\kappa:G\rightarrow S$. Going back yet again
to the graph in Figure 1, we see that $\chi(G)=3$. Indeed, $\kappa^{\prime}$
is a proper coloring with three colors. And no proper coloring exists with
fewer colors because of the triangle $\\{uv,vx,xu\\}$ which requires three
colors. Call a graph planar if it can be drawn in the Cartesian plane so that
none of its edges cross. Here is the landmark theorem of Appel and Haken
(assisted by Koch).

######  Theorem 1.1 (The Four Color Theorem [AH77, AHK77]).

If $G$ is a planar graph then

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle\chi(G)\leq
4.}\hfill\qed$

This theorem is striking for several reasons. First of all, there is no such
bound for arbitrary graphs. For consider the complete graph, $K_{n}$, which
has $n$ vertices and all $\binom{n}{2}$ possible edges. A drawing of $K_{4}$
is on the left in Figure 2. (The crossing of two edges in the middle of the
graph is not a vertex.) Clearly $\chi(K_{n})=n$ which can be as large as
desired. Second, this result had been conjectured for over $100$ years.
Finally, the proof was the first one to use computers in an integral way since
the number of cases involved was too large for a human to check. The reader
interested in the history of the Four Color Theorem is encouraged to consult
Robin Wilson’s excellent book [Wil02].

Finding $\chi(G)$ is an extremal task since it involves minimization. In this
article we will be interested in a corresponding enumeration problem which was
first studied by George Birkhoff [Bir13]. Given a graph $G=(V,W)$ and
$t\in{\mathbb{N}}$ the corresponding chromatic polynomial is

$P(G)=P(G;t)=\\#\\{\kappa:V\rightarrow[t]\mid\text{$\kappa$ is proper}\\}.$

Note that we could have used any set $S$ with $\\#S=t$ in place of $[t]$ and
gotten the same count. Also, it is not clear why we are calling this a
polynomial. But let’s compute it for our perennial example in Figure 1. We
will color the vertices in the order $u,v,w,x$. Since $u$ is the first vertex
colored, any of the $t$ elements in $[t]$ could be used. So there are $t$
choices for $u$. When we color $v$, it can be any color except the one used on
$u$. This gives $t-1$ choices. Similarly there are $t-1$ choices for $w$.
Finally, when coloring $x$ we see that it is adjacent to the two previously
colored vertices $u$ and $v$. Furthermore, $u$ and $v$ are different colors
since they are also adjacent. This means that there are $t-2$ possible
remaining colors for $x$. Putting all these counts together, we see that the
number of proper colorings of $G$ is

$P(G;t)=t(t-1)(t-1)(t-2)=t^{4}-4t^{3}+5t^{2}-2t.$ (1)

Notice that this is a polynomial in $t$, the number of colors! It turns out
that this is always the case, which explains why $P(G;t)$ is called the
chromatic polynomial.

However, it is not true that one can always count the colorings as we did
above and so obtain a polynomial whose roots are nonnegative integers. To see
what could go wrong, consider the $n$-cycle, $C_{n}$, which has $n$ vertices
which can be ordered as $v_{1},v_{2},\ldots,v_{n}$ and $n$ edges
$v_{i}v_{i+1}$ where $i$ is taken modulo $n$. A copy of the cycle $C_{4}$ is
shown on the right in Figure 2. Let us now try coloring $C_{4}$ in the order
$u,v,w,x$. As before, there are $t$ choices for $u$ and $t-1$ for $v$ and $w$.
But we now have a problem trying to color $x$. For this vertex has edges to
both $u$ and $w$. But since $u$ and $w$ are not adjacent, we do not know
whether they were assigned the same color or not. There is an elegant way
around this difficulty called deletion-contraction which we will discuss in
the next section.

We should also note that there is a simple relationship between the chromatic
number and the chromatic polynomial. Specifically, $\chi(G)$ is the smallest
positive integer such that $P(G;\chi(G))\neq 0$. To see this note that if
$0<t<\chi(G)$ then, by definition of $\chi$, there are no proper colorings of
$G$ with $t$ colors. So, since $P(G;t)$ counts the number of such colorings,
it must evaluate to zero. On the other hand, there must be at least one proper
coloring of $G$ with $t=\chi(G)$ colors. It follows that $P(G;\chi(G))>0$.

The rest of this paper is organized as follows. In the next section we will
introduce the method of deletion-contraction. It will be used to prove that
$P(G;t)$ is always a polynomial in $t$ as well as to compute the chromatic
polynomial of $C_{4}$. We will also exhibit a combinatorial interpretation of
the coefficients of $P(G;t)$ in terms of certain sets of edges of $G$ which
are said to contain no broken circuit. One of the amazing things about
$P(G;t)$ is that it often appears in contexts which seem to have nothing to do
with graph coloring, or even with graphs! Three examples of this will be given
in Section 3. We will end with a section giving more information about the
chromatic polynomial, including connections with symmetric functions and with
algebraic geometry.

$K_{4}$$x$$w$$u$$v$

$C_{4}$$x$$w$$u$$v$

Figure 2: The complete graph $K_{4}$ and the cycle $C_{4}$

##  2 Why is it a polynomial?

In this section we will prove that $P(G;t)$ is actually a polynomial in $t$ by
using the deletion-contraction method. We will also define NBC (no broken
circuit) sets and use them to describe the coefficients of this polynomial.

$G$$x$$w$$u$$v$

$G\setminus vx$$x$$w$$u$$v$

$G/vx$$w$$u$$v^{\prime}$

Figure 3: Deletion and contraction

If $G=(V,E)$ is a graph and $e\in E$ then deleting $e$ from $G$ gives a graph
$G\setminus e$ on the same vertex set and with edges the set difference
$E\setminus\\{e\\}$. The central graph in Figure 3 shows the result of
deleting the edge $e=vx$ from our canonical graph $G$. The contraction of
$e=vx$ in $G$, denoted $G/e$, is obtained by collapsing the edge to a new
vertex $v^{\prime}$ where $v^{\prime}$ is adjacent to all the vertices which
were adjacent either the $v$ or $x$. All other vertices and edges stay the
same in $G/e$. The graph on the right in Figure 3 illustrates $G/vx$. Note
also that the two edges $uv$ and $ux$ in $G$ become a single edge
$uv^{\prime}$ in $G/vx$. Since both $G\setminus e$ and $G/e$ have fewer edges
than $G$, the next result is a perfect recursion for induction on the number
of edges.

######  Lemma 2.1 (Deletion-Contraction Lemma).

Given a graph $G=(V,E)$ and $e\in E$ we have

$P(G)=P(G\setminus e)-P(G/e).$

###### Proof.

We will prove this result in the form

$P(G\setminus e)=P(G)+P(G/e).$ (2)

Suppose $e=vx$. Since $v$ and $x$ are no longer adjacent in $G\setminus e$,
the proper colorings $\kappa$ of this graph are of two types: those where
$\kappa(v)\neq\kappa(x)$ and those where $\kappa(v)=\kappa(x)$. But if
$\kappa$ is proper on $G\setminus e$ and also satisfies
$\kappa(v)\neq\kappa(x)$ then $\kappa$ is a proper coloring of $G$.
Conversely, every proper coloring of $G$ gives rise to a proper coloring of
$G\setminus e$ where $\kappa(v)\neq\kappa(x)$. So these colorings of
$G\setminus e$ are counted by $P(G)$.

Now consider the proper colorings $\kappa$ of $G\setminus e$ with
$\kappa(v)=\kappa(x)$. Such a coloring can be lifted to a proper coloring
$\kappa^{\prime}$ of $G/e$ where $\kappa^{\prime}(w)=\kappa(w)$ for $w\neq
v^{\prime}$, and $\kappa^{\prime}(v^{\prime})$ is the common color assigned to
$v$ and $x$ by $\kappa$. As with colorings of the first type, this produces a
bijections between the proper colorings of $G/e$ and those of $G\setminus e$
with $\kappa(v)=\kappa(x)$. It follows that the number of colorings in this
case is $P(G/e)$. Combining the two possibilties yields equation (2) and
proves the lemma. ∎

It is now easy to prove Birkhoff’s fundamental result about the chromatic
polynomial.

######  Theorem 2.2 ([Bir13]).

Let $G=(V,E)$ be a graph with $\\#V=n$. Then $P(G;t)$ is a polynomial in $t$
of degree

$\deg P(G;t)=n.$

###### Proof.

We will induct on $m=\\#E$. If $m=0$ then $G$ is just a set of $n$ vertices.
Since there are no edges, each vertex can be colored independently in any of
$t$ ways. So in this case $P(G;t)=t^{n}$ which certainly satisfies the
requirements of the theorem.

Now suppose that $m>0$. So $E$ is nonempty and pick any $e\in E$. By the
Deletion-Contraction Lemma, $P(G)=P(G\setminus e)-P(G/e)$. By induction,
$P(G\setminus e)$ is a polynomial in $t$ of degree $n$ since $G\setminus e$
and $G$ have the same number of vertices. We also have that $P(G/e)$ is a
polynomial in $t$. But it has one fewer vertex than $G$ and so is of degree
$n-1$. The proof is completed by observing that the difference of a polynomial
of degree $n$ and one of degree $n-1$ is a polynomial of degree $n$. ∎

Deletion-contraction is also a useful tool when it comes to computing
chromatic polynomials. Recall that we were not able to compute $P(C_{4})$ for
the $4$-cycle in the previous section. But after deleting and contracting one
of its edges $e$, the computation is reduced to graphs where we can apply the
vertex-by-vertex technique used earlier. Specifically,

$P\left(\rule{0.0pt}{20.0pt}\right.$$e$$\left.\rule{0.0pt}{20.0pt}\right)$
=$P\left(\rule{0.0pt}{20.0pt}\right.$$\left.\rule{0.0pt}{20.0pt}\right)$$-$$P\left(\rule{0.0pt}{20.0pt}\right.$$\left.\rule{0.0pt}{20.0pt}\right)$
$\displaystyle=t(t-1)^{3}-t(t-1)(t-2)$ $\displaystyle=t(t-1)(t^{2}-3t+3).$

Note that, unlike the polynomial computed in Section 1, this one has complex
roots.

$G$$b$$c$$d$$e$

$C$$b$$c$$d$

$B$$c$$d$

Figure 4: A broken circuit

Since $P(G;t)$ is a polynomial, one would like a description of its
coefficients. This was done by Hassler Whitney [Whi32]. Fix a total ordering
$e_{1}<e_{2}<\ldots<e_{m}$ of the edge set $E$. A broken circuit of $G$ is a
subset $B\subset E$ obtained by removing the smallest edge from the edge set
of some cycle of $G$. Consider our usual graph $G$ with edges labeled as in
Figure 4 and ordered by $b<c<d<e$. Then $G$ has a unique cycle $C$ with edges
$\\{b,c,d\\}$. The corresponding broken circuit is $\\{c,d\\}$. Call
$A\subseteq E$ an NBC set (short for no broken circuit set) if $A$ does not
contain any broken circuit of $G$. In our example, these are exactly the edge
sets not containing $\\{c,d\\}$. Let

$\operatorname{nbc}_{k}(G)=\\#\\{A\subseteq E\mid\text{$A$ is an NBC set with
$k$ edges}\\}.$

Making a chart of these numbers for our example graph gives

$\begin{array}[]{c|c|c}k&\text{NBC sets with $k$
edges}&\operatorname{nbc}_{k}(G)\\\ \hline\cr\hline\cr
0&\emptyset&1\rule{0.0pt}{15.0pt}\\\\[5.0pt] 1&\\{b\\},\ \\{c\\},\ \\{d\\},\
\\{e\\}&4\\\\[5.0pt] 2&\\{b,c\\},\ \\{b,d\\},\ \\{b,e\\},\ \\{c,e\\},\
\\{d,e\\}&5\\\\[5.0pt] 3&\\{b,c,e\\},\ \\{b,d,e\\}&2\\\\[5.0pt]
4&\text{none}&0\end{array}$

Comparing the last column to the coefficients of $P(G;t)$ as calculated in
(1), the reader should have a conjecture in mind.

######  Theorem 2.3 ([Whi32]).

For any graph $G=(V,E)$ with $\\#V=n$ and any total order on $E$ we have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle
P(G;t)=\sum_{k=0}^{n}(-1)^{k}\operatorname{nbc}_{k}(G)\ t^{n-k}.}\hfill\qed$.

This theorem is remarkable since it implies that the numbers
$\operatorname{nbc}_{k}(G)$ do not depend on the ordering given to the edge
set, even though the actual NBC sets may be different. It also makes
calculating certain coefficients of $P(G;t)$ very easy. For example
$\operatorname{nbc}_{0}(G)=1$ because of the empty edge set. So $P(G;t)$ is
monic. Furthermore, since a cycle has at least three edges, any broken circuit
has at least two. It follows that all single edges are NBC and thus the
coefficient of $t^{n-1}$ is $-|E|$.

##  3 Three applications

We will now look at three theorems where the chromatic polynomial makes a
surprising appearance. These are results of Stanley [Sta73] on acyclic
orientations, Zaslavsky [Zas75] on hyperplane arrangements, and Hallam and
Sagan [HS15] on increasing forests (later improved upon by Hallam, Martin and
Sagan [HMS19]).

$O$$x$$w$$u$$v$

$O^{\prime}$$x$$w$$u$$v$

Figure 5: Two orientations

A digraph or directed graph is $D=(V,A)$ consisting of a set of vertices $V$
and a set of arcs $A$ where each arc goes from one vertex to another. If arc
$a$ goes from vertex $u$ to vertex $v$ then we write $a=\vec{uv}$. For
example, the arc set for the digraph $O$ in Figure 5 is $A=\\{\vec{uv},\
\vec{vx},\ \vec{xu},\ \vec{wv}\\}$. A directed cycle
$v_{1},v_{2},\ldots,v_{n}$ in a digraph is defined analogously to a cycle in a
graph where one insists that there is an arc from $v_{i}$ to $v_{i+1}$ for all
$i$ modulo $n$. A digraph without cycles is said to be acyclic. In Figure 5,
the digraph $O$ has a cycle $u,v,x$ while $O^{\prime}$ is acyclic.

Given a graph $G=(V,E)$, an orientation of $G$ is a digraph obtained by
replacing each edge $uv$ by one of its two possible orientations $\vec{uv}$ or
$\vec{vu}$. The two digraphs in Figure 5 are both orientations of our standard
example graph $G$ in Figure 1. Clearly the number of orientations of $G$ is
$2^{\\#E}$. But what if we require the orientations to be acyclic? Let

${\cal O}(G)=\\{O\mid\text{$O$ is an acyclic orientation of $G$}\\}.$

Returning to our standard example, there are $2^{3}$ orientations of the
(undirected) cycle $u,v,x$. Of these, two of them create a directed cycle, one
going clockwise and the other counterclockwise. So there are $2^{3}-2=6$
acyclic orientations of this part of $G$. As for the edge $vw$, it can be
oriented either way without producing a cycle. So for this graph $\\#{\cal
O}(G)=6\cdot 2=12$. We will now do something completely crazy. Let’s plug
$t=-1$ into the chromatic polynomial of $G$ as computed in (1). This gives

$P(G;-1)=(-1)^{4}-4(-1)^{3}+5(-1)^{2}-2(-1)=12.$

This is the same $12$ as the previous one.

######  Theorem 3.1 ([Sta73]).

For any graph $G=(V,E)$ with $\\#V=n$ we have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle
P(G;-1)=(-1)^{n}\\#{\cal O}(G).}\hfill\qed$

It is not at all clear what it means to color a graph with $-1$ colors.
However, we can make some combinatorial sense of this result. By Theorem 2.3
we have

$P(G;-1)=\sum_{k=0}^{n}(-1)^{k}\operatorname{nbc}_{k}(G)\
(-1)^{n-k}=(-1)^{n}\sum_{k=0}^{n}\operatorname{nbc}_{k}(G).$

So one could give a combinatorial proof of Theorem 3.1 by constructing a
bijection between the NBC sets of $G$ and its acyclic orientations as was done
by Blass and Sagan [BS86].

$y=2x$$y=-x$ Figure 6: A hyperplane arrangement in ${\mathbb{R}}^{2}$

We now turn to hyperplane arrangements. Let ${\mathbb{R}}$ be the real
numbers. A hyperplane $H$ in ${\mathbb{R}}^{n}$ is a subspace of dimension
$n-1$. Note that, as a subspace, a hyperplane must go through the origin. A
hyperplane arrangement is just a finite set of hyperplanes ${\cal
H}=\\{H_{1},H_{2},\ldots,H_{k}\\}$. For example, in ${\mathbb{R}}^{2}$ the
hyperplanes are just lines through $(0,0)$ and the arrangement ${\cal
H}=\\{y=2x,\ y=-x$} is shown in Figure 6 (without the coordinate axes for
clarity in what comes later). The regions of an arrangement ${\cal H}$ are the
connected components that remain after one removes the hyperplanes of the
arrangement from ${\mathbb{R}}^{n}$. Let $R({\cal H})$ be the set of regions
of ${\cal H}$. So in Figure 6, $R({\cal H})$ consists of four regions. Indeed,
any arrangement of $k$ hyperplanes in ${\mathbb{R}}^{2}$ has $2k$ regions, but
things get more complicated in ${\mathbb{R}}^{n}$.

At first blush, these concepts seem to have nothing to do with the chromatic
polynomial. But wait! Suppose $G=(V,E)$ is a graph with $V=[n]$. Note that we
are now using an interval of integers for the labels of the vertices, not for
the colors of a coloring. Write

${\mathbb{R}}^{n}=\\{(x_{1},x_{2},\ldots,x_{n})\mid\text{$x_{i}\in{\mathbb{R}}$
for all $i\in[n]$}\\}.$

We can now associate with $G$ an arrangement of hyperplanes in
${\mathbb{R}}^{n}$ defined by

${\cal H}(G)=\\{x_{i}=x_{j}\mid ij\in E\\}.$

So each edge of $G$ gives rise to a hyperplane gotten by setting the
coordinate functions of its endpoints equal. As an example, suppose $G$ has
$V=[3]$ and $E=\\{12,23\\}$. Then the corresponding arrangement would be
${\cal H}(G)=\\{x_{1}=x_{2},\ x_{2}=x_{3}\\}$ in ${\mathbb{R}}^{3}$. Notice
that the number of regions of ${\cal H}(G)$ is $4$ in this case. It is also
easy to see that $P(G;t)=t(t-1)^{2}$ so that $P(G;-1)=-4$. Again, this is not
an accident.

######  Theorem 3.2 ([Zas75]).

For any graph $G=(V,E)$ with $V=[n]$ we have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle
P(G;-1)=(-1)^{n}\cdot\\#R({\cal H}(G)).}\hfill\qed$

Seeing the two previous theorems back-to-back, the reader may suspect that
they are related. In fact there is a bijection between acyclic orientations of
$G$ with vertices labeled by $[n]$ and regions of its hyperplane arrangement.
Every hyperplane $x_{i}=x_{j}$ determines two half-spaces, namely
$x_{i}<x_{j}$ and $x_{i}>x_{j}$. Consider these as corresponding to the arcs
$\vec{ij}$ and $\vec{ji}$, respectively. One can then show that an orientation
$O$ of $G$ is acyclic if and only if the intersection of the associated half-
spaces is a region of ${\cal H}(G)$.

For our third application, we will need a few more definitions from graph
theory. A subgraph of $G=(V,E)$ is a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ with $V^{\prime}\subseteq V$ and
$E^{\prime}\subseteq E$. We say $G^{\prime}$ is spanning if $V^{\prime}=V$. In
this case, we often identify $G$ with its edge set since the set of vertices
is fixed. In Figure 7 we see our usual example graph with the vertices
relabeled by $[4]$, as well as two spanning subgraphs $F=\\{12,24\\}$ and
$F^{\prime}=\\{14,24\\}$. A path from $u$ to $v$ in $G$ is a sequence of
distinct vertices $P:u=v_{1},v_{2},\ldots,v_{n}=v$ where $v_{i}v_{i+1}\in E$
for $i\in[n-1]$. Returning to Figure 7 we see that $P:4,1,2,3$ is a path from
$4$ to $3$ in $G$. Call $G$ connected if for every pair of vertices $u,v$
there is a path from $u$ to $v$. More generally, the components of $G$ are the
connected subgraphs which are maximal with respect to inclusion. So a
connected graph has one component. The graph $G$ in Figure 7 is connected, but
the subgraphs $F$ and $F^{\prime}$ are not. Both of these subgraphs have two
components.

$G$$4$$3$$1$$2$

$F$$4$$3$$1$$2$

$F^{\prime}$$4$$3$$1$$2$

Figure 7: A graph $G$ and two spanning forests $F,F^{\prime}$

A graph $F$ is a forest if it contains no (undirected) cycles. The components
of $F$ are called trees. Trees can be characterized by the fact that for any
pair of vertices there is a unique path between them, So $F$ and $F^{\prime}$
in Figure 7 are spanning forests of $G$. Let $F$ be a forest with $V=[n]$ so
that we can compare the size of the vertex labels. Say that $F$ is increasing
if the vertex labels of any path starting at the minimum vertex in its
component tree form an increasing sequence. So the forest $F$ in Figure 7 is
increasing. Indeed, in the tree with one vertex, there is only the path $3$
which is trivially increasing. Note that a similar argument shows that any
tree with only one or two vertices satisfies the increasing condition. As far
as the tree with three vertices in $F$, all paths from the minimum vertex $1$
are subpaths of $1,2,4$. And this is an increasing sequence. On the other
hand, the forest $F^{\prime}$ is not increasing since $1,4,2$ is a path
starting at $1$ which is not an increasing sequence.

Given $G$ with vertices $[n]$, consider the integers

$\operatorname{isf}_{k}(G)=\\#\\{F\mid\text{$F$ is an increasing spanning
forest of $G$ with $k$ edges}\\}$

with generating function

$\operatorname{ISF}(G)=\operatorname{ISF}(G;t)=\sum_{k=0}^{n}(-1)^{k}\operatorname{isf}_{k}(G)\
t^{n-k},$

Note that, although our notation doesn’t show it, $\operatorname{isf}_{k}(G)$
depends on how the vertices of $G$ are labeled. Also, it is not clear why we
have introduced the signs in $\operatorname{ISF}(G)$ or why we made
$\operatorname{isf}_{k}(G)$ the coefficient of $t^{n-k}$ rather than $t^{k}$.
But this will become obvious shortly. Let us compute the generating function
for $G$ as in Figure 7. First of all $\operatorname{isf}_{0}(G)=1$ because the
spanning graph with no edges has only single vertex trees which are all
increasing. Next $\operatorname{isf}_{1}(G)=\\#E=4$ since any single edge is
increasing. There are $\binom{4}{2}=6$ ways to choose a spanning forest with
two edges, of which only the $F^{\prime}$ in Figure 7 is not increasing. So
$\operatorname{isf}_{2}(G)=6-1=5$. Similarly, one computes that
$\operatorname{isf}_{3}(G)=2$. Finally, $\operatorname{isf}_{4}(G)=0$ since
the only spanning subgraph of $G$ with $4$ edges is $G$ itself which is not
even a forest. Putting everything together we obtain

$\operatorname{ISF}(G;t)=t^{4}-4t^{3}+5t^{2}-2t,$

a polynomial which we have seen previously!

But before we explore the connection between $\operatorname{ISF}(G;t)$ and
$P(G;t)$, we wish to mention a nice factorization of the former. As usual,
suppose $G=(V,E)$ has $V=[n]$ and define the following edges sets

$E_{j}=E_{j}(G)=\\{ij\in E\mid i<j\\}$

for $j\in[n]$. Note that we always have $E_{1}=\emptyset$ since there are no
vertices with label smaller than $1$. Also the $E_{j}$ partition $E$ in that
$E=\uplus_{j\in[n]}E_{j}$. In our usual example

$E_{1}=\emptyset,\ E_{2}=\\{12\\},\ E_{3}=\\{23\\},\ E_{4}=\\{14,24\\}.$

These sets give rise to the polynomial

$\prod_{j=1}^{4}(t-\\#E_{j})=(t-0)(t-1)(t-1)(t-2)=t^{4}-4t^{3}+5t^{2}-2t$

which by now should be very familiar! This is explained by the next result.

######  Theorem 3.3 ([HS15]).

For any graph $G=(V,E)$ with $V=[n]$ we have the following.

  1. (a)

Subgraph $F$ of $G$ is an increasing spanning forest if and only if $|F\cap
E_{j}|\leq 1$ for all $j\in[n]$.

  2. (b)

We have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle\operatorname{ISF}(G;t)=\prod_{j=1}^{n}(t-\\#E_{j}).}\hfill\qed$

Note that part (b) of this theorem follows directly from part (a). For
expanding the product shows that the coefficient of $t^{n-k}$ is (up to sign)
the number of way of choosing $k$ edges of $G$ with no two coming from the
same $E_{j}$.

There are at least two reasons why one can not always have
$\operatorname{ISF}(G;t)=P(G;t)$. For one thing, the former depends on which
labels are given to the vertices while the latter does not. And we have seen
that $P(C_{4})$ has complex roots, while the previous result shows that the
roots of $\operatorname{ISF}(G)$ are always nonnegative integers. So the
question becomes when are the two polynomials equal? The answer has to do with
the notion of a perfect elimination ordering.

Given $G=(V,E)$ then the graph induced by $W\subseteq V$ is

$G[W]=G\setminus W^{\prime}$

where $W^{\prime}$ is the complement of $W$ in $V$ and deletion of multiple
edges is defined just as it was for a single edge. Another description of
$G[W]$ is that it is the subgraph of $G$ with vertex set $W$ and all possible
edges of $G$ whose endpoints are in $W$. For example, in Figure 7 the graph
$G[1,2,4]$ is a $3$-cycle while $G[2,3,4]$ is the path $3,2,4$.

We say that $G=(V,E)$ has a perfect elimination ordering if there is an
ordering of $V$ as $v_{1},v_{2},\ldots,v_{n}$ such that for all $j\in[n]$ the
induced subgraph $G[V_{j}]$ is complete where

$V_{j}=\\{v_{i}\mid\text{$i<j$ and $v_{i}v_{j}\in E$}\\}.$

This definition may seem strange to those seeing it for the first time. But it
is a useful concept, for example, as a characterization of chordal graphs.
Suppose the vertices of the graph $G$ in Figure 7 are ordered in the natural
way as $1,2,3,4$. Then the corresponding $V_{j}$ are just the vertices smaller
than $j$ in the edges of $E_{j}$ which gives

$V_{1}=\emptyset,\ V_{2}=\\{1\\},\ V_{3}=\\{2\\},\ V_{4}=\\{1,2\\}.$

Clearly the graphs $G[V_{j}]$ for $j\leq 3$ are complete since $G[\emptyset]$
is the empty graph, and $G[v]$ is just $v$ for any single vertex $v$. Finally,
$G[V_{4}]$ is the edge $12$ which is also a complete graph. So we have a
perfect elimination ordering which presages the next theorem.

######  Theorem 3.4 ([HS15]).

Let $G$ be a graph with $V=[n]$. We have $P(G;t)=\operatorname{ISF}(G;t)$ if
and only if the natural order on $[n]$ is a perfect elimination ordering of
$G$. ∎

##  4 Going further

We will now discuss even more striking results related to the chromatic
polynomial. These will include a generalization to symmetric functions and
connections with algebraic geometry.

###  4.1 Credit where credit is due

For pedagogical reasons, the results presented in the previous section only
gave a partial picture of the authors’ contributions. Here we will take a
wider view.

Since the chromatic polynomial of $G=(V,E)$ at $t=-1$ has a nice combinatorial
interpretation, one might ask what happens at negative integers in general.
Let $t\in{\mathbb{P}}$ and $\kappa:V\rightarrow[t]$ a coloring which may not
be proper. Also consider an acyclic orientation $O=(V,A)$ of $G$. We say that
$O$ and $\kappa$ are compatible if

$\vec{uv}\in A\implies\kappa(u)\leq\kappa(v).$

So $O$ is like a gradient vector field, always pointing from lower to higher
values of $\kappa$. Stanley’s full theorem is as follows.

######  Theorem 4.1 ([Sta73]).

For any graph $G=(V,E)$ with $\\#V=n$ and any $t\in{\mathbb{P}}$ we have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle
P(G;-t)=(-1)^{n}\cdot\\#\\{(O,\kappa)\mid\text{$O$ and $\kappa$ are
compatible}\\}.}\hfill\qed$

Note that this result implies Theorem 3.1. For if $t=1$ then there is only one
coloring $\kappa:V\rightarrow[1]$. And this coloring is compatible with any
acyclic orientation. So in this case, the number of compatible pairs is just
the number of acyclic orientations. Sagan and Vatter [SV21] have given a
bijective proof of Theorem 4.1.

As far as Theorem 3.2, there is actually a stronger result which holds for any
hyperplane arrangement. Given an arrangement ${\cal H}$, consider all the
subspaces $S$ of ${\mathbb{R}}^{n}$ which can be formed by intersecting
hyperplanes in ${\cal H}$. This includes ${\mathbb{R}}^{n}$ itself which is
the empty intersection. Partially order the subspaces by reverse inclusion to
form a poset (partially ordered set) called the intersection lattice of ${\cal
H}$ and denoted $L({\cal H})$. Note that ${\mathbb{R}}^{n}$ is the minimum
element of $L({\cal H})$. Given any finite poset $P$ with a minimum there is
an associated function

$\mu:P\rightarrow{\mathbb{Z}}$

call the Möbius function of $P$. This map is a vast generalization of the
Möbius function from number theory and more information about it can be found
in the texts of Sagan [Sag20] or Stanley [Sta97]. We can now form the
characteristic polynomial of ${\cal H}$ which is the generating function

$\chi({\cal H};t)=\sum_{S\in L({\cal H})}\mu(S)\ t^{\dim S}.$

It turns out that if ${\cal H}={\cal H}(G)$ for some graph $G$ then
$\chi({\cal H};t)=P(G;t)$. Here is the full strength of Theorem 3.2.

######  Theorem 4.2 ([Zas75]).

For any hyperplane arrangement ${\cal H}$ in ${\mathbb{R}}^{n}$ we have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle\chi({\cal
H};-1)=(-1)^{n}\cdot\\#R({\cal H}).}\hfill\qed$

Hallam, Martin, and Sagan were able to improve on Theorem 3.4. Let $G=(V,E)$
be a graph with $V=[n]$ and define

${\cal I}{\cal S}{\cal F}_{k}(G)=\\{F\mid\text{$F$ is an increasing spanning
forest of $G$ with $k$ edges}\\}$

so $\\#{\cal I}{\cal S}{\cal F}_{k}(G)=\operatorname{isf}_{k}(G)$. Since
$V=[n]$ and $E$ is a set of pairs of vertices, order $E$ lexicographically
where each $e=ij\in E$ is listed with $i<j$. Let

${\cal N}{\cal B}{\cal C}_{k}(G)=\\{A\subseteq E\mid\text{$A$ is an NBC set
with $k$ edges}\\}$

so that $\\#{\cal N}{\cal B}{\cal C}_{k}(G)=\operatorname{nbc}_{k}(G)$.

######  Theorem 4.3 ([HMS19]).

Let $G=(V,E)$ be a graph with $V=[n]$ and $E$ ordered lexicographically. For
all $k\in{\mathbb{N}}$ we have

${\cal I}{\cal S}{\cal F}_{k}(G)\subseteq{\cal N}{\cal B}{\cal C}_{k}(G)$

with equality for all $k$ if and only if the natural order on $[n]$ is a
perfect elimination order. ∎

In [HMS19] the authors also generalize both Theorems 3.3 and 3.4 to certain
pure simplicial complexes of dimension $d$. When $d=1$, the graphical results
are recovered.

###  4.2 Chromatic symmetric functions

Stanley [Sta95] generalized the chromatic polynomial to a symmetric function.
Let ${\bf x}=\\{x_{1},x_{2},x_{3},\ldots\\}$ be a countably infinite set of
variables. A formal power series $f({\bf x})$ is symmetric if it is of bounded
degree and invariant under permutations of the variables. For example

$f({\bf
x})=7x_{1}x_{2}^{2}+7x_{2}x_{1}^{2}+7x_{1}x_{3}^{2}+\cdots-2x_{1}x_{2}x_{3}-2x_{1}x_{2}x_{4}-2x_{1}x_{3}x_{4}-\cdots$

is symmetric since all monomials of the form $x_{i}x_{j}^{2}$ have coefficient
$7$, and all monomials of the form $x_{i}x_{j}x_{k}$ have coefficient $-2$.

$P$$u$$w$$v$

$\kappa$$1$$1$$2$

$\kappa^{\prime}$$2$$2$$1$

Figure 8: A path and two of its colorings

Consider colorings of a graph $G=(V,E)$ using the positive integers
$\kappa:V\rightarrow{\mathbb{P}}$. Associated with each such coloring is its
monomial

${\bf x}^{\kappa}=\prod_{v\in V}x_{\kappa(v)}.$

Going back to our faithful example graph in Figure 1, the middle coloring has
${\bf x}^{\kappa}=x_{1}^{2}x_{2}^{2}$ while the one on the right has ${\bf
x}^{\kappa^{\prime}}=x_{1}x_{2}^{2}x_{3}$. We now define the chromatic
symmetric function of $G$ to be

$X(G)=X(G;{\bf x})=\sum_{\kappa:V\rightarrow{\mathbb{P}}}{\bf x}^{\kappa}$

where the sum is over proper colorings $\kappa:V\rightarrow{\mathbb{P}}$. As
an example, consider the path $P$ as shown in Figure 8. There are no proper
colorings of $P$ with a single color. Suppose we wish to use the two colors
$1$ and $2$. Then there are two possibilities as shown in the figure which
contribute ${\bf x}^{\kappa}=x_{1}^{2}x_{2}$ and ${\bf
x}^{\kappa^{\prime}}=x_{1}x_{2}^{2}$ to $X(P)$. The same argument shows that
we get a term $x_{i}x_{j}^{2}$ for any distinct $i,j\in{\mathbb{P}}$. Now
consider using three colors on $P$, say $1$, $2$, and $3$. Then any bijection
$\kappa:V\rightarrow[3]$ is proper. There are $6$ such maps for a contribution
of $6x_{1}x_{2}x_{3}$. Again, the choice of these three particular colors is
immaterial so we get a term $6x_{i}x_{j}x_{k}$ for any three positive integers
$i,j,k$. Putting things all together we obtain

$X(P)=\sum_{\text{$i,j$ distinct}}x_{i}^{2}x_{j}+6\sum_{\text{$i,j,k$
distinct}}x_{i}x_{j}x_{k}$

which is a symmetric function. In general, $X(G)$ is symmetric because
permuting colors in a proper coloring leaves it proper.

Note also that $X(G;{\bf x})$ generalizes $P(G;t)$ in the following way. Set

$\text{$x_{1}=x_{2}=\ldots=x_{t}=1$ and $x_{i}=0$ for $i>t$}.$ (3)

Then each ${\bf x}^{\kappa}$ equals $0$ or $1$, and the latter happens only
when $\kappa$ uses colors in $[t]$. So, under this substitution

$X(G;{\bf x})=\sum_{\kappa:V\rightarrow[t]}1=P(G;t)$

by definition of the chromatic polynomial.

One can now prove symmetric function generalizations of results about
chromatic polynomials and also theorems about $X(G)$ which do not have
analogues for $P(G)$. To illustrate, we give an analogue of Whitney’s NBC
Theorem. Define

$c(G)=\text{number of components of $G$}.$

Note that if $G=(V,E)$ with $\\#V=n$ and $A\in{\cal N}{\cal B}{\cal C}_{k}(G)$
then $A$ is a forest, since if $A$ contained any cycle it would contain the
corresponding broken circuit. And $A$ is a spanning subgraph so $c(A)=n-k$.
Thus we can rewrite Theorem 2.3 as

$P(G;t)=\sum_{k=0}^{n}\ \sum_{A\in{\cal N}{\cal B}{\cal C}_{k}(G)}\ (-1)^{k}\
t^{n-k}=\sum_{\text{$A$ NBC}}(-1)^{\\#A}\ t^{c(A)}.$ (4)

Symmetric functions form an algebra whose bases are indexed by partitions
which are weakly decreasing sequences
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{l})$ of positive integers
called parts. Consider the power sum symmetric function basis defined
multiplicitively by

$p_{n}=x_{1}^{n}+x_{2}^{n}+x_{3}^{n}+\cdots$

for $n\in{\mathbb{P}}$ and

$p_{\lambda}=p_{\lambda_{1}}p_{\lambda_{2}}\cdots p_{\lambda_{l}}.$

To illustrate

$p_{3}=x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+\cdots$

and

$p_{(3,3,1)}=p_{3}p_{3}p_{1}=(x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+\cdots)^{2}(x_{1}+x_{2}+x_{3}+\cdots).$

Note that using the substitution (3) we get $p_{n}=t$ and $p_{\lambda}=t^{l}$
where $l$ is the number of parts of $\lambda$. Given any graph $G$ there is a
corresponding partition $\lambda(G)$ whose parts are just the vertex sizes of
the components of $G$. As an example, in Figure 7 we have
$\lambda(F)=\lambda(F^{\prime})=(3,1)$. The usual substitution shows that the
following result generalizes Whitney’s Theorem in the form (4),

######  Theorem 4.4 ([Sta95]).

For any graph $G=(V,E)$ and any total order on $E$ we have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle
X(G;x)=\sum_{\text{$A$ NBC}}(-1)^{\\#A}\ p_{\lambda(A)}.}\hfill\qed$

However, the symmetric function does not always mirror the polynomial. Let $T$
be a tree with $n$ vertices. Then it is easy to see that for all such trees
$P(T;t)=t(t-1)^{n-1}$. It seems as if the opposite may be true for $X(T;t)$.
Call two graphs isomorphic if they yield the same graph once the labels on the
vertices are removed. For example, the two forests in Figure 7 are isomorphic.
For more information about the following conjecture, the reader can consult
[APZ14, MMW08, OS14].

######  Conjecture 4.5 ([Sta95]).

If $T$ and $T^{\prime}$ are non-isomorphic trees then

$X(T;{\bf x})\neq X(T^{\prime};x).$

Gessel [Ges84] introduced quasisymmetric functions which are an important
refinement of symmetric functions. Recently Shareshian and Wachs [SW16] showed
that there is a quasisymmetric refinement of $X(G;{\bf x})$. This
quasisymmetric function has important connections with Hessenberg varieties in
algebraic geometry.

###  4.3 Log-concavity

A sequence of real numbers $a_{0},a_{1},\ldots,a_{n}$ is said to be log-
concave if

$a_{k}^{2}\geq a_{k-1}a_{k+1}$

for all $0<k<n$. As an example, the $n$th row of Pascal’s Triangle

$\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$

can be easily shown to be log-concave by using the formula for a binomial
coefficient in terms of factorials. Log-conave sequences abound in
combinatorics, algebra, and geometry. See the survey articles of Stanley
[Sta89], Brenti [Bre94], and Brändén [Br15] for a plethora of examples. We
call a polynomial $p(t)=\sum_{k\geq 0}a_{k}t^{k}$ log-concave if its
coefficient sequence is. In 2012, June Huh stunned the combinatorial world by
using deep methods from algebraic geometry to prove the following result which
generalizes a conjecture of Ronald Read [Rea68] from 1968.

######  Theorem 4.6 ([Huh12]).

For any graph $G$ we have that $P(G;t)$ is log-concave. ∎

By developing a combinatorial version of Hodge theory, Adiprasito, Huh, and
Katz [AHK18] were able to extend this result by proving the log-concavity of
the characteristic polynomial of a matroid (a combinatorial object which
generalizes both graphs and vector spaces).

## References

  * [AH77] K. Appel and W. Haken.  Every planar map is four colorable. I. Discharging.  Illinois J. Math., 21(3):429–490, 1977.
  * [AHK77] K. Appel, W. Haken, and J. Koch.  Every planar map is four colorable. II. Reducibility.  Illinois J. Math., 21(3):491–567, 1977.
  * [AHK18] Karim Adiprasito, June Huh, and Eric Katz.  Hodge theory for combinatorial geometries.  Ann. of Math. (2), 188(2):381–452, 2018.
  * [APZ14] José Aliste-Prieto and José Zamora.  Proper caterpillars are distinguished by their chromatic symmetric function.  Discrete Math., 315:158–164, 2014.
  * [Bir13] George D. Birkhoff.  A determinant formula for the number of ways of coloring a map.  Ann. of Math. (2), 14(1-4):42–46, 1912/13.
  * [Br15] Petter Brändén.  Unimodality, log-concavity, real-rootedness and beyond.  In Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), pages 437–483. CRC Press, Boca Raton, FL, 2015.
  * [Bre94] Francesco Brenti.  Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update.  In Jerusalem combinatorics ’93, volume 178 of Contemp. Math., pages 71–89. Amer. Math. Soc., Providence, RI, 1994.
  * [BS86] Andreas Blass and Bruce Eli Sagan.  Bijective proofs of two broken circuit theorems.  J. Graph Theory, 10(1):15–21, 1986.
  * [Ges84] Ira M. Gessel.  Multipartite $P$-partitions and inner products of skew Schur functions.  In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math., pages 289–317. Amer. Math. Soc., Providence, RI, 1984.
  * [HMS19] Joshua Hallam, Jeremy L. Martin, and Bruce E. Sagan.  Increasing spanning forests in graphs and simplicial complexes.  European J. Combin., 76:178–198, 2019.
  * [HS15] Joshua Hallam and Bruce Sagan.  Factoring the characteristic polynomial of a lattice.  J. Combin. Theory Ser. A, 136:39–63, 2015.
  * [Huh12] June Huh.  Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs.  J. Amer. Math. Soc., 25(3):907–927, 2012.
  * [MMW08] Jeremy L. Martin, Matthew Morin, and Jennifer D. Wagner.  On distinguishing trees by their chromatic symmetric functions.  J. Combin. Theory Ser. A, 115(2):237–253, 2008.
  * [OS14] Rosa Orellana and Geoffrey Scott.  Graphs with equal chromatic symmetric functions.  Discrete Math., 320:1–14, 2014.
  * [Rea68] Ronald C. Read.  An introduction to chromatic polynomials.  J. Combinatorial Theory, 4:52–71, 1968.
  * [Sag20] Bruce E. Sagan.  Combinatorics: The art of counting, volume 210 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, [2020] ©2020.
  * [Sta73] Richard P. Stanley.  Acyclic orientations of graphs.  Discrete Math., 5:171–178, 1973.
  * [Sta89] Richard P. Stanley.  Log-concave and unimodal sequences in algebra, combinatorics, and geometry.  In Graph theory and its applications: East and West (Jinan, 1986), volume 576 of Ann. New York Acad. Sci., pages 500–535. New York Acad. Sci., New York, 1989.
  * [Sta95] Richard P. Stanley.  A symmetric function generalization of the chromatic polynomial of a graph.  Adv. Math., 111(1):166–194, 1995.
  * [Sta97] Richard P. Stanley.  Enumerative Combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1997.  With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.
  * [SV21] Bruce Sagan and Vincent Vatter.  Bijective Proofs of Proper Coloring Theorems.  Amer. Math. Monthly, 128(6):483–499, 2021.
  * [SW16] John Shareshian and Michelle L. Wachs.  Chromatic quasisymmetric functions.  Adv. Math., 295:497–551, 2016.
  * [Whi32] Hassler Whitney.  A logical expansion in mathematics.  Bull. Amer. Math. Soc., 38(8):572–579, 1932.
  * [Wil02] Robin Wilson.  Four colors suffice.  Princeton University Press, Princeton, NJ, 2002.  How the map problem was solved.
  * [Zas75] Thomas Zaslavsky.  Facing up to arrangements: face-count formulas for partitions of space by hyperplanes.  Mem. Amer. Math. Soc., 1(issue 1, 154):vii+102, 1975.