# Socle pairings on tautological rings

Felix Janda and Aaron Pixton

###### Abstract.

We study some aspects of the $\lambda_{g}$ pairing on the tautological ring of
$M_{g}^{c}$, the moduli space of genus $g$ stable curves of compact type. We
consider pairing $\kappa$ classes with pure boundary strata, all tautological
classes supported on the boundary, or the full tautological ring. We prove
that the rank of this restricted pairing is equal in the first two cases and
has an explicit formula in terms of partitions, while in the last case the
rank increases by precisely the rank of the $\lambda_{g}\lambda_{g-1}$ pairing
on the tautological ring of $M_{g}$.

##  1\. Introduction

Let $M_{g,n}$ be the moduli space of smooth curves of genus $g$ with $n$
marked points and let $\overline{M}_{g,n}$ be the Deligne-Mumford
compactification, the moduli space of stable $n$-pointed nodal curves of
arithmetic genus $g$. Inside this, let $M_{g,n}^{c}$ be the subspace of stable
pointed curves of compact type, i.e. curves whose dual graph is a tree.

The intersection theory of these moduli spaces of curves is a subject of
fundamental importance in algebraic geometry. When studying the Chow ring
$A^{*}(\overline{M}_{g,n})$, one is naturally led to consider a subring
consisting of the classes such as the Arborella-Cornalba $kappa$ classes that
are defined via certain tautological maps between the $\overline{M}_{g,n}$.
This subring is the tautological ring $R^{*}(\overline{M}_{g.n})$.
Tautological rings $R^{*}(M_{g,n})$ and $R^{*}(M_{g,n}^{c})$ for $M_{g,n}$ and
$M^{c}_{g,n}$ can be defined by restriction. We will primarily be interested
in $R^{*}(M_{g}^{c})$, the case of compact type with no marked points.

Inside $R^{*}(M_{g,n}^{c})$ there is the subring $\kappa^{*}(M_{g,n}^{c})$
generated by the $\kappa$ classes $\kappa_{1},\kappa_{2},\ldots$. The kappa
ring $\kappa^{*}(M_{g,n}^{c})$ has been studied in detail by Pandharipande
[6]. In particular, for $n>1$ a complete description of the kappa ring is
given.

When restricted to the moduli space of smooth curves $M_{g}$, the tautological
ring $R^{*}(M_{g})$ is actually equal to the kappa ring $\kappa^{*}(M_{g})$.
This means that on $M_{g}^{c}$, any tautological class can be written as the
sum of a polynomial in the $\kappa$ classes and a class supported on the
boundary. We denote by $BR^{*}(M_{g}^{c})$ the ideal of tautological classes
supported on the boundary, so the tautological ring $R^{*}(M_{g}^{c})$ is
linearly spanned by $\kappa^{*}(M_{g}^{c})$ and $BR^{*}(M_{g}^{c})$.

A general element of $BR^{*}(M_{g}^{c})$ is a linear combination of classes
obtained by taking the pushforward of tautological classes via gluing maps

$M_{g_{1},n_{1}}^{c}\times M_{g_{2},n_{2}}^{c}\times\cdots\times
M_{g_{k},n_{k}}^{c}\to M_{g}^{c}.$

When the class $1$ is pushed forward along such a map, this construction gives
pure boundary strata. We let $PBR^{*}(M_{g}^{c})$ denote the linear subspace
of $BR^{*}(M_{g}^{c})$ generated by the pure boundary strata.

There are natural bilinear pairings

$\displaystyle R^{r}(M_{g}^{c})\times R^{2g-3-r}(M_{g}^{c})\to
R^{2g-3}(M_{g}^{c})\cong\mathbb{Q},$ $\displaystyle R^{r}(M_{g})\times
R^{g-2-r}(M_{g})\to R^{g-2}(M_{g})\cong\mathbb{Q},$

given by the product in the Chow ring and the socle evaluations. These
pairings are called the $\lambda_{g}$ and $\lambda_{g}\lambda_{g-1}$ pairings
respectively because they may be defined by integrating against these classes
in $\overline{M}_{g}$.

In this paper we will study the restriction

$\kappa^{d}(M_{g}^{c})\times R^{r}(M_{g}^{c})\to\mathbb{Q}$

of the $\lambda_{g}$-pairing for $r+d=2g-3$, for any $g\geq 2$. The following
theorems, our main results, were previously conjectured by Pandharipande.

######  Housing Theorem.

The rank of the $\lambda_{g}$-pairing of $\kappa$ classes against boundary
classes

$\kappa^{d}(M_{g}^{c})\times BR^{r}(M_{g}^{c})\to\mathbb{Q}$

equals the rank of the $\lambda_{g}$-pairing of $\kappa$ classes against pure
boundary strata

$\kappa^{d}(M_{g}^{c})\times PBR^{r}(M_{g}^{c})\to\mathbb{Q}.$

Furthermore, these ranks are equal to the number of partitions of $d$ of
length less than $r+1$ plus the number of partitions of $d$ of length $r+1$
which contain at least two even parts.

######  Rank Theorem.

The rank of the $\lambda_{g}$-pairing of $\kappa$ classes against general
tautological classes

$\kappa^{d}(M_{g}^{c})\times R^{r}(M_{g}^{c})\to\mathbb{Q}$

equals the sum of the rank of the $\lambda_{g}$-pairing of $\kappa$ classes
against boundary classes

$\kappa^{d}(M_{g}^{c})\times BR^{r}(M_{g}^{c})\to\mathbb{Q}$

and the rank of the $\lambda_{g}\lambda_{g-1}$ pairing

$\kappa^{r}(M_{g})\times\kappa^{g-2-r}(M_{g})\to\mathbb{Q}.$

These theorems will be proven by direct combinatorial analysis of the well
known formulae for calculating the integrals arising in the pairings. In
particular, we have no geometric explanation of the Rank Theorem, which
connects the compact type case and the smooth case.

###  1.1. Consequences

It has been conjectured by Faber [1] that $\kappa^{*}(M_{g})=R^{*}(M_{g})$ is
a Gorenstein ring with socle in degree $g-2$. He verified this for $g\leq 23$
by computing many relations between the $\kappa$ classes and checking that
they produced a Gorenstein ring. However, starting in genus $24$, the known
methods of producing relations have failed to give enough relations to yield a
Gorenstein ring. In fact, the known relations have all been in the span of the
Faber-Zagier (FZ) relations, and these relations produce a Gorenstein ring if
and only if $g\leq 23$.

There are therefore _mystery relations_ in $R^{*}(M_{g})$: formal polynomials
in $\kappa$ classes which pair to zero with any $\kappa$ polynomial in
$R^{*}(M_{g})$ of complementary degree but are not a linear combination of FZ
relations. If one assumes Faber’s Gorenstein conjecture then these relations
must hold in $R(M_{g})$. Since FZ relations extend to tautological relations
in $R^{*}(\overline{M}_{g})$ (this is a consequence of the proof of the FZ
relations in [7]), a possible reason for the existence of mystery relations
might be if they do not extend tautologically to $R^{*}(M_{g}^{c})$ or
$R^{*}(\overline{M}_{g})$. The Rank Theorem can be interpreted as saying that
part of the obstruction to this extension is zero: the mystery relations at
least extend to classes in the tautological ring of $M_{g}^{c}$ which pair to
zero with the $\kappa$ subring. It is an interesting question whether the
mystery relations extend to classes in the tautological ring of $M_{g}^{c}$
which are relations in the Gorenstein quotient (i.e. pair to zero with the
entire tautological ring).

In [6] Pandharipande gives a minimal set of generators of
$\kappa^{*}(M_{g,n}^{c})$ and relates higher genus relations to genus 0
relations. More precisely, he shows that there is a surjective (graded) ring
homomorphism

$\kappa^{*}(M_{0,2g+n}^{c})\stackrel{{\scriptstyle\iota_{g,n}}}{{\to}}\kappa^{*}(M_{g,n}^{c}),$

which is an isomorphism for $n\geq 1$, or in degrees up to $g-2$ when $n=0$.
The Rank Theorem gives us information about the $n=0$ case in higher degrees.

######  Theorem 1.

Let $g\geq 2$, $0\leq e\leq g-2$, and $d=g-1+e$. Let $\delta_{d}$ be the rank
of the kernel of the map from $\kappa^{d}(M_{g}^{c})$ to the Gorenstein
quotient of $R^{*}(M_{g}^{c})$. Let $\gamma_{e}$ be the rank of the space of
$\kappa$ relations of degree $e$ in the Gorenstein quotient of $R^{*}(M_{g})$.
Then the degree $d$ part of the kernel of $\iota_{g,0}$ has rank
$\gamma_{e}-\delta_{d}$.

