# A note on non-broken-circuit sets and the chromatic polynomial

Darij Grinberg

(version 1.1, )

###### Contents

  1. 1 Definitions and a main result
    1. 1.1 Graphs and colorings
    2. 1.2 Symmetric functions
    3. 1.3 Chromatic symmetric functions
    4. 1.4 Connected components
    5. 1.5 Circuits and broken circuits
  2. 2 Proof of Theorem 1.11
    1. 2.1 $\operatorname*{Eqs}f$ and basic lemmas
    2. 2.2 Alternating sums
  3. 3 The chromatic polynomial
    1. 3.1 Definition
    2. 3.2 Formulas for $\chi_{G}$
    3. 3.3 Proofs
    4. 3.4 Special case: Whitney’s Broken-Circuit Theorem
  4. 4 Application to transitive directed graphs
  5. 5 A matroidal generalization
    1. 5.1 An introduction to matroids
    2. 5.2 The lattice of flats
    3. 5.3 Generalized formulas

## ***

The purpose of this note is to demonstrate several generalizations of
Whitney’s theorem [BlaSag86] – a classical formula for the chromatic
polynomial of a graph. The directions in which we generalize this formula are
the following:

  * •

Instead of summing over the sets which contain no broken circuits, we can sum
over the sets which are “$\mathfrak{K}$-free” (i.e., contain no element of
$\mathfrak{K}$ as a subset), where $\mathfrak{K}$ is some fixed set of broken
circuits (in particular, $\mathfrak{K}$ can be $\varnothing$, yielding another
well-known formula for the chromatic polynomial).

  * •

Even more generally, instead of summing over $\mathfrak{K}$-free subsets, we
can make a weighted sum over all subsets, where the weight depends on the
broken circuits contained in the subset.

  * •

Analogous (and more general) results hold for chromatic symmetric functions.

  * •

Analogous (and more general) results hold for matroids instead of graphs.

Note that, to my knowledge, the last two generalizations cannot be combined:
Unlike graphs, matroids do not seem to have a well-defined notion of a
chromatic symmetric function.

We shall explore these generalizations in the note below. We shall also use
them to prove an apparently new formula for the chromatic polynomial of a
graph obtained from a transitive digraph by forgetting the orientations of the
edges (Proposition 4.2). This latter formula was suggested to me as a
conjecture by Alexander Postnikov, during a discussion on hyperplane
arrangements on a space with a bilinear form; it is this formula which gave
rise to this whole note. The subject of hyperplane arrangements, however, will
not be breached here.

### Acknowledgments

I thank Alexander Postnikov and Richard Stanley for discussions on hyperplane
arrangements that led to the results in this note.

##  1 Definitions and a main result

###  1.1 Graphs and colorings

This note will be concerned with finite graphs. While some results of this
note can be generalized to matroids, we shall not discuss this generalization
here. Let us start with the definition of a graph that we shall be using:

######  Definition 1.1.

(a) If $V$ is any set, then $\dbinom{V}{2}$ will denote the set of all
$2$-element subsets of $V$. In other words, if $V$ is any set, then we set

$\displaystyle\dbinom{V}{2}$
$\displaystyle=\left\\{S\in\mathcal{P}\left(V\right)\ \mid\
\left|S\right|=2\right\\}$ $\displaystyle=\left\\{\left\\{s,t\right\\}\ \mid\
s\in V,\ t\in V,\ s\neq t\right\\}$

(where $\mathcal{P}\left(V\right)$ denotes the powerset of $V$).

(b) A graph means a pair $\left(V,E\right)$, where $V$ is a set, and where $E$
is a subset of $\dbinom{V}{2}$. A graph $\left(V,E\right)$ is said to be
finite if the set $V$ is finite. If $G=\left(V,E\right)$ is a graph, then the
elements of $V$ are called the vertices of the graph $G$, while the elements
of $E$ are called the edges of the graph $G$. If $e$ is an edge of a graph
$G$, then the two elements of $e$ are called the endpoints of the edge $e$. If
$e=\left\\{s,t\right\\}$ is an edge of a graph $G$, then we say that the edge
$e$ connects the vertices $s$ and $t$ of $G$.

Comparing our definition of a graph with some of the other definitions used in
the literature, we thus observe that our graphs are undirected (i.e., their
edges are sets, not pairs), loopless (i.e., the two endpoints of an edge must
always be distinct), edge-unlabelled (i.e., their edges are just $2$-element
sets of vertices, rather than objects with “their own identity”), and do not
have multiple edges (or, more precisely, there is no notion of several edges
connecting two vertices, since the edges form a set, nor a multiset, and do
not have labels).

######  Definition 1.2.

Let $G=\left(V,E\right)$ be a graph. Let $X$ be a set.

(a) An $X$-coloring of $G$ is defined to mean a map $V\rightarrow X$.

(b) An $X$-coloring $f$ of $G$ is said to be proper if every edge
$\left\\{s,t\right\\}\in E$ satisfies $f\left(s\right)\neq f\left(t\right)$.

###  1.2 Symmetric functions

We shall now briefly introduce the notion of symmetric functions. We shall not
use any nontrivial results about symmetric functions; we will merely need some
notations.111For an introduction to symmetric functions, see any of [Stanle99,
Chapter 7], [Martin15, Chapter 9] and [GriRei14, Chapter 2] (and a variety of
other texts).

In the following, $\mathbb{N}$ means the set $\left\\{0,1,2,\ldots\right\\}$.
Also, $\mathbb{N}_{+}$ shall mean the set $\left\\{1,2,3,\ldots\right\\}$.

A partition will mean a sequence
$\left(\lambda_{1},\lambda_{2},\lambda_{3},\ldots\right)\in\mathbb{N}^{\infty}$
of nonnegative integers such that
$\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\geq\cdots$ and such that all
sufficiently high integers $i\geq 1$ satisfy $\lambda_{i}=0$. If
$\lambda=\left(\lambda_{1},\lambda_{2},\lambda_{3},\ldots\right)$ is a
partition, and if a positive integer $n$ is such that all integers $i\geq n$
satisfy $\lambda_{i}=0$, then we shall identify the partition $\lambda$ with
the finite sequence
$\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n-1}\right)$. Thus, for
example, the sequences $\left(3,1\right)$ and $\left(3,1,0\right)$ and the
partition $\left(3,1,0,0,0,\ldots\right)$ are all identified. Every weakly
decreasing finite list of positive integers thus is identified with a unique
partition.

Let $\mathbf{k}$ be a commutative ring with unity. We shall keep $\mathbf{k}$
fixed throughout the paper. The reader will not be missing out on anything if
she assumes that $\mathbf{k}=\mathbb{Z}$.

We consider the $\mathbf{k}$-algebra
$\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ of
(commutative) power series in countably many distinct indeterminates
$x_{1},x_{2},x_{3},\ldots$ over $\mathbf{k}$. It is a topological
$\mathbf{k}$-algebra222See [GriRei14, Section 2.6] or [Grinbe16, §2] for the
definition of its topology. This topology makes sure that a sequence
$\left(P_{n}\right)_{n\in\mathbb{N}}$ of power series converges to some power
series $P$ if and only if, for every monomial $\mathfrak{m}$, all sufficiently
high $n\in\mathbb{N}$ satisfy  $\left(\text{the
}\mathfrak{m}\text{-coefficient of }P_{n}\right)=\left(\text{the
}\mathfrak{m}\text{-coefficient of }P\right)$ (where the meaning of
“sufficiently high” can depend on the $\mathfrak{m}$).. A power series
$P\in\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ is said to
be bounded-degree if there exists an $N\in\mathbb{N}$ such that every monomial
of degree $>N$ appears with coefficient $0$ in $P$. A power series
$P\in\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ is said to
be symmetric if and only if $P$ is invariant under any permutation of the
indeterminates. We let $\Lambda$ be the subset of
$\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ consisting of
all symmetric bounded-degree power series
$P\in\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$. This
subset $\Lambda$ is a $\mathbf{k}$-subalgebra of
$\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$, and is called
the $\mathbf{k}$-algebra of symmetric functions over $\mathbf{k}$.

We shall now define the few families of symmetric functions that we will be
concerned with in this note. The first are the power-sum symmetric functions:

######  Definition 1.3.

Let $n$ be a positive integer. We define a power series
$p_{n}\in\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ by

$p_{n}=x_{1}^{n}+x_{2}^{n}+x_{3}^{n}+\cdots=\sum\limits_{j\geq 1}x_{j}^{n}.$
(1)

This power series $p_{n}$ lies in $\Lambda$, and is called the $n$-th power-
sum symmetric function.

We also set $p_{0}=1\in\Lambda$. Thus, $p_{n}$ is defined not only for all
positive integers $n$, but also for all $n\in\mathbb{N}$.

######  Definition 1.4.

Let $\lambda=\left(\lambda_{1},\lambda_{2},\lambda_{3},\ldots\right)$ be a
partition. We define a power series
$p_{\lambda}\in\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$
by

$p_{\lambda}=\prod\limits_{i\geq 1}p_{\lambda_{i}}.$

This is well-defined, because the infinite product $\prod\limits_{i\geq
1}p_{\lambda_{i}}$ converges (indeed, all but finitely many of its factors are
$1$ (because every sufficiently high integer $i$ satisfies $\lambda_{i}=0$ and
thus $p_{\lambda_{i}}=p_{0}=1$)).

We notice that every partition
$\lambda=\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)$ (written as
a finite list of nonnegative integers) satisfies

$p_{\lambda}=p_{\lambda_{1}}p_{\lambda_{2}}\cdots p_{\lambda_{k}}.$ (2)

###  1.3 Chromatic symmetric functions

The next symmetric functions we introduce are the actual subject of this note;
they are the chromatic symmetric functions and originate in [Stanle95,
Definition 2.1]:

######  Definition 1.5.

Let $G=\left(V,E\right)$ be a finite graph. For every
$\mathbb{N}_{+}$-coloring $f:V\rightarrow\mathbb{N}_{+}$, we let
$\mathbf{x}_{f}$ denote the monomial $\prod\limits_{v\in
V}x_{f\left(v\right)}$ in the indeterminates $x_{1},x_{2},x_{3},\ldots$. We
define a power series
$X_{G}\in\mathbf{k}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ by

$X_{G}=\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+}\text{ is
a}\\\ \text{proper }\mathbb{N}_{+}\text{-coloring of
}G\end{subarray}}\mathbf{x}_{f}.$

This power series $X_{G}$ is called the chromatic symmetric function of $G$.

We have $X_{G}\in\Lambda$ for every finite graph $G=\left(V,E\right)$; this
will follow from Theorem 1.8 further below (but is also rather obvious).

We notice that $X_{G}$ is denoted by $\Psi\left[G\right]$ in [GriRei14,
§7.3.3].

###  1.4 Connected components

We shall now briefly recall the notion of connected components of a graph.

######  Definition 1.6.

Let $G=\left(V,E\right)$ be a finite graph. Let $u$ and $v$ be two elements of
$V$ (that is, two vertices of $G$). A walk from $u$ to $v$ in $G$ will mean a
sequence $\left(w_{0},w_{1},\ldots,w_{k}\right)$ of elements of $V$ such that
$w_{0}=u$ and $w_{k}=v$ and

$\left(\left\\{w_{i},w_{i+1}\right\\}\in E\ \ \ \ \ \ \ \ \ \ \text{for every
}i\in\left\\{0,1,\ldots,k-1\right\\}\right).$

We say that $u$ and $v$ are connected (in $G$) if there exists a walk from $u$
to $v$ in $G$.

######  Definition 1.7.

Let $G=\left(V,E\right)$ be a graph.

(a) We define a binary relation $\sim_{G}$ (written infix) on the set $V$ as
follows: Given $u\in V$ and $v\in V$, we set $u\sim_{G}v$ if and only if $u$
and $v$ are connected (in $G$). It is well-known that this relation $\sim_{G}$
is an equivalence relation. The $\sim_{G}$-equivalence classes are called the
connected components of $G$.

(b) Assume that the graph $G$ is finite. We let $\lambda\left(G\right)$ denote
the list of the sizes of all connected components of $G$, in weakly decreasing
order. (Each connected component should contribute only one entry to the
list.) We view $\lambda\left(G\right)$ as a partition (since
$\lambda\left(G\right)$ is a weakly decreasing finite list of positive
integers).

Now, we can state a formula for chromatic symmetric functions:

######  Theorem 1.8.

Let $G=\left(V,E\right)$ be a finite graph. Then,

$X_{G}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}p_{\lambda\left(V,F\right)}.$

(Here, of course, the pair $\left(V,F\right)$ is regarded as a graph, and the
expression $\lambda\left(V,F\right)$ is understood according to Definition 1.7
(b).)

This theorem is not new; it appears, e.g., in [Stanle95, Theorem 2.5]. We
shall show a far-reaching generalization of it (Theorem 1.11) soon.

###  1.5 Circuits and broken circuits

Let us now define the notions of cycles and circuits of a graph:

######  Definition 1.9.

Let $G=\left(V,E\right)$ be a graph. A cycle of $G$ denotes a list
$\left(v_{1},v_{2},\ldots,v_{m+1}\right)$ of elements of $V$ with the
following properties:

  * •

We have $m>1$.

  * •

We have $v_{m+1}=v_{1}$.

  * •

The vertices $v_{1},v_{2},\ldots,v_{m}$ are pairwise distinct.

  * •

We have $\left\\{v_{i},v_{i+1}\right\\}\in E$ for every
$i\in\left\\{1,2,\ldots,m\right\\}$.

If $\left(v_{1},v_{2},\ldots,v_{m+1}\right)$ is a cycle of $G$, then the set
$\left\\{\left\\{v_{1},v_{2}\right\\},\left\\{v_{2},v_{3}\right\\},\ldots,\left\\{v_{m},v_{m+1}\right\\}\right\\}$
is called a circuit of $G$.

######  Definition 1.10.

Let $G=\left(V,E\right)$ be a graph. Let $X$ be a totally ordered set. Let
$\ell:E\rightarrow X$ be a function. We shall refer to $\ell$ as the labeling
function. For every edge $e$ of $G$, we shall refer to $\ell\left(e\right)$ as
the label of $e$.

A broken circuit of $G$ means a subset of $E$ having the form
$C\setminus\left\\{e\right\\}$, where $C$ is a circuit of $G$, and where $e$
is the unique edge in $C$ having maximum label (among the edges in $C$). Of
course, the notion of a broken circuit of $G$ depends on the function $\ell$;
however, we suppress the mention of $\ell$ in our notation, since we will not
consider situations where two different $\ell$’s coexist.

Thus, if $G$ is a graph with a labeling function, then any circuit $C$ of $G$
gives rise to a broken circuit provided that among the edges in $C$, only one
attains the maximum label. (If more than one of the edges of $C$ attains the
maximum label, then $C$ does not give rise to a broken circuit.) Notice that
two different circuits may give rise to one and the same broken circuit.

######  Theorem 1.11.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set of
broken circuits of $G$ (not necessarily containing all of them). Let $a_{K}$
be an element of $\mathbf{k}$ for every $K\in\mathfrak{K}$. Then,

$X_{G}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq F\end{subarray}}a_{K}\right)p_{\lambda\left(V,F\right)}.$

(Here, of course, the pair $\left(V,F\right)$ is regarded as a graph, and the
expression $\lambda\left(V,F\right)$ is understood according to Definition 1.7
(b).)

Before we come to the proof of this result, let us explore some of its
particular cases. First, a definition is in order:

######  Definition 1.12.

Let $E$ be a set. Let $\mathfrak{K}$ be a subset of the powerset of $E$ (that
is, a set of subsets of $E$). A subset $F$ of $E$ is said to be
$\mathfrak{K}$-free if $F$ contains no $K\in\mathfrak{K}$ as a subset. (For
instance, if $\mathfrak{K}=\varnothing$, then every subset $F$ of $E$ is
$\mathfrak{K}$-free.)

######  Corollary 1.13.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set of
broken circuits of $G$ (not necessarily containing all of them). Then,

$X_{G}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{ is
}\mathfrak{K}\text{-free}\end{subarray}}\left(-1\right)^{\left|F\right|}p_{\lambda\left(V,F\right)}.$

######  Corollary 1.14.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Then,

$X_{G}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{ contains no
broken}\\\ \text{circuit of }G\text{ as a
subset}\end{subarray}}\left(-1\right)^{\left|F\right|}p_{\lambda\left(V,F\right)}.$

Corollary 1.14 appears in [Stanle95, Theorem 2.9], at least in the particular
case in which $\ell$ is supposed to be injective.

Let us now see how Theorem 1.8, Corollary 1.13 and Corollary 1.14 can be
derived from Theorem 1.11:

######  Proof 1.15 (Proof of Corollary 1.13 using Theorem 1.11.).

For every subset $F$ of $E$, we have

$\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\ K\subseteq
F\end{subarray}}0=\begin{cases}1,&\text{if }F\text{ is
}\mathfrak{K}\text{-free;}\\\ 0,&\text{if }F\text{ is not
}\mathfrak{K}\text{-free}\end{cases}$ (3)

(because if $F$ is $\mathfrak{K}$-free, then the product
$\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\ K\subseteq
F\end{subarray}}0$ is empty and thus equals $1$; otherwise, the product
$\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\ K\subseteq
F\end{subarray}}0$ contains at least one factor and thus equals $0$). Now,
Theorem 1.11 (applied to $0$ instead of $a_{K}$) yields

$\displaystyle X_{G}$ $\displaystyle=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\underbrace{\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}0\right)}_{\begin{subarray}{c}=\begin{cases}1,&\text{if
}F\text{ is }\mathfrak{K}\text{-free;}\\\ 0,&\text{if }F\text{ is not
}\mathfrak{K}\text{-free}\end{cases}\\\ \text{(by
(\ref{pf.cor.chromsym.K-free.short.prod0}))}\end{subarray}}p_{\lambda\left(V,F\right)}$
$\displaystyle=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\begin{cases}1,&\text{if }F\text{ is
}\mathfrak{K}\text{-free;}\\\ 0,&\text{if }F\text{ is not
}\mathfrak{K}\text{-free}\end{cases}p_{\lambda\left(V,F\right)}=\sum\limits_{\begin{subarray}{c}F\subseteq
E;\\\ F\text{ is
}\mathfrak{K}\text{-free}\end{subarray}}\left(-1\right)^{\left|F\right|}p_{\lambda\left(V,F\right)}.$

