Partitions of vertices and facets in trees and stacked simplicial complexes

Gunnar Fløystad Matematisk Institutt
Postboks
5020 Bergen [email protected]

Abstract.

For stacked simplicial complexes, (special subclasses of such are: trees, triangulations of polygons, stacked polytopes with their triangulations), we give an explicit bijection between partitions of facets (for trees: edges), and partitions of vertices into independent sets. More generally we give bijections between facet partitions whose parts have minimal distance $\geq s$ and vertex partitions whose parts have minimal distance $\geq s+1$ .

Key words and phrases:

tree, partition, independent vertices, stacked simplicial complex, natural numbers, Stirling numbers, bijection

2020 Mathematics Subject Classification:

Primary: 05C05 05C69, 05E45; Secondary: 05C70

1. Introduction

If $G=(V,E)$ is a graph with vertices $V$ and edges $E$ , a set of vertices $A\subseteq V$ is independent if no two vertices in $A$ are on the same edge. Between any two vertices there is a well-defined distance, and the vertices are independent if their distance is $\geq 2$ . Distance may also be defined between edges in a graph.

Assume the graph $G=T$ is a tree and consider partitions of vertices in a tree

V=V_{0}\sqcup V_{1}\sqcup\cdots\sqcup V_{r}

into $r+1$ non-empty parts. We can also partition edges

E=E_{1}\sqcup E_{2}\sqcup\cdots\sqcup E_{r}

into $r$ non-empty parts.

0. We give a bijection between:

i)

Partitions of vertices into $r+1$ non-empty parts, each part consisting of independent vertices, and
ii)

partitions of edges into $r$ non-empty parts (and no further requirements).

Example 1.1.

Any tree has a unique partition of the vertices into two independent sets (two colors modulo $S_{2}$ ). This corresponds to the partition of the edges into one part (one color).

Moreover the above generalizes in two directions.

1. Define a set of vertices $A\subseteq V$ to be $s$ -scattered if the distance between any two vertices is $\geq s$ . Similarly we have the notion of a set of edges $B\subseteq E$ being $s$ -scattered. We show, Theorem 3.6, for a tree and for $r,s\geq 1$ there is a bijection between:

i)

Partitions of vertices into $r+1$ non-empty parts, each part being $s+1$ -scattered, and
ii)

Partitions of edges into $r$ non-empty parts, each part being $s$ -scattered

2. Stacked simplicial complexes is a generalization of trees to higher dimensions. Stacked polytopes [8] with the triangulation coming from a stacking of simplices, induce a well-known subclass of stacked simplicial complexes. The main feature of stacked simplicial complexes for us is that between any two facets (maximal faces) there is a unique path. Similarly between any pair of vertices there is a unique path of facets. We show:

Theorem 3.6 Let $X$ be a stacked simplicial complex of dimension $d$ and $r,s\geq 1$ . There is a bijection between:

i)

Partitions of vertices of $X$ into $r+d$ non-empty parts, each part being $s+1$ -scattered,
ii)

Partitions of facets of $X$ into $r$ non-empty parts, each part being $s$ -scattered

The results on trees appear quite non-trivial even for the simplest of graphs, the line graph. By considering larger and large line graphs, we get in the limit results for partitions of natural numbers.

Theorem 4.1 There is a bijection between partitions of the natural numbers ${\mathbb{N}}$ into $r$ non-empty parts, each part being $s$ -scattered, and partitions of ${\mathbb{N}}$ into $r+1$ non-empty parts, each part being $s+1$ -scattered.

As a consequence we get for instance:

Corollary 4.3 There is a bijection between partitions of ${\mathbb{N}}$ into two parts $A_{0}\sqcup A_{1}$ (each part automatically $1$ -scattered) and partitions of ${\mathbb{N}}$ into $d+1$ parts $B_{0}\sqcup\cdots\sqcup B_{d}$ , each part being $d$ -scattered.

(A trivial special case by repeated use of Theorem 4.1, starting from $r=s=1$ and successively increasing $r,s$ : There is a unique partition of ${\mathbb{N}}$ into $r$ parts, each being $r$ -scattered. These parts are of course the congruence classes modulo $r$ .)

Let us explain in more detail the bijection, first for trees, and secondly in an example of triangulations of polygons. Such triangulations are stacked simplicial complexes of dimension two.

Given a tree and a partition of the vertices $V$ , make a partition of the edges $E$ as follows: If $v$ and $w$ are vertices consider the unique path in $T$ linking $v$ and $w$ . Let $f$ , respectively $g$ , be the edge incident to $v$ , respectively $w$ , on this path. If (i) $v$ and $w$ are in the same part $V_{i}$ of $V$ and (ii) no other vertex on this path is in the part $V_{i}$ , then put $f$ and $g$ into the same part of $E$ , and write $f\sim_{E}g$ . The partition of edges is the equivalence relation generated by $\sim_{E}$ .

Conversely given a partition of the edges $E$ , make a partition of the vertices $V$ as follows: Let $v$ and $w$ be distinct vertices, and consider again the path from $v$ to $w$ . Let the edges $f,g$ be as above. If (i) the edges $f$ and $g$ are distinct (equivalently the vertices $v,w$ are independent), (ii) $f$ and $g$ are in the same part $E_{j}$ , and (iii) no other edge on this path is in the part $E_{j}$ , then put $v$ and $w$ in the same part of $V$ , and write $v\sim_{V}w$ . The partition of vertices is the equivalence relation generated by $\sim_{V}$ .

Example 1.2.

In Figure 1 we partition the edges into two parts, colored red and black. The vertices are then partitioned into three parts, each consisting of independent vertices. The partition of the vertex set of the first tree is

\{1,3,5\}\cup\{2,6\}\cup\{4\},

and that of the second tree is

\{1,3,5,8,10\}\cup\{2,4,7\}\cup\{6,9\}.

Figure 1. Partitions of edges into two parts and corresponding partitions of vertices into three parts

Example 1.3.

Consider now a triangulation of the heptagon, which is a stacked simplicial complex. We partition the facets into two parts: three blue and two red, Figure 2. This corresponds, in a similar way as for trees, to a partition of the vertices, now into four parts of independent vertices: two yellow vertices $3,7$ , three red $1,4,6$ , one blue $2$ , and one green $5$ . In fact the facet parts here are $2$ -scattered and so each of the vertex parts will even be $3$ -scattered.

Note that the colors have no real significance here, they are just added for pedagogical and visualisation purposes. In particular there is no connection between colors of facets and colors of vertices.

Figure 2. Partition of facets into two parts and corresponding partition of vertices into four parts

Our results here came out of work in [7] by M.Orlich and the author on triangulations of polygons and more generally on stacked simplicial complexes.

Results related to the present article are to be found in enumerative combinatorics. A first result in this direction is W.Yang [14] considering trees on $n+1$ vertices, showing that partitions into independent sets of vertices are counted by Bell numbers $B_{n}$ . He also considers generalized $d$ -trees and show that partitions into independent sets of vertices of such a tree with $n+d$ vertices is counted by the Bell number $B_{n}$ . A generalized $d$ -tree is the same as the edges (or $1$ -skeleton) of a stacked simplicial complex of dimension $d$ .

B.Duncan and R.Peele [4] consider enumerative aspects of partitions of vertices of graphs into independent sets. For trees they show that partitions of a tree with $n+1$ vertices into $k+1$ independent parts are in bijection with partitions of an $n$ -set into $k$ parts. They give, mostly illustrated by a large example, a bijection which is essentially the same as we give. But we gain here the conceptual advantage of expressing this in terms of edges of the tree. Their statement involves choosing an arbitrary vertex $r$ , a root, and then relating independent vertex partitions of $V$ to partitions of $V\backslash\{r\}$ . Their less conceptual form may also be the reason they do not have the extension to $s$ -scattered parts. [9] and [11] considers enumerative aspects of graphical Bell numbers further, and the latter also generalized $d$ -trees.