###### Proof.

By [6], the rank of $\kappa^{d}(M_{0,2g}^{c})$ is equal to $|P(d,2g-2-d)|$,
the number of partitions of $d$ of length at most $2g-2-d$. On the other side,
the rank of $\kappa^{r}(M_{g}^{c})$ is equal to $\delta_{r}$ plus the rank of
the first pairing appearing in the Rank Theorem. The rank of the second
pairing appearing in the Rank Theorem is given by the Housing Theorem, and the
rank of the third pairing appearing in the Rank Theorem is equal to
$|P(e)|-\gamma_{e}$. Putting these pieces together gives the theorem
statement. ∎

Remark. The components $\gamma_{e}$ and $\delta_{d}$ appearing in the above
theorem both have conjectural values. The FZ relations give a prediction for
$\gamma_{e}$ (if they are the only relations in the first half of the
Gorenstein quotient and are linearly independent):

$\gamma_{e}=\begin{cases}a(3e-g-1)&\text{ if }e\leq\frac{g-2}{2}\\\
a(3(g-2-e)-g-1)&\text{ else},\end{cases}$

where $a(n)$ is the number of partitions of $n$ with no parts of sizes
$5,8,11,\ldots$.

The Gorenstein conjecture in compact type would imply that $\delta_{d}=0$,
though in fact this is a much weaker statement. Combining these predictions
gives a conjecture for all the Betti numbers of $\kappa^{*}(M_{g}^{c})$.

###  1.2. Plan of the paper

In Section 2 we review basic facts about the tautological ring. In Section 3
we prove the Housing Theorem. In Section 4 we state and prove a slightly more
explicit version of the Rank Theorem (see Theorem 2).

### Acknowledgments

The first named author wants to thank his advisor Rahul Pandharipande for the
introduction to this topic and various discussions. The beginning of Section
1.1 elaborates an email from him.

The first named author was supported by the Swiss National Science Foundation
grant SNF 200021_143274. The second named author was supported by an NDSEG
graduate fellowship.

##  2\. The tautological ring

###  2.1. Tautological Classes

The subrings $R^{*}(\overline{M}_{g.n})$ of tautological classes in the Chow
rings $A^{*}(\overline{M}_{g,n})$ are collectively defined as the smallest
subrings which are closed under pushforward by the maps forgetting markings
$\overline{M}_{g,n}\to\overline{M}_{g,n-1}$ and the gluing maps

$\overline{M}_{g_{1},n_{1}\sqcup\\{\star\\}}\times\overline{M}_{g_{2},n_{2}\sqcup\\{\bullet\\}}\to\overline{M}_{g_{1}+g_{2},n_{1}+n_{2}}$
and $\overline{M}_{g,n\sqcup\\{\star,\bullet\\}}\to\overline{M}_{g+1,n}$

defined by gluing together $\star$ and $\bullet$. It turns out that nearly all
classes on the moduli space of curves that appear naturally in geometry lie in
the tautological ring.

For each $i=1,2,\ldots,n$, there is a line bundle $\mathbb{L}_{i}$ on
$\overline{M}_{g,n}$ given by the cotangent space at the $i$th marked point.
The first Chern classes of these line bundles are denoted by
$\psi_{i}=c_{1}(\mathbb{L}_{i})\in A^{1}(\overline{M}_{g,n})$. The $\kappa$
classes are then pushforwards of powers of the $\psi$ classes:

$\kappa_{m}=\pi_{*}(\psi_{n+1}^{m+1})\in A^{m}(\overline{M}_{g,n}),$

where $\pi$ is the forgetful map $\overline{M}_{g,n+1}\to\overline{M}_{g,n}$.

It is well known (see e.g. [5]) that the $\kappa$ and $\psi$ classes combined
with pushforward by the gluing morphisms alone are sufficient to generate the
tautological rings. In other words, $R^{*}(\overline{M}_{g,n})$ is additively
generated by classes of the form

$\xi_{\Gamma}\left(\prod_{v\text{ vertex of }\Gamma}\theta_{v}\right),$

where $\Gamma$ is a stable graph expressing the data of the gluing map

$\xi_{\Gamma}:\prod_{v\text{ vertex of
}\Gamma}\overline{M}_{g(v),n(v)}\to\overline{M}_{g,n}$

and the $\theta_{v}\in R^{*}(\overline{M}_{g(v),n(v)})$ are arbitrary
monomials in the $\psi$ and $\kappa$ classes.

The tautological rings $R^{*}(M_{g,n}^{c})$ and $R^{*}(M_{g,n})$ are defined
as the image of $R^{*}(\overline{M}_{g,n})$ under restriction. In the case of
$R^{*}(M_{g,n}^{c})$, this means that the stable graph $\Gamma$ must be a
tree, while $R^{*}(M_{g,n})$ is simply the subring of polynomials in the
$\kappa$ and $\psi$ classes.

The ring $R^{*}(M_{g,n}^{c})$ has one-dimensional socle, in degree $2g-3+n$:

$R^{2g-3+n}(M_{g,n}^{c})\cong\mathbb{Q}.$

This gives a canonical (up to scaling) bilinear pairing on
$R^{*}(M_{g,n}^{c})$, which can be realized explicitly by integrating against
the Hodge class $\lambda_{g}$:

$R^{*}(M_{g,n}^{c})\times
R^{*}(M_{g,n}^{c})\to\mathbb{Q},\quad(\alpha,\beta)\mapsto\int_{\overline{M}_{g,n}}\alpha\beta\lambda_{g}.$

Here the integral is defined by taking any extensions of $\alpha$ and $\beta$
to $R^{*}(\overline{M}_{g,n})$. It is independent of which particular
extension one has chosen because $\lambda_{g}$ vanishes on the complement of
$M_{g,n}^{c}$.

The $\lambda_{g}\lambda_{g-1}$ pairing is a similar pairing for the moduli
space of smooth curves, given by

$R^{*}(M_{g})\times
R^{*}(M_{g})\to\mathbb{Q},\quad(\alpha,\beta)\mapsto\int_{\overline{M}_{g}}\alpha\beta\lambda_{g}\lambda_{g-1}.$

Notice that the $\lambda_{g}$ pairing on $R^{*}(M_{g}^{c})$ vanishes above
degree $2g-3$ whereas the $\lambda_{g}\lambda_{g-1}$ pairing on $R^{*}(M_{g})$
already vanishes above degree $g-2$.

###  2.2. Notation concerning partitions

In the following sections we will use the following notation heavily. A
_partition_ $\sigma$ is an unordered collection of natural numbers (a
multiset). We call its elements _parts_. Its _size_ is the sum of all its
parts. The _length_ $\ell(\sigma)$ of a partition $\sigma$ is the number of
parts in it. For natural numbers $n$, $r$ we denote by $P(n)$ the set of
partitions of size $n$ and by $P(n,r)$ the set of partitions of size $n$ and
length at most $r$. Furthermore, let $I(\sigma)$ be a set of $\ell(\sigma)$
elements which we will use to index the parts of $\sigma$. For example we
could take

$I(\sigma)=[\ell(\sigma)]:=\\{1,\dots,\ell(\sigma)\\}.$

For two partitions $\sigma,\tau\in P(n)$ and a map $\varphi:I(\sigma)\to
I(\tau)$ we say that $\varphi$ is a _refining function_ of $\tau$ into
$\sigma$ if for any $i\in I(\tau)$ we have

$\tau_{i}=\sum_{j\in\varphi^{-1}(i)}\sigma_{j}.$

If for given $\sigma,\tau$ there exists a refining function $\varphi$ of
$\tau$ into $\sigma$ we say that $\sigma$ is a refinement of $\tau$.

For a finite set $S$, a _set partition_ $P$ of $S$ (written $P\vdash S$) is a
set $P=\\{S_{1},\dots,S_{m}\\}$ of nonempty subsets of $S$ such that $S$ is
the disjoint union of the $S_{i}$.

For a partition $\sigma$ and a set $S$ of subsets of $I(\sigma)$ we define a
new partition $\sigma^{S}$ indexed by the elements of $S$ by setting
$(\sigma^{S})_{s}=\sum_{i\in s}\sigma_{i}$ for each $s\in S$. Usually we will
take a set partition $P$ of $I(\sigma)$ for $S$. For a subset $T\subseteq
I(\sigma)$ we define the _restriction $\sigma|_{T}$ of $\sigma$ to $T$_ by
$\sigma^{S}$, where $S$ is the set of all 1-element subsets of $T$; in other
words, $\sigma|_{T}=(\sigma_{t})_{t\in T}$.