This proves Corollary 1.13.

######  Proof 1.16 (Proof of Corollary 1.14 using Corollary 1.13.).

Corollary 1.14 follows from Corollary 1.13 when $\mathfrak{K}$ is set to be
the set of all broken circuits of $G$.

######  Proof 1.17 (Proof of Theorem 1.8 using Theorem 1.11.).

Let $X$ be the totally ordered set $\left\\{1\right\\}$, and let
$\ell:E\rightarrow X$ be the only possible map. Let $\mathfrak{K}$ be the
empty set. Clearly, $\mathfrak{K}$ is a set of broken circuits of $G$. For
every $F\subseteq E$, the product
$\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\ K\subseteq
F\end{subarray}}0$ is empty (since $K$ is the empty set), and thus equals $1$.
Now, Theorem 1.11 (applied to $0$ instead of $a_{K}$) yields

$X_{G}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\underbrace{\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}0\right)}_{=1}p_{\lambda\left(V,F\right)}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}p_{\lambda\left(V,F\right)}.$

This proves Theorem 1.8.

##  2 Proof of Theorem 1.11

We shall now prepare for the proof of Theorem 1.11 with some notations and
some lemmas. Our proof will imitate [BlaSag86, proof of Whitney’s theorem].

###  2.1 $\operatorname*{Eqs}f$ and basic lemmas

######  Definition 2.1.

Let $V$ and $X$ be two sets. Let $f:V\rightarrow X$ be a map. We let
$\operatorname*{Eqs}f$ denote the subset

$\left\\{\left\\{s,t\right\\}\ \mid\ \left(s,t\right)\in V^{2},\ s\neq t\text{
and }f\left(s\right)=f\left(t\right)\right\\}$

of $\dbinom{V}{2}$. (This is well-defined, because any two elements $s$ and
$t$ of $V$ satisfying $s\neq t$ clearly satisfy
$\left\\{s,t\right\\}\in\dbinom{V}{2}$.)

We shall now state some first properties of this notion:

######  Lemma 2.2.

Let $G=\left(V,E\right)$ be a graph. Let $X$ be a set. Let $f:V\rightarrow X$
be a map. Then, the $X$-coloring $f$ of $G$ is proper if and only if
$E\cap\operatorname*{Eqs}f=\varnothing$.

######  Proof 2.3 (Proof of Lemma 2.2.).

The set $E\cap\operatorname*{Eqs}f$ is precisely the set of edges
$\left\\{s,t\right\\}$ of $G$ satisfying $f\left(s\right)=f\left(t\right)$;
meanwhile, the $X$-coloring $f$ is called proper if and only if no such edges
exist. Thus, Lemma 2.2 becomes obvious.

######  Lemma 2.4.

Let $G=\left(V,E\right)$ be a graph. Let $X$ be a set. Let $f:V\rightarrow X$
be a map. Let $C$ be a circuit of $G$. Let $e\in C$ be such that
$C\setminus\left\\{e\right\\}\subseteq\operatorname*{Eqs}f$. Then, $e\in
E\cap\operatorname*{Eqs}f$.

######  Proof 2.5 (Proof of Lemma 2.4.).

The set $C$ is a circuit of $G$. Hence, we can write $C$ in the form

$C=\left\\{\left\\{v_{1},v_{2}\right\\},\left\\{v_{2},v_{3}\right\\},\ldots,\left\\{v_{m},v_{m+1}\right\\}\right\\}$

for some cycle $\left(v_{1},v_{2},\ldots,v_{m+1}\right)$ of $G$. Consider this
cycle $\left(v_{1},v_{2},\ldots,v_{m+1}\right)$. According to the definition
of a “cycle”, the cycle $\left(v_{1},v_{2},\ldots,v_{m+1}\right)$ is a list of
elements of $V$ having the following properties:

  * •

We have $m>1$.

  * •

We have $v_{m+1}=v_{1}$.

  * •

The vertices $v_{1},v_{2},\ldots,v_{m}$ are pairwise distinct.

  * •

We have $\left\\{v_{i},v_{i+1}\right\\}\in E$ for every
$i\in\left\\{1,2,\ldots,m\right\\}$.

Recall that $e\in C$. We can thus WLOG assume that
$e=\left\\{v_{m},v_{m+1}\right\\}$ (since otherwise, we can simply relabel the
vertices along the cycle $\left(v_{1},v_{2},\ldots,v_{m+1}\right)$). Assume
this. Since $\left\\{v_{m},v_{m+1}\right\\}=e$, we have

$C\setminus\left\\{e\right\\}=\left\\{\left\\{v_{1},v_{2}\right\\},\left\\{v_{2},v_{3}\right\\},\ldots,\left\\{v_{m-1},v_{m}\right\\}\right\\}$

(since $v_{1},v_{2},\ldots,v_{m}$ are distinct, and since $m>1$ and
$v_{m+1}=v_{1}$). For every $i\in\left\\{1,2,\ldots,m-1\right\\}$, we have
$f\left(v_{i}\right)=f\left(v_{i+1}\right)$ (since

$\left\\{v_{i},v_{i+1}\right\\}\subseteq\left\\{\left\\{v_{1},v_{2}\right\\},\left\\{v_{2},v_{3}\right\\},\ldots,\left\\{v_{m-1},v_{m}\right\\}\right\\}=C\setminus\left\\{e\right\\}\subseteq\operatorname*{Eqs}f$

). Hence,
$f\left(v_{1}\right)=f\left(v_{2}\right)=\cdots=f\left(v_{m}\right)$, so that
$f\left(v_{m}\right)=f\left(\underbrace{v_{1}}_{=v_{m+1}}\right)=f\left(v_{m+1}\right)$.
Thus, $\left\\{v_{m},v_{m+1}\right\\}\in\operatorname*{Eqs}f$. Thus,
$e=\left\\{v_{m},v_{m+1}\right\\}\in\operatorname*{Eqs}f$. Combined with $e\in
E$, this yields $e\in E\cap\operatorname*{Eqs}f$. This proves Lemma 2.4.

######  Lemma 2.6.

Let $\left(V,B\right)$ be a finite graph. Then,

$\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}\mathbf{x}_{f}=p_{\lambda\left(V,B\right)}$

(Here, $\mathbf{x}_{f}$ is defined as in Definition 1.5, and the expression
$\lambda\left(V,B\right)$ is understood according to Definition 1.7 (b).)

######  Proof 2.7 (Proof of Lemma 2.6.).

Let $\left(C_{1},C_{2},\ldots,C_{k}\right)$ be a list of all connected
components of $\left(V,B\right)$, ordered such that
$\left|C_{1}\right|\geq\left|C_{2}\right|\geq\cdots\geq\left|C_{k}\right|$.
333Every connected component of $\left(V,B\right)$ should appear exactly once
in this list. Then,
$\lambda\left(V,B\right)=\left(\left|C_{1}\right|,\left|C_{2}\right|,\ldots,\left|C_{k}\right|\right)$
(by the definition of $\lambda\left(V,B\right)$). Hence, (2) (applied to
$\lambda\left(V,B\right)$ and $\left|C_{i}\right|$ instead of $\lambda$ and
$\lambda_{i}$) shows that

$p_{\lambda\left(V,B\right)}=p_{\left|C_{1}\right|}p_{\left|C_{2}\right|}\cdots
p_{\left|C_{k}\right|}=\prod\limits_{i=1}^{k}p_{\left|C_{i}\right|}.$ (4)

But for every $i\in\left\\{1,2,\ldots,k\right\\}$, we have
$p_{\left|C_{i}\right|}=\sum\limits_{s\in\mathbb{N}_{+}}x_{s}^{\left|C_{i}\right|}$
(by the definition of $p_{\left|C_{i}\right|}$). Hence, (4) becomes

$p_{\lambda\left(V,B\right)}=\prod\limits_{i=1}^{k}\underbrace{p_{\left|C_{i}\right|}}_{=\sum\limits_{s\in\mathbb{N}_{+}}x_{s}^{\left|C_{i}\right|}}=\prod\limits_{i=1}^{k}\sum\limits_{s\in\mathbb{N}_{+}}x_{s}^{\left|C_{i}\right|}=\sum\limits_{\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}}\prod\limits_{i=1}^{k}x_{s_{i}}^{\left|C_{i}\right|}$
(5)

(by the product rule).

The list $\left(C_{1},C_{2},\ldots,C_{k}\right)$ contains all connected
components of $\left(V,B\right)$, each exactly once. Thus,
$V=\bigsqcup_{i=1}^{k}C_{i}$.

We now define a map

$\Phi:\left(\mathbb{N}_{+}\right)^{k}\rightarrow\left\\{f:V\rightarrow\mathbb{N}_{+}\
\mid\ B\subseteq\operatorname*{Eqs}f\right\\}$

as follows: Given any
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$, we
let $\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$ be the map
$V\rightarrow\mathbb{N}_{+}$ which sends every $v\in V$ to $s_{i}$, where
$i\in\left\\{1,2,\ldots,k\right\\}$ is such that $v\in C_{i}$. (This is well-
defined, because for every $v\in V$, there exists a unique
$i\in\left\\{1,2,\ldots,k\right\\}$ such that $v\in C_{i}$; this follows from
$V=\bigsqcup_{i=1}^{k}C_{i}$.) This map $\Phi$ is well-defined, because for
every
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$, the
map $\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$ actually belongs to
$\left\\{f:V\rightarrow\mathbb{N}_{+}\ \mid\
B\subseteq\operatorname*{Eqs}f\right\\}$ 444Proof. We just need to check that
$B\subseteq\operatorname*{Eqs}\left(\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)\right)$.
But this is easy: For every $\left(u,v\right)\in B$, the vertices $u$ and $v$
of $\left(V,B\right)$ lie in one and the same connected component $C_{i}$ of
the graph $\left(V,B\right)$, and thus (by the definition of
$\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$) the map
$\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$ sends both of them to $s_{i}$; but
this shows that
$\left(u,v\right)\in\operatorname*{Eqs}\left(\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)\right)$..

A moment’s thought reveals that the map $\Phi$ is injective555In fact, we can
reconstruct
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$ from
its image $\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$, because each $s_{i}$ is
the image of any element of $C_{i}$ under
$\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$ (and this allows us to compute
$s_{i}$, since $C_{i}$ is nonempty).. Let us now show that the map $\Phi$ is
surjective.

In order to show this, we must prove that every map
$f:V\rightarrow\mathbb{N}_{+}$ satisfying $B\subseteq\operatorname*{Eqs}f$ has
the form $\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$ for some
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$. So
let us fix a map $f:V\rightarrow\mathbb{N}_{+}$ satisfying
$B\subseteq\operatorname*{Eqs}f$. We must find some
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$ such
that $f=\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$.

We have $B\subseteq\operatorname*{Eqs}f$. Thus, for every
$\left\\{s,t\right\\}\in B$, we have $\left\\{s,t\right\\}\in
B\subseteq\operatorname*{Eqs}f$ and thus

$f\left(s\right)=f\left(t\right).$ (6)

Now, if $x$ and $y$ are two elements of $V$ lying in the same connected
component of $\left(V,B\right)$, then

$f\left(x\right)=f\left(y\right)$ (7) 666Proof of (7): Let $x$ and $y$ be two
elements of $V$ lying in the same connected component of $\left(V,B\right)$.
Then, the vertices $x$ and $y$ are connected by a walk in the graph
$\left(V,B\right)$ (by the definition of a “connected component”). Let
$\left(v_{0},v_{1},\ldots,v_{j}\right)$ be this walk (regarded as a sequence
of vertices); thus, $v_{0}=x$ and $v_{j}=y$. For every
$i\in\left\\{0,1,\ldots,j-1\right\\}$, we have
$\left\\{v_{i},v_{i+1}\right\\}\in B$ (since
$\left(v_{0},v_{1},\ldots,v_{j}\right)$ is a walk in the graph
$\left(V,B\right)$) and thus $f\left(v_{i}\right)=f\left(v_{i+1}\right)$ (by
(6), applied to $\left(s,t\right)=\left(v_{i},v_{i+1}\right)$). In other
words, $f\left(v_{0}\right)=f\left(v_{1}\right)=\cdots=f\left(v_{j}\right)$.
Hence, $f\left(v_{0}\right)=f\left(v_{j}\right)$, so that
$f\left(\underbrace{x}_{=v_{0}}\right)=f\left(v_{0}\right)=f\left(\underbrace{v_{j}}_{=y}\right)=f\left(y\right)$,
qed.

. In other words, the map $f$ is constant on each connected component of
$\left(V,B\right)$. Thus, the map $f$ is constant on $C_{i}$ for each
$i\in\left\\{1,2,\ldots,k\right\\}$ (since $C_{i}$ is a connected component of
$\left(V,B\right)$). Hence, for each $i\in\left\\{1,2,\ldots,k\right\\}$, we
can define a positive integer $s_{i}\in\mathbb{N}_{+}$ to be the image of any
element of $C_{i}$ under $f$ (this is well-defined, because $f$ is constant on
$C_{i}$ and thus the choice of the element does not matter). Define
$s_{i}\in\mathbb{N}_{+}$ for each $i\in\left\\{1,2,\ldots,k\right\\}$ this
way. Thus, we have defined a $k$-tuple
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$.
Now, $f=\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$ (this follows immediately
by recalling the definitions of $\Phi$ and $s_{i}$).

Let us now forget that we fixed $f$. We thus have shown that for every map
$f:V\rightarrow\mathbb{N}_{+}$ satisfying $B\subseteq\operatorname*{Eqs}f$,
there exists some
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$ such
that $f=\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)$. In other words, the map
$\Phi$ is surjective. Since $\Phi$ is both injective and surjective, we
conclude that $\Phi$ is a bijection.

Moreover, it is straightforward to see that every map
$\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}$
satisfies

$\mathbf{x}_{\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)}=\prod\limits_{i=1}^{k}x_{s_{i}}^{\left|C_{i}\right|}$
(8)

(by the definitions of
$\mathbf{x}_{\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)}$ and of $\Phi$). Now,

$\displaystyle\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}\mathbf{x}_{f}$
$\displaystyle=\sum\limits_{\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}}\underbrace{\mathbf{x}_{\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)}}_{\begin{subarray}{c}=\prod\limits_{i=1}^{k}x_{s_{i}}^{\left|C_{i}\right|}\\\
\text{(by (\ref{pf.lem.Eqs.sum.short.4}))}\end{subarray}}$ $\displaystyle\ \ \
\ \ \ \ \ \ \ \left(\begin{array}[c]{c}\text{here, we have substituted
}\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)\text{ for }f\text{ in the sum,}\\\
\text{since the map
}\Phi:\left(\mathbb{N}_{+}\right)^{k}\rightarrow\left\\{f:V\rightarrow\mathbb{N}_{+}\
\mid\ B\subseteq\operatorname*{Eqs}f\right\\}\\\ \text{is a
bijection}\end{array}\right)$
$\displaystyle=\sum\limits_{\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left(\mathbb{N}_{+}\right)^{k}}\prod\limits_{i=1}^{k}x_{s_{i}}^{\left|C_{i}\right|}=p_{\lambda\left(V,B\right)}\
\ \ \ \ \ \ \ \ \ \left(\text{by (\ref{pf.lem.Eqs.sum.short.p2})}\right).$

This proves Lemma 2.6.

######  Lemma 2.8.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $K$ be a broken circuit of $G$.
Then, $K\neq\varnothing$.

######  Proof 2.9 (Proof of Lemma 2.8.).

The set $K$ is a broken circuit of $G$, and thus is a circuit of $G$ with an
edge removed (by the definition of a broken circuit). Thus, the set $K$
contains at least $1$ edge (since every circuit of $G$ contains at least $2$
edges). This proves Lemma 2.8.

###  2.2 Alternating sums

We shall now come to less simple lemmas.

######  Definition 2.10.

We shall use the so-called Iverson bracket notation: If $\mathcal{S}$ is any
logical statement, then $\left[\mathcal{S}\right]$ shall mean the integer
$\begin{cases}1,&\text{if }\mathcal{S}\text{ is true;}\\\ 0,&\text{if
}\mathcal{S}\text{ is false}\end{cases}$.

The following lemma is probably the most crucial one in this note:

######  Lemma 2.11.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set of
broken circuits of $G$ (not necessarily containing all of them). Let $a_{K}$
be an element of $\mathbf{k}$ for every $K\in\mathfrak{K}$.

Let $Y$ be any set. Let $f:V\rightarrow Y$ be any map. Then,

$\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}=\left[E\cap\operatorname*{Eqs}f=\varnothing\right].$

######  Proof 2.12 (Proof of Lemma 2.11.).

We WLOG assume that $E\cap\operatorname*{Eqs}f\neq\varnothing$ (since
otherwise, the claim is obvious777In (slightly) more detail: If
$E\cap\operatorname*{Eqs}f=\varnothing$, then the sum $\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}$ has only one addend (namely, the addend for
$B=\varnothing$), and thus simplifies to
$\displaystyle\underbrace{\left(-1\right)^{\left|\varnothing\right|}}_{=\left(-1\right)^{0}=1}\underbrace{\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\varnothing\end{subarray}}}_{=\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K=\varnothing\end{subarray}}}a_{K}$
$\displaystyle=\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K=\varnothing\end{subarray}}a_{K}=\left(\text{empty product}\right)\ \ \ \ \ \
\ \ \ \ \left(\begin{array}[c]{c}\text{since no }K\in\mathfrak{K}\text{
satisfies }K=\varnothing\\\ \text{(by Lemma
\ref{lem.BC.nonempty})}\end{array}\right)$
$\displaystyle=1=\left[E\cap\operatorname*{Eqs}f=\varnothing\right].$ ). Thus,
$\left[E\cap\operatorname*{Eqs}f=\varnothing\right]=0$.