W.Chen, E.Deng, and R.Du [2] consider ordered sets and use the terminology $m$ -regular for $m$ -scattered. They show that partitions of an ordered $n+1$ -set into $k+1$ parts which are $m+1$ -regular are in bijection with partitions of an $n$ -set into $k$ parts which are $m$ -regular. This corresponds to the case of line graphs, and for this case the bijection they give is essentially the same as ours. We discuss this in Section 4. They also show that we have bijections in this case when considering non-crossing partitions. Related enumerative results are found in [13] and [3]. The book [12] is a comprehensive account of partitions of ordered sets.

Remark 1.4.

The results of this paper dropped out of investigations in [7], concerning Stanley-Reisner rings of stacked simplicial complexes. Among such simplicial complexes there are certain separated models, and from these models we obtain every stacked simplicial complex by partitioning the vertices into independent classes and then collapsing each class into a single vertex. This is done such that the essential algebraic and homological properties of the associated rings are preserved.

The algebra involved here should generalize to much larger classes of simplicial complexes. Polarizing Artin monomial ideals gives separated models, and in [1] we describe all such for polarizations of any power of a graded maximal ideal in a polynomial ring. The case of stacked simplicial complex is the case of the second power. Polarizing Artin monomial ideals in general still goes much further than [1]. The results in the present article therefore likely have vast generalizations, see Subsection 8.2 of [6]. This should involve partitions of vertices, but it is a challenge what other ingredients and statements should be involved.

Let us also mention that the main result of [6] is a fundamental theorem of combinatorial geometry of monomial ideals. Namely that any polarization of an Artin monomial ideal, via the Stanley-Reisner correspondence, is a simplicial complex whose topological realization is a ball.

We describe the organization of this article. Section 2 gives the notion of stacked simplicial complex of dimension $d$ . It characterizes these, Proposition 2.9, as the simplicial complexes for which there is a unique path between any pair of facets, and the number of vertices is $d$ more then that number of facets. Section 3 describes the correspondence between partitions of vertices and partitions of facets, and shows our main Theorem 3.6. In the last Section 4 we specialize these results to bijections between partitions of natural numbers, the parts having lower bound requirements on minimal distance.

Acknowledgements. I thank M.Orlich for making Figure 1.

2. Stacked simplicial complexes

We recall the notion of stacked simplicial complex. Its main feature from our perspective, is that it generalizes the property of trees, that for every two faces, there is a unique path between them.

2.1. Paths

Let $V$ be a finite set. A simplicial complex $X$ on $V$ is a family of subsets of $V$ closed under taking subsets of each element of the family. So for an element $F\in X$ and $G\subseteq F$ , then also $G\in X$ . The elements of $V$ are vertices, the elemens of $X$ are faces, and the maximal elements of $X$ for the inclusion relation are facets. A simplicial complex has a natural geometric realization. A face with $d$ vertices is then realized as a simplex of dimension $d-1$ .

Given any family $Y$ of subsets of $V$ , the simplicial complex generated by $Y$ is the family of all subsets $G$ of $V$ such that $G\subseteq F$ for some $F\in Y$ .

Definition 2.1.

A pure simplicial complex (i.e., where all the facets have the same dimension) is stacked if there is an ordering of its facets $F_{0},F_{1},\ldots,F_{k}$ such that if $X_{p-1}$ is the simplicial complex generated by $F_{0},\ldots,F_{p-1}$ , then for $p\geq 1$ the facet $F_{p}$ is attached to $X_{p-1}$ along a single codimension one face of $F_{p}$ . So we may write $F_{p}=G_{p}\cup\{v_{p}\}$ where $G_{p}$ is a codimension one face of $X_{p-1}$ and $v_{p}$ is not a vertex of $X_{p-1}$ . The vertex $v_{p}$ is the free vertex of $F_{p}$ , in this stacking order.

Remark 2.2.

This is a special case of shellable simplicial complexes, see [10, Subsection 8.2]. It is not the same as the notion of simplicial complex being a tree as in [5], even if the tree is pure. Rather the notion of stacked simplicial complex is more general. For instance the triangulation of the heptagon given in Figure 2, is not a tree in the sense of [5], since removing the triangles $234$ and $257$ one has no facet which is a leaf.

Definition 2.3.

A (gallery) walk in a pure simplicial complex, is a sequence of facets $f_{1},\ldots,f_{p}$ such that each $g_{i}=f_{i}\cap f_{i+1}$ has codimension one in $f_{i}$ (and hence also in $f_{i+1}$ ). The left end vertex is the single element of $f_{1}\backslash f_{2}$ and the right end vertex is the single element of $f_{p}\backslash f_{p-1}$ .

If $f_{i}\cap f_{i+1}=f_{j}\cap f_{j+1}$ for some $1\leq i<j<p$ , we can make a shorter walk from $f_{1}$ to $f_{p}$ . If $f_{i}\neq f_{j+1}$ then

f_{1},\ldots,f_{i},f_{j+1},\ldots,f_{p}

is a shorter walk. If $f_{i}=f_{j+1}$ , then

f_{1},\ldots,f_{i-1},f_{j+1},\ldots,f_{p}

is a shorter walk from $f_{1}$ to $f_{p}$ .

Definition 2.4.

A path is a walk $f_{1},f_{2},\ldots,f_{p}$ where all the $f_{i}\cap f_{i+1}$ are distinct. The length of the path is $p-1$ .

By the explanation before this definition, any walk from $f_{1}$ to $f_{p}$ may be reduced to a path between $f_{1}$ and $f_{p}$ .

Lemma 2.5.

Let $X$ be a stacked simplicial complex and $f_{1},f_{2},\ldots,f_{p}$ a path in $X$ .

a.

Let $f_{i}$ come last among the facets on the path, for a stacking order of $X$ , and let $v$ be its free vertex. Then either $f_{i}=f_{1}$ and $\{v\}=f_{1}\backslash f_{2}$ or $f_{i}=f_{p}$ and $\{v\}=f_{p}\backslash f_{p-1}$ .
b.

All the $f_{i}$ are distinct.

Proof.

a. If $1<i<p$ , then $f_{i}=(f_{i}\cap f_{i-1})\cup(f_{i}\cap f_{i+1})$ , and so $v$ would be on two facets. But this is not so. So $f_{i}$ must be one of the end vertices and $\{v\}$ must be as above.

b. If $f_{1}=f_{p}$ then $p\geq 3$ and as $v$ is on only one facet on the path, $f_{1}\cap f_{2}=f_{1}\backslash\{v\}=f_{p}\backslash\{v\}=f_{p-1}\cap f_{p}$ , contradicting that we have a path.

If $1\leq j<k\leq p$ , then $f_{j},f_{j+1},\ldots,f_{k}$ is also a path and so $f_{j}$ and $f_{k}$ must be distinct. ∎∎

Definition 2.6.

Let $X$ be a pure simplicial complex, and $h,k$ faces in $X$ such that $h\cup k$ is not contained in any codimension one face. A path between $h$ and $k$ , written

h|f_{1},\ldots,f_{p}|k

is a path $f_{1},\ldots,f_{p}$ such that

h\subseteq f_{1},\,h\not\subseteq f_{1}\cap f_{2},\quad k\subseteq f_{p},\,k\not\subseteq f_{p}\cap f_{p-1}.

The face-distance (or simply distance) between $h$ and $k$ is $p$ . In particular, if $h,k$ are contained in a common facet, and not in a codimension one face, their distance is one. If $h\cup k$ is contained in a codimension one face, a path between is an empty path consisting of no facets, written $h||k$ . Their distance is defined to be zero.

We mostly use this definition when $h$ and $k$ are single vertex sets $\{v\}$ and $\{w\}$ , in which case we simply write $v$ instead of $\{v\}$ , and similarly for $w$ .

Lemma 2.7.

Let $X$ be a stacked simplicial complex, and $h,k$ faces of $X$ .

a.