###  2.3. Integral calculations

The basic formula for the evaluation of the integrals arising in the
$\lambda_{g}$ pairing is (see [3])

$\int_{\overline{M}_{g,n}}\prod_{i=1}^{n}\psi_{i}^{\tau_{i}}\lambda_{g}=\binom{2g-3+n}{\tau}\int_{\overline{M}_{g,1}}\psi_{1}^{2g-2}\lambda_{g},$

where $\tau_{1},\dotsc,\tau_{n}$ are nonnegative integer numbers with sum
$2g-3+n$. The formula is symmetric with respect to the sorting of the markings
and hence we only need to know the partition corresponding to $\tau$ in order
to calculate these integrals. The only thing we will need to know about the
integral on the right hand side is that it is nonzero (see [2]) since we are
only interested in the ranks of the pairing.

We will need to evaluate integrals involving $\psi$ classes as part of the
proof of the housing theorem. However our main interest lies in the
calculation of integrals involving $\kappa$ classes. Using the definition of
the $\kappa$ classes as push-forwards of powers of $\psi$ classes we can find
a nice expression for the quotients

$\vartheta(\sigma;\tau):=\left(\int_{\overline{M}_{g,\ell(\tau)}}\kappa_{\sigma}\psi^{\tau}\lambda_{g}\right)\left(\int_{\overline{M}_{g,1}}\psi_{1}^{2g-2}\lambda_{g}\right)^{-1}.$

In this equation we have used $\kappa_{\sigma}$ as an abbreviation for
$\prod_{i\in I(\sigma)}\kappa_{\sigma_{i}}$ and $\psi^{\tau}$ for $\prod_{i\in
I(\tau)}\psi_{i}^{\tau_{i}}$ indexing the $|\tau|$ marked points by the parts
of $\tau$. We will write

$\vartheta(\sigma):=\vartheta(\sigma;\emptyset)$

when we just have $\kappa$ classes and no $\psi$ classes.

######  Lemma 1.

For partitions $\sigma$ and $\tau$ such that $2g-3+\ell(\tau)=|\sigma|+|\tau|$
we have

$\vartheta(\sigma;\tau)=\sum_{P\vdash
I(\sigma)}(-1)^{|P|+\ell(\sigma)}\binom{2g-3+|P|+\ell(\tau)}{((\sigma^{P})_{i}+1)_{i\in
P},\tau}.$

###### Proof.

From the basic socle evaluation formula we see that it suffices to prove the
identity

$\kappa_{\sigma}\psi^{\tau}\lambda_{g}=\sum_{P\vdash
I(\sigma)}(-1)^{|P|+\ell(\sigma)}\pi_{*}\left(\psi^{((\sigma^{P})_{i}+1)_{i\in
P}}\psi^{\tau}\lambda_{g}\right).$

in the Chow ring $R(\overline{M}_{g,\ell(\tau)})$, where by abuse of notation
$\pi$ is the forgetful map
$\overline{M}_{g,\ell(\tau)+n}\to\overline{M}_{g,\ell(\tau)}$ for the
appropriate $n$. Since $\pi^{*}(\lambda_{g})=\lambda_{g}$, we can further
reduce to

$\kappa_{\sigma}\psi^{\tau}=\sum_{P\vdash
I(\sigma)}(-1)^{|P|+\ell(\sigma)}\pi_{*}\left(\psi^{((\sigma^{P})_{i}+1)_{i\in
P}}\psi^{\tau}\right).$

This follows from the pushforward formula

$\pi_{*}\left(\psi^{(\sigma_{i}+1)_{i\in P}}\psi^{\tau}\right)=\sum_{P\vdash
I(\sigma)}\left(\prod_{S\in P}(|S|-1)!\right)\kappa_{\sigma^{P}}\psi^{\tau}.$

and partition refinement inversion. ∎

To evaluate the more general integrals which arise when we pair $\kappa$
classes with arbitrary tautological classes, we can restrict ourselves to
pairing a $\kappa$ monomial with the additive set of generators described in
Section 2.1. In this case we have to sum over the set of possible
distributions of the $\kappa$ classes to the vertices of $\Gamma$ and then
multiply the $\lambda_{g}$ integrals at each vertex.

The $\lambda_{g}\lambda_{g-1}$ pairing formula is similar:

$\int_{\overline{M}_{g,n}}\psi^{\sigma}\lambda_{g}\lambda_{g-1}=\frac{(2g-3+\ell(\sigma))!(2g-1)!!}{(2g-1)!\prod_{i\in
I(p)}(2\sigma_{i}+1)!!}\int_{\overline{M}_{g}}\psi^{g-2}\lambda_{g}\lambda_{g-1}.$

The integral on the right hand side is known to be nonzero (see [4]). We can
calculate the $\kappa$ integrals analogously to Lemma 1.

##  3\. The Housing Theorem

###  3.1. Housing Partitions

Let us now study pairing $\kappa$ monomials of degree $d$ with pure boundary
classes via the $\lambda_{g}$ pairing. Each pure boundary stratum in
codimension $2g-3-d$ is determined by a tree $\Gamma=(V,E)$ with $|V|=2g-2-d$
vertices and $|E|=2g-3-d$ edges and a genus function $g:V\to\mathbb{Z}_{\geq
0}$ with $\sum_{v\in V}g(v)=g$. Then the class is the push-forward of $1$
along the gluing map $\xi_{\Gamma}:\prod_{v\in V}M_{g(v),n(v)}^{c}\to
M_{g}^{c}$ corresponding to the tree $\Gamma$, where $n(v)$ is the degree of
the vertex $v$. From this data we obtain a partition of

$\displaystyle\sum_{v\in V}(2g(v)-3+n(v))$
$\displaystyle=2g-3(2g-2-d)+2(2g-3-d)$ $\displaystyle=d$

by collecting the socle dimensions $2g(v)-3+n(v)$ for each vertex $v\in V$ and
throwing away the zeroes. We will call this partition the _housing data_ of
the pure boundary stratum. From the $\lambda_{g}$ formula it is easy to see
that the pairing of the $\kappa$ ring with a pure boundary stratum is
determined by its housing data.

On the other hand it is interesting to consider which partitions of $d$ can
arise as housing data corresponding to a pure boundary stratum. We will call
these partitions _housing partitions_.

######  Lemma 2.

A partition $\sigma$ of $d$ is a housing partition if and only if it either
has fewer than $2g-2-d$ parts or exactly $2g-2-d$ parts with at least two
even.

###### Proof.

Only partitions of length at most $2g-2-d$ can be housing partitions because
there are only that many vertices. Furthermore it is easy to see that no
partition of $2g-2-d$ parts with fewer than two even parts can arise since
every vertex with only one edge gives an even part (or no part if $g(v)=1$).

Now suppose $\sigma$ is a partition of $d$ with either fewer than $2g-2-d$
parts or exactly $2g-2-d$ parts with at least two even. Let $(\tau_{i})_{1\leq
i\leq 2g-2-d}$ be the tuple of nonnegative integers given by appending
$2g-2-d-\ell(\sigma)$ zeroes to $\sigma$, so the sum of the $\tau_{i}$ is $d$
and exactly $2k+2$ of the $\tau_{i}$ are even for some nonnegative integer
$k$.

Construct a tree $\Gamma$ by taking a path of $2g-2-d-k$ vertices and adding
$k$ additional leaves connected to vertices $2,3,\ldots,k+1$ along the path
respectively. Thus $\Gamma$ has $2g-2-d$ vertices, each of degree at most
three, and exactly $2k+2$ of the vertices of $\Gamma$ have odd degree. We now
choose a bijection between the $\tau_{i}$ and the vertices of $\Gamma$ such
that even $\tau_{i}$ are assigned to vertices of odd degree. We can then
assign a genus $g_{i}=(\tau_{i}+3-n_{i})/2$ to each vertex, where $n_{i}$ is
the degree of the vertex to which $\tau_{i}$ was assigned. The resulting
stable tree has housing data $\sigma$, as desired. ∎

###  3.2. Reduction to a combinatorial problem

We have already described the housing data of a pure boundary stratum. Let us
now describe a similar notion for any class in the generating set described in
Section 2.1. Such a class is given by a boundary stratum corresponding to a
tree $\Gamma=(V,E)$ and a genus assignment $g:V\to\mathbb{Z}_{\geq 0}$, along
with assignments of monomials in $\kappa$ and $\psi$ classes (of degrees
$r(v)$ and $s(v)$ respectively) to each component of the stratum. Let
$k=\sum_{v\in V}(r(v)+s(v))$; then we must have $|E|=2g-3-d-k$ edges in the
tree in order to obtain a class of degree $2g-3-d$. If this class does not
vanish by dimension reasons then we can obtain a partition $\gamma$ of