Pick any $d\in E\cap\operatorname*{Eqs}f$ with maximum $\ell\left(d\right)$
(among all $d\in E\cap\operatorname*{Eqs}f$). (This is clearly possible, since
$E\cap\operatorname*{Eqs}f\neq\varnothing$.) Define two subsets $\mathcal{U}$
and $\mathcal{V}$ of $\mathcal{P}\left(E\cap\operatorname*{Eqs}f\right)$ as
follows:

$\displaystyle\mathcal{U}$
$\displaystyle=\left\\{F\in\mathcal{P}\left(E\cap\operatorname*{Eqs}f\right)\
\mid\ d\notin F\right\\};$ $\displaystyle\mathcal{V}$
$\displaystyle=\left\\{F\in\mathcal{P}\left(E\cap\operatorname*{Eqs}f\right)\
\mid\ d\in F\right\\}.$

Thus, we have
$\mathcal{P}\left(E\cap\operatorname*{Eqs}f\right)=\mathcal{U}\cup\mathcal{V}$,
and the sets $\mathcal{U}$ and $\mathcal{V}$ are disjoint. Now, we define a
map $\Phi:\mathcal{U}\rightarrow\mathcal{V}$ by

$\left(\Phi\left(B\right)=B\cup\left\\{d\right\\}\ \ \ \ \ \ \ \ \ \ \text{for
every }B\in\mathcal{U}\right).$

This map $\Phi$ is well-defined (because for every $B\in\mathcal{U}$, we have
$B\cup\left\\{d\right\\}\in\mathcal{V}$ 888This follows from the fact that
$d\in E\cap\operatorname*{Eqs}f$.) and a bijection999Its inverse is the map
$\Psi:\mathcal{V}\rightarrow\mathcal{U}$ defined by
$\left(\Psi\left(B\right)=B\setminus\left\\{d\right\\}\ \ \ \ \ \ \ \ \ \
\text{for every }B\in\mathcal{V}\right)$.. Moreover, every $B\in\mathcal{U}$
satisfies

$\left(-1\right)^{\left|\Phi\left(B\right)\right|}=-\left(-1\right)^{\left|B\right|}$
(9) 101010Proof. Let $B\in\mathcal{U}$. Thus, $d\notin B$ (by the definition
of $\mathcal{U}$). Now,
$\left|\underbrace{\Phi\left(B\right)}_{=B\cup\left\\{d\right\\}}\right|=\left|B\cup\left\\{d\right\\}\right|=\left|B\right|+1$
(since $d\notin B$), so that
$\left(-1\right)^{\left|\Phi\left(B\right)\right|}=-\left(-1\right)^{\left|B\right|}$,
qed.

.

Now, we claim that, for every $B\in\mathcal{U}$ and every $K\in\mathfrak{K}$,
we have the following logical equivalence:

$\left(K\subseteq B\right)\ \Longleftrightarrow\
\left(K\subseteq\Phi\left(B\right)\right).$ (10)

Proof of (10): Let $B\in\mathcal{U}$ and $K\in\mathfrak{K}$. We must prove the
equivalence (10). The definition of $\Phi$ yields
$\Phi\left(B\right)=B\cup\left\\{d\right\\}\supseteq B$, so that
$B\subseteq\Phi\left(B\right)$. Hence, if $K\subseteq B$, then $K\subseteq
B\subseteq\Phi\left(B\right)$. Therefore, the forward implication of the
equivalence (10) is proven. It thus remains to prove the backward implication
of this equivalence. In other words, it remains to prove that if
$K\subseteq\Phi\left(B\right)$, then $K\subseteq B$. So let us assume that
$K\subseteq\Phi\left(B\right)$.

We want to prove that $K\subseteq B$. Assume the contrary. Thus,
$K\not\subseteq B$. We have $K\in\mathfrak{K}$. Thus, $K$ is a broken circuit
of $G$ (since $\mathfrak{K}$ is a set of broken circuits of $G$). In other
words, $K$ is a subset of $E$ having the form $C\setminus\left\\{e\right\\}$,
where $C$ is a circuit of $G$, and where $e$ is the unique edge in $C$ having
maximum label (among the edges in $C$) (because this is how a broken circuit
is defined). Consider these $C$ and $e$. Thus,
$K=C\setminus\left\\{e\right\\}$.

The element $e$ is the unique edge in $C$ having maximum label (among the
edges in $C$). Thus, if $e^{\prime}$ is any edge in $C$ satisfying
$\ell\left(e^{\prime}\right)\geq\ell\left(e\right)$, then

$e^{\prime}=e.$ (11)

But
$\underbrace{K}_{\subseteq\Phi\left(B\right)=B\cup\left\\{d\right\\}}\setminus\left\\{d\right\\}\subseteq\left(B\cup\left\\{d\right\\}\right)\setminus\left\\{d\right\\}\subseteq
B$.

If we had $d\notin K$, then we would have $K\setminus\left\\{d\right\\}=K$ and
therefore $K=K\setminus\left\\{d\right\\}\subseteq B$; this would contradict
$K\not\subseteq B$. Hence, we cannot have $d\notin K$. We thus must have $d\in
K$. Hence, $d\in K=C\setminus\left\\{e\right\\}$. Hence, $d\in C$ and $d\neq
e$.

But $C\setminus\left\\{e\right\\}=K\subseteq\Phi\left(B\right)\subseteq
E\cap\operatorname*{Eqs}f$ (since
$\Phi\left(B\right)\in\mathcal{P}\left(E\cap\operatorname*{Eqs}f\right)$), so
that $C\setminus\left\\{e\right\\}\subseteq
E\cap\operatorname*{Eqs}f\subseteq\operatorname*{Eqs}f$. Hence, Lemma 2.4
(applied to $Y$ instead of $X$) shows that $e\in E\cap\operatorname*{Eqs}f$.
Thus, $\ell\left(d\right)\geq\ell\left(e\right)$ (since $d$ was defined to be
an element of $E\cap\operatorname*{Eqs}f$ with maximum $\ell\left(d\right)$
among all $d\in E\cap\operatorname*{Eqs}f$).

Also, $d\in C$. Since $\ell\left(d\right)\geq\ell\left(e\right)$, we can
therefore apply (11) to $e^{\prime}=d$. We thus obtain $d=e$. This contradicts
$d\neq e$. This contradiction proves that our assumption was wrong. Hence,
$K\subseteq B$ is proven. Thus, we have proven the backward implication of the
equivalence (10); this completes the proof of (10).

Now, recall that we have
$\mathcal{P}\left(E\cap\operatorname*{Eqs}f\right)=\mathcal{U}\cup\mathcal{V}$,
and the sets $\mathcal{U}$ and $\mathcal{V}$ are disjoint. Hence, the sum
$\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}$ can be split into two sums as follows:

$\displaystyle\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}$
$\displaystyle=\sum\limits_{B\in\mathcal{U}}\underbrace{\left(-1\right)^{\left|B\right|}}_{\begin{subarray}{c}=-\left(-1\right)^{\left|\Phi\left(B\right)\right|}\\\
\text{(by
(\ref{pf.lem.NBCm.moeb.short.Phi.-1}))}\end{subarray}}\underbrace{\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}}_{\begin{subarray}{c}=\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\Phi\left(B\right)\end{subarray}}\\\ \text{(because of the
equivalence
(\ref{pf.lem.NBCm.moeb.short.Phi.equiv}))}\end{subarray}}a_{K}+\underbrace{\sum\limits_{B\in\mathcal{V}}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}}_{\begin{subarray}{c}=\sum\limits_{B\in\mathcal{U}}\left(-1\right)^{\left|\Phi\left(B\right)\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\Phi\left(B\right)\end{subarray}}a_{K}\\\ \text{(here, we have
substituted }\Phi\left(B\right)\text{ for }B\text{ in the sum,}\\\ \text{since
the map }\Phi:\mathcal{U}\rightarrow\mathcal{V}\text{ is a
bijection)}\end{subarray}}$
$\displaystyle=\sum\limits_{B\in\mathcal{U}}\left(-\left(-1\right)^{\left|\Phi\left(B\right)\right|}\right)\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\Phi\left(B\right)\end{subarray}}a_{K}+\sum\limits_{B\in\mathcal{U}}\left(-1\right)^{\left|\Phi\left(B\right)\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\Phi\left(B\right)\end{subarray}}a_{K}$
$\displaystyle=-\sum\limits_{B\in\mathcal{U}}\left(-1\right)^{\left|\Phi\left(B\right)\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\Phi\left(B\right)\end{subarray}}a_{K}+\sum\limits_{B\in\mathcal{U}}\left(-1\right)^{\left|\Phi\left(B\right)\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\Phi\left(B\right)\end{subarray}}a_{K}$
$\displaystyle=0=\left[E\cap\operatorname*{Eqs}f=\varnothing\right]\ \ \ \ \ \
\ \ \ \ \left(\text{since
}\left[E\cap\operatorname*{Eqs}f=\varnothing\right]=0\right).$ (12)

This proves Lemma 2.11.

We now finally proceed to the proof of Theorem 1.11:

######  Proof 2.13 (Proof of Theorem 1.11.).

The definition of $X_{G}$ shows that

$\displaystyle X_{G}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+}\text{
is a}\\\ \text{proper }\mathbb{N}_{+}\text{-coloring of
}G\end{subarray}}\mathbf{x}_{f}$
$\displaystyle=\sum\limits_{f:V\rightarrow\mathbb{N}_{+}}\left[\underbrace{f\text{
is a proper }\mathbb{N}_{+}\text{-coloring of
}G}_{\begin{subarray}{c}\Longleftrightarrow\ \left(\text{the
}\mathbb{N}_{+}\text{-coloring }f\text{ of }G\text{ is proper}\right)\\\
\Longleftrightarrow\ \left(E\cap\operatorname*{Eqs}f=\varnothing\right)\\\
\text{(by Lemma \ref{lem.Eqs.proper}, applied to }\mathbb{N}_{+}\text{ instead
of }X\text{)}\end{subarray}}\right]\mathbf{x}_{f}$
$\displaystyle=\sum\limits_{f:V\rightarrow\mathbb{N}_{+}}\underbrace{\left[E\cap\operatorname*{Eqs}f=\varnothing\right]}_{\begin{subarray}{c}=\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}\\\ \text{(by Lemma \ref{lem.NBCm.moeb},
applied to }Y=\mathbb{N}_{+}\text{)}\end{subarray}}\mathbf{x}_{f}$
$\displaystyle=\sum\limits_{f:V\rightarrow\mathbb{N}_{+}}\underbrace{\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}}_{=\sum\limits_{\begin{subarray}{c}B\subseteq E;\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}\right)\mathbf{x}_{f}=\underbrace{\sum\limits_{f:V\rightarrow\mathbb{N}_{+}}\sum\limits_{\begin{subarray}{c}B\subseteq
E;\\\ B\subseteq\operatorname*{Eqs}f\end{subarray}}}_{=\sum\limits_{B\subseteq
E}\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}\right)\mathbf{x}_{f}$
$\displaystyle=\sum\limits_{B\subseteq
E}\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}\right)\mathbf{x}_{f}=\sum\limits_{B\subseteq
E}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}\right)\underbrace{\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}\mathbf{x}_{f}}_{\begin{subarray}{c}=p_{\lambda\left(V,B\right)}\\\
\text{(by Lemma \ref{lem.Eqs.sum})}\end{subarray}}$
$\displaystyle=\sum\limits_{B\subseteq
E}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}\right)p_{\lambda\left(V,B\right)}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq F\end{subarray}}a_{K}\right)p_{\lambda\left(V,F\right)}$

(here, we have renamed the summation index $B$ as $F$). This proves Theorem
1.11.

Thus, Theorem 1.11 is proven; as we know, this entails the correctness of
Theorem 1.8, Corollary 1.13 and Corollary 1.14.

##  3 The chromatic polynomial

###  3.1 Definition

We have so far studied the chromatic symmetric function. We shall now apply
the above results to the chromatic polynomial. The definition of the chromatic
polynomial rests upon the following fact:

######  Theorem 3.1.

Let $G=\left(V,E\right)$ be a finite graph. Then, there exists a unique
polynomial $P\in\mathbb{Z}\left[x\right]$ such that every $q\in\mathbb{N}$
satisfies

$P\left(q\right)=\left(\text{the number of all proper
}\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right).$

######  Definition 3.2.

Let $G=\left(V,E\right)$ be a finite graph. Theorem 3.1 shows that there
exists a polynomial $P\in\mathbb{Z}\left[x\right]$ such that every
$q\in\mathbb{N}$ satisfies $P\left(q\right)=\left(\text{the number of all
proper }\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right)$. This
polynomial $P$ is called the chromatic polynomial of $G$, and will be denoted
by $\chi_{G}$.

We shall later prove Theorem 3.1 (as a consequence of something stronger that
we show). First, we shall state some formulas for the chromatic polynomial
which are analogues of results proven before for the chromatic symmetric
function.

###  3.2 Formulas for $\chi_{G}$

Before we state several formulas for $\chi_{G}$, we need to introduce one more
notation:

######  Definition 3.3.

Let $G$ be a finite graph. We let $\operatorname*{conn}G$ denote the number of
connected components of $G$.

The following results are analogues of Theorem 1.8, Theorem 1.11, Corollary
1.13 and Corollary 1.14, respectively:

######  Theorem 3.4.

Let $G=\left(V,E\right)$ be a finite graph. Then,

$\chi_{G}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}x^{\operatorname*{conn}\left(V,F\right)}.$

(Here, of course, the pair $\left(V,F\right)$ is regarded as a graph, and the
expression $\operatorname*{conn}\left(V,F\right)$ is understood according to
Definition 3.3.)

######  Theorem 3.5.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set of
broken circuits of $G$ (not necessarily containing all of them). Let $a_{K}$
be an element of $\mathbf{k}$ for every $K\in\mathfrak{K}$. Then,

$\chi_{G}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)x^{\operatorname*{conn}\left(V,F\right)}.$

(Here, of course, the pair $\left(V,F\right)$ is regarded as a graph, and the
expression $\operatorname*{conn}\left(V,F\right)$ is understood according to
Definition 3.3.)

######  Corollary 3.6.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set of
broken circuits of $G$ (not necessarily containing all of them). Then,

$\chi_{G}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{ is
}\mathfrak{K}\text{-free}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{\operatorname*{conn}\left(V,F\right)}.$

######  Corollary 3.7.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Then,

$\chi_{G}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{ contains no
broken}\\\ \text{circuit of }G\text{ as a
subset}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{\operatorname*{conn}\left(V,F\right)}.$

###  3.3 Proofs

There are two approaches to these results: One is to derive them similarly to
how we derived the analogous results about $X_{G}$; the other is to derive
them from the latter. We shall take the first approach, since it yields a
proof of the classical Theorem 3.1 “for free”. We begin with an analogue of
Lemma 2.6:

######  Lemma 3.8.

Let $\left(V,B\right)$ be a finite graph. Let $q\in\mathbb{N}$. Then,

$\sum\limits_{\begin{subarray}{c}f:V\rightarrow\left\\{1,2,\ldots,q\right\\};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}1=q^{\operatorname*{conn}\left(V,B\right)}.$

(Here, the expression $\operatorname*{conn}\left(V,B\right)$ is understood
according to Definition 1.7 (b).)

One way to prove Lemma 3.8 is to evaluate the equality given by Lemma 2.6 at
$x_{k}=\begin{cases}1,&\text{if }k\leq q\\\ 0,&\text{if }k>q\end{cases}$.
Another proof can be obtained by mimicking our proof of Lemma 2.6:

######  Proof 3.9 (Proof of Lemma 3.8.).

Define $\left(C_{1},C_{2},\ldots,C_{k}\right)$ as in the proof of Lemma 2.6.
Thus, $\operatorname*{conn}\left(V,B\right)=k$. Define a map $\Phi$ as in the
proof of Lemma 2.6, but with $\mathbb{N}_{+}$ replaced by
$\left\\{1,2,\ldots,q\right\\}$. Then,

$\Phi:\left\\{1,2,\ldots,q\right\\}^{k}\rightarrow\left\\{f:V\rightarrow\left\\{1,2,\ldots,q\right\\}\
\mid\ B\subseteq\operatorname*{Eqs}f\right\\}$

is a bijection111111This can be shown in the same way as for the map $\Phi$ in
the proof of Lemma 2.6; we just have to replace every $\mathbb{N}_{+}$ by
$\left\\{1,2,\ldots,q\right\\}$.. Now,

$\displaystyle\sum\limits_{\begin{subarray}{c}f:V\rightarrow\left\\{1,2,\ldots,q\right\\};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}1$
$\displaystyle=\sum\limits_{\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left\\{1,2,\ldots,q\right\\}^{k}}1$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\begin{array}[c]{c}\text{here, we have
substituted }\Phi\left(s_{1},s_{2},\ldots,s_{k}\right)\text{ for }f\text{ in
the sum,}\\\ \text{since the map
}\Phi:\left\\{1,2,\ldots,q\right\\}^{k}\rightarrow\left\\{f:V\rightarrow\left\\{1,2,\ldots,q\right\\}\
\mid\ B\subseteq\operatorname*{Eqs}f\right\\}\\\ \text{is a
bijection}\end{array}\right)$ $\displaystyle=\left(\text{the number of all
}\left(s_{1},s_{2},\ldots,s_{k}\right)\in\left\\{1,2,\ldots,q\right\\}^{k}\right)$
$\displaystyle=q^{k}=q^{\operatorname*{conn}\left(V,B\right)}\ \ \ \ \ \ \ \ \
\ \left(\text{since }k=\operatorname*{conn}\left(V,B\right)\right).$

This proves Lemma 3.8.

We shall now show a weaker version of Theorem 3.5 (as a stepping stone to the
actual theorem):

######  Lemma 3.10.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set of
broken circuits of $G$ (not necessarily containing all of them). Let $a_{K}$
be an element of $\mathbf{k}$ for every $K\in\mathfrak{K}$. Let
$q\in\mathbb{N}$. Then,