In a path $f_{1},\ldots,f_{p}$ between $h$ and $k$ we have $h\not\subseteq f_{i}\cap f_{i+1}$ and $k\not\subseteq f_{i}\cap f_{i+1}$ for each $1\leq i<p$ .
b.

Let $f$ be the facet on the path which is last for a stacking order on $X$ . The free vertex of $f$ is in $h$ or in $k$ .

Proof.

a. Suppose for $h$ there was an $r$ such that $h\subseteq f_{r}\cap f_{r+1}$ , and let $r$ be minimal such. Then $r\geq 2$ and consider the path

f_{1},\ldots,f_{r}

Let $f$ be the last among these facets in the stacking order of $X$ , and $v$ its free vertex. Then $f=f_{1}$ or $f=f_{r}$ . If $f=f_{1}$ , since $h\subseteq f_{1}$ and $h\not\subseteq f_{1}\cap f_{2}$ , $h$ must contain the single vertex in $f_{1}\backslash f_{1}\cap f_{2}$ , and this vertex is $v$ . But then $v$ is also in $f_{r}$ . Since $v$ is only on a single facet, then $f_{r}=f_{1}$ , and this contradicts all facets on a path being distinct.

b. The last facet is one of the end facets, say $f_{1}$ . If $p=1$ then $f_{1}=h\cup k$ and the statement holds. If $p\geq 2$ , the $f_{1}=h\cup(f_{1}\cap f_{2})$ and since $v$ is not on two facets in the path, we get $v\in h$ . ∎∎

2.2. Existence and uniqueness of paths

Proposition 2.8.

Let $h,k$ be faces with union $h\cup k$ not contained in any codimension one face. Then there is a unique path between them.

Proof.

Existence: If $h\cup k$ is a facet $f$ , then $h|f|k$ is a path between them. Assume then $h\cup k$ is not contained in a facet.

Let $f$ be a facet containing $h$ and $f^{\prime}$ a facet containing $k$ . Let

f=f_{1},\ldots,f_{p}=f^{\prime}

be the path between them. Let $i$ be maximal such that $h\subseteq f_{i}$ . Let $j\geq i$ be minimal such that $k\subseteq f_{j}$ . Then we have a path from $h$ to $k$ :

h|f_{i},\ldots,f_{j}|k.

Uniqueness: Let

h|f_{1},\ldots,f_{p}|k,\quad h|f_{1}^{\prime},\ldots,f_{q}^{\prime}|k

be paths with $p,q\geq 1$ .

Let $f$ be the last of the facets in these paths, in the stacking order, and with free vertex $v$ . By Lemma 2.7, $v$ is in say $h$ . As $v$ is in a single facet on these paths, we get $f=f_{1}^{\prime}=f_{1}$ . If $p=q=1$ we are done.

i) Suppose exactly one of $p,q$ is $\geq 2$ , say $p=1$ (and $q\geq 2$ ). Then $f_{1}^{\prime}=f_{1}=h\cup k$ so $k\subseteq f_{1}^{\prime}$ . Since $k\not\subseteq f_{1}^{\prime}\cap f_{2}^{\prime}$ the free vertex $v$ is also in $k$ , and so in $f_{q}^{\prime}$ . Then $f_{q}^{\prime}=f=f_{1}^{\prime}$ , which is not so for a path.

ii) Suppose the paths have $p,q\geq 2$ . Let

g:=f\backslash\{v\}=f_{1}\cap f_{2}=f_{1}^{\prime}\cap f_{2}^{\prime}.

Since $k\not\subseteq f_{1}\cap f_{2}=g$ , we have $g\cup k$ not included in a codimension one face. So we get paths

g|f_{2},\ldots,f_{p}|k,\quad g|f_{2}^{\prime},\ldots,f_{q}^{\prime}|k.

By induction on length, these paths are equal. ∎∎

The following generalizes the well-known situation for trees.

Proposition 2.9.

Let $X$ be a pure simplicial complex of dimension $d$ with $n$ facets and $v$ vertices. Then $X$ is stacked iff $v=n+d$ and between every pair of facets there is a unique path.

Proof.

When $X$ is stacked it is clear from construction that $v=n+d$ . By Proposition 2.8 there is a unique path between any two facets.

Conversely, assume $v=n+d$ and that between every pair of facets there is a unique path. Choose a facet $f$ , order the facets of $X$ :

(1)

f=f_{1},f_{2},\ldots,f_{n}

such that the distance $\text{dist}(f,f_{i})\leq\text{dist}(f,f_{j})$ for $i\leq j$ . Let $Y_{p}$ be the simplicial complex generated by $f_{1},\ldots,f_{p}$ . Consider the path from $f$ to $f_{p+1}$ :

f=f^{1},f^{2},\ldots,f^{r}=f_{p+1}.

Here all facets except the last $f^{r}$ are in $Y_{p}$ as they must be listed before $f_{p+1}$ in (1) due to distance. Since $f^{r-1}\cap f^{r}$ has codimension one in $f_{p+1}$ , when passing from $Y_{p}$ to $Y_{p+1}$ we have added at most one new vertex. Since $Y_{n}=X$ has $d+n$ vertices, we must have added exactly one new vertex each time, and so $f_{n}$ has a single free vertex, and $Y_{n-1}$ has $d+n-1$ vertices.

We show that between any two facets of $Y_{n-1}$ there is a unique path. By induction $f_{1},\ldots,f_{n-1}$ is a stacking order for $Y_{n-1}$ , and so (1) gives that $Y_{n}$ is also stacked.

Let $f_{r},f_{s}$ be two facets in $Y_{n-1}$ . Consider the path $f_{r}=f_{1}^{\prime},\ldots,f_{p}^{\prime}=f_{s}$ in $X=Y_{n}$ . If the last facet $f_{n}$ is on this path, say $f_{n}=f_{t}^{\prime}$ , then $1<t<p$ and

f_{n}=f_{t}^{\prime}=(f_{t}^{\prime}\cap f_{t-1}^{\prime})\cup(f_{t}^{\prime}\cap_{t+1})\subseteq Y_{n-1}.

This is not so, and so the path from $f_{r}$ to $f_{s}$ is entirely in $Y_{n-1}$ . ∎∎

The facet-distance between two facets $f,g$ is defined to be the length of the path $f|f_{1},\ldots,f_{p}|g$ between them (note that $f=f_{1}$ and $g=f_{p}$ ), and this length is $p-1$ .

Remark 2.10.

Note that for two facets $f,g$ their face-distance is one more than their facet-distance. It may seem awkward to have two notions of distance. But by looking at the graph:

it is natural. The facet-distance between $f$ and $g$ is one, and the face-distance between $v$ and $w$ is two. (And the face-distance between $f$ and $g$ is also two.)

2.3. Distance neighborhoods

Let $X$ be a pure simplicial complex. Choose a codimension one face $g$ in $X$ . For $m\geq 1$ , let $X_{m}$ be the simplicial complex generated by those facets of $X$ whose face-distance to $g$ is $\leq m$ . In particular $X_{0}=\emptyset$ and the facets of $X_{1}$ are the facets of $X$ containing $g$ . Let $V_{0}$ be the vertices of $g$ and $V_{m}$ the vertices of $X_{m}$ for $m\geq 1$ .

Lemma 2.11.

Assume $X$ is a stacked simplicial complex. For $m\geq 1$ , if $v\in V_{m}\backslash V_{m-1}$ , there is a unique facet $f_{v}$ in $X_{m}$ containing $v$ , and $f_{v}\backslash\{v\}$ is a subset of $V_{m-1}$ .

Proof.

Let $f_{1}$ be a facet in $X_{m}$ containing $v$ , and

f_{1}|f_{1},\ldots,f_{r}|g

the unique path from $f_{1}$ to $g$ . We have $r\leq m$ . Let $s$ be maximal with $v\in f_{s}$ . Then in $X_{m}$ :

v|f_{s},\ldots,f_{r}|g