$\sum_{v\in V}(2g(v)-3+n(v)-r(v)-s(v))=\\\ 2g-3(2g-2-d-k)+2(2g-3-d-k)-k=d$

by assigning to each vertex of $V$ the number $2g(v)-3+n(v)-r(v)-s(v)$. This
is exactly the degree $d^{\prime}(v)$ such that the $\lambda_{g(v)}$ pairing
of $R^{d^{\prime}(v)}(M_{g(v),n(v)}^{c})$ with the monomial of $\psi$ and
$\kappa$ classes at $v$ is not zero for dimension reasons. Then the pairing
with the boundary class is determined by the partition $\gamma$, an assignment
of degrees $r(i)$ and $s(i)$ to the parts $i\in I(\gamma)$ and partitions
$\tau_{i}\in P(r(i))$ and $\rho_{i}\in P(s(i))$ corresponding to the $\kappa$
and $\psi$ monomials. In particular we can leave out classes which were
assigned to vertices with $2g(v)-3+n(v)-r(v)-s(v)=0$ and we do not need to
remember which node corresponds to each $\psi$. The result of the
$\lambda_{g}$ pairing of this class together with a $\kappa$ monomial
corresponding to a partition $\pi$ of $d$ is (up to scaling) given by

$\sum_{\varphi}\prod_{j\in
I(\gamma)}\vartheta\left(\pi_{\varphi^{-1}(j)},\tau_{j};\rho_{j}\right),$

where the sum runs over all refining functions $\varphi$ of $\gamma$ into
$\pi$.

When we view $\mathbb{Q}^{P(d)}$ as a ring of formal $\kappa$ polynomials,
this pairing gives linear forms
$v_{\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}\in\left(\mathbb{Q}^{P(d)}\right)^{*}$.
We notice that the formulas still make combinatorial sense even if the
$\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}$ data does not come from pairing with an
actual tautological class.

The special case where all the $r(i)$ and $s(i)$ are zero gives the pairing of
$\kappa$ classes with pure boundary classes. We get $|P(d)|$ linear forms
$M_{\lambda}$, which we normalize such that $M_{\lambda}(\lambda)=1$:

(1) $M_{\lambda}(\pi)=\frac{1}{\mathrm{Aut}(\lambda)}\sum_{\varphi}\prod_{j\in
I(\lambda)}\vartheta\left(\pi_{\varphi^{-1}(j)}\right).$

In this way we obtain a basis of $\left(\mathbb{Q}^{P(d)}\right)^{*}$. If we
sort partitions in any way such that shorter partitions come before longer
partitions, then the basis change matrix from this basis to the standard basis
is triangular with ones on the diagonal. Note that this basis uses some
partitions which are not housing partitions.

The housing theorem can now be reformulated as follows:

######  Claim.

The span of $\\{M_{\lambda}:\lambda\text{ is a housing partition}\\}$ in
$\left(\mathbb{Q}^{P(d)}\right)^{*}$ equals the span of the
$v_{\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}$ for all choices of housing data.

To prove this claim we will first express the vectors
$v_{\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}$ for any choice of housing data in
terms of the basis of $\left(\mathbb{Q}^{P(d)}\right)^{*}$ we have described
above in Section 3.3. We will then in Section 3.4 rewrite the coefficients as
counts of certain combinatorial objects. This combinatorial interpretation is
proved in Section 3.5. We conclude in Section 3.6 by showing that when
expressing vectors $v$ corresponding to actual housing data in terms of the
$M_{\lambda}$, the coefficient is zero whenever $\lambda$ is not a housing
partition.

###  3.3. A Matrix Inversion

In section 3.2 we have seen that there are formal expansions

$v_{\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}=\sum_{\lambda\in
P(d)}c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}M_{\lambda}$

for some coefficients $c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}$.

We can calculate $c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}$ explicitly
by inverting the triangular matrix given by equation (1). We obtain

$\displaystyle
c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}=\sum_{l=0}^{\infty}(-1)^{l}\sum_{\lambda_{0}\stackrel{{\scriptstyle\varphi_{1}}}{{\to}}\dots\stackrel{{\scriptstyle\varphi_{l}}}{{\to}}\lambda_{l}\stackrel{{\scriptstyle\varphi_{l+1}}}{{\to}}\gamma}\frac{v_{\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}(\lambda_{l})}{\prod_{i=1}^{l}|\mathrm{Aut}(\lambda_{i})|}\prod_{i=1}^{l}\prod_{j\in
I(\lambda_{i})}\vartheta\left((\lambda_{i-1})_{\varphi_{i}^{-1}(j)}\right),$

where we sum over chains $\lambda=\lambda_{0},\dotsc\lambda_{l}$ of
refinements of $\gamma$ with corresponding refinement functions $\varphi_{i}$.
In particular $c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}=0$ if
$\lambda$ is not a refinement of $\gamma$.

We can reduce to the special case in which $\gamma=(d)$ is of length one by
splitting this sum based on the composition
$\varphi:=\varphi_{l+1}\circ\varphi_{l}\circ\dots\circ\varphi_{1}$ and
examining the contribution of the preimages of the $j\in I(\gamma)$. The
result is

(2)
$c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}=\sum_{\varphi}\prod_{j\in
I(\gamma)}c_{\lambda_{\varphi^{-1}(j)},(\gamma_{j}),\\{\tau_{j}\\},\\{\rho_{j}\\}},$

summed over refinements $\varphi$ of $\gamma$ into $\lambda$.

When $\gamma=(d)$, we set $\tau_{1}=:\tau$ and $\rho_{1}=:\rho$ and we can
write more compactly

(3)
$c_{\lambda,(d),\\{\tau\\},\\{\rho\\}}=\sum_{l=0}^{\infty}(-1)^{l}\sum_{\lambda_{0}\stackrel{{\scriptstyle\varphi_{1}}}{{\to}}\dots\stackrel{{\scriptstyle\varphi_{l}}}{{\to}}\lambda_{l}}\frac{\vartheta(\lambda_{l},\tau;\rho)}{\prod_{i=1}^{l}|\mathrm{Aut}(\lambda_{i})|}\prod_{i=1}^{l}\prod_{j\in
I(\lambda_{i})}\vartheta\left((\lambda_{i-1})_{\varphi_{i}^{-1}(j)}\right).$

###  3.4. Interpreting the coefficients combinatorially

We will interpret the coefficients $c_{\lambda,(d),\\{\tau\\},\\{\rho\\}}$ as
counting certain permutations of symbols labeled by the parts of the
partitions $\lambda,\tau$, and $\rho$. We say that a symbol is _of kind $i$_
if it is labelled by some $i$ belonging to the disjoint union of the indexing
sets of the partitions, $I(\lambda)\sqcup I(\tau)\sqcup I(\rho)$. There will
in general be multiple symbols of a given kind.

######  Main Claim.

The coefficient $c_{\lambda,(d),\\{\tau\\},\\{\rho\\}}$ counts the number of
permutations of

  * •

$\lambda_{i}+1$ symbols of kind $i$ for each $i\in I(\lambda)$,

  * •

$\tau_{i}+1$ symbols of kind $i$ for each $i\in I(\tau)$, and

  * •

$\rho_{i}$ symbols of kind $i$ for each $i\in I(\rho)$

such that:

  1. (1)

If the last symbol of some kind $i$ is immediately followed by the first
symbol of kind $j$ with $i,j\in I(\lambda)\sqcup I(\tau)$, then we have $i<j$.

  2. (2)

For $i\in I(\lambda)$ the last element of kind $i$ is not immediately followed
by a symbol of kind $j$ for any $j\in I(\lambda)$,

averaged over all total orders $<$ of $I(\lambda)\sqcup I(\tau)$ such that
elements of $I(\tau)$ are smaller than elements of $I(\lambda)$.

It follows in particular that the coefficient
$c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}$ is non-negative.

###  3.5. Proof of the main claim

####  3.5.1. Refinements of permutations of symbols