$\displaystyle\left(\text{the number of all proper
}\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right)$
$\displaystyle=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)q^{\operatorname*{conn}\left(V,F\right)}.$

(Here, of course, the pair $\left(V,F\right)$ is regarded as a graph, and the
expression $\operatorname*{conn}\left(V,F\right)$ is understood according to
Definition 3.3.)

######  Proof 3.11 (Proof of Lemma 3.10.).

We have121212We are again using the Iverson bracket notation, as defined in
Definition 2.10.

$\displaystyle\left(\text{the number of all proper
}\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right)$
$\displaystyle=\sum\limits_{f:V\rightarrow\left\\{1,2,\ldots,q\right\\}}\left[\underbrace{f\text{
is a proper }\left\\{1,2,\ldots,q\right\\}\text{-coloring of
}G}_{\begin{subarray}{c}\Longleftrightarrow\ \left(\text{the
}\left\\{1,2,\ldots,q\right\\}\text{-coloring }f\text{ of }G\text{ is
proper}\right)\\\ \Longleftrightarrow\
\left(E\cap\operatorname*{Eqs}f=\varnothing\right)\\\ \text{(by Lemma
\ref{lem.Eqs.proper}, applied to }\left\\{1,2,\ldots,q\right\\}\text{ instead
of }X\text{)}\end{subarray}}\right]$
$\displaystyle=\sum\limits_{f:V\rightarrow\left\\{1,2,\ldots,q\right\\}}\underbrace{\left[E\cap\operatorname*{Eqs}f=\varnothing\right]}_{\begin{subarray}{c}=\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}\\\ \text{(by Lemma \ref{lem.NBCm.moeb},
applied to }Y=\mathbb{N}_{+}\text{)}\end{subarray}}$
$\displaystyle=\sum\limits_{f:V\rightarrow\left\\{1,2,\ldots,q\right\\}}\underbrace{\sum\limits_{B\subseteq
E\cap\operatorname*{Eqs}f}}_{=\sum\limits_{\begin{subarray}{c}B\subseteq E;\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}\right)=\underbrace{\sum\limits_{f:V\rightarrow\left\\{1,2,\ldots,q\right\\}}\sum\limits_{\begin{subarray}{c}B\subseteq
E;\\\ B\subseteq\operatorname*{Eqs}f\end{subarray}}}_{=\sum\limits_{B\subseteq
E}\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{N}_{+};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}\right)$
$\displaystyle=\sum\limits_{B\subseteq
E}\sum\limits_{\begin{subarray}{c}f:V\rightarrow\left\\{1,2,\ldots,q\right\\};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}\right)=\sum\limits_{B\subseteq
E}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}\right)\underbrace{\sum\limits_{\begin{subarray}{c}f:V\rightarrow\left\\{1,2,\ldots,q\right\\};\\\
B\subseteq\operatorname*{Eqs}f\end{subarray}}1}_{\begin{subarray}{c}=q^{\operatorname*{conn}\left(V,B\right)}\\\
\text{(by Lemma \ref{lem.Eqs.sum1})}\end{subarray}}$
$\displaystyle=\sum\limits_{B\subseteq
E}\left(-1\right)^{\left|B\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
B\end{subarray}}a_{K}\right)q^{\operatorname*{conn}\left(V,B\right)}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)q^{\operatorname*{conn}\left(V,F\right)}$

(here, we have renamed the summation index $B$ as $F$). This proves Theorem
1.11.

From Lemma 3.10, we obtain the following consequence:

######  Lemma 3.12.

Let $G=\left(V,E\right)$ be a finite graph. Let $q\in\mathbb{N}$. Then,

$\displaystyle\left(\text{the number of all proper
}\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right)$
$\displaystyle=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}q^{\operatorname*{conn}\left(V,F\right)}.$

(Here, of course, the pair $\left(V,F\right)$ is regarded as a graph, and the
expression $\operatorname*{conn}\left(V,F\right)$ is understood according to
Definition 3.3.)

######  Proof 3.13 (Proof of Lemma 3.12.).

This is derived from Lemma 3.10 in the same way as Theorem 1.8 was derived
from Theorem 3.5.

Next, we recall a classical fact about a polynomials over fields: Namely, if a
polynomial (in one variable) over a field has infinitely many roots, then this
polynomial is $0$. Let us state this more formally:

######  Proposition 3.14.

Let $K$ be a field. Let $P\in K\left[x\right]$ be a polynomial over $K$.
Assume that there are infinitely many $\lambda\in K$ satisfying
$P\left(\lambda\right)=0$. Then, $P=0$.

We shall use the following consequence of this proposition:

######  Corollary 3.15.

Let $R$ be an integral domain. Assume that the canonical ring homomorphism
from the ring $\mathbb{Z}$ to the ring $R$ is injective. Let $P\in
R\left[x\right]$ be a polynomial over $R$. Assume that $P\left(q\cdot
1_{R}\right)=0$ for every $q\in\mathbb{N}$ (where $1_{R}$ denotes the unity of
$R$). Then, $P=0$.

######  Proof 3.16 (Proof of Corollary 3.15.).

Let $K$ denote the fraction field of the integral domain $R$. We regard $R$
and $R\left[x\right]$ as subrings of $K$ and $K\left[x\right]$, respectively.
By assumption, we have $P\left(q\cdot 1_{R}\right)=0$ for every
$q\in\mathbb{N}$. But the elements $q\cdot 1_{R}$ of $R$ for $q\in\mathbb{N}$
are pairwise distinct (since the canonical ring homomorphism from the ring
$\mathbb{Z}$ to the ring $R$ is injective). Hence, there are infinitely many
$\lambda\in K$ satisfying $P\left(\lambda\right)=0$ (namely, $\lambda=q\cdot
1_{R}$ for all $q\in\mathbb{N}$). Thus, Proposition 3.14 shows that $P=0$.
This proves Corollary 3.15.

We can now prove the classical Theorem 3.1:

######  Proof 3.17 (Proof of Theorem 3.1.).

We need to show that there exists a unique polynomial
$P\in\mathbb{Z}\left[x\right]$ such that every $q\in\mathbb{N}$ satisfies

$P\left(q\right)=\left(\text{the number of all proper
}\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right).$

To see that such a polynomial exists, we notice that
$P=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}x^{\operatorname*{conn}\left(V,F\right)}$ is
such a polynomial (by Lemma 3.12). It remains to prove that such a polynomial
is unique. This follows from the fact that if two polynomials
$P_{1}\in\mathbb{Z}\left[x\right]$ and $P_{2}\in\mathbb{Z}\left[x\right]$
satisfy

$P_{1}\left(q\right)=P_{2}\left(q\right)\ \ \ \ \ \ \ \ \ \ \text{for all
}q\in\mathbb{N},$

then $P_{1}=P_{2}$ 131313This fact follows from Corollary 3.15 (applied to
$R=\mathbb{Z}$ and $P=P_{1}-P_{2}$).. Theorem 3.1 is therefore proven.

Next, it is the turn of Theorem 3.5:

######  Proof 3.18 (Proof of Theorem 3.5.).

Let $R$ be the polynomial ring $\mathbb{Z}\left[y_{K}\ \mid\
K\in\mathfrak{K}\right]$, where $y_{K}$ is a new indeterminate for each
$K\in\mathfrak{K}$.

The claim of Theorem 3.5 is a polynomial identity in the elements $a_{K}$ of
$\mathbf{k}$. Hence, we can WLOG assume that $\mathbf{k}=R$ and $a_{K}=y_{K}$
for each $K\in\mathfrak{K}$. Assume this. Thus, $\mathbf{k}$ is an integral
domain, and the canonical ring homomorphism from the ring $\mathbb{Z}$ to the
ring $\mathbf{k}$ is injective.

For every $q\in\mathbb{N}$, we have

$\displaystyle\chi_{G}\left(q\right)$ $\displaystyle=\left(\text{the number of
all proper }\left\\{1,2,\ldots,q\right\\}\text{-colorings of }G\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{by the definition of the
chromatic polynomial }\chi_{G}\right)$ $\displaystyle=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)q^{\operatorname*{conn}\left(V,F\right)}$ (13)

(by Lemma 3.10). Define a polynomial $P\in\mathbf{k}\left[x\right]$ by

$P=\chi_{G}-\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)x^{\operatorname*{conn}\left(V,F\right)}.$ (14)

Then, for every $q\in\mathbb{N}$, we have

$\displaystyle P\left(\underbrace{q\cdot 1_{\mathbf{k}}}_{=q}\right)$
$\displaystyle=P\left(q\right)=\chi_{G}\left(q\right)-\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)q^{\operatorname*{conn}\left(V,F\right)}\ \ \ \ \
\ \ \ \ \ \left(\text{by (\ref{pf.thm.chrompol.varis.short.P=})}\right)$
$\displaystyle=0\ \ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.thm.chrompol.varis.short.eq1})}\right).$

Thus, Corollary 3.15 (applied to $R=\mathbf{k}$) shows that $P=0$. In light of
(14), this rewrites as follows:

$\chi_{G}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq
F\end{subarray}}a_{K}\right)x^{\operatorname*{conn}\left(V,F\right)}.$

This proves Theorem 3.5.

Now that Theorem 3.5 is proven, we could derive Theorem 3.4, Corollary 3.6 and
Corollary 3.7 from it in the same way as we have derived Theorem 1.8,
Corollary 1.13 and Corollary 1.14 from Theorem 1.11. We leave the details to
the reader.

###  3.4 Special case: Whitney’s Broken-Circuit Theorem

Corollary 3.7 is commonly stated in the following simplified (if less general)
form:

######  Corollary 3.19.

Let $G=\left(V,E\right)$ be a finite graph. Let $X$ be a totally ordered set.
Let $\ell:E\rightarrow X$ be an injective function. Then,

$\chi_{G}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{ contains no
broken}\\\ \text{circuit of }G\text{ as a
subset}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{\left|V\right|-\left|F\right|}.$

Corollary 3.19 is known as Whitney’s Broken-Circuit theorem (see, e.g.,
[BlaSag86]).

Notice that $\ell$ is required to be injective in Corollary 3.19; the purpose
of this requirement is to ensure that every circuit of $G$ has a unique edge
$e$ with maximum $\ell\left(e\right)$, and thus induces a broken circuit of
$G$. The proof of Corollary 3.19 relies on the following standard result:

######  Lemma 3.20.

Let $\left(V,F\right)$ be a finite graph. Assume that $\left(V,F\right)$ has
no circuits. Then,
$\operatorname*{conn}\left(V,F\right)=\left|V\right|-\left|F\right|$.

(A graph which has no circuits is commonly known as a forest.)

Lemma 3.20 is both extremely elementary and well-known; for example, it
appears in [Bona11, Proposition 10.6] and in [Bollob79, §I.2, Corollary 6].
Let us now see how it entails Corollary 3.19:

######  Proof 3.21 (Proof of Corollary 3.19.).

Corollary 3.19 follows from Corollary 3.7. Indeed, the injectivity of $\ell$
shows that every circuit of $G$ has a unique edge $e$ with maximum
$\ell\left(e\right)$, and thus contains a broken circuit of $G$. Therefore, if
a subset $F$ of $E$ contains no broken circuit of $G$ as a subset, then $F$
contains no circuit of $G$ either, and therefore the graph $\left(V,F\right)$
contains no circuits; but this entails that
$\operatorname*{conn}\left(V,F\right)=\left|V\right|-\left|F\right|$ (by Lemma
3.20). Hence, Corollary 3.7 immediately yields Corollary 3.19.

##  4 Application to transitive directed graphs

We shall now see an application of Corollary 3.6 to graphs which are obtained
from certain directed graphs by “forgetting the directions of the edges”. Let
us first introduce the notations involved:

######  Definition 4.1.

(a) A digraph means a pair $\left(V,A\right)$, where $V$ is a set, and where
$A$ is a subset of $V^{2}$. Digraphs are also called directed graphs. A
digraph $\left(V,A\right)$ is said to be finite if the set $V$ is finite. If
$D=\left(V,A\right)$ is a digraph, then the elements of $V$ are called the
vertices of the digraph $D$, while the elements of $A$ are called the arcs (or
the directed edges) of the digraph $D$. If $a=\left(v,w\right)$ is an arc of a
digraph $D$, then $v$ is called the source of $a$, whereas $w$ is called the
target of $a$.

(b) A digraph $\left(V,A\right)$ is said to be loopless if every $v\in V$
satisfies $\left(v,v\right)\notin A$. (In other words, a digraph is loopless
if and only if it has no arc whose source and target are identical.)

(c) A digraph $\left(V,A\right)$ is said to be transitive if it has the
following property: For any $u\in V$, $v\in V$ and $w\in V$ satisfying
$\left(u,v\right)\in A$ and $\left(v,w\right)\in A$, we have
$\left(u,w\right)\in A$.

(d) A digraph $\left(V,A\right)$ is said to be $2$-path-free if there exist no
three elements $u$, $v$ and $w$ of $V$ satisfying $\left(u,v\right)\in A$ and
$\left(v,w\right)\in A$.

(e) Let $D=\left(V,A\right)$ be a loopless digraph. Define a map
$\operatorname*{set}:A\rightarrow\dbinom{V}{2}$ by setting

$\left(\operatorname*{set}\left(v,w\right)=\left\\{v,w\right\\}\ \ \ \ \ \ \ \
\ \ \text{for every }\left(v,w\right)\in A\right).$

(It is easy to see that $\operatorname*{set}$ is well-defined, because
$\left(V,A\right)$ is loopless.) The graph
$\left(V,\operatorname*{set}A\right)$ will be denoted by $\underline{D}$.

We can now state our application of Corollary 3.6, answering a question
suggested by Alexander Postnikov:

######  Proposition 4.2.

Let $D=\left(V,A\right)$ be a finite transitive loopless digraph. Then,

$\chi_{\underline{D}}=\sum\limits_{\begin{subarray}{c}F\subseteq A;\\\
\text{the digraph }\left(V,F\right)\text{ is }2\text{-path-
free}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{\operatorname*{conn}\left(V,\operatorname*{set}F\right)}.$

######  Proof 4.3 (Proof of Proposition 4.2.).

Let $E=\operatorname*{set}A$. Then, the definition of $\underline{D}$ yields
$\underline{D}=\left(V,\underbrace{\operatorname*{set}A}_{=E}\right)=\left(V,E\right)$.

The map $\operatorname*{set}:A\rightarrow\dbinom{V}{2}$ (which sends every arc
$\left(v,w\right)\in A$ to $\left\\{v,w\right\\}\in\dbinom{V}{2}$) restricts
to a surjection $A\rightarrow E$ (since $E=\operatorname*{set}A$). Let us
denote this surjection by $\pi$. Thus, $\pi$ is a map from $A$ to $E$ sending
each arc $\left(v,w\right)\in A$ to $\left\\{v,w\right\\}\in E$. We shall soon
see that $\pi$ is a bijection.

We define a partial order on the set $V$ as follows: For $i\in V$ and $j\in
V$, we set $i<j$ if and only if $\left(i,j\right)\in A$ (that is, if and only
if there is an arc from $i$ to $j$ in $D$). This is a well-defined partial
order141414Indeed, the relation $<$ that we have just defined is transitive
(since the digraph $\left(V,A\right)$ is transitive) and antisymmetric (since
the digraph $\left(V,A\right)$ is loopless).. Thus, $V$ becomes a poset. For
every $i\in V$ and $j\in V$ satisfying $i\leq j$, we let $\left[i,j\right]$
denote the interval $\left\\{k\in V\ \mid\ i\leq k\leq j\right\\}$ of the
poset $V$.

There exist no $i,j\in V$ such that both $\left(i,j\right)$ and
$\left(j,i\right)$ belong to $A$ (because if such $i$ and $j$ would exist,
then they would satisfy $i<j$ and $j<i$, but this would contradict the fact
that $V$ is a poset). Hence, the projection $\pi:A\rightarrow E$ is injective,
and thus bijective (since we already know that $\pi$ is surjective). Hence,
its inverse map $\pi^{-1}:E\rightarrow A$ is well-defined. For every subset
$F$ of $E$, we have

$\displaystyle F$ $\displaystyle=\pi\left(\pi^{-1}\left(F\right)\right)\ \ \ \
\ \ \ \ \ \ \left(\text{since }\pi\text{ is bijective}\right)$
$\displaystyle=\operatorname*{set}\left(\pi^{-1}\left(F\right)\right)$ (15)

(since $\pi$ is a restriction of the map $\operatorname*{set}$).

For any $\left(u,v\right)\in A$ and any subset $F$ of $E$, we have the
following logical equivalence:

$\left(\left\\{u,v\right\\}\in F\right)\ \Longleftrightarrow\
\left(\left(u,v\right)\in\pi^{-1}\left(F\right)\right)$ (16) 151515Proof of
(16): Let $\left(u,v\right)\in A$, and let $F$ be a subset of $E$. We need to
prove the equivalence (16). From $\left(u,v\right)\in A$, we see that
$\pi\left(u,v\right)$ is well-defined. The definition of $\pi$ shows that
$\pi\left(u,v\right)=\left\\{u,v\right\\}$. Hence, we have the following chain
of equivalences:
$\left(\underbrace{\left\\{u,v\right\\}}_{=\pi\left(u,v\right)}\in F\right)\
\Longleftrightarrow\ \left(\pi\left(u,v\right)\in F\right)\
\Longleftrightarrow\ \left(\left(u,v\right)\in\pi^{-1}\left(F\right)\right).$
This proves (16).

.

Define a function $\ell^{\prime}:A\rightarrow\mathbb{N}$ by

$\ell^{\prime}\left(i,j\right)=\left|\left[i,j\right]\right|\ \ \ \ \ \ \ \ \
\ \text{for all }\left(i,j\right)\in A.$

Define a function $\ell:E\rightarrow\mathbb{N}$ by
$\ell=\ell^{\prime}\circ\pi^{-1}$. Thus, $\ell\circ\pi=\ell^{\prime}$.
Therefore,

$\ell\left(\underbrace{\left\\{i,j\right\\}}_{=\pi\left(i,j\right)}\right)=\underbrace{\left(\ell\circ\pi\right)}_{=\ell^{\prime}}\left(i,j\right)=\ell^{\prime}\left(i,j\right)=\left|\left[i,j\right]\right|$
(17)

for all $\left(i,j\right)\in A$.

Let $\mathfrak{K}$ be the set

$\left\\{\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\}\right\\}\ \mid\
\left(i,k\right)\in A\text{ and }\left(k,j\right)\in A\right\\}.$