is the unique path from $v$ to $g$ . Since $v\in V_{m}\backslash V_{m-1}$ we must have $r-s+1=m$ , and so $r=m$ and $s=1$ . Then $f_{1}$ is the first facet in the unique path from $v$ to $g$ and $f_{1}\backslash\{v\}\subseteq f_{2}\subseteq V_{m-1}$ . ∎∎

Corollary 2.12.

$X_{m}$ is a stacked simplicial complex on $V_{m}$ .

Proof.

Let $f_{1},\ldots,f_{r}$ be any ordering of the facets in $X_{m}$ such that the face-distance between $g$ and $f_{i}$ is weakly increasing with $i$ . Choose $1\leq k\leq r$ and let $d$ be the distance from $g$ to $f_{k}$ . The facets $f_{1},\ldots,f_{k}$ are then all in $X_{d}$ . Let $f_{1}^{\prime},\ldots,f_{d}^{\prime}=f_{k}$ be the unique path from $g$ to $f_{k}$ . Then:

•

If $d\geq 2$ then $f_{d-1}^{\prime}=f_{i}$ for some $i<k$ ,
•

$f_{k}=f_{v}$ for some $v\in V_{d}\backslash V_{d-1}$ ,
•

$f_{i}\cap f_{k}=f_{k}\backslash\{v\}$ ,
•

By Lemma 2.11, $v$ is in none of the $f_{i}$ for $i<k$ .

Thus $f_{1},\ldots,f_{r}$ is a stacking order for $X_{m}$ . ∎∎

3. Bijections between partitions of facets and of vertices

We show how partitions of facets and partitions of vertices into independent sets correspond, and we show that this correspondence is really a bijection. Our arguments are by induction on the distance neighbourhood $X_{m}$ . We develop some lemmata before the proof of the main theorem.

3.1. Bijections between partitions

Definition 3.1.

Let $X$ be a be a stacked simplicial complex with vertex set $V$ , and $s$ an integer $\geq 1$ . A subset $A\subseteq V$ is $s$ -scattered if the face-distance between any two distinct vertices in $A$ is $\geq s$ . The vertex set is independent if it is $2$ -scattered, i.e. no two vertices in $A$ are on the same facet.

Similarly a subset $B$ of the facets is $s$ -scattered if the facet-distance between any two facets in $B$ is $\geq s$ .

We consider partitions of the vertices

(2)

V=V_{1}\sqcup V_{2}\sqcup\cdots\sqcup V_{r}

into non-empty disjoint sets. Note that the order here is not relevant, so if we switch $V_{i}$ and $V_{j}$ we have the same partition.

Remark 3.2.

If the $V_{i}$ are independent, this is almost the same as a graph coloring of vertices, but not quite. A coloring of the vertices $V$ is a map $f:V\rightarrow C$ where $C=\{c_{1},\ldots,c_{r}\}$ is a set of colors, such that each inverse image $f^{-1}(c_{i})$ is a set of independent vertices. The symmetric group $S_{r}$ acts on colorings by permuting the colors $c_{1},\ldots,c_{r}$ . So a partition as above (2) is an orbit for the action of $S_{r}$ . The class of such orbits, or equivalently of partitions (2) are also called non-equivalent vertex colorings, see [9].

We also consider partitions of the facets

F=F_{1}\sqcup F_{2}\sqcup\cdots\sqcup F_{s}.

3.1.1. From vertex partitions to facet partitions.

Now we make a correspondence as follows. Given a partition of $V$ into non-empty independent sets, given by an equivalence relation $\sim_{V}$ . For ease of following the arguments, we will think of each part as having a specific color. Make a partition of $F$ as follows. Let $f$ and $f^{\prime}$ be distinct facets. Consider the unique path in $X$ between them:

f=f_{1},\ldots,f_{p}=f^{\prime},

and let $v$ and $w$ be respectively the left and right end vertices. If $v$ and $w$ have the same color, say blue, and none of the facets $f_{2},\ldots,f_{p-1}$ has any blue vertex, then write $f\sim^{\prime}_{F}f^{\prime}$ . This means that $f$ and $f^{\prime}$ will be in the same part of facets, these facets get the same color. The colors of vertices and edges are however unrelated, so the facets $f$ and $f^{\prime}$ get some color unrelated to blue. The relation $\sim_{F}$ on $F$ is the equivalence relation generated by $\sim_{F}^{\prime}$ .

3.1.2. From facet partitions to vertex partitions

Conversely given a partition of the facets $F$ , given by an equivalence relation $\sim_{F}$ . Make a partition of the vertices $V$ as follows. Let $v$ and $w$ be independent vertices, and consider the path from $v$ to $w$ :

v|f_{1},\ldots,f_{p}|w.

If $f_{1}$ and $f_{p}$ have the same color, say green, and none of the facets $f_{2},\ldots,f_{p-1}$ are green, then let $v\sim^{\prime}_{V}w$ . The relation $\sim_{V}$ is the equivalence relation generated by $\sim^{\prime}_{V}$ . See Example 1.2.

We want to show that these correspondences are inverse to each other. To do this we show:

A. From an equivalence relation $\sim_{F}$ on $F$ , we have constructed the equivalence relation $\sim_{V}$ on $V$ . We show that the equivalence relation $\sim_{V}$ in turn induces the equivalence relation $\sim_{F}$ by showing:

1.

If $v\sim_{V}w$ are distinct and, say blue, and

$v|f_{1},\ldots,f_{p}|w$

where none of $f_{2},\ldots,f_{p-1}$ have a blue vertex, then $p\geq 2$ and $f_{1}\sim_{F}f_{p}$ (in the original equivalence relation for $F$ )
2.

If $f\sim_{F}g$ in the original relation with $f,g$ distinct, there is a sequence $f=f_{0},f_{1},\ldots,f_{p}=g$ such that

(3) $f_{0}\sim_{F}^{\prime}f_{1}\sim_{F}^{\prime}\cdots\sim_{F}^{\prime}f_{p}$

where $\sim^{\prime}_{F}$ is the relation constructed from $\sim_{V}$ .
3.

We also show that if the original $\sim_{F}$ is $s$ -scattered, then $\sim_{V}$ is $s+1$ -scattered.

B. From an equivalence relation $\sim_{V}$ on $V$ , we have constructed the equivalence relation $\sim_{F}$ on $F$ . We show that this in turn induces the equivalence relation $\sim_{V}$ , by showing:

1.

If we have a path with $p\geq 2$

$v|f_{1},\ldots,f_{p}|w$

where $f_{1}$ and $f_{p}$ are, say green, and none of $f_{2},\ldots,f_{p-1}$ are green, then $v\sim_{V}w$ (in the original equivalence relation for $V$ ).
2.

If $v\sim_{V}w$ in the original relation, there is a sequence $v=v_{0},v_{1},\ldots,v_{p}=w$ such that

(4) $v_{0}\sim_{V}^{\prime}v_{1}\sim_{V}^{\prime}\cdots\sim_{V}^{\prime}v_{p},$

where $\sim_{V}^{\prime}$ is the relation constructed from $\sim_{F}$ .
3.

We also show that if the original $\sim_{V}$ is $s+1$ -scattered, then $\sim_{F}$ is $s$ -scattered.

3.2. Induction arguments on $X_{m}$

We show A, B for the $X_{m}$ by induction on $m$ . For this we need some lemmata.

Lemma 3.3.

Given a partition of the facets $F$ , and consider the relation $\sim_{V}^{\prime}$ on vertices, constructed above in Subsection 3.1.2. Let $v\in V_{m}\backslash V_{m-1}$ , and $u,w$ distinct in $V_{m}$ . If $v\sim_{V}^{\prime}u$ and $v\sim_{V}^{\prime}w$ , then $u\sim_{V}^{\prime}w$ .

Proof.

We show first that $u,w$ are independent. Recall, Lemma 2.11, that $f_{v}$ is the unique facet on $X_{m}$ containing $v$ .

i) Suppose $u,w$ were on the same face $f$ . Let