For given natural numbers $d$, $n$ and a partition $\tau\in P(d)$ we will
study permutations of $\tau_{i}+1$ symbols of kind $i$ for $i\in I(\tau)$ and
$n$ symbols of kind $c$. (The permutations of symbols appearing in the
previous section are an instance of this.) We will need to construct refined
permutations of this type for partition refinements $\varphi:I(\sigma)\to
I(\tau)$. For this we need additional _refinement data_ : for each $i\in
I(\tau)$, let $T_{i}$ be a permutation of $\sigma_{j}+1$ symbols of kind $j$
for $j\in\varphi^{-1}(i)$. Then we can obtain a permutation $S^{\prime}$ of
$\sigma_{i}+1$ symbols of kind $i$ and $n$ symbols of kind $c$ in the
following way:

For each $i\in I(\tau)$ and each $j\in\varphi^{-1}(i)$, modify $T_{i}$ by
gluing the last symbol of kind $j$ with the immediately following symbol; the
result is a permutation $T^{\prime}_{i}$ of $\tau_{i}+1$ symbols. To construct
$S^{\prime}$ from $S$, for each $i$ we replace the symbols of kind $i$ by
$T^{\prime}_{i}$ and then remove the glue.

####  3.5.2. Reinterpretation

We start with a combinatorial interpretation of the number
$\vartheta(\sigma;\tau)$ for partitions $\sigma$ and $\tau$.

######  Lemma 3.

Given an arbitrary total order $<$ on $I(\sigma)$, the number
$\vartheta(\sigma;\tau)$ is equal to the number of permutations of

  * •

$\sigma_{i}+1$ symbols of kind $i$ for each $i\in I(\sigma)$ and

  * •

$\tau_{i}$ symbols of kind $i$ for each $i\in I(\tau)$

such that the following property holds:

If the last symbol of kind $i$ is immediately followed by the first symbol of
kind $j$ for $i,j\in I(\sigma)$ then we have $i<j$.

###### Proof.

For each permutation $S$ of symbols as above, but not necessarily satifying
the property, we can assign a set partition $Q_{S}\vdash I(\sigma)$ which
measures in what ways it fails to satisfy the property: $Q_{S}$ is the finest
set partition such that if $i<j$ and the last symbol of kind $i$ is
immediately followed by the first symbol of kind $j$ in $S$, then $i$ and $j$
are in the same part of $Q_{S}$. Thus $S$ satisfies the given property if and
only if $Q_{S}$ is the set partition with all parts of size $1$.

The multinomial coefficient in the summand in the formula for
$\vartheta(\sigma;\tau)$ given by Lemma 1 corresponding to a set partition
$P\vdash I(\sigma)$ counts the number of permutations $S$ such that for
$p=\\{p_{1},\ldots,p_{k}\\}\in P$ with $p_{1}<\cdots<p_{k}$, the last element
of kind $p_{i}$ is immediately followed by the first element of kind $p_{i+1}$
in $S$ for $i=1,\cdots,k-1$. These are precisely the $S$ such that $Q_{S}$ can
be obtained by combining parts of $P$ such that the largest element in one
part is smaller than the smallest element of the other part.

This means that the contribution of a permutation with failure set partition
$Q=\\{Q_{1},\ldots,Q_{k}\\}$ to the sum in Lemma 1 is precisely

$\prod_{i=1}^{k}\sum_{j=0}^{|Q_{k}|-1}(-1)^{j}\binom{|Q_{k}|-1}{j},$

which is $1$ for $Q$ the set partition with all parts of size $1$ and $0$
otherwise. ∎

Equipped with Lemma 3, the next step is to interpret the coefficient
$c_{\lambda,(d),\\{\tau\\},\\{\rho\\}}$ as the sum of the values of a function
$f$ on the set $S_{\lambda,\tau,\rho}$ of permutations of $\lambda_{i}+1$,
$\tau_{i}+1$, $\rho_{i}$ symbols of kind $i$ for $i\in I(\lambda)$, $i\in
I(\tau)$ and $i\in I(\rho)$ respectively.

Fix

  * •

a chain of partitions $\lambda_{0}=\lambda,\lambda_{1},\dots,\lambda_{l}$ with
refining maps $\varphi_{i}$,

  * •

an order $<$ on $I(\lambda_{l})\sqcup I(\tau)$ such that elements of $I(\tau)$
appear before elements of $I(\lambda_{l})$,

  * •

orders on $\varphi_{i}^{-1}(j)$ for $1\leq i\leq l$ and $j\in I(\lambda_{i})$.

Then we identify each $\kappa$ socle evaluation factor

$\vartheta\left((\lambda_{i-1})_{\varphi_{i}^{-1}(j)}\right)$

with the number of permutations of $(\lambda_{i-1})_{k}+1$ symbols of kind
$k\in\varphi_{i}^{-1}(j)$ such that if the last symbol of kind $k$ is
immediately followed by the first symbol of kind $k^{\prime}$, then
$k<k^{\prime}$. We interpret each such permutation as refinement data
corresponding to the refinement $\varphi_{i}$ of $\lambda_{i}$ into
$\lambda_{i+1}$.

Furthermore we interpret the factor

$\vartheta\left(\lambda_{l},\tau;\rho\right)$

as the number of permutations of $(\lambda_{l})_{k}+1$, $\tau_{k}+1$ and
$\rho_{k}$ symbols of kind $k$ with $k\in I(\lambda_{l})$, $k\in I(\tau)$ and
$k\in I(\rho)$ respectively such that if the last symbol of kind $k$ is
immediately followed by the first symbol of kind $k^{\prime}$ for
$k,k^{\prime}\in I(\lambda_{l})\sqcup I(\tau)$, then $k<k^{\prime}$. In order
to remove the dependence on the chosen orders we will average over all choices
of them.

####  3.5.3. Simplification

Given all this data, we can build a “composite permutation” by repeatedly
refining the collection of symbols of kind $k$ with $k\in I(\lambda_{l})$
using the construction from Section 3.5.1 and keeping the order of the other
symbols intact. The result is a permutation of $\lambda_{k}+1$, $\tau_{k}+1$
and $\rho_{k}$ symbols of kind $k$ for $k\in I(\lambda)$, $k\in I(\tau)$ and
$k\in I(\rho)$ respectively. Any permutation obtained in this way has the
property that the last symbol of any kind $j\in I(\lambda)$ is not immediately
followed by the first symbol of some kind $j^{\prime}\in I(\tau)$.

For any permutation in $S_{\lambda,\tau,\rho}$ we assign a set partition
$P\vdash I(\lambda)$, which measures in what way it fails to satisfy condition
(2) in the main claim. We define $P$ to be the finest set partition such that
if the last symbol of kind $i$ is immediately followed by a symbol of kind $j$
for $i,j\in I(\lambda)$ then $i$ and $j$ lie in the same set in $P$.

Now, suppose we are given a chain of partitions
$\lambda,\lambda_{1},\dots,\lambda_{l}$ along with additional refining data
and base permutation as above, and supppose the resulting composite
permutation has failure set partition $P$ that is not the partition into one-
element sets.

By the definition of $P$, if we change the order on $I(\lambda)\sqcup I(\tau)$
such that the order on $I(\tau)$ and each element of $P$ is preserved, all the
conditions on the data are still satisfied.

On the other hand, consider the following data:

  * •

the chain $\lambda,\lambda_{1},\dots,\lambda_{l},\lambda_{l}^{P}$ with
refining maps $\varphi_{i}$ as before,

  * •

any refining map $\varphi^{\prime}:I(\lambda_{l})\to I(\lambda_{l}^{P})$ which
is up to an automorphism of $\lambda_{l}^{P}$ the canonical one,

  * •

the orders and refining data corresponding to the $\varphi_{i}$ as before,

  * •

in addition an order on each element of $P$ induced by the order on
$I(\lambda_{l})\sqcup I(\tau)$,

  * •

refining data corresponding to $\varphi^{\prime}$ induced from the permutation
corresponding to $\lambda_{l}$, $\tau$ and $\rho$,

  * •

any order on $I(\lambda_{l}^{P})\sqcup I(\tau)$ such that the restriction to
$I(\tau)$ is the restriction of the order on $I(\lambda_{l})\sqcup I(\tau)$
and such that elements of $I(\tau)$ appear before elements of
$I(\lambda_{l}^{P})$,

  * •

permutations of $(\lambda_{l}^{P})_{i}+1$, $\tau_{i}+1$, $\rho_{i}$ symbols of
kind $i$ for $i\in P$, $i\in I(\tau)$ and $i\in I(\rho)$ respectively, defined
from the permutation corresponding to $\lambda_{l}$ by leaving out the last
symbol of any kind $i\in I(\lambda_{l})$ which is not the last one in a set of
$P$ and identifying symbols according to $P$.

It is easy to check that the refining data and the permutation still satisfy
the order conditions. Furthermore, the failure set partition of the composite
partition of this new data is the partition into one-element sets.