Each $K\in\mathfrak{K}$ is a broken circuit of $\underline{D}$ 161616Proof.
Let $K\in\mathfrak{K}$. Then,
$K=\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\}\right\\}$ for some
$\left(i,k\right)\in A$ and $\left(k,j\right)\in A$ (by the definition of
$\mathfrak{K}$). Consider these $\left(i,k\right)$ and $\left(k,j\right)$.
Since $\left(V,A\right)$ is transitive, we have $\left(i,j\right)\in A$. Thus,
$\left\\{i,k\right\\}$, $\left\\{k,j\right\\}$ and $\left\\{i,j\right\\}$ are
edges of $\underline{D}$. These edges form a circuit of $\underline{D}$. In
particular, $i$, $j$ and $k$ are pairwise distinct. Applications of (17) yield
$\ell\left(\left\\{i,j\right\\}\right)=\left|\left[i,j\right]\right|$,
$\ell\left(\left\\{i,k\right\\}\right)=\left|\left[i,k\right]\right|$ and
$\ell\left(\left\\{k,j\right\\}\right)=\left|\left[k,j\right]\right|$. But we
have $i<k$ (since $\left(i,k\right)\in A$) and $k<j$ (since
$\left(k,j\right)\in A$). Hence, $\left[i,k\right]$ is a proper subset of
$\left[i,j\right]$. (It is proper because it does not contain $j$, whereas
$\left[i,j\right]$ does.) Hence,
$\left|\left[i,k\right]\right|<\left|\left[i,j\right]\right|$. Thus,
$\ell\left(\left\\{i,j\right\\}\right)=\left|\left[i,j\right]\right|>\left|\left[i,k\right]\right|=\ell\left(\left\\{i,k\right\\}\right)$.
Similarly,
$\ell\left(\left\\{i,j\right\\}\right)>\ell\left(\left\\{k,j\right\\}\right)$.
The last two inequalities show that $\left\\{i,j\right\\}$ is the unique edge
of the circuit
$\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\},\left\\{i,j\right\\}\right\\}$
having maximum label. Hence,
$\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\},\left\\{i,j\right\\}\right\\}\setminus\left\\{\left\\{i,j\right\\}\right\\}$
is a broken circuit of $\underline{D}$. Since
$\displaystyle\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\},\left\\{i,j\right\\}\right\\}\setminus\left\\{\left\\{i,j\right\\}\right\\}$
$\displaystyle=\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\}\right\\}\ \ \
\ \ \ \ \ \ \ \left(\text{since }i\text{, }j\text{ and }k\text{ are pairwise
distinct}\right)$ $\displaystyle=K,$ this shows that $K$ is a broken circuit
of $\underline{D}$, qed.. Thus, $\mathfrak{K}$ is a set of broken circuits of
$\underline{D}$.

A subset $F$ of $E$ is $\mathfrak{K}$-free if and only if the digraph
$\left(V,\pi^{-1}\left(F\right)\right)$ is $2$-path-free171717Proof. Let $F$
be a subset of $E$. Then, we have the following equivalence of statements:
$\displaystyle\ \left(F\text{ is }\mathfrak{K}\text{-free}\right)$
$\displaystyle\Longleftrightarrow\
\left(\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\}\right\\}\not\subseteq
F\text{ whenever }\left(i,k\right)\in A\text{ and }\left(k,j\right)\in
A\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{by the definition of
}\mathfrak{K}\right)$ $\displaystyle\Longleftrightarrow\ \left(\text{no
}\left(i,k\right)\in A\text{ and }\left(k,j\right)\in A\text{ satisfy
}\left\\{\left\\{i,k\right\\},\left\\{k,j\right\\}\right\\}\subseteq F\right)$
$\displaystyle\Longleftrightarrow\ \left(\text{no }\left(i,k\right)\in A\text{
and }\left(k,j\right)\in A\text{ satisfy }\left\\{i,k\right\\}\in F\text{ and
}\left\\{k,j\right\\}\in F\right)$ $\displaystyle\Longleftrightarrow\
\left(\text{no }\left(i,k\right)\in A\text{ and }\left(k,j\right)\in A\text{
satisfy }\left(i,k\right)\in\pi^{-1}\left(F\right)\text{ and
}\left\\{k,j\right\\}\in F\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\begin{array}[c]{c}\text{because for }\left(i,k\right)\in A\text{, we
have }\left\\{i,k\right\\}\in F\text{ if and only if
}\left(i,k\right)\in\pi^{-1}\left(F\right)\\\ \text{(by
(\ref{pf.prop.digraph.2pf-chrom.short.equiv}), applied to }u=i\text{ and
}v=k\text{)}\end{array}\right)$ $\displaystyle\Longleftrightarrow\
\left(\text{no }\left(i,k\right)\in A\text{ and }\left(k,j\right)\in A\text{
satisfy }\left(i,k\right)\in\pi^{-1}\left(F\right)\text{ and
}\left(k,j\right)\in\pi^{-1}\left(F\right)\right)$ $\displaystyle\ \ \ \ \ \ \
\ \ \ \left(\begin{array}[c]{c}\text{because for }\left(k,j\right)\in A\text{,
we have }\left\\{k,j\right\\}\in F\text{ if and only if
}\left(k,j\right)\in\pi^{-1}\left(F\right)\\\ \text{(by
(\ref{pf.prop.digraph.2pf-chrom.short.equiv}), applied to }u=k\text{ and
}v=j\text{)}\end{array}\right)$ $\displaystyle\Longleftrightarrow\
\left(\text{the digraph }\left(V,\pi^{-1}\left(F\right)\right)\text{ is
}2\text{-path-free}\right)\ \ \ \ \ \ \ \ \ \ \left(\text{by the definition of
\textquotedblleft}2\text{-path-free\textquotedblright}\right),$ qed.. Now,
Corollary 3.6 (applied to $X=\mathbb{N}$ and $G=\underline{D}$) shows that

$\displaystyle\chi_{\underline{D}}$
$\displaystyle=\underbrace{\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\
F\text{ is
}\mathfrak{K}\text{-free}\end{subarray}}}_{\begin{subarray}{c}=\sum\limits_{\begin{subarray}{c}F\subseteq
E;\\\ \text{the digraph }\left(V,\pi^{-1}\left(F\right)\right)\text{ is
}2\text{-path-free}\end{subarray}}\\\ \text{(since we have just shown that}\\\
\text{a subset }F\text{ of }E\text{ is }\mathfrak{K}\text{-free if and only
if}\\\ \text{the digraph }\left(V,\pi^{-1}\left(F\right)\right)\text{ is
}2\text{-path-
free)}\end{subarray}}\underbrace{\left(-1\right)^{\left|F\right|}}_{\begin{subarray}{c}=\left(-1\right)^{\left|\pi^{-1}\left(F\right)\right|}\\\
\text{(since }\pi\text{ is
bijective)}\end{subarray}}\underbrace{x^{\operatorname*{conn}\left(V,F\right)}}_{\begin{subarray}{c}=x^{\operatorname*{conn}\left(V,\operatorname*{set}\left(\pi^{-1}\left(F\right)\right)\right)}\\\
\text{(by (\ref{pf.prop.digraph.2pf-chrom.short.F=set}))}\end{subarray}}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ \text{the
digraph }\left(V,\pi^{-1}\left(F\right)\right)\text{ is }2\text{-path-
free}\end{subarray}}\left(-1\right)^{\left|\pi^{-1}\left(F\right)\right|}x^{\operatorname*{conn}\left(V,\operatorname*{set}\left(\pi^{-1}\left(F\right)\right)\right)}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}B\subseteq A;\\\ \text{the
digraph }\left(V,B\right)\text{ is }2\text{-path-
free}\end{subarray}}\left(-1\right)^{\left|B\right|}x^{\operatorname*{conn}\left(V,\operatorname*{set}B\right)}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\begin{array}[c]{c}\text{here, we have
substituted }B\text{ for }\pi^{-1}\left(F\right)\text{ in the sum,}\\\
\text{since the map }\pi:A\rightarrow E\text{ is bijective and thus
induces}\\\ \text{a bijection from the subsets of }E\text{ to the subsets of
}A\\\ \text{sending each }F\subseteq E\text{ to
}\pi^{-1}\left(F\right)\end{array}\right)$
$\displaystyle=\sum\limits_{\begin{subarray}{c}F\subseteq A;\\\ \text{the
digraph }\left(V,F\right)\text{ is }2\text{-path-
free}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{\operatorname*{conn}\left(V,\operatorname*{set}F\right)}$

(here, we have renamed the summation index $B$ as $F$). This proves
Proposition 4.2.

##  5 A matroidal generalization

###  5.1 An introduction to matroids

We shall now present a result that can be considered as a generalization of
Theorem 3.5 in a different direction than Theorem 1.11: namely, a formula for
the characteristic polynomial of a matroid. Let us first recall the basic
notions from the theory of matroids that will be needed to state it.

First, we introduce some basic poset-related terminology:

######  Definition 5.1.

Let $P$ be a poset.

(a) An element $v$ of $P$ is said to be maximal (with respect to $P$) if and
only if every $w\in P$ satisfying $w\geq v$ must satisfy $w=v$.

(b) An element $v$ of $P$ is said to be minimal (with respect to $P$) if and
only if every $w\in P$ satisfying $w\leq v$ must satisfy $w=v$.

######  Definition 5.2.

For any set $E$, we shall regard the powerset $\mathcal{P}\left(E\right)$ as a
poset (with respect to inclusion). Thus, any subset $\mathcal{S}$ of
$\mathcal{P}\left(E\right)$ also becomes a poset, and therefore the notions of
“minimal” and “maximal” elements in $\mathcal{S}$ make sense. Beware that
these notions are not related to size; i.e., a maximal element of
$\mathcal{S}$ might not be a maximum-size element of $\mathcal{S}$.

Now, let us define the notion of “matroid” that we will use:

######  Definition 5.3.

(a) A matroid means a pair $\left(E,\mathcal{I}\right)$ consisting of a finite
set $E$ and a set $\mathcal{I}\subseteq\mathcal{P}\left(E\right)$ satisfying
the following axioms:

  * •

Matroid axiom 1: We have $\varnothing\in\mathcal{I}$.

  * •

Matroid axiom 2: If $Y\in\mathcal{I}$ and $Z\in\mathcal{P}\left(E\right)$ are
such that $Z\subseteq Y$, then $Z\in\mathcal{I}$.

  * •

Matroid axiom 3: If $Y\in\mathcal{I}$ and $Z\in\mathcal{I}$ are such that
$\left|Y\right|<\left|Z\right|$, then there exists some $x\in Z\setminus Y$
such that $Y\cup\left\\{x\right\\}\in\mathcal{I}$.

(b) Let $\left(E,\mathcal{I}\right)$ be a matroid. A subset $S$ of $E$ is said
to be independent (for this matroid) if and only if $S\in\mathcal{I}$. The set
$E$ is called the ground set of the matroid $\left(E,\mathcal{I}\right)$.

Different texts give different definitions of a matroid; these definitions are
(mostly) equivalent, but not always in the obvious way181818I.e., it sometimes
happens that two different texts both define a matroid as a pair
$\left(E,U\right)$ of a finite set $E$ and a subset
$U\subseteq\mathcal{P}\left(E\right)$, but they require these pairs
$\left(E,U\right)$ to satisfy non-equivalent axioms, and the equivalence
between their definitions is more complicated than just “a pair
$\left(E,U\right)$ is a matroid for one definition if and only if it is a
matroid for the other”.. Definition 5.3 is how a matroid is defined in
[Schrij13, §10.1] and in [Martin15, Definition 3.15] (where it is called a
“(matroid) independence system”). There exist other definitions of a matroid,
which turn out to be equivalent. The definition of a matroid given in
Stanley’s [Stanley06, Definition 3.8] is directly equivalent to Definition
5.3, with the only differences that

  * •

Stanley replaces Matroid axiom 1 by the requirement that
$\mathcal{I}\neq\varnothing$ (which is, of course, equivalent to Matroid axiom
1 as long as Matroid axiom 2 is assumed), and

  * •

Stanley replaces Matroid axiom 3 by the requirement that for every
$T\in\mathcal{P}\left(E\right)$, all maximal elements of
$\mathcal{I}\cap\mathcal{P}\left(T\right)$ have the same
cardinality191919Here, as we have already explained, we regard
$\mathcal{I}\cap\mathcal{P}\left(T\right)$ as a poset with respect to
inclusion. Thus, an element $Y$ of this poset is maximal if and only if there
exists no $Z\in\mathcal{I}\cap\mathcal{P}\left(T\right)$ such that $Y$ is a
proper subset of $Z$. (this requirement is equivalent to Matroid axiom 3 as
long as Matroid axiom 2 is assumed).

We now introduce some terminology related to matroids:

######  Definition 5.4.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid.

(a) We define a function
$r_{M}:\mathcal{P}\left(E\right)\rightarrow\mathbb{N}$ by setting

$r_{M}\left(S\right)=\max\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{
and }Z\subseteq S\right\\}\ \ \ \ \ \ \ \ \ \ \text{for every }S\subseteq E.$
(18)

(Note that the right hand side of (18) is well-defined, because there exists
at least one $Z\in\mathcal{I}$ satisfying $Z\subseteq S$ (namely,
$Z=\varnothing$).) If $S$ is a subset of $E$, then the nonnegative integer
$r_{M}\left(S\right)$ is called the rank of $S$ (with respect to $M$). It is
clear that $r_{M}$ is a weakly increasing function from the poset
$\mathcal{P}\left(E\right)$ to $\mathbb{N}$.

(b) If $k\in\mathbb{N}$, then a $k$-flat of $M$ means a subset of $E$ which
has rank $k$ and is maximal among all such subsets (i.e., it is not a proper
subset of any other subset having rank $k$). (Beware: Not all $k$-flats have
the same size.) A flat of $M$ is a subset of $E$ which is a $k$-flat for some
$k\in\mathbb{N}$. We let $\operatorname*{Flats}M$ denote the set of all flats
of $M$; thus, $\operatorname*{Flats}M$ is a subposet of
$\mathcal{P}\left(E\right)$.

(c) A circuit of $M$ means a minimal element of
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$. (That is, a circuit of $M$
means a subset of $E$ which is not independent (for $M$) and which is minimal
among such subsets.)

(d) An element $e$ of $E$ is said to be a loop (of $M$) if
$\left\\{e\right\\}\notin\mathcal{I}$. The matroid $M$ is said to be loopless
if no loops (of $M$) exist.

Notice that the function that we called $r_{M}$ in Definition 5.4 (a) is
denoted by $\operatorname*{rk}$ in Stanley’s [Stanley06, Lecture 3].

One of the most classical examples of a matroid is the graphical matroid of a
graph:

######  Example 5.5.

Let $G=\left(V,E\right)$ be a finite graph. Define a subset $\mathcal{I}$ of
$\mathcal{P}\left(E\right)$ by

$\mathcal{I}=\left\\{T\in\mathcal{P}\left(E\right)\ \mid\ T\text{ contains no
circuit of }G\text{ as a subset}\right\\}.$

Then, $\left(E,\mathcal{I}\right)$ is a matroid; it is called the graphical
matroid (or the cycle matroid) of $G$. It has the following properties:

  * •

The matroid $\left(E,\mathcal{I}\right)$ is loopless.

  * •

For each $T\in\mathcal{P}\left(E\right)$, we have

$r_{\left(E,\mathcal{I}\right)}\left(T\right)=\left|V\right|-\operatorname*{conn}\left(V,T\right)$

(where $\operatorname*{conn}\left(V,T\right)$ is defined as in Definition
3.3).

  * •

The circuits of the matroid $\left(E,\mathcal{I}\right)$ are precisely the
circuits of the graph $G$.

  * •

The flats of the matroid $\left(E,\mathcal{I}\right)$ are related to colorings
of $G$. More precisely: For each set $X$ and each $X$-coloring $f$ of $G$, the
set $E\cap\operatorname*{Eqs}f$ is a flat of $\left(E,\mathcal{I}\right)$.
Every flat of $\left(E,\mathcal{I}\right)$ can be obtained in this way when
$X$ is chosen large enough; but often, several distinct $X$-colorings $f$ lead
to one and the same flat $E\cap\operatorname*{Eqs}f$.

We recall three basic facts that are used countless times in arguing about
matroids:

######  Lemma 5.6.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $T\in\mathcal{I}$. Then,
$r_{M}\left(T\right)=\left|T\right|$.

######  Proof 5.7 (Proof of Lemma 5.6.).

We have $T\in\mathcal{I}$ and $T\subseteq T$. Thus, $T$ is a $Z\in\mathcal{I}$
satisfying $Z\subseteq T$. Therefore,
$\left|T\right|\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{ and
}Z\subseteq T\right\\}$, so that

$\left|T\right|\leq\max\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{ and
}Z\subseteq T\right\\}$ (19)

(since any element of a set of integers is smaller or equal to the maximum of
this set).

On the other hand, the definition of $r_{M}$ yields

$r_{M}\left(T\right)=\max\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{
and }Z\subseteq T\right\\}.$

Hence, (19) rewrites as follows:

$\left|T\right|\leq r_{M}\left(T\right).$

Also,

$\displaystyle r_{M}\left(T\right)$ $\displaystyle=\max\left\\{\left|Z\right|\
\mid\ Z\in\mathcal{I}\text{ and }Z\subseteq T\right\\}\ \ \ \ \ \ \ \ \ \
\left(\text{by the definition of }r_{M}\right)$
$\displaystyle\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{ and
}Z\subseteq T\right\\}$