f_{v}=f_{1},\ldots,f_{p}=f

be the path from $f_{v}$ to $f$ . If $u,w$ are both on $f_{p-1}$ we may make a shorter path. So we may assume $u,w\in f_{p}$ and not both in $f_{p}\cap f_{p-1}$ . Assume then that $u$ is the right end vertex of $f_{p}$ . Then the above must be the unique path from $v$ to $u$ . Since $v\sim_{V}^{\prime}u$ , $f_{1}$ and $f_{p}$ have the same color, say green. We have $w\in f_{p-1}$ and $w\not\in f_{1}$ (since $v,w$ are independent). Let $r\geq 2$ be minimal such that $w\in f_{r}$ . We then have a path

v|f_{1},\ldots,f_{r}|w

and this is the unique path from $v$ to $w$ . By definition of $\sim_{V}^{\prime}$ , $f_{1}$ and $f_{r}$ also have the same color, which must be green. But by definition of $v\sim_{V}^{\prime}u$ there should not have been any green color between the faces $f_{1}$ and $f_{p}$ . Hence $u,w$ must be independent.

ii) Let

(5)

v|f_{1},\ldots,f_{p}|u,\quad v|f^{\prime}_{1},\ldots,f^{\prime}_{q}|w,

be the unique paths where $f_{1}=f_{1}^{\prime}$ by Lemma 2.11. Here $f_{1}$ and $f_{p}$ have the same color, say green, and $f_{1}^{\prime}(=f_{1})$ and $f_{q}^{\prime}$ have the same color, also green, and none of the facets in between have color green. None of the two paths is then a subpath of the other. Hence there is an $r$ such that $f_{r}\neq f_{r}^{\prime}$ , and let $r$ be minimal such, so $r\geq 2$ . If $r\geq 3$ there is a walk

(6)

u|f_{p},\ldots,f_{r},f_{r-1}=f_{r-1}^{\prime},f_{r}^{\prime},\ldots,f_{q}^{\prime}|w

where $f_{p}$ and $f_{q}^{\prime}$ are the only green facets. If $r=2$ then $f_{2},f_{2}^{\prime}\supseteq f_{1}\backslash\{v\}$ and so $f_{2}\cap f_{2}^{\prime}$ has codimension one. There is then a walk

(7)

u|f_{p},\ldots,f_{2},f_{2}^{\prime},\ldots,f_{q}^{\prime}|w

where only the end facets are green. By reducing these walks like before Definition 2.4, we get a path giving $u\sim_{V}^{\prime}w$ . ∎∎

Note. The process of suitably cutting the sequences (5), then splicing them, (6) or (7), and lastly reducing to a path, will be used a couple of times and we call it cut-splice-reduction.

Lemma 3.4.

Given a partition of $V$ into independent sets, and the relation $\sim_{F}^{\prime}$ constructed as in Subsection 3.1.1. Let $f$ be a facet in $X_{m}$ which is not in $X_{m-1}$ . If $f\sim^{\prime}_{F}g$ and $f\sim^{\prime}_{F}h$ , then $g\sim^{\prime}_{F}h$ .

Proof.

Note first that $f$ is $f_{v}$ for a unique $v$ . By Lemma 2.11 any path in $X_{m}$ starting from $f$ must have left end vertex $v$ . So we have the following paths

v|f=f_{1},\ldots,f_{p}=g|u,\quad v|f=f_{1}^{\prime},\ldots,f_{q}^{\prime}=h|w

where $v,u$ have the same color blue and none of $f_{2},\ldots,f_{p-1}$ have blue vertices. Similarly $v,w$ have the same color blue, and none of $f^{\prime}_{2},\ldots,f^{\prime}_{q-1}$ have blue vertices. None of these paths is then a subpath of the other, and hence there is $r\geq 2$ such that $f_{r}\neq f_{r}^{\prime}$ and let $r$ be minimal such. If $r\geq 3$ , as above (6), we get a walk

w|h=f_{q}^{\prime},\ldots,f_{r}^{\prime},f^{\prime}_{r-1}=f_{r-1},f_{r},\ldots,f_{p}=g|u,

where none of the intermediate facets have blue vertices. If $r\geq 2$ , as above (7), get a walk

(8)

u|f_{p},\ldots,f_{2},f_{2}^{\prime},\ldots,f_{q}^{\prime}|w.

Aagain as above these walks may be reduced to paths (cut-splice-reduction) and so $g\sim^{\prime}_{F}h$ . ∎∎

Lemma 3.5.

Suppose the relation $\sim_{F}$ , induces the relation $\sim_{V}$ on $V$ . Consider the subcomplex $X_{m}$ . i) The restricted relation $\sim_{F}|_{X_{m}}$ then induces the restricted relation $\sim_{V}|_{X_{m}}$ . Similarly, ii) if $\sim_{V}$ induces $\sim_{F}$ the restricted relation $\sim_{V}|_{X_{m}}$ induces the restricted relation $\sim_{F}|_{X_{m}}$ .

Proof.

Note that if $v,w\in V_{m}$ and $v\sim_{V}^{\prime}w$ and $v|f_{1},\ldots,f_{p}|w$ is the path in $X$ between them, then since $X_{m}$ is stacked, this path is entirely in $X_{m}$ .

i) Suppose given $\sim_{F}$ . Let $v,w\in V_{m}$ such that $v\sim_{V}w$ , so we have

v=v_{0}\sim^{\prime}_{V}v_{1}\sim^{\prime}_{V}\cdots\sim^{\prime}_{V}v_{t}=w.

Let $\ell$ minimal such that all $v_{i}\in V_{\ell}$ . If $\ell>m$ then some $v_{i}\in V_{\ell}\backslash V_{\ell-1}$ where $0<i<t$ . By the above Lemma 3.3 we may replace $v_{i-1}\sim^{\prime}_{V}v_{i}\sim^{\prime}_{V}v_{i+1}$ by $v_{i-1}\sim^{\prime}_{V}v_{i+1}$ . In this way we may reduce the above so all $v_{i}\in V_{m}$ , and thus $\sim_{F}|_{X_{m}}$ induces $\sim_{V}|_{X_{m}}$ .

ii) Suppose given $\sim_{V}$ . Let $f,g\in X_{m}$ and $f\sim_{F}g$ , so we have

f=f_{1}\sim^{\prime}_{F}f_{2}\sim^{\prime}_{F}\cdots\sim^{\prime}_{F}=g.

Again using Lemma 3.4 above we may reduce to all $f_{i}\in X_{m}$ . ∎∎

3.3. The main theorem

Theorem 3.6.

Let $X$ be a stacked simplicial complex of dimension $d$ , with vertex set $V$ and facet set $F$ , and $s$ an integer $\geq 1$ . The correspondences in Subsections 3.1.1 and 3.1.2 give a one-to-one correspondence between partitions of the vertices $V$ into $r+d$ non-empty sets, each $s+1$ -scattered, and partitions of the facets $F$ into $r$ non-empty sets, each $s$ -scattered.

Proof.

A. Assume we have started from a partition $\sim_{F}$ of facets $F$ , and have constructed the equivalence relation $\sim_{V}$ corresponding to a partition of the vertices $V$ . We show properties A1, A2, A3 for $X_{m}$ by induction on $m$ , so that $\sim_{V}$ in turn induces the original partition $\sim_{F}$ .

Property A1: Suppose $v\sim_{V}w$ are distinct and, say blue, and let $m$ be minimal such that $v,w\in X_{m}$ . We may assume $v\in V_{m}\backslash V_{m-1}$ . Suppose we have a path from $v$ to $w$ :

v|f_{1},\ldots,f_{p}|w

where $f_{2},\ldots,f_{p-1}$ have no blue vertices. We want to show $f_{1}\sim_{F}f_{p}$ (in the original equivalence relation for $F$ ), that is, they have the same color, say green. Let $f_{1}$ have color green, and let

(9)