The original chain with additional data giving failure set partition $P$ and
the extended chain with additional data giving failure set partition the
partition into one-element sets contribute to
$c_{\lambda,(d),\\{\tau\\},\\{\rho\\}}$ in formula (3) with opposite signs,
since the extended chain is one element longer. We claim these contributions
are actually equal.

For the original chain, we have

$\frac{(\ell(\lambda_{l}))!}{\prod_{j\in P}|\varphi^{\prime-1}(j)|!}$

choices of orders on $I(\lambda)\sqcup I(\tau)$ in the above construction. For
the extended chain, we made

$|\mathrm{Aut}(\lambda_{l}^{P})|(\ell(\lambda_{l}^{P}))!$

choices in the above construction.

However, the contributions are also weighted by averaging over choices of
orders and by the coefficients in (3). For the original chain the weight is

$((\ell(\lambda_{l}))!)^{-1}$

and for the extended chain the weight is

$\left(|\mathrm{Aut}(\lambda_{l}^{P})|(\ell(\lambda_{l}^{P}))!\prod_{j\in
P}|\varphi^{\prime-1}(j)|!\right)^{-1}.$

Thus the two contributions cancel.

The only remaining contributions come when $l=0$ and $P$ is the set partition
into one-element sets. These are the permutations counted in the main claim.

###  3.6. Proof of the Housing Theorem

We begin with a simple lemma.

######  Lemma 4.

Suppose $r+s+\ell(\gamma)<\ell(\lambda)$. Then
$c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}=0$.

###### Proof.

We examine the summand in formula (2) corresponding to some $\varphi$. A
factor in this summand can only be nonzero if
$r(i)+s(i)+1\geq\ell(\varphi^{-1}(i))$. Therefore each summand will vanish
unless $r+s+\ell(\gamma)\geq\ell(\lambda)$. ∎

Now let us suppose that $\gamma$, $\\{\tau_{i}\\}$, $\\{\rho_{i}\\}$ is the
housing data of a boundary class of the generating set. We need to show that
$c_{\lambda,\gamma,\\{\tau_{i}\\},\\{\rho_{i}\\}}=0$ for each $\lambda$ which
is not a housing partition.

Let us first study the case $\ell(\lambda)>2g-2-d$. Since $\gamma$ is derived
from a boundary stratum of at most codimension $2g-3-d-r-s$ (we are missing
the $\psi$ and $\kappa$ classes from the components, which do not contribute
to $\gamma$) by diminishing parts by their $\kappa$ and $\psi$ degrees, we
have the inequality $\ell(\gamma)\leq 2g-2-d-r-s$. Then by Lemma 4 we are done
in this case. The same argument settles also the case where there are
components of the boundary stratum we are considering which do not appear in
$\gamma$ and $\ell(\lambda)=2g-2-d$.

Now assume that $\ell(\lambda)=2g-2-d$ and that $\lambda$ contains no even
part. Then by the same arguments if the coefficient is nonzero, we must have
$\ell(\gamma)=2g-2-d-r-s$. Then from the proof of Lemma 4 we see that
$r(i)+s(i)=\ell(\varphi^{-1}(i))-1$ for each $i\in I(\gamma)$. This implies
$\ell(\varphi^{-1}(i))+r(i)+s(i)\equiv 1\pmod{2}$ and therefore for each $i\in
I(\gamma)$ we have $\gamma_{i}+r(i)+s(i)\equiv 1\pmod{2}$. Hence each part of
the housing data (for the underlying boundary stratum), which $\gamma$ was
obtained from by subtraction of $r(i)+s(i)$ at each part, is odd. This is a
contradiction, so the coefficient must be zero, as desired.

##  4\. The Rank Theorem

###  4.1. Reformulation

Let us first formulate a stronger version of the Rank Theorem.

######  Theorem 2.

For any $\kappa$ polynomial $F$ in degree $r:=2g-3-d$ the following two
statements are equivalent:

  1. (1)

For any $\pi\in P(g-2-r)$ we have
$\int_{\overline{M}_{g}}F\kappa_{\pi}\lambda_{g}\lambda_{g-1}=0$.

  2. (2)

There is a $B\in PBR^{r}(M_{g}^{c})$ such that for any $\pi^{\prime}\in
P(2g-3-r)$ we have
$\int_{\overline{M}_{g}}(F-B)\kappa_{\pi^{\prime}}\lambda_{g}=0$.

It will be convenient to show that we can replace the first condition in
Theorem 2 by

  1. (3)

For any $\pi\in P(g-2-r)$ of length at most $r+1$ we have
$\int_{\overline{M}_{g}}F\kappa_{\pi}\lambda_{g}\lambda_{g-1}=0$.

Then Theorem 2 will follow from the following simple argument. Consider an $F$
satisfying the second condition and we want to show that
$\int_{\overline{M}_{g}}F\kappa_{\pi}\lambda_{g}\lambda_{g-1}=0$ for some
given $\pi\in P(g-2-r)$. Notice that then also $F\kappa_{\pi}$ satisfies the
second condition since $B\kappa_{\pi}$ lies in $BR^{g-2}(M^{c}_{g})$ and by
the housing theorem can be replaced by some $B^{\prime}\in
PBR^{g-2}(M^{c}_{g})$. We then find that
$\int_{\overline{M}_{g}}F\kappa_{\pi}\lambda_{g}\lambda_{g-1}=0$ since in this
case the length condition is trivial.

As we have seen in Section 3.5.2, not only boundary classes but also every
$\kappa$ class can be written in terms of virtual boundary strata in the
$\lambda_{g}$ pairing with the kappa ring. So the second condition in the
theorem is equivalent to the condition that only actual boundary strata are
needed in the expansion of $F$. Notice that by Lemma 4 we only need strata
corresponding to partitions of $2g-3-r$ of length at most $r+1$. However we
might need terms corresponding to partitions $2g-3-r$ of length equal to $r+1$
with only odd parts, and those are the terms we are interested in. For the
proof of the Rank Theorem we will need to understand the coefficients
corresponding to these classes better.

Observe that partitions of $2g-3-r$ of length being equal to $r+1$ with only
odd parts correspond to partitions of $g-2-r$ of length at most $r+1$. So for
any $\sigma\in P(g-2-r,r+1)$ we can look at
$\eta_{\sigma},\mu_{\sigma}\in(\mathbb{Q}^{P(r)})^{*}$ with
$\eta_{\sigma}(\tau):=c_{\lambda,\tau,\emptyset}$, where $\lambda$ is the
partition of $2g-3-r$ of length $r+1$ corresponding to $\sigma$, and
$\mu_{\sigma}(\tau)$ is up to a factor the integral
$\int_{\overline{M}_{g}}\kappa_{\sigma}\kappa_{\tau}\lambda_{g}\lambda_{g-1}$,
namely

$\mu_{\sigma}(\tau)=\sum_{P\vdash I(\sigma)\sqcup
I(\tau)}(-1)^{\ell(\sigma)+\ell(\tau)+|P|}\frac{(2g-3+|P|)!}{\prod_{i\in
P}(2(\sigma,\tau)^{P}_{i}+1)!!}.$

So what we need to show is the following:

######  Claim.

The $\mathbb{Q}$-subspaces of $(\mathbb{Q}^{P(r)})^{*}$ spanned by
$\eta_{\sigma}$ and $\mu_{\sigma}$ for $\sigma$ ranging over all partitions of
$g-2-r$ of length at most $r+1$ are equal.

Recall from Section 3.5.2 that $\eta_{\sigma}(\tau)$ is the number of all
permutations $S$ of $\lambda_{i}+1$ symbols of kind $i\in I(\lambda)$ and
$\tau_{i}+1$ symbols of kind $i\in I(\tau)$ satisfying

  1. (1)

The last symbol of kind $i$ for some $i\in I(\lambda)$ is either at the end of
the sequence or immediately followed by a symbol of kind $j$ for some $j\in
I(\tau)$ which is not the first of its kind.

  2. (2)

The successor of the last element of kind $i$ is not the first element of kind
$j$ for any $i,j\in I(\tau)$ with $i<j$, where we fix some order on $I(\tau)$.

Before coming to the main part of the proof we apply an invertible
transformation $\Phi$ to $(\mathbb{Q}^{P(r)})^{*}$ to simplify the definitions
of $\eta$ and $\mu$. The inverse of the transformation we want to apply sends
a linear form $\varphi^{\prime}\in(\mathbb{Q}^{P(r)})^{*}$ to a linear form
$\varphi$ defined by