(since the maximum of any set belongs to this set). Thus, there exists a
$Z\in\mathcal{I}$ satisfying $Z\subseteq T$ and
$r_{M}\left(T\right)=\left|Z\right|$. Consider this $Z$. From $Z\subseteq T$,
we obtain $\left|Z\right|\leq\left|T\right|$, so that
$r_{M}\left(T\right)=\left|Z\right|\leq\left|T\right|$. Combining this with
$\left|T\right|\leq r_{M}\left(T\right)$, we obtain
$r_{M}\left(T\right)=\left|T\right|$. This proves Lemma 5.6.

######  Lemma 5.8.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let
$Q\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$. Then, there exists a
circuit $C$ of $M$ such that $C\subseteq Q$.

######  Proof 5.9 (Proof of Lemma 5.8.).

We have $Q\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$. Thus, there
exists at least one $C\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$ such
that $C\subseteq Q$ (namely, $C=Q$). Thus, there also exists a minimal such
$C$. Consider this minimal $C$. We know that $C$ is a minimal element of
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$ such that $C\subseteq Q$. In
other words, $C$ is an element of
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$ satisfying $C\subseteq Q$, and
moreover,

$\text{every }D\in\mathcal{P}\left(E\right)\setminus\mathcal{I}\text{
satisfying }D\subseteq Q\text{ and }D\subseteq C\text{ must satisfy }D=C.$
(20)

Thus, $C$ is a minimal element of
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$ 202020Proof. We need to show
that every $D\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$ satisfying
$D\subseteq C$ must satisfy $D=C$ (since we already know that
$C\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$). So let
$D\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$ be such that $D\subseteq
C$. Then, $D\subseteq C\subseteq Q$. Hence, (20) shows that $D=C$. This
completes our proof.. In other words, $C$ is a circuit of $M$ (by the
definition of a “circuit”). This circuit $C$ satisfies $C\subseteq Q$. Thus,
we have constructed a circuit $C$ of $M$ satisfying $C\subseteq Q$. Lemma 5.8
is thus proven.

######  Lemma 5.10.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $T$ be a subset of $E$.
Let $S\in\mathcal{I}$ be such that $S\subseteq T$. Then, there exists an
$S^{\prime}\in\mathcal{I}$ satisfying $S\subseteq S^{\prime}\subseteq T$ and
$\left|S^{\prime}\right|=r_{M}\left(T\right)$.

######  Proof 5.11 (Proof of Lemma 5.10.).

Clearly, there exists at least one $S^{\prime}\in\mathcal{I}$ satisfying
$S\subseteq S^{\prime}\subseteq T$ (namely, $S^{\prime}=S$). Hence, there
exists a maximal such $S^{\prime}$. Let $Q$ be such a maximal $S^{\prime}$.
Thus, $Q$ is an element of $\mathcal{I}$ satisfying $S\subseteq Q\subseteq T$.

Recall that

$\displaystyle r_{M}\left(T\right)$ $\displaystyle=\max\left\\{\left|Z\right|\
\mid\ Z\in\mathcal{I}\text{ and }Z\subseteq T\right\\}\ \ \ \ \ \ \ \ \ \
\left(\text{by the definition of }r_{M}\right)$
$\displaystyle\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{ and
}Z\subseteq T\right\\}$

(since the maximum of any set must belong to this set). Hence, there exists
some $Z\in\mathcal{I}$ satisfying $Z\subseteq T$ and
$r_{M}\left(T\right)=\left|Z\right|$. Denote such a $Z$ by $W$. Thus, $W$ is
an element of $\mathcal{I}$ satisfying $W\subseteq T$ and
$r_{M}\left(T\right)=\left|W\right|$.

We have $\left|Q\right|\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{
and }Z\subseteq T\right\\}$ (since $Q\in\mathcal{I}$ and $Q\subseteq T$).
Since any element of a set is smaller or equal to the maximum of this set,
this entails that $\left|Q\right|\leq\max\left\\{\left|Z\right|\ \mid\
Z\in\mathcal{I}\text{ and }Z\subseteq
T\right\\}=r_{M}\left(T\right)=\left|W\right|$.

Now, assume (for the sake of contradiction) that
$\left|Q\right|\neq\left|W\right|$. Thus, $\left|Q\right|<\left|W\right|$
(since $\left|Q\right|\leq\left|W\right|$). Hence, Matroid axiom 3 (applied to
$Y=Q$ and $Z=W$) shows that there exists some $x\in W\setminus Q$ such that
$Q\cup\left\\{x\right\\}\in\mathcal{I}$. Consider this $x$. We have $x\in
W\setminus Q\subseteq W\subseteq T$, so that $Q\cup\left\\{x\right\\}\subseteq
T$ (since $Q\subseteq T$). Also, $x\notin Q$ (since $x\in W\setminus Q$).

Recall that $Q$ is a maximal $S^{\prime}\in\mathcal{I}$ satisfying $S\subseteq
S^{\prime}\subseteq T$. Thus, if some $S^{\prime}\in\mathcal{I}$ satisfies
$S\subseteq S^{\prime}\subseteq T$ and $S^{\prime}\supseteq Q$, then
$S^{\prime}=Q$. Applying this to $S^{\prime}=Q\cup\left\\{x\right\\}$, we
obtain $Q\cup\left\\{x\right\\}=Q$ (since $S\subseteq Q\subseteq
Q\cup\left\\{x\right\\}\subseteq T$ and $Q\cup\left\\{x\right\\}\supseteq Q$).
Thus, $x\in Q$. But this contradicts $x\notin Q$. This contradiction shows
that our assumption (that $\left|Q\right|\neq\left|W\right|$) was wrong.
Hence, $\left|Q\right|=\left|W\right|=r_{M}\left(T\right)$. Thus, there exists
an $S^{\prime}\in\mathcal{I}$ satisfying $S\subseteq S^{\prime}\subseteq T$
and $\left|S^{\prime}\right|=r_{M}\left(T\right)$ (namely, $S^{\prime}=Q$).
This proves Lemma 5.10.

###  5.2 The lattice of flats

We shall now show a lemma that can be regarded as an alternative criterion for
a subset of $E$ to be a flat:

######  Lemma 5.12.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $T$ be a subset of $E$.
Then, the following statements are equivalent:

Statement $\mathfrak{F}_{1}$: The set $T$ is a flat of $M$.

Statement $\mathfrak{F}_{2}$: If $C$ is a circuit of $M$, and if $e\in C$ is
such that $C\setminus\left\\{e\right\\}\subseteq T$, then $C\subseteq T$.

######  Proof 5.13 (Proof of Lemma 5.12.).

Proof of the implication
$\mathfrak{F}$${}_{1}\Longrightarrow\mathfrak{F}_{2}$: Assume that Statement
$\mathfrak{F}_{1}$ holds. We must prove that Statement $\mathfrak{F}_{2}$
holds.

Let $C$ be a circuit of $M$. Let $e\in C$ be such that
$C\setminus\left\\{e\right\\}\subseteq T$. We must prove that $C\subseteq T$.

Assume the contrary. Thus, $C\not\subseteq T$. Combining this with
$C\setminus\left\\{e\right\\}\subseteq T$, we obtain $e\notin T$. Hence, $T$
is a proper subset of $T\cup\left\\{e\right\\}$.

We have assumed that Statement $\mathfrak{F}_{1}$ holds. In other words, the
set $T$ is a flat of $M$. In other words, there exists some $k\in\mathbb{N}$
such that $T$ is a $k$-flat of $M$. Consider this $k$.

The set $T$ is a $k$-flat of $M$, thus a subset of $E$ which has rank $k$ and
is maximal among all such subsets. In other words, $r_{M}\left(T\right)=k$,
but every subset $S$ of $E$ for which $T$ is a proper subset of $S$ must
satisfy

$r_{M}\left(S\right)\neq k.$ (21)

Applying (21) to $S=T\cup\left\\{e\right\\}$, we obtain
$r_{M}\left(T\cup\left\\{e\right\\}\right)\neq k$. Since
$T\cup\left\\{e\right\\}\supseteq T$ (and since the function
$r_{M}:\mathcal{P}\left(E\right)\rightarrow\mathbb{N}$ is weakly increasing),
we have $r_{M}\left(T\cup\left\\{e\right\\}\right)\geq r_{M}\left(T\right)=k$.
Combined with $r_{M}\left(T\cup\left\\{e\right\\}\right)\neq k$, this yields
$r_{M}\left(T\cup\left\\{e\right\\}\right)>k$. Thus,
$r_{M}\left(T\cup\left\\{e\right\\}\right)\geq k+1$.

Notice that $C\setminus\left\\{e\right\\}$ is a proper subset of $C$ (since
$e\in C$). The set $C$ is a circuit of $M$, thus a minimal element of
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$ (by the definition of a
“circuit”). Hence, no proper subset of $C$ belongs to
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$ (because $C$ is minimal). In
other words, every proper subset of $C$ belongs to $\mathcal{I}$. Applying
this to the proper subset $C\setminus\left\\{e\right\\}$ of $C$, we conclude
that $C\setminus\left\\{e\right\\}$ belongs to $\mathcal{I}$. Hence, Lemma
5.10 (applied to $S=C\setminus\left\\{e\right\\}$) shows that there exists an
$S^{\prime}\in\mathcal{I}$ satisfying $C\setminus\left\\{e\right\\}\subseteq
S^{\prime}\subseteq T$ and $\left|S^{\prime}\right|=r_{M}\left(T\right)$.
Denote this $S^{\prime}$ by $S$. Thus, $S$ is an element of $\mathcal{I}$
satisfying $C\setminus\left\\{e\right\\}\subseteq S\subseteq T$ and
$\left|S\right|=r_{M}\left(T\right)$.

Furthermore, $S\subseteq T\subseteq T\cup\left\\{e\right\\}$. Thus, Lemma 5.10
(applied to $T\cup\left\\{e\right\\}$ instead of $T$) shows that there exists
an $S^{\prime}\in\mathcal{I}$ satisfying $S\subseteq S^{\prime}\subseteq
T\cup\left\\{e\right\\}$ and
$\left|S^{\prime}\right|=r_{M}\left(T\cup\left\\{e\right\\}\right)$. Consider
this $S^{\prime}$.

We have
$\left|S^{\prime}\right|=r_{M}\left(T\cup\left\\{e\right\\}\right)>r_{M}\left(T\right)$.
Hence, $S^{\prime}\not\subseteq T$ 212121Proof. Assume the contrary. Thus,
$S^{\prime}\subseteq T$. Hence, $S^{\prime}$ is an element of $\mathcal{I}$
and satisfies $S^{\prime}\subseteq T$. Thus,
$\left|S^{\prime}\right|\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{
and }Z\subseteq T\right\\}$. Now, the definition of $r_{M}$ yields
$r_{M}\left(T\right)=\max\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{
and }Z\subseteq T\right\\}\geq\left|S^{\prime}\right|$ (since
$\left|S^{\prime}\right|\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{
and }Z\subseteq T\right\\}$). This contradicts
$\left|S^{\prime}\right|>r_{M}\left(T\right)$. This contradiction proves that
our assumption was wrong, qed.. Combining this with $S^{\prime}\subseteq
T\cup\left\\{e\right\\}$, we obtain $e\in S^{\prime}$. Combining this with
$C\setminus\left\\{e\right\\}\subseteq S^{\prime}$, we find that
$\left(C\setminus\left\\{e\right\\}\right)\cup\left\\{e\right\\}\subseteq
S^{\prime}$. Thus,
$C=\left(C\setminus\left\\{e\right\\}\right)\cup\left\\{e\right\\}\subseteq
S^{\prime}$. Since $S^{\prime}\in\mathcal{I}$, this entails that
$C\in\mathcal{I}$ (by Matroid axiom 2). But
$C\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$ (since $C$ is a minimal
element of $\mathcal{P}\left(E\right)\setminus\mathcal{I}$), so that
$C\notin\mathcal{I}$. This contradicts $C\in\mathcal{I}$. This contradiction
shows that our assumption was wrong. Hence, $C\subseteq T$ is proven.
Therefore, Statement $\mathfrak{F}_{2}$ holds. Thus, the implication
$\mathfrak{F}_{1}\Longrightarrow\mathfrak{F}_{2}$ is proven.

Proof of the implication
$\mathfrak{F}$${}_{2}\Longrightarrow\mathfrak{F}_{1}$: Assume that Statement
$\mathfrak{F}_{2}$ holds. We must prove that Statement $\mathfrak{F}_{1}$
holds.

Let $k=r_{M}\left(T\right)$. We shall show that $T$ is a $k$-flat of $M$.

Let $W$ be a subset of $E$ which has rank $k$ and satisfies $T\subseteq W$. We
shall show that $T=W$.

Indeed, assume the contrary. Thus, $T\neq W$. Combined with $T\subseteq W$,
this shows that $T$ is a proper subset of $W$. Thus, there exists an $e\in
W\setminus T$. Consider this $e$. We have $e\notin T$ (since $e\in W\setminus
T$).

We have

$\displaystyle k$
$\displaystyle=r_{M}\left(T\right)=\max\left\\{\left|Z\right|\ \mid\
Z\in\mathcal{I}\text{ and }Z\subseteq T\right\\}\ \ \ \ \ \ \ \ \ \
\left(\text{by the definition of }r_{M}\right)$
$\displaystyle\in\left\\{\left|Z\right|\ \mid\ Z\in\mathcal{I}\text{ and
}Z\subseteq T\right\\}$

(since the maximum of a set must belong to that set). Hence, there exists some
$Z\in\mathcal{I}$ satisfying $Z\subseteq T$ and $k=\left|Z\right|$. Denote
this $Z$ by $K$. Thus, $K$ is an element of $\mathcal{I}$ and satisfies
$K\subseteq T$ and $k=\left|K\right|$. Notice that $e\notin T$, so that
$e\notin K$ (since $K\subseteq T$).

We have $r_{M}\left(W\right)=k$ (since $W$ has rank $k$). Hence,
$K\cup\left\\{e\right\\}\notin\mathcal{I}$ 222222Proof. Assume the contrary.
Thus, $K\cup\left\\{e\right\\}\in\mathcal{I}$. Thus,
$r_{M}\left(K\cup\left\\{e\right\\}\right)=\left|K\cup\left\\{e\right\\}\right|$
(by Lemma 5.6). Thus,
$r_{M}\left(K\cup\left\\{e\right\\}\right)=\left|K\cup\left\\{e\right\\}\right|>\left|K\right|$
(since $e\notin K$). But $K\cup\left\\{e\right\\}\subseteq W$ (since
$K\subseteq T\subseteq W$ and $e\in W\setminus T\subseteq W$). Since the
function $r_{M}$ is weakly increasing, this yields
$r_{M}\left(K\cup\left\\{e\right\\}\right)\leq
r_{M}\left(W\right)=k=\left|K\right|$. This contradicts
$r_{M}\left(K\cup\left\\{e\right\\}\right)>\left|K\right|$. This contradiction
proves that our assumption was wrong, qed.. In other words,
$K\cup\left\\{e\right\\}\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$.
Hence, Lemma 5.8 (applied to $Q=K\cup\left\\{e\right\\}$) shows that there
exists a circuit $C$ of $M$ such that $C\subseteq K\cup\left\\{e\right\\}$.
Consider this $C$. From $C\subseteq K\cup\left\\{e\right\\}$, we obtain
$C\setminus\left\\{e\right\\}\subseteq K\subseteq T$.

From $C\setminus\left\\{e\right\\}\subseteq K$, we conclude (using Matroid
axiom 2) that $C\setminus\left\\{e\right\\}\in\mathcal{I}$ (since
$K\in\mathcal{I}$). On the other hand, $C$ is a circuit of $M$. In other
words, $C$ is a minimal element of
$\mathcal{P}\left(E\right)\setminus\mathcal{I}$ (by the definition of a
“circuit”). Hence, $C\in\mathcal{P}\left(E\right)\setminus\mathcal{I}$, so
that $C\notin\mathcal{I}$. Hence, $e\in C$ (since otherwise, we would have
$C\setminus\left\\{e\right\\}=C\notin\mathcal{I}$, which would contradict
$C\setminus\left\\{e\right\\}\in\mathcal{I}$). Now, Statement
$\mathfrak{F}_{2}$ shows that $C\subseteq T$. Hence, $e\in C\subseteq T$,
which contradicts $e\notin T$.

This contradiction shows that our assumption was wrong. Hence, $T=W$ is
proven.

Now, forget that we fixed $W$. Thus, we have shown that if $W$ is a subset of
$E$ which has rank $k$ and satisfies $T\subseteq W$, then $T=W$. In other
words, $T$ is a subset of $E$ which has rank $k$ and is maximal among all such
subsets (because we already know that $T$ has rank $r_{M}\left(T\right)=k$).
In other words, $T$ is a $k$-flat of $M$ (by the definition of a “$k$-flat”).
Thus, $T$ is a flat of $M$. In other words, Statement $\mathfrak{F}_{1}$
holds. This proves the implication
$\mathfrak{F}_{2}\Longrightarrow\mathfrak{F}_{1}$.

We have now proven the implications
$\mathfrak{F}_{1}\Longrightarrow\mathfrak{F}_{2}$ and
$\mathfrak{F}_{2}\Longrightarrow\mathfrak{F}_{1}$. Together, these
implications show that Statements $\mathfrak{F}_{1}$ and $\mathfrak{F}_{2}$
are equivalent. This proves Lemma 5.12.

######  Corollary 5.14.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let
$F_{1},F_{2},\ldots,F_{k}$ be flats of $M$. Then, $F_{1}\cap
F_{2}\cap\cdots\cap F_{k}$ is a flat of $M$. (Notice that $k$ is allowed to be
$0$ here; in this case, the empty intersection $F_{1}\cap F_{2}\cap\cdots\cap
F_{k}$ is to be interpreted as $E$.)

######  Proof 5.15 (Proof of Corollary 5.14.).