v=v_{0}\sim^{\prime}_{V}v_{1}\sim^{\prime}_{V}\cdots\sim^{\prime}_{V}v_{t}=w.

By Lemma 3.5 we may assume all $v_{i}\in X_{m}$ . Also, if $v_{i}\in V_{m}\backslash V_{m-1}$ for some $0<i<t$ , we may by Lemma 3.3 reduce to a shorter such sequence. We may therefore assume the $v_{i}$ for $0<i<t$ are in $V_{m-1}$ . If $t=1$ , then $f_{1}\sim_{F}f_{p}$ by definition of $\sim_{V}^{\prime}$ , and we are done. So assume $t\geq 2$ and consider the path in $X_{m}$ :

(10)

v=v_{0}|f_{1}^{\prime},\cdots,f_{q}^{\prime}|v_{1}.

Then $f_{1}^{\prime}=f_{1}$ and $f_{q}^{\prime}$ have the same color green by definition of $\sim_{V}^{\prime}$ and none of $f_{2}^{\prime},\ldots,f^{\prime}_{q-1}$ are green. Both $v=v_{0}$ and $v_{1}$ are blue. We claim that none of $f_{2}^{\prime},\ldots,f_{q-1}^{\prime}$ has any blue vertex. Otherwise, let $2\leq r\leq q-1$ be maximal such that $f^{\prime}_{r}$ has a blue vertex $v^{\prime}$ . We get a sequence $v^{\prime}|f^{\prime}_{r},\ldots,f^{\prime}_{q}|v_{1}$ . Then $v^{\prime}\in V_{m-1}$ , since $g=f_{1}^{\prime}\backslash\{v\}\subseteq V_{m-1}$ by Lemma 2.11, and the path from $g$ to $v_{1}$ is in $V_{m-1}$ ). By induction (on $m$ ) the facets $f_{r}^{\prime}$ and $f_{q}^{\prime}$ have the same color, a contradiction. Thus none of $f_{2}^{\prime},\ldots,f_{q-1}^{\prime}$ has a blue vertex.

We claim that $v$ and $w$ are independent, which is now equivalent to show that $w$ is not in $f_{1}$ . This will give $p\geq 2$ . Recall by Lemma 2.11 that $f_{1}=f_{v}$ is the only facet in $X_{m}$ containing $v$ . If $w$ was in $f_{1}$ then $w\in f_{1}\backslash\{v\}=f_{1}^{\prime}\backslash\{v\}$ , which is $f_{1}\cap f_{2}=f_{1}^{\prime}\cap f_{2}^{\prime}$ . In particular $w\in V_{m-1}$ . By induction, since $w,v_{1}$ are in $X_{m-1}$ and are related by (9), they are either equal or independent. If equal, $v$ and $w$ are independent since $v\sim_{V}^{\prime}w$ , and so not both in $f_{1}$ . If $w$ and $v_{1}$ are independent, $w$ is not in $f_{q}^{\prime}$ . Then $q\geq 3$ , and $f_{2}^{\prime}$ has a blue vertex $w$ , contradicting that no intermediate facet in (10) has a blue vertex. The upshot is that $w$ is not in $f_{1}$ , and so $p\geq 2$ .

By cut-splice-reducing the sequences,

(11)

v|f_{1},\ldots,f_{p}|w,\quad v|f_{1}^{\prime},\ldots f_{q}^{\prime}|v_{1},(\text{ where }f_{1}=f_{1}^{\prime}),

as in Lemma 3.4 we reduce to a path

(12)

v_{1}|f_{q}^{\prime},\ldots,f_{p}|w,

where no intermediate facet has blue vertices.

Case 1: $w\in V_{m-1}$ . Then by induction on $m$ , since $v_{1}$ and $w$ are in $X_{m-1}$ , $f_{q}^{\prime}$ and $f_{p}$ have the same color green. As $f_{q}^{\prime}$ and $f_{1}^{\prime}=f_{1}$ has the same color, green, we get that $f_{1}$ and $f_{p}$ are both green.

Case 2: $w\in V_{m}\backslash V_{m-1}.$ We have $w\sim_{V}v_{1}$ , and only one of $w,v_{1}$ (i.e. $w$ ) is in $V_{m}\backslash V_{m-1}$ . Then we can start the argument of Property A1 over again and reduce to Case 1. So we conclude again that $f_{q}^{\prime}$ and $f_{p}$ have the same color. Again as $f_{q}^{\prime}$ and $f_{1}^{\prime}=f_{1}$ have the same color, green, we get that $f_{1}$ and $f_{p}$ are green.

Property A2: Suppose $f,g$ are distinct and green. Let

f=f^{1},f^{2},\ldots,f^{p}=g

be the unique path from $f$ to $g$ . Let $q>1$ be minimal such that $f^{q}$ is green, and consider the path

v|f^{1},\ldots,f^{q}|w.

Then $v\sim_{V}w$ and so are, say blue. If one $f^{r}$ where $r\in[2,q-1]$ has a blue vertex, let $r$ be minimal such, and let $v^{\prime}$ be this vertex, so we have a path

v|f^{1},\ldots,f^{r}|v^{\prime}.

By part A1, $f^{1}$ and $f^{r}$ have the same color, which must be green. This is a contradiction and so none of $f^{2},\ldots,f^{q-1}$ has a blue vertex. Thus $f^{1}\sim_{F}^{\prime}f^{q}$ . Let $f_{0}=f$ and $f_{1}=f^{q}$ . Considering now the shorter path $f^{q},f^{q+1},\ldots,f^{p}$ . By induction on length of path, there are

f^{q}=f_{1}\sim_{F}^{\prime}\cdots\sim_{F}^{\prime}f_{r}=f^{p},

and so we get part A2.

Property A3: Suppose $\sim_{F}$ is $s$ -scattered. Let $v,w$ be distinct blue vertices whose face-distance $p$ is as small as possible. We showed in the argument of Property A1 that $v$ and $w$ are independent, and so we have a path

v|f^{1},f^{2},\ldots,f^{p}|w

with $p\geq 2$ . None of $f^{2},\ldots,f^{p-1}$ can then have blue vertices. Thus $f^{1}\sim_{F}f^{p}$ by what we showed in A1, and their facet-distance is $p-1\geq s$ . Whence $p\geq s+1$ and the blue vertices are $s+1$ -scattered.

B. We have started from a partition $\sim_{V}$ of the vertices $V$ into independent sets. We have constructed from this an equivalence relation $\sim_{F}$ and corresponding partition of the facets. We show that properties B1, B2, B3 holds for $X_{m}$ by induction on $m$ , so that $\sim_{F}$ induces the original partition $\sim_{V}$ .

Property B1: Suppose $f\sim_{F}g$ , and the path from $f$ to $g$ is

(13)

v|f=f_{1},\ldots,f_{p}=g|w

where $f_{1},f_{p}$ are green and none of $f_{2},\ldots,f_{p-1}$ are green. We show that $v\sim_{V}w$ , they have the same color, say blue.

There is a sequence

f=f^{0}\sim^{\prime}_{F}f^{1}\sim^{\prime}_{F}\ldots\sim^{\prime}_{F}f^{t}=g.

Let $m$ be smallest such that $f,g$ is in $X_{m}$ . By Lemma 3.5 we may assume all $f^{i}$ are in $X_{m}$ . If some $f^{i}$ for $0<i<t$ is in $X_{m}\backslash X_{m-1}$ , by Lemma 3.4 we may reduce to a shorter sequence. So we may assume $f^{i}\in X_{m-1}$ for $0<i<t$ .

If $t=1$ then $v\sim_{V}w$ and we are done. So assume $t\geq 2$ . Since $v\in V_{m}\backslash V_{m-1}$ , by Lemma 2.11 we have $f^{0}=f_{v}$ . Now look at at the path from $f^{0}$ to $f^{1}$

v=v^{0}|f^{0}=f_{1}^{\prime},\ldots,f_{q}^{\prime}=f^{1}|v^{1},