$\varphi(\tau)=\sum_{P\vdash
I(\tau)}(-1)^{\ell(\tau)+|P|}\varphi^{\prime}(\tau^{P}).$

The transformation $\Phi$ defined in this way is clearly invertible. By a
similar argument as in the proof of Lemma 3, we can show that the image
$\eta^{\prime}_{\sigma}$ of $\eta_{\sigma}$ under $\Phi$ is defined in the
same way as $\eta_{\sigma}$ but leaving out Condition 2 on the permutations.

To study the action of $\Phi$ on $\mu$ we use the following lemma:

######  Lemma 5.

Let $F$ be a function $F:P(n+m)\to\mathbb{Q}$ and define for any $\sigma\in
P(n)$ functions $G_{\sigma},G^{\prime}_{\sigma}:P(m)\to\mathbb{Q}$ in terms of
$F$ by

$\displaystyle G_{\sigma}(\tau)$ $\displaystyle=\sum_{P\vdash I(\sigma)\sqcup
I(\tau)}F((\sigma\sqcup\tau)^{P})$ $\displaystyle G^{\prime}_{\sigma}(\tau)$
$\displaystyle=\sum_{\begin{subarray}{c}P\vdash I(\sigma)\sqcup I(\tau)\\\
P\text{ separates }I(\tau)\end{subarray}}F((\sigma\sqcup\tau)^{P}),$

where the second sum just runs over set partitions $P$ such that each element
of $I(\tau)$ belongs to a separate part. Then

$G_{\sigma}(\tau)=\sum_{P\vdash I(\tau)}G^{\prime}_{\sigma}(\tau^{P}).$

###### Proof.

Given set partitions $P$ of $I(\tau)$ and $Q$ of $I(\sigma)\sqcup
I(\tau^{P})$, with $Q$ separating $I(\tau^{P})$, we can alter $Q$ by replacing
each element of $I(\tau^{P})$ by the elements in the corresponding part of
$P$. Each set partition of $I(\sigma)\sqcup I(\tau)$ is obtained exactly once
by this construction. ∎

Using this lemma and keeping track of the sign factors, we have that
$\mu^{\prime}_{\sigma}(\tau)$ is

$\mu^{\prime}_{\sigma}(\tau)=\sum_{\begin{subarray}{c}P\vdash I(\sigma)\sqcup
I(\tau)\\\ P\text{ separates
}I(\tau)\end{subarray}}(-1)^{\ell(\sigma)+\ell(\tau)+|P|}\frac{(2g-3+|P|)!}{\prod_{i\in
P}(2(\sigma\sqcup\tau)^{P}_{i}+1)!!}.$

We can use the lemma again with the roles of $\sigma$ and $\tau$ interchanged
to replace the generators of the span of $\mu^{\prime}_{\sigma}$ by
$\mu^{\prime\prime}_{\sigma}$ with

(4) $\mu^{\prime\prime}_{\sigma}(\tau):=\sum_{\begin{subarray}{c}P\vdash
I(\sigma)\sqcup I(\tau)\\\ P\text{ separates }I(\tau)\\\ P\text{ separates
}I(\sigma)\end{subarray}}(-1)^{\ell(\sigma)+\ell(\tau)+|P|}\frac{(2g-3+|P|)!}{\prod_{i\in
P}(2(\sigma\sqcup\tau)^{P}_{i}+1)!!}.$

Therefore we have reduced the proof of the Rank Theorem to proving the
following claim.

######  Claim.

The $\mathbb{Q}$-subspaces of $(\mathbb{Q}^{P(r)})^{*}$ spanned by
$\eta^{\prime}_{\sigma}$ and $\mu^{\prime\prime}_{\sigma}$ for $\sigma$
ranging over all partitions of $g-2-r$ of length at most $r+1$ are equal.

###  4.2. Further strategy of proof

In order to prove the claim we will establish interpretations for
$\eta^{\prime}_{\sigma}(\tau)$ and $\mu^{\prime\prime}_{\sigma}(\tau)$ as
counts of symbols of different kinds satisfying some ordering constraints.
This enables us to find nonzero constants $F(i)$ for each $i\in I(\sigma)$
independent of $\tau$ such that

$\mu^{\prime\prime}_{\sigma}(\tau)=\sum_{P\vdash I(\sigma)}\prod_{i\in
P}F(i)\frac{\eta^{\prime}_{\sigma^{P}}(\tau)}{(r+1-|P|)!},$

giving a triangular transformation.

For the interpretations the notion of a _comb-like order_ plays an important
role. We say that symbols $i_{1}\dotsc i_{2m+1}$ are in comb-like order if we
have the relations $i_{1}<i_{3}<\dots<i_{2m+1}$ and $i_{2j}<i_{2j+1}$ for
$j\in[m]$. This is illustrated in Figure 1.

$i_{1}$$i_{2}$$i_{3}$$i_{4}$$i_{5}$$i_{2m-1}$$i_{2m}$$i_{2m+1}$ Figure 1. A
comb-like order

Note that the number of comb-like orderings of $2m+1$ symbols is
$(2m+1)!/(2m+1)!!$. More generally the number

$\frac{(2|\pi|+\ell(\pi))!}{\prod_{i\in I(\pi)}(2\pi_{i}+1)!!}$

corresponding to a partition $\pi$ counts the number of permutations of the
$2|\pi|+\ell(\pi)$ symbols $\bigcup_{i\in
I(\pi)}\\{i_{1},\dots,i_{2\pi_{i}+1}\\}$ such that symbols corresponding to
the same part of $\pi$ appear in comb-like order.

###  4.3. Combing orders

We obtain a first reinterpretation of $\eta^{\prime}_{\sigma}(\tau)$ by
numbering the symbols of equal kind:

######  Interpretation A1.

$\eta^{\prime}_{\sigma}(\tau)$ is the number of all permutations of symbols
$i_{1},\dotsc,i_{\tau_{i}+1}$ for $i\in I(\tau)$ and
$i_{1},\dotsc,i_{\lambda_{i}+1}$ for $i\in I(\lambda)$ such that for fixed
$i\in I(\tau)\sqcup I(\lambda)$ the $i_{j}$ appear in order and for all $i\in
I(\lambda)$ the symbol $i_{\lambda_{i}+1}$ is either at the end of the
sequence or immediately followed by some $j_{k}$ for $j\in I(\tau)$ and $k\neq
1$.

Since $\lambda$ has length $r+1$ and $|\tau|=r$, such a permutation gives a
bijection between the $j_{k}$ for $j\in I(\tau)$ with $k\neq 1$ and all but
one of the $i_{\lambda_{i}+1}$ for $i\in I(\lambda)$. After picking this
bijection, we can remove the $i_{\lambda_{i}+1}$.

######  Interpretation A2.

$\eta^{\prime}_{\sigma}(\tau)$ is the sum over bijections

$\varphi:I(\lambda)\to\\{i_{j}\mid i\in I(\tau),j\neq
1\\}\sqcup\\{\text{End}\\}$

of the number of permutations of symbols $i_{1},\dotsc,i_{\tau_{i}+1}$ for
$i\in I(\tau)$ and $i_{1},\dotsc,i_{\lambda_{i}}$ for $i\in I(\lambda)$ such
that symbols of the same kind appear in order and all symbols $i_{j}$ for
$i\in I(\lambda)$ appear before $\varphi(i)$ (this condition is empty if
$\varphi(i)=\text{End}$).

We can then add new symbols immediately following each $i_{\lambda_{i}}$ for
$i\in I(\lambda)$ and reindex the $i_{j}$ for $i\in I(\tau)$ to create comb-
like orderings.

######  Interpretation A3.

$\eta^{\prime}_{\sigma}(\tau)$ is the sum over bijections

$\varphi:I(\lambda)\to\\{i_{j}\mid i\in I(\tau),j\text{
even}\\}\sqcup\\{\text{End}\\}$

of the number of permutations of symbols $i_{1},\dotsc,i_{2\tau_{i}+1}$ for
$i\in I(\tau)$, $i_{1},\dotsc,i_{\lambda_{i}}$ for $i\in I(\lambda)$, and an
additional symbol End such that the $i_{j}$ for $i\in I(\tau)$ appear in comb-
like order, the $i_{j}$ for $i\in I(\lambda)$ appear in order, and
$i_{\lambda_{i}}$ for $i\in I(\lambda)$ is immediately followed by
$\varphi(i)$.