Lemma 5.12 gives a necessary and sufficient criterion for a subset $T$ of $E$
to be a flat of $M$. It is easy to see that if this criterion is satisfied for
$T=F_{1}$, for $T=F_{2}$, etc., and for $T=F_{k}$, then it is satisfied for
$T=F_{1}\cap F_{2}\cap\cdots\cap F_{k}$. In other words, if
$F_{1},F_{2},\ldots,F_{k}$ are flats of $M$, then $F_{1}\cap
F_{2}\cap\cdots\cap F_{k}$ is a flat of $M$. 232323Here is this argument in
slightly more detail: For every $i\in\left\\{1,2,\ldots,k\right\\}$, the
following statement holds: If $C$ is a circuit of $M$, and if $e\in C$ is such
that $C\setminus\left\\{e\right\\}\subseteq F_{i}$, then  $C\subseteq F_{i}.$
(22) Proof of (22): Let $i\in\left\\{1,2,\ldots,k\right\\}$. Then, the set
$F_{i}$ is a flat of $M$. In other words, Statement $\mathfrak{F}_{1}$ of
Lemma 5.12 is satisfied for $T=F_{i}$. Therefore, Statement $\mathfrak{F}_{2}$
of Lemma 5.12 must also be satisfied for $T=F_{i}$ (since Lemma 5.12 shows
that the Statements $\mathfrak{F}_{1}$ and $\mathfrak{F}_{2}$ are equivalent).
In other words, if $C$ is a circuit of $M$, and if $e\in C$ is such that
$C\setminus\left\\{e\right\\}\subseteq F_{i}$, then $C\subseteq F_{i}$. This
proves (22). Now, let $C$ be a circuit of $M$, and let $e\in C$ be such that
$C\setminus\left\\{e\right\\}\subseteq F_{1}\cap F_{2}\cap\cdots\cap F_{k}$.
For every $i\in\left\\{1,2,\ldots,k\right\\}$, we have
$C\setminus\left\\{e\right\\}\subseteq F_{1}\cap F_{2}\cap\cdots\cap
F_{k}\subseteq F_{i}$, and therefore $C\subseteq F_{i}$ (by (22)). So we have
shown the inclusion $C\subseteq F_{i}$ for each
$i\in\left\\{1,2,\ldots,k\right\\}$. Combining these $k$ inclusions, we obtain
$C\subseteq F_{1}\cap F_{2}\cap\cdots\cap F_{k}$. Now, forget that we fixed
$C$. We thus have shown that if $C$ is a circuit of $M$, and if $e\in C$ is
such that $C\setminus\left\\{e\right\\}\subseteq F_{1}\cap F_{2}\cap\cdots\cap
F_{k}$, then $C\subseteq F_{1}\cap F_{2}\cap\cdots\cap F_{k}$. In other words,
Statement $\mathfrak{F}_{2}$ of Lemma 5.12 is satisfied for $T=F_{1}\cap
F_{2}\cap\cdots\cap F_{k}$. Therefore, Statement $\mathfrak{F}_{1}$ of Lemma
5.12 must also be satisfied for $T=F_{1}\cap F_{2}\cap\cdots\cap F_{k}$ (since
Lemma 5.12 shows that the Statements $\mathfrak{F}_{1}$ and $\mathfrak{F}_{2}$
are equivalent). In other words, the set $F_{1}\cap F_{2}\cap\cdots\cap F_{k}$
is a flat of $M$. Qed. This proves Corollary 5.14.

Corollary 5.14 (a well-known fact, which is left to the reader to prove in
[Stanley06, §3.1]) allows us to define the closure of a set in a matroid:

######  Definition 5.16.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $T$ be a subset of $E$.
The closure of $T$ is defined to be the intersection of all flats of $M$ which
contain $T$ as a subset. In other words, the closure of $T$ is defined to be
$\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\ T\subseteq
F\end{subarray}}F$. The closure of $T$ is denoted by $\overline{T}$.

The following proposition gathers some simple properties of closures in
matroids:

######  Proposition 5.17.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid.

(a) If $T$ is a subset of $E$, then $\overline{T}$ is a flat of $M$ satisfying
$T\subseteq\overline{T}$.

(b) If $G$ is a flat of $M$, then $\overline{G}=G$.

(c) If $T$ is a subset of $E$ and if $G$ is a flat of $M$ satisfying
$T\subseteq G$, then $\overline{T}\subseteq G$.

(d) If $S$ and $T$ are two subsets of $E$ satisfying $S\subseteq T$, then
$\overline{S}\subseteq\overline{T}$.

(e) If the matroid $M$ is loopless, then $\overline{\varnothing}=\varnothing$.

(f) Every subset $T$ of $E$ satisfies
$r_{M}\left(T\right)=r_{M}\left(\overline{T}\right)$.

(g) If $T$ is a subset of $E$ and if $G$ is a flat of $M$, then the conditions
$\left(\overline{T}\subseteq G\right)$ and $\left(T\subseteq G\right)$ are
equivalent.

######  Proof 5.18 (Proof of Proposition 5.17.).

(a) The set $\operatorname*{Flats}M$ is a subset of the finite set
$\mathcal{P}\left(E\right)$, and thus itself finite.

Let $T$ be a subset of $E$. The closure $\overline{T}$ of $T$ is defined as
$\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\ T\subseteq
F\end{subarray}}F$. Now, Corollary 5.14 shows that any intersection of
finitely many flats of $M$ is a flat of $M$. Hence,
$\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\ T\subseteq
F\end{subarray}}F$ (being an intersection of finitely many flats of $M$
242424“Finitely many” since the set $\operatorname*{Flats}M$ is finite.) is a
flat of $M$. In other words, $\overline{T}$ is a flat of $M$ (since
$\overline{T}=\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\
T\subseteq F\end{subarray}}F$).

Also, $T\subseteq F$ for every $F\in\operatorname*{Flats}M$ satisfying
$T\subseteq F$. Hence,
$T\subseteq\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\
T\subseteq F\end{subarray}}F=\overline{T}$. This completes the proof of
Proposition 5.17 (a).

(c) Let $T$ be a subset of $E$, and let $G$ be a flat of $M$ satisfying
$T\subseteq G$. Then, $G$ is an element of $\operatorname*{Flats}G$ satisfying
$T\subseteq G$. Hence, $G$ is one term in the intersection
$\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\ T\subseteq
F\end{subarray}}F$. Thus,
$\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\ T\subseteq
F\end{subarray}}F\subseteq G$. But the definition of $\overline{T}$ yields
$\overline{T}=\bigcap\limits_{\begin{subarray}{c}F\in\operatorname*{Flats}M;\\\
T\subseteq F\end{subarray}}F\subseteq G$. This proves Proposition 5.17 (c).

(b) Let $G$ be a flat of $M$. Proposition 5.17 (b) (applied to $T=G$) yields
$\overline{G}\subseteq G$. But Proposition 5.17 (a) (applied to $T=G$) shows
that $\overline{G}$ is a flat of $M$ satisfying $G\subseteq\overline{G}$.
Combining $G\subseteq\overline{G}$ with $\overline{G}\subseteq G$, we obtain
$\overline{G}=G$. This proves Proposition 5.17 (b).

(d) Let $S$ and $T$ be two subsets of $E$ satisfying $S\subseteq T$.
Proposition 5.17 (a) shows that $\overline{T}$ is a flat of $M$ satisfying
$T\subseteq\overline{T}$. Now, $S\subseteq T\subseteq\overline{T}$. Hence,
Proposition 5.17 (b) (applied to $S$ and $\overline{T}$ instead of $T$ and
$G$) shows $\overline{S}\subseteq\overline{T}$. This proves Proposition 5.17
(d).

(e) Assume that the matroid $M$ is loopless. In other words, no loops (of $M$)
exist.

The definition of $r_{M}$ quickly yields $r_{M}\left(\varnothing\right)=0$. In
other words, the set $\varnothing$ has rank $0$. We shall now show that
$\varnothing$ is a $0$-flat of $M$.

Indeed, let $W$ be a subset of $E$ which has rank $0$ and satisfies
$\varnothing\subseteq W$. We shall show that $\varnothing=W$.

Assume the contrary. Thus, $\varnothing\neq W$. Hence, $W$ has an element $w$.
Consider this $w$. The element $w$ of $E$ is not a loop (since no loops
exist). In other words, we cannot have $\left\\{w\right\\}\notin\mathcal{I}$
(since $w$ is a loop if and only if $\left\\{w\right\\}\notin\mathcal{I}$ (by
the definition of a loop)). In other words, we must have
$\left\\{w\right\\}\in\mathcal{I}$. Clearly, $\left\\{w\right\\}\subseteq W$
(since $w\in W$). Thus, $\left\\{w\right\\}$ is a $Z\in\mathcal{I}$ satisfying
$Z\subseteq W$. Thus,
$\left|\left\\{w\right\\}\right|\in\left\\{\left|Z\right|\ \mid\
Z\in\mathcal{I}\text{ and }Z\subseteq W\right\\}$.

But $W$ has rank $0$. In other words,

$\displaystyle 0$
$\displaystyle=r_{M}\left(W\right)=\max\left\\{\left|Z\right|\ \mid\
Z\in\mathcal{I}\text{ and }Z\subseteq W\right\\}\ \ \ \ \ \ \ \ \ \
\left(\text{by the definition of }r_{M}\right)$
$\displaystyle\geq\left|\left\\{w\right\\}\right|\ \ \ \ \ \ \ \ \ \
\left(\text{since }\left|\left\\{w\right\\}\right|\in\left\\{\left|Z\right|\
\mid\ Z\in\mathcal{I}\text{ and }Z\subseteq W\right\\}\right)$
$\displaystyle=1,$

which is absurd. This contradiction shows that our assumption was wrong.
Hence, $\varnothing=W$ is proven.

Let us now forget that we fixed $W$. We thus have proven that if $W$ is any
subset of $E$ which has rank $0$ and satisfies $\varnothing\subseteq W$, then
$\varnothing=W$. Thus, $\varnothing$ is a subset of $E$ which has rank $0$ and
is maximal among all such subsets (because we already know that $\varnothing$
has rank $0$). In other words, $\varnothing$ is a $0$-flat of $M$ (by the
definition of a “$0$-flat”). Thus, $\varnothing$ is a flat of $M$. Thus,
Proposition 5.17 (b) (applied to $G=\varnothing$) yields
$\overline{\varnothing}=\varnothing$. This proves Proposition 5.17 (e).

(f) Let $T$ be a subset of $E$. We have $T\subseteq\overline{T}$ (by
Proposition 5.17 (a)), and thus $r_{M}\left(T\right)\leq
r_{M}\left(\overline{T}\right)$ (since the function $r_{M}$ is weakly
increasing).

Let $k=r_{M}\left(T\right)$. Thus, there exists a
$Q\in\mathcal{P}\left(E\right)$ satisfying $T\subseteq Q$ and
$k=r_{M}\left(Q\right)$ (namely, $Q=T$). Hence, there exists a maximal such
$Q$. Denote this $Q$ by $R$. Thus, $R$ is a maximal
$Q\in\mathcal{P}\left(E\right)$ satisfying $T\subseteq Q$ and
$k=r_{M}\left(Q\right)$. In particular, $R$ is an element of
$\mathcal{P}\left(E\right)$ and satisfies $T\subseteq R$ and
$k=r_{M}\left(R\right)$.

Now, $R$ is a subset of $E$ (since $R\in\mathcal{P}\left(E\right)$) and has
rank $r_{M}\left(R\right)=k$. Thus, $R$ is a subset of $E$ which has rank $k$.
Furthermore, $R$ is maximal among all such subsets252525Proof. Let $W$ be any
subset of $E$ which has rank $k$ and satisfies $W\supseteq R$. We must prove
that $W=R$. We have $W\in\mathcal{P}\left(E\right)$, $T\subseteq R\subseteq W$
and $k=r_{M}\left(W\right)$ (since $W$ has rank $k$). Thus, $W$ is a
$Q\in\mathcal{P}\left(E\right)$ satisfying $T\subseteq Q$ and
$k=r_{M}\left(Q\right)$. But recall that $R$ is a maximal such $Q$. Hence, if
$W\supseteq R$, then $W=R$. Therefore, $W=R$ (since we know that $W\supseteq
R$). Qed.. Thus, $R$ is a $k$-flat of $M$ (by the definition of a “$k$-flat”),
and therefore a flat of $M$. Now, Proposition 5.17 (c) (applied to $G=R$)
shows that $\overline{T}\subseteq R$. Since the function $r_{M}$ is weakly
increasing, this yields $r_{M}\left(\overline{T}\right)\leq
r_{M}\left(R\right)=k$. Combining this with $k=r_{M}\left(T\right)\leq
r_{M}\left(\overline{T}\right)$, we obtain
$r_{M}\left(\overline{T}\right)=k=r_{M}\left(T\right)$. This proves
Proposition 5.17 (f).

(g) Let $T$ be a subset of $E$. Let $G$ be a flat of $M$. Proposition 5.17 (a)
shows that $T\subseteq\overline{T}$. Hence, if $\overline{T}\subseteq G$, then
$T\subseteq\overline{T}\subseteq G$. Thus, we have proven the implication
$\left(\overline{T}\subseteq G\right)\Longrightarrow\left(T\subseteq
G\right)$. The reverse implication (i.e., the implication $\left(T\subseteq
G\right)\Longrightarrow\left(\overline{T}\subseteq G\right)$) follows from
Proposition 5.17 (c). Combining these two implications, we obtain the
equivalence $\left(\overline{T}\subseteq
G\right)\Longleftrightarrow\left(T\subseteq G\right)$. This proves Proposition
5.17 (g).

We shall now recall a few more classical notions related to posets:

######  Definition 5.19.

Let $P$ be a poset.

(a) An element $p\in P$ is said to be a global minimum of $P$ if every $q\in
P$ satisfies $p\leq q$. Clearly, a global minimum of $P$ is unique if it
exists.

(b) An element $p\in P$ is said to be a global maximum of $P$ if every $q\in
P$ satisfies $p\geq q$. Clearly, a global maximum of $P$ is unique if it
exists.

(c) Let $x$ and $y$ be two elements of $P$. An upper bound of $x$ and $y$ (in
$P$) means an element $z\in P$ satisfying $z\geq x$ and $z\geq y$. A join (or
least upper bound) of $x$ and $y$ (in $P$) means an upper bound $z$ of $x$ and
$y$ such that every upper bound $z^{\prime}$ of $x$ and $y$ satisfies
$z^{\prime}\geq z$. In other words, a join of $x$ and $y$ is a global minimum
of the subposet $\left\\{w\in P\ \mid\ w\geq x\text{ and }w\geq y\right\\}$ of
$P$. Thus, a join of $x$ and $y$ is unique if it exists.

(d) Let $x$ and $y$ be two elements of $P$. A lower bound of $x$ and $y$ (in
$P$) means an element $z\in P$ satisfying $z\leq x$ and $z\leq y$. A meet (or
greatest lower bound) of $x$ and $y$ (in $P$) means a lower bound $z$ of $x$
and $y$ such that every lower bound $z^{\prime}$ of $x$ and $y$ satisfies
$z^{\prime}\leq z$. In other words, a meet of $x$ and $y$ is a global maximum
of the subposet $\left\\{w\in P\ \mid\ w\leq x\text{ and }w\leq y\right\\}$ of
$P$. Thus, a meet of $x$ and $y$ is unique if it exists.

(e) The poset $P$ is said to be a lattice if and only if it has a global
minimum and a global maximum, and every two elements of $P$ have a meet and a
join.

######  Proposition 5.20.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. The subposet
$\operatorname*{Flats}M$ of the poset $\mathcal{P}\left(E\right)$ is a
lattice.

######  Proof 5.21 (Proof of Proposition 5.20.).

By the definition of a lattice, it suffices to check the following four
claims:

Claim 1: The poset $\operatorname*{Flats}M$ has a global minimum.

Claim 2: The poset $\operatorname*{Flats}M$ has a global maximum.

Claim 3: Every two elements of $\operatorname*{Flats}M$ have a meet (in
$\operatorname*{Flats}M$).

Claim 4: Every two elements of $\operatorname*{Flats}M$ have a join (in
$\operatorname*{Flats}M$).

Proof of Claim 1: Applying Proposition 5.17 (a) to $T=\varnothing$, we see
that $\overline{\varnothing}$ is a flat of $M$ satisfying
$\varnothing\subseteq\overline{\varnothing}$. In particular,
$\overline{\varnothing}$ is a flat of $M$, so that
$\overline{\varnothing}\in\operatorname*{Flats}M$. If $G$ is a flat of $M$,
then $\overline{\varnothing}\subseteq G$ (by Proposition 5.17 (c), applied to
$T=\varnothing$). Hence, $\overline{\varnothing}$ is a global minimum of the
poset $\operatorname*{Flats}M$. Thus, the poset $\operatorname*{Flats}M$ has a
global minimum. This proves Claim 1.

Proof of Claim 2: Applying Proposition 5.17 (a) to $T=E$, we see that
$\overline{E}$ is a flat of $M$ satisfying $E\subseteq\overline{E}$. From
$E\subseteq\overline{E}$, we conclude that $\overline{E}=E$. Thus, $E$ is a
flat of $M$ (since $\overline{E}$ is a flat of $M$). In other words,
$E\in\operatorname*{Flats}M$. If $G$ is a flat of $M$, then $E\supseteq G$
(obviously). Hence, $E$ is a global maximum of the poset
$\operatorname*{Flats}M$. Thus, the poset $\operatorname*{Flats}M$ has a
global maximum. This proves Claim 2.

Proof of Claim 3: Let $F$ and $G$ be two elements of $\operatorname*{Flats}M$.
We have to prove that $F$ and $G$ have a meet.

We know that $F$ and $G$ are elements of $\operatorname*{Flats}M$, thus flats
of $M$. Hence, Corollary 5.14 shows that $F\cap G$ is a flat of $M$. In other
words, $F\cap G\in\operatorname*{Flats}M$. Clearly, $F\cap G\subseteq F$ and
$F\cap G\subseteq G$; thus, $F\cap G$ is a lower bound of $F$ and $G$ in
$\operatorname*{Flats}M$. Also, every lower bound $H$ of $F$ and $G$ in
$\operatorname*{Flats}M$ satisfies $H\subseteq F\cap G$ 262626Proof. Let $H$
be a lower bound of $F$ and $G$ in $\operatorname*{Flats}M$. Thus, $H\subseteq
F$ and $H\subseteq G$. Combining these two inclusions, we obtain $H\subseteq
F\cap G$, qed.. Hence, $F\cap G$ is a meet of $F$ and $G$. Thus, $F$ and $G$
have a meet. This proves Claim 3.