where $v=v^{0}$ and $v^{1}$ are blue, and $f_{2}^{\prime},\ldots,f_{q-1}^{\prime}$ do not have any blue vertex. The facets $f_{1}^{\prime}=f^{0}=f$ and $f_{q}^{\prime}$ have the same color, which is green. Are there any green facets in between? Suppose $2\leq r\leq q-1$ is maximal such that $f_{r}^{\prime}$ is green. We have a path

v^{2}|f_{r}^{\prime},\cdots,f_{q}^{\prime}|v^{1}

where all $f_{r}^{\prime},\ldots,f_{q}^{\prime}$ are in $X_{m-1}$ . By induction on $m$ , $v^{2}$ and $v^{1}$ have the same color, blue. This is a contradiction, as $f_{r}^{\prime}$ has no blue vertex. So $f_{1}^{\prime}$ and $f_{q}^{\prime}$ are green, while no facets in between are green.

Look at the two paths:

v|f=f_{1},\ldots,f_{p}=g|w,\quad v=v^{0}|f_{1}=f_{1}^{\prime},\ldots,f_{q}^{\prime}|v^{1}

where $v^{1}\in V_{m-1}$ . None of these is a sub-sequence of the other, as $f_{p}$ and $f_{q}^{\prime}$ are green, and no intermediate facet is green. As in Lemma 3.4 we may cut-splice-reduce these together to get a path

v^{1}|f_{q}^{\prime},\ldots,f_{p}|w,

where only the end facets are green.

Case 1: $w\in V_{m-1}$ . Then in the path from $v^{1}$ to $w$ , the end facets are green, and no intermediate facet is green. By induction on $m$ (since both $v^{1}$ and $w$ are in $X_{m-1}$ ), we get that $v^{1}$ and $w$ have the same color. Furthermore $v$ and $v^{1}$ have the same color, blue, so both $v$ and $w$ are blue.

Case 2: $w\in V_{m}\backslash V_{m-1}$ . We have exactly one of $w,v^{1}$ (i.e. $w$ ) in $V_{m}\backslash V_{m-1}$ . The path from $v^{1}$ to $w$ has end facets green and no intermediate facet green. But then we can start the argument of Property B1 over again, and reduce to Case 1. So we conclude that $w$ and $v^{1}$ have the same color. Since $v$ and $v^{1}$ are both blue, we get that $v$ and $w$ are both blue.

Property B2: Suppose $v,w$ are distinct and blue. Let

v|f^{1},\ldots,f^{p}|w

be the unique path from $v$ to $w$ . Since $v$ and $w$ are independent, $p\geq 2$ . Let $q\geq 2$ be minimal such that $f^{q}$ contains a blue vertex $v^{\prime}=v_{1}$ . Then $f^{1}\sim_{F}f^{q}$ by construction, say they are green. Consider the path

v|f^{1},\ldots,f^{q}|v^{\prime}.

If one $f^{r}$ for $r\in[2,q-1]$ is green, let $r$ minimal such. Then we have a path

v|f^{1},\ldots,f^{r}|v^{\prime\prime}

and by B1 we have $v\sim_{V}v^{\prime\prime}$ , both blue. This contradicts the choice of $q$ . Thus $v\sim_{V}^{\prime}v^{\prime}$ . Now $v^{\prime}\in f^{q}$ . If $q=p$ we have $v^{\prime}=w$ and we are done. If $q<p$ then $v^{\prime}\neq w$ . Let $r$ be maximal with $q\leq r<p$ such that $v^{\prime}\in f^{r}$ . We then get

v^{\prime}|f^{r},\ldots,f^{p}|w

where both $v^{\prime}$ and $w$ are blue.

By induction on path length there are

v^{\prime}=v_{1}\sim_{V}^{\prime}v_{2}\sim_{V}^{\prime}\cdots\sim_{V}^{\prime}v_{s}=w,

and so we get part B2.

Property B3: Suppose $\sim_{V}$ is $s+1$ -scattered. Let $f\sim_{F}g$ be distinct green facets whose facet-distance $p-1$ is as small as possible with path

v|f=f^{1},f^{2},\ldots,f^{p}=g|w.

None of the intermediate facets $f^{2},\ldots,f^{p-1}$ are green. Then we have just shown in B1 that $v\sim_{V}w$ and so their face-distance $p\geq s+1$ . Then $p-1\geq s$ and the green facets are $s$ -scattered.

Final part: We show that if there are $r$ facet parts, there are $r+d$ vertex parts. This is by induction on the number of facets. Clearly this is true if we have one facet, a simplex. For a stacked simplicial complex $X$ let $m$ be minimal such that $X_{m}=X$ , and let $X^{\prime}=X_{m-1}$ . Let $f$ be a facet in $X_{m}\backslash X_{m-1}$ , and $v$ the free vertex of $f$ . By induction, if there are $r$ facet parts in $X^{\prime}$ , there are $r+d$ vertex parts.

If the facet $f$ makes a part of its own in $X$ , the free vertex $v$ becomes a part of its own, by construction of vertex classes. Then we have $r+1$ facet parts and $r+1+d$ vertex parts in $X$ .

If the facet $f$ is put into an existing part, say the green part, look at paths $v|f=f_{1},\ldots,f_{p}|w$ where $f_{1},f_{p}$ are green and the intermediate facets are not green. Then $v$ will be given the color of $w$ , say blue. If $v|f=f_{1}^{\prime},\ldots,f_{q}^{\prime}|w^{\prime}$ is another path with $f=f_{1}^{\prime}$ and $f_{q}^{\prime}$ green, and not intermediate facet is green, by Lemma 3.4 we may cut-splice-reduce and get in $X^{\prime}$ a path $w|f_{p},\ldots,f_{q}^{\prime}|w^{\prime}$ with $f_{p},f_{q}^{\prime}$ green and with no intermediate green facets. Both $w$ and $w^{\prime}$ have the same color. Then $v$ is uniquely in the blue color class. So $X$ has $r$ facet parts and $r+d$ vertex parts. ∎∎

Corollary 3.7.

Let $X$ be a tree, and $s\geq 1$ . There is a bijection between partitions of the vertices into $r+1$ non-empty parts, each part $s+1$ -scattered, and partitions of the edges into $r$ non-empty parts, each $s$ -scattered.

Corollary 3.8.

Let $X$ be a triangulation of a polygon and $s\geq 1$ . There is a bijection between partitions of the vertices into $r+2$ non-empty parts, each part $s+1$ -scattered, and partitions of the triangles into $r$ non-empty parts, each $s$ -scattered.

4. Partitions of natural numbers

The main theorem here appears quite surprising and non-trivial even for the simplest of trees, the line graph. Then it corresponds to studying ordered set partitions, which has a comprehensive theory [12].

Taking the colimit of longer and longer line graphs, we get results for the natural numbers. These are simple consequences of known results for ordered set partitions [2, Thm.2.2] or in a more enumerative form [3, Thm.1], but do not seem to have been stated in this form for natural numbers. In a similar vein, [13] considers partitions of intervals $[n]$ , but with requirements on the parts which are different from ours here.

Consider the infinite line graph

The set of edges $E$ may be identified with the natural numbers ${\mathbb{N}}$ , and also the set of vertices $V$ may be identified with ${\mathbb{N}}$ . Let $L_{n}$ be the line graph with $n$ edges. The bijection between partitions edges into $r$ parts, each $d$ -scattered, and partitions of vertices into $r+1$ parts, each $d$ -scattered, is compatible with extending the line graph $L_{n}=(V_{n},E_{n})$ with one edge and vertex to the line graph $L_{n+1}$ : If $(E^{i})$ is a partition of edges in $L_{n+1}$ corresponding to a partition $(V^{j})$ of vertices. Then the partition $(E^{i}\cap E_{n})$ corresponds to $(V^{j}\cap V_{n})$ .