Recall that $\lambda$ is defined in terms of $\sigma$ by taking the numbers
$2\sigma_{i}+1$ for each $i\in I(\sigma)$ and adding as many ones as needed to
reach length $r+1$. There is only one symbol $i_{1}$ of kind $i$ for $i\in
I(\lambda)\setminus I(\sigma)$ in Interpretation Interpretation A3 of
$\eta^{\prime}_{\sigma}(\tau)$ and it must be immediately followed by
$\varphi(i)$. For convenience set
$(r+1-\ell(\sigma))!\cdot\eta^{\prime\prime}_{\sigma}:=\eta^{\prime}_{\sigma}$.
Removing these symbols $i_{1}$ gives an interpretation of
$\eta^{\prime\prime}_{\sigma}$.

######  Interpretation A4.

$\eta^{\prime\prime}_{\sigma}(\tau)$ is a sum over all injections

$\varphi:I(\sigma)\to\\{i_{j}\mid i\in I(\tau),j\text{
even}\\}\sqcup\\{\text{End}\\}$

of the number of permutations of symbols $i_{1},\dotsc,i_{2\tau_{i}+1}$ for
$i\in I(\tau)$, $i_{1},\dotsc,i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$, and an
additional symbol End such that the $i_{j}$ for $i\in I(\tau)$ appear in comb-
like order, the $i_{j}$ for $i\in I(\sigma)$ appear in order, and
$i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ is immediately followed by
$\varphi(i)$.

We now switch to the interpretation of $\mu^{\prime\prime}_{\sigma}(\tau)$,
which was defined in (4). The coefficient corresponding to a set partition $P$
can be interpreted as the number of permutations of symbols
$i_{1},\dotsc,i_{2(\sigma\sqcup\tau)^{P}_{i}+1}$ for $i\in
I((\sigma\sqcup\tau)^{P})$ and one additional symbol $\star$ such that all
$i_{1},\dotsc,i_{2(\sigma\sqcup\tau)^{P}_{i}+1}$ for $i\in
I((\sigma\sqcup\tau)^{P})$ appear in comb-like order.

Because of the restrictions in the sum, the parts of $P$ are either singletons
or contain exactly one element from each of $I(\sigma)$ and $I(\tau)$. This
defines a function $\psi:I(\sigma)\to I(\tau)\sqcup\\{\star\\}$, injective
when restricted to the preimage of $I(\tau)$. Interpreting the summands as
counting comb-like orders and cutting combs into two pieces for each part of
$P$ of size two gives the following:

######  Interpretation B1.

$\mu^{\prime\prime}_{\sigma}(\tau)$ is the sum over functions

$\psi:I(\sigma)\to I(\tau)\sqcup\\{\star\\}$

such that $\psi|_{\psi^{-1}(I(\tau))}$ is injective, of a sign of
$(-1)^{|\psi^{-1}(I(\tau))|}$ times the number of permutations of symbols
$i_{1},\dotsc,i_{2\tau_{i}+1}$ for $i\in I(\tau)$,
$i_{1},\dotsc,i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ and one additional
symbol $\star$ such that all $i_{1},\dotsc,i_{2\tau_{i}+1}$ for $i\in I(\tau)$
and all $i_{1},\dotsc,i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ appear in comb-
like order and such that $i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ with
$\psi(i)\neq\star$ is immediately followed by $\psi(i)_{1}$.

Now we split the set of such permutations depending on the symbols immediately
following symbols $i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$. We notice that the
signed sum exactly kills those permutations where some $i_{2\sigma_{i}+1}$ for
$i\in I(\sigma)$ is immediately followed by some $j_{1}$ for $j\in I(\tau)$
since if such a summand appears for some $\psi$ with $\psi(i)\neq j$ we must
have $\psi(i)=\star$ and we find the same summand with opposite sign in the
sum corresponding to the map $\psi^{\prime}$ defined by $\psi^{\prime}(i)=j$
and $\psi^{\prime}(k)=\psi(k)$ for $k\neq i$ and vice versa.

######  Interpretation B2.

$\mu^{\prime\prime}_{\sigma}(\tau)$ is the number of permutations of symbols
$i_{1},\dotsc,i_{2\tau_{i}+1}$ for $i\in I(\tau)$,
$i_{1},\dotsc,i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ and one additional
symbol $\star$ such that all $i_{1},\dotsc,i_{2\tau_{i}+1}$ for $i\in I(\tau)$
and all $i_{1},\dotsc,i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ appear in comb-
like order and such that $i_{2\sigma_{i}+1}$ for $i\in I(\sigma)$ is not
immediately followed by a symbol of the form $j_{1}$ with $j\in I(\tau)$.

Interpretations Interpretation A4 and Interpretation B2 are very close. The
differences between the two of them are that the $\sigma$-type symbols are in
total order rather than comb-like order in Interpretation A4 and that the
conditions on the elements immediately following the $i_{2\sigma_{i}+1}$ are
different.

We now break $\mu^{\prime\prime}_{\sigma}(\tau)$ into a sum over set
partitions $P$ of $I(\sigma)$. Given a permutation of the symbols appearing in
Interpretation Interpretation B2, define a function

$\varphi:I(\sigma)\to\\{i_{j}\mid i\in I(\tau),j\text{
even}\\}\sqcup\\{\text{End}\\}$

recursively by

$\varphi(i)=\left\\{\begin{aligned} j_{2k}&&\text{if }i_{2\sigma_{i}+1}\text{
for }i\in I(\sigma)\text{ is immediately followed by a symbol }\\\ &&\text{ of
the form }j_{2k}\text{ or }j_{2k+1}\text{ with }j\in I(\tau),\\\
\text{End}&&\text{if }i_{2\sigma_{i}+1}\text{ for }i\in I(\sigma)\text{ is
immediately followed by }\star\\\ &&\text{ or at the end of the sequence},\\\
\varphi(j)&&\text{if }i_{2\sigma_{i}+1}\text{ for }i\in I(\sigma)\text{ is
immediately followed by a symbol }\\\ &&\text{ of the form }j_{k}\text{ with
}j\in I(\sigma).\end{aligned}\right.$

Then let $P$ be the set partition of preimages under $\varphi$. We will
identify the summand of $\mu^{\prime\prime}_{\sigma}(\tau)$ corresponding to
such a set partition $P$ as $\eta^{\prime\prime}_{\sigma^{P}}(\tau)$ times a
factor depending only on $\sigma$ and $P$.

This factor is equal to

$\prod_{i\in P}F(i),$

where

$F(i)=\frac{(2\sigma^{P}_{i}+|i|+1)!}{\prod_{j\in i}(2\sigma_{j}+1)!!}.$

Here $F(i)$ should be interpreted as the number of permutations of
$2\sigma_{j}+1$ symbols of kind $j$ for each $j\in i$ and one additional
symbol End such that the symbols of each kind appear in comb-like order. If
these permutations are interpreted as refinement data, then the permutations
counted by the $P$-summand of $\mu^{\prime\prime}_{\sigma}(\tau)$ are the
refinements by this data of the permutations counted by
$\eta^{\prime\prime}_{\sigma^{P}}(\tau)$.

Thus we have the identity

$\mu^{\prime\prime}_{\sigma}=\sum_{P\vdash I(\sigma)}\prod_{i\in
P}F(i)\eta^{\prime\prime}_{\sigma^{P}}.$

This is a triangular change of basis with nonzero entries on the diagonal, so
the $\mu^{\prime\prime}$ and $\eta^{\prime\prime}$ span the same subspace in
$(\mathbb{Q}^{P(r)})^{*}$. This completes the proof of the Rank Theorem.

## References

  * [1] C. Faber.  A conjectural description of the tautological ring of the moduli space of curves.  In Moduli of curves and abelian varieties, Aspects Math., E33, pages 109–129. Vieweg, Braunschweig, 1999.
  * [2] C. Faber and R. Pandharipande.  Hodge integrals and Gromov-Witten theory.  Invent. Math., 139(1):173–199, 2000.
  * [3] C. Faber and R. Pandharipande.  Hodge integrals, partition matrices, and the $\lambda_{g}$ conjecture.  Ann. of Math. (2), 157(1):97–124, 2003.
  * [4] E. Getzler and R. Pandharipande.  Virasoro constraints and the Chern classes of the Hodge bundle.  Nuclear Phys. B, 530(3):701–714, 1998.
  * [5] T. Graber and R. Pandharipande.  Constructions of nontautological classes on moduli spaces of curves.  Michigan Math. J., 51(1):93–109, 2003.
  * [6] R. Pandharipande.  The kappa ring of the moduli of curves of compact type.  Acta Math., 208(2):335–388, 2012.
  * [7] R. Pandharipande and A. Pixton.  Relations in the tautological ring of the moduli space of curves.  arXiv:1301.4561, Jan 2013.