Proof of Claim 4: Let $F$ and $G$ be two elements of $\operatorname*{Flats}M$.
We have to prove that $F$ and $G$ have a join.

We know that $F$ and $G$ are elements of $\operatorname*{Flats}M$, thus flats
of $M$. Proposition 5.17 (a) (applied to $T=F\cup G$) shows that
$\overline{F\cup G}$ is a flat of $M$ satisfying $F\cup
G\subseteq\overline{F\cup G}$. Now, $\overline{F\cup
G}\in\operatorname*{Flats}M$ (since $\overline{F\cup G}$ is a flat of $M$).
Clearly, $F\subseteq F\cup G\subseteq\overline{F\cup G}$ and $G\subseteq F\cup
G\subseteq\overline{F\cup G}$; thus, $\overline{F\cup G}$ is an upper bound of
$F$ and $G$ in $\operatorname*{Flats}M$. Also, every upper bound $H$ of $F$
and $G$ in $\operatorname*{Flats}M$ satisfies $H\supseteq\overline{F\cup G}$
272727Proof. Let $H$ be an upper bound of $F$ and $G$ in
$\operatorname*{Flats}M$. Thus, $H\supseteq F$ and $H\supseteq G$. Combining
these two inclusions, we obtain $H\supseteq F\cup G$. But
$H\in\operatorname*{Flats}M$; thus, $H$ is a flat of $M$. Since $H$ satisfies
$F\cup G\subseteq H$, we therefore obtain $\overline{F\cup G}\subseteq H$ (by
Proposition 5.17 (c), applied to $F\cup G$ and $H$ instead of $T$ and $G$). In
other words, $H\supseteq\overline{F\cup G}$, qed.. Hence, $\overline{F\cup G}$
is a join of $F$ and $G$. Thus, $F$ and $G$ have a join. This proves Claim 4.

We have now proven all four Claims 1, 2, 3, and 4. Thus, Proposition 5.20 is
proven.

######  Definition 5.22.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Proposition 5.20 shows that
the subposet $\operatorname*{Flats}M$ of the poset $\mathcal{P}\left(E\right)$
is a lattice. This subposet $\operatorname*{Flats}M$ is called the lattice of
flats of $M$. (Beware: It is a subposet, but not a sublattice of
$\mathcal{P}\left(E\right)$, since its join is not a restriction of the join
of $\mathcal{P}\left(E\right)$.)

The lattice of flats $\operatorname*{Flats}M$ of a matroid $M$ is denoted by
$L\left(M\right)$ in [Stanley06, §3.2].

Next, we recall the definition of the Möbius function of a poset (see, e.g.,
[Stanley06, Definition 1.2] or [Martin15, §5.2]):

######  Definition 5.23.

Let $P$ be a poset.

(a) If $x$ and $y$ are two elements of $P$ satisfying $x\leq y$, then the set
$\left\\{z\in P\ \mid\ x\leq z\leq y\right\\}$ is denoted by
$\left[x,y\right]$.

(b) A subset of $P$ is called a closed interval of $P$ if it has the form
$\left[x,y\right]$ for two elements $x$ and $y$ of $P$ satisfying $x\leq y$.

(c) We denote by $\operatorname*{Int}P$ the set of all closed intervals of
$P$.

(d) If $f:\operatorname*{Int}P\rightarrow\mathbb{Z}$ is any map, then the
image $f\left(\left[x,y\right]\right)$ of a closed interval
$\left[x,y\right]\in\operatorname*{Int}P$ under $f$ will be abbreviated by
$f\left(x,y\right)$.

(e) Assume that every closed interval of $P$ is finite. The Möbius function of
the poset $P$ is defined to be the unique function
$\mu:\operatorname*{Int}P\rightarrow\mathbb{Z}$ having the following two
properties:

  * •

We have

$\mu\left(x,x\right)=1\ \ \ \ \ \ \ \ \ \ \text{for every }x\in P.$ (23)

  * •

We have

$\mu\left(x,y\right)=-\sum\limits_{\begin{subarray}{c}z\in P;\\\ x\leq
z<y\end{subarray}}\mu\left(x,z\right)\ \ \ \ \ \ \ \ \ \ \text{for all }x,y\in
P\text{ satisfying }x<y.$ (24)

(It is easy to see that these two properties indeed determine $\mu$ uniquely.)
This Möbius function is denoted by $\mu$.

We can now define the characteristic polynomial of a matroid $M$, following
[Stanley06, (22)]282828Our notation slightly differs from that in [Stanley06,
(22)]. Namely, we use $x$ as the indeterminate, while Stanley instead uses
$t$. Stanley also denotes the global minimum $\overline{\varnothing}$ of
$\operatorname*{Flats}M$ by $\widehat{0}$.:

######  Definition 5.24.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $m=r_{M}\left(E\right)$.
The characteristic polynomial $\chi_{M}$ of the matroid $M$ is defined to be
the polynomial

$\sum\limits_{F\in\operatorname*{Flats}M}\mu\left(\overline{\varnothing},F\right)x^{m-r_{M}\left(F\right)}\in\mathbb{Z}\left[x\right]$

(where $\mu$ is the Möbius function of the lattice $\operatorname*{Flats}M$).
We further define a polynomial
$\widetilde{\chi}_{M}\in\mathbb{Z}\left[x\right]$ by
$\widetilde{\chi}_{M}=\left[\overline{\varnothing}=\varnothing\right]\chi_{M}$.
Here, we are using the Iverson bracket notation (as in Definition 2.10). If
the matroid $M$ is loopless, then

$\widetilde{\chi}_{M}=\underbrace{\left[\overline{\varnothing}=\varnothing\right]}_{\begin{subarray}{c}=1\\\
\text{(by Proposition \ref{prop.matroid.closure.props}
{(e)})}\end{subarray}}\chi_{M}=\chi_{M}.$

######  Example 5.25.

Let $G=\left(V,E\right)$ be a finite graph. Consider the graphical matroid
$\left(E,\mathcal{I}\right)$ defined as in Example 5.5. Then, the
characteristic polynomial $\chi_{\left(E,\mathcal{I}\right)}$ of this matroid
is connected to the chromatic polynomial $\chi_{G}$ of the graph $G$ as
follows:

$x^{\operatorname*{conn}G}\cdot\chi_{\left(E,\mathcal{I}\right)}\left(x\right)=\chi_{G}\left(x\right).$

###  5.3 Generalized formulas

Let us next define broken circuits of a matroid
$M=\left(E,\mathcal{I}\right)$. Stanley, in [Stanley06, §4.1], defines them in
terms of a total ordering $\mathcal{O}$ on the set $E$, whereas we shall use a
“labeling function” $\ell:E\rightarrow X$ instead (as in the case of graphs);
our setting is slightly more general than Stanley’s.

######  Definition 5.26.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $X$ be a totally ordered
set. Let $\ell:E\rightarrow X$ be a function. We shall refer to $\ell$ as the
labeling function. For every $e\in E$, we shall refer to $\ell\left(e\right)$
as the label of $e$.

A broken circuit of $M$ means a subset of $E$ having the form
$C\setminus\left\\{e\right\\}$, where $C$ is a circuit of $M$, and where $e$
is the unique element of $C$ having maximum label (among the elements of $C$).
Of course, the notion of a broken circuit of $M$ depends on the function
$\ell$; however, we suppress the mention of $\ell$ in our notation, since we
will not consider situations where two different $\ell$’s coexist.

We shall now state analogues (and, in light of Example 5.25, generalizations,
although we shall not elaborate on the few minor technicalities of seeing them
as such) of Theorem 3.5, Theorem 3.4, Corollary 3.6, Corollary 3.7 and
Corollary 3.19:

######  Theorem 5.27.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $m=r_{M}\left(E\right)$.
Let $X$ be a totally ordered set. Let $\ell:E\rightarrow X$ be a function. Let
$\mathfrak{K}$ be some set of broken circuits of $M$ (not necessarily
containing all of them). Let $a_{K}$ be an element of $\mathbf{k}$ for every
$K\in\mathfrak{K}$. Then,

$\widetilde{\chi}_{M}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}\left(\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq F\end{subarray}}a_{K}\right)x^{m-r_{M}\left(F\right)}.$

######  Theorem 5.28.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $m=r_{M}\left(E\right)$.
Then,

$\widetilde{\chi}_{M}=\sum\limits_{F\subseteq
E}\left(-1\right)^{\left|F\right|}x^{m-r_{M}\left(F\right)}.$

######  Corollary 5.29.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $m=r_{M}\left(E\right)$.
Let $X$ be a totally ordered set. Let $\ell:E\rightarrow X$ be a function. Let
$\mathfrak{K}$ be some set of broken circuits of $M$ (not necessarily
containing all of them). Then,

$\widetilde{\chi}_{M}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{
is
}\mathfrak{K}\text{-free}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{m-r_{M}\left(F\right)}.$

######  Corollary 5.30.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $m=r_{M}\left(E\right)$.
Let $X$ be a totally ordered set. Let $\ell:E\rightarrow X$ be a function.
Then,

$\widetilde{\chi}_{M}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{
contains no broken}\\\ \text{circuit of }M\text{ as a
subset}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{m-r_{M}\left(F\right)}.$

######  Corollary 5.31.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $m=r_{M}\left(E\right)$.
Let $X$ be a totally ordered set. Let $\ell:E\rightarrow X$ be an injective
function. Then,

$\widetilde{\chi}_{M}=\sum\limits_{\begin{subarray}{c}F\subseteq E;\\\ F\text{
contains no broken}\\\ \text{circuit of }M\text{ as a
subset}\end{subarray}}\left(-1\right)^{\left|F\right|}x^{m-\left|F\right|}.$

We notice that Corollary 5.31 is equivalent to [Stanley06, Theorem 4.12] (at
least when $M$ is loopless).

Before we prove these results, let us state a lemma which will serve as an
analogue of Lemma 2.11:

######  Lemma 5.32.

Let $M=\left(E,\mathcal{I}\right)$ be a matroid. Let $X$ be a totally ordered
set. Let $\ell:E\rightarrow X$ be a function. Let $\mathfrak{K}$ be some set
of broken circuits of $M$ (not necessarily containing all of them). Let
$a_{K}$ be an element of $\mathbf{k}$ for every $K\in\mathfrak{K}$.

Let $F$ be any flat of $M$. Then,

$\sum\limits_{B\subseteq
F}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}=\left[F=\varnothing\right].$ (25)

(Again, we are using the Iverson bracket notation as in Definition 2.10.)

######  Proof 5.33 (Proof of Lemma 5.32.).

Our proof will imitate the proof of Lemma 2.11 much of the time (with
$E\cap\operatorname*{Eqs}f$ replaced by $F$); thus, we will allow ourselves
some more brevity.

We WLOG assume that $F\neq\varnothing$ (since otherwise, the claim is
obvious292929Proof. Assume that $F=\varnothing$. We must show that the claim
is obvious. Let us first show that no $K\in\mathfrak{K}$ satisfies
$K=\varnothing$. Indeed, assume the contrary. Thus, there exists a
$K\in\mathfrak{K}$ satisfying $K=\varnothing$. In other words,
$\varnothing\in\mathfrak{K}$. Thus, $\varnothing$ is a broken circuit of $M$
(since $\mathfrak{K}$ is a set of broken circuits of $M$). Therefore,
$\varnothing$ is obtained from a circuit of $M$ by removing one element (by
the definition of a broken circuit). This latter circuit must therefore be a
one-element set, i.e., it has the form $\left\\{e\right\\}$ for some $e\in E$.
Consider this $e$. Thus, $\left\\{e\right\\}$ is a circuit of $M$. But $F$ is
a flat of $M$. In other words, Statement $\mathfrak{F}_{1}$ (of Lemma 5.12)
holds for $T=F$. Hence, Statement $\mathfrak{F}_{2}$ (of Lemma 5.12) also
holds for $T=F$ (since Lemma 5.12 shows that these two statements are
equivalent). Applying Statement $\mathfrak{F}_{2}$ to $T=F$ and
$C=\left\\{e\right\\}$, we thus obtain $\left\\{e\right\\}\subseteq F$
(because $\left\\{e\right\\}\setminus\left\\{e\right\\}=\varnothing\subseteq
F$). Thus, $e\in\left\\{e\right\\}\subseteq F=\varnothing$, which is absurd.
This contradiction proves that our assumption was wrong. Hence, we have shown
that no $K\in\mathfrak{K}$ satisfies $K=\varnothing$. But from
$F=\varnothing$, we see that the sum $\sum\limits_{B\subseteq
F}\left(-1\right)^{\left|B\right|}\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq B\end{subarray}}a_{K}$ has only one addend (namely, the addend for
$B=\varnothing$), and thus simplifies to
$\displaystyle\underbrace{\left(-1\right)^{\left|\varnothing\right|}}_{=\left(-1\right)^{0}=1}\underbrace{\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K\subseteq\varnothing\end{subarray}}}_{=\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K=\varnothing\end{subarray}}}a_{K}$
$\displaystyle=\prod\limits_{\begin{subarray}{c}K\in\mathfrak{K};\\\
K=\varnothing\end{subarray}}a_{K}=\left(\text{empty product}\right)\ \ \ \ \ \
\ \ \ \ \left(\text{since no }K\in\mathfrak{K}\text{ satisfies
}K=\varnothing\right)$ $\displaystyle=1=\left[F=\varnothing\right]\ \ \ \ \ \
\ \ \ \ \left(\text{since }F=\varnothing\right).$ Thus, Lemma 5.32 is
proven.). Thus, $\left[F=\varnothing\right]=0$.

Pick any $d\in F$ with maximum $\ell\left(d\right)$ (among all $d\in F$).
(This is clearly possible, since $F\neq\varnothing$.) Define two subsets
$\mathcal{U}$ and $\mathcal{V}$ of $\mathcal{P}\left(F\right)$ as follows:

$\displaystyle\mathcal{U}$
$\displaystyle=\left\\{T\in\mathcal{P}\left(F\right)\ \mid\ d\notin
T\right\\};$ $\displaystyle\mathcal{V}$
$\displaystyle=\left\\{T\in\mathcal{P}\left(F\right)\ \mid\ d\in T\right\\}.$

Thus, we have $\mathcal{P}\left(F\right)=\mathcal{U}\cup\mathcal{V}$, and the
sets $\mathcal{U}$ and $\mathcal{V}$ are disjoint. Now, we define a map
$\Phi:\mathcal{U}\rightarrow\mathcal{V}$ by

$\left(\Phi\left(B\right)=B\cup\left\\{d\right\\}\ \ \ \ \ \ \ \ \ \ \text{for
every }B\in\mathcal{U}\right).$

This map $\Phi$ is well-defined (because for every $B\in\mathcal{U}$, we have
$B\cup\left\\{d\right\\}\in\mathcal{V}$ 303030This follows from the fact that
$d\in F$.) and a bijection313131Its inverse is the map
$\Psi:\mathcal{V}\rightarrow\mathcal{U}$ defined by
$\left(\Psi\left(B\right)=B\setminus\left\\{d\right\\}\ \ \ \ \ \ \ \ \ \
\text{for every }B\in\mathcal{V}\right)$.. Moreover, every $B\in\mathcal{U}$
satisfies

$\left(-1\right)^{\left|\Phi\left(B\right)\right|}=-\left(-1\right)^{\left|B\right|}$
(26) 323232Proof. This is proven exactly like we proved (9).

.

Now, we claim that, for every $B\in\mathcal{U}$ and every $K\in\mathfrak{K}$,
we have the following logical equivalence:

$\left(K\subseteq B\right)\ \Longleftrightarrow\
\left(K\subseteq\Phi\left(B\right)\right).$ (27)

Proof of (27): Let $B\in\mathcal{U}$ and $K\in\mathfrak{K}$. We must prove the
equivalence (27). The definition of $\Phi$ yields
$\Phi\left(B\right)=B\cup\left\\{d\right\\}\supseteq B$, so that
$B\subseteq\Phi\left(B\right)$. Hence, if $K\subseteq B$, then $K\subseteq
B\subseteq\Phi\left(B\right)$. Therefore, the forward implication of the
equivalence (27) is proven. It thus remains to prove the backward implication
of this equivalence. In other words, it remains to prove that if
$K\subseteq\Phi\left(B\right)$, then $K\subseteq B$. So let us assume that
$K\subseteq\Phi\left(B\right)$.

We want to prove that $K\subseteq B$. Assume the contrary. Thus,
$K\not\subseteq B$. We have $K\in\mathfrak{K}$. Thus, $K$ is a broken circuit
of $M$ (since $\mathfrak{K}$ is a set of broken circuits of $M$). In other
words, $K$ is a subset of $E$ having the form $C\setminus\left\\{e\right\\}$,
where $C$ is a circuit of $M$, and where $e$ is the unique element of $C$
having maximum label (among the elements of $C$) (because this is how a broken
circuit is defined). Consider these $C$ and $e$. Thus,
$K=C\setminus\left\\{e\right\\}$.

The element $e$ is the unique element of $C$ having maximum label (among the
elements of $C$). Thus, if $e^{\prime}$ is any element of $C$ satisfying
$\ell\left(e^{\prime}\right)\geq\ell\left(e\right)$, then

$e^{\prime}=e.$ (28)

But
$\underbrace{K}_{\subseteq\Phi\left(B\right)=B\cup\left\\{d\right\\}}\setminus\left\\{d\right\\}\subseteq\left(B\cup\left\\{d\right\\}\right)\setminus\left\\{d\right\\}\subseteq
B$.

If we had $d\notin K$, then we would have $K\setminus\left\\{d\right\\}=K$ and