Thus taking the colimit, we get for the infinite line graph (4) a bijection between partitions of edges $(E^{i})$ into $r$ parts, each $d$ -scattered, and partitions of vertices $(V^{j})$ into $r+1$ parts, each $d+1$ -scattered.

Recall that a subset $A\subseteq{\mathbb{N}}$ of natural numbers is $d$ -scattered if for every $p<q$ in $A$ we have $q-p\geq d$ .

Theorem 4.1.

There is a bijection between partitions of ${\mathbb{N}}$ into $r$ sets, each $d$ -scattered, and partitions of ${\mathbb{N}}$ into $r+1$ sets, each $d+1$ -scattered.

By successively going from $r$ to $r+1$ to $r+2$ and so on we get:

Corollary 4.2.

There is a bijection between partitions of ${\mathbb{N}}$ into $r+1$ parts $A_{0}\sqcup A_{1}\sqcup\cdots\sqcup A_{r}$ (each set by default being $1$ -scattered) and partitions of ${\mathbb{N}}$ into $r+d$ parts $B_{0}\sqcup\cdots\sqcup B_{r+d-1}$ , each $d$ -scattered.

Specializing to $r=0$ we get the trivial fact that there is a unique partition of ${\mathbb{N}}$ into $d$ parts, each $d$ -scattered. Clearly this partition is the congruence classes modulo $d$ . However specializing to $r=1$ , we get the quite non-trivial:

Corollary 4.3.

For each $d\geq 1$ there is a bijection between partitions of ${\mathbb{N}}$ into two parts $A_{0}\sqcup A_{1}$ and partitions of ${\mathbb{N}}$ into $d+1$ parts $B_{0}\sqcup\cdots\sqcup B_{d}$ , each being $d$ -scattered.

Example 4.4.

For $r=1$ let the partition be $\{p\}\sqcup{\mathbb{N}}\backslash\{p\}$ , the one part consisting of a single element $p$ . This corresponds to a partition of ${\mathbb{N}}$ into three parts, each being $2$ -scattered. We use $\ldots$ to indicate arithmetic progression of step size $2$ . These parts are:

	$\displaystyle\ldots,p-4,p-2,$	$\displaystyle\,\,p$
		$\displaystyle\,\,p+1,p+3,p+5,\ldots$
	$\displaystyle\ldots,p-3,p-1,$	$\displaystyle\,\,p+2,p+4,\ldots$

It also corresponds to a partition of ${\mathbb{N}}$ into four parts, each being $3$ -scattered. (Here $\ldots$ denotes progression with step size $3$ .) These parts are:

	$\displaystyle\ldots,p-6,p-3,$	$\displaystyle\,\,p$
	$\displaystyle\ldots,p-5,p-2,$	$\displaystyle\,\,p+1,p+4,p+7,\ldots$
		$\displaystyle\,\,p+2,p+5,\ldots$
	$\displaystyle\ldots,p-4,p-1,$	$\displaystyle\,\,p+3,p+6,\ldots.$

Example 4.5.

Let again $r=1$ . Consider the partition $\{p,q\}\sqcup{\mathbb{N}}\backslash\{p,q\}$ where $p<q$ . It corresponds to the following three parts, each $2$ -scattered. We get two cases, according to whether $q-p$ is even or odd. When $q-p$ is even:

$\displaystyle\ldots,p-3,$	$\displaystyle\,\,p-1,p+2,\quad\ldots$	$\displaystyle q-2,$	$\displaystyle\,\,q$
$\displaystyle\ldots,p-4,p-2,$	$\displaystyle\,\,p,$		$\displaystyle\,\,q+1,q+3,\ldots$
	$\displaystyle\,\,p+1,p+3,\quad\ldots$	$\displaystyle q-3,q-1,$	$\displaystyle\,\,q+2,q+4,\ldots.$

Note that in the middle part there is quite a long gap from $p$ to $q+1$ . When $q-p$ is odd:

	$\displaystyle\,\,p+1,p+3,\quad\ldots$	$\displaystyle q-2,$	$\displaystyle\,\,q$
$\displaystyle\ldots,p-4,p-2,$	$\displaystyle\,\,p,$		$\displaystyle\,\,q+1,q+3,\ldots$
$\displaystyle\ldots,p-3,$	$\displaystyle\,\,p-1,p+2,\quad\ldots$	$\displaystyle q-1,$	$\displaystyle\,\,q+2,q+4,\ldots$

References

[1] Ayah Almousa, Gunnar Fløystad, and Henning Lohne, Polarizations of powers of graded maximal ideals, Journal of Pure and Applied Algebra 226 (2022), no. 5, 106924.
[2] William YC Chen, Eva YP Deng, and Rosena RX Du, Reduction of m-regular noncrossing partitions, European Journal of Combinatorics 26 (2005), no. 2, 237–243.
[3] Wenchang Chu and Chuanan Wei, Set partitions with restrictions, Discrete mathematics 308 (2008), no. 15, 3163–3168.
[4] Bryce Duncan and Rhodes Peele, Bell and Stirling numbers for graphs, J. Integer Seq 12 (2009), no. 09.7.1, 1–13.
[5] Sara Faridi, The facet ideal of a simplicial complex, Manuscripta Mathematica 109 (2002), no. 2, 159–174.
[6] Gunnar Fløystad and Amir Mafi, Polarizations of artin monomial ideals define triangulated balls, https://arxiv.org/abs/2212.09528 (2022).
[7] Gunnar Fløystad and Milo Orlich, Triangulations of polygons and stacked simplicial complexes: separating their Stanley–Reisner ideals, Journal of Algebraic Combinatorics (2022), 1–28.
[8] Branko Grünbaum, Convex polytopes, second ed., Graduate Texts in Mathematics, vol. 221, Springer-Verlag, New York, 2003, Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler.
[9] A Hertz and H Mélot, Counting the Number of Non-Equivalent Vertex Colorings of a Graph, Les Cahiers du GERAD ISSN G-2013-82 (2013), 1–16.
[10] Jürgen Herzog and Takayuki Hibi, Monomial ideals, Springer, 2011.
[11] Zsófia Kereskényi-Balogh and Gábor Nyul, Stirling numbers of the second kind and Bell numbers for graphs, Australas. J Comb. 58 (2014), 264–274.
[12] Toufik Mansour, Combinatorics of set partitions, CRC Press Boca Raton, 2013.
[13] Augustine O Munagi, Extended set partitions with successions, European Journal of Combinatorics 29 (2008), no. 5, 1298–1308.
[14] Winston Yang, Bell numbers and k-trees, Discrete Mathematics 156 (1996), no. 1-3, 247–252.

Partitions of vertices and facets in trees and stacked simplicial complexes

Abstract.

Key words and phrases:

2020 Mathematics Subject Classification:

1. Introduction

Example 1.1.

Example 1.2.

Example 1.3.

Remark 1.4.

2. Stacked simplicial complexes

2.1. Paths

Definition 2.1.

Remark 2.2.

Definition 2.3.

Definition 2.4.

Lemma 2.5.

Proof.

Definition 2.6.

Lemma 2.7.

Proof.

2.2. Existence and uniqueness of paths

Proposition 2.8.

Proof.

Proposition 2.9.

Proof.

Remark 2.10.

2.3. Distance neighborhoods

Lemma 2.11.

Proof.

Corollary 2.12.

Proof.

3. Bijections between partitions of facets and of vertices

3.1. Bijections between partitions

Definition 3.1.

Remark 3.2.

3.1.1. From vertex partitions to facet partitions.

3.1.2. From facet partitions to vertex partitions

3.2. Induction arguments on XmX_{m}

Lemma 3.3.

Proof.

Lemma 3.4.

Proof.

Lemma 3.5.

Proof.

3.3. The main theorem

Theorem 3.6.

Proof.

Corollary 3.7.

Corollary 3.8.

4. Partitions of natural numbers

Theorem 4.1.

Corollary 4.2.

Corollary 4.3.

Example 4.4.

Example 4.5.

References

3.2. Induction arguments on $X_{m}$