Partitions of Vertices and Facets in Trees and Stacked Simplicial Complexes

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 $\ge s$ and vertex partitions whose parts have minimal distance $\ge s+1$.

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 $\ge 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

$$\begin{aligned} V = V_0 \sqcup V_1 \sqcup \cdots \sqcup V_r \end{aligned}$$

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

$$\begin{aligned} E = E_1 \sqcup E_2 \sqcup \cdots \sqcup E_r \end{aligned}$$

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 $\ge s$. Similarly, we have the notion of a set of edges $B \subseteq E$ being s-scattered. We show, Theorem 3.1, for a tree and for $r,s \ge 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 [9] 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.1

Let X be a stacked simplicial complex of dimension d and $r,s \ge 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.2

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 Fig. 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

$$\begin{aligned} \{1,3,5\}\cup \{2,6\}\cup \{4\}, \end{aligned}$$

and that of the second tree is

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

Fig. 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, Fig. 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 visualization purposes. In particular, there is no connection between colors of facets and colors of vertices.

Fig. 2

Partition of facets into two parts and corresponding partition of vertices into four parts

Our results here came out of work in [8] 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 Yang [15] 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.

Duncan and 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. References [10, 12] consider enumerative aspects of graphical Bell numbers further, and the latter also generalized d-trees.

Chen, Deng, and 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 Sect. 4. They also show that we have bijections in this case when considering non-crossing partitions. Related enumerative results are found in [3, 14]. The book [13] is a comprehensive account of partitions of ordered sets.

Remark 1.1

The results of this paper dropped out of investigations in [8], 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 complexes 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 [7]. 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 [7] 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.2, 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.1. In the last Sect. 4 we specialize these results to bijections between partitions of natural numbers, the parts having lower bound requirements on minimal distance.

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 elements 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 \ge 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.1

This is a special case of shellable simplicial complexes, see [11, Subsection 8.2]. In the literature there are also other notions, [5], of simplicial complexes or even cell complexes being trees. A tree T of dimension d in [5, Def. 2.6] is defined by the vanishing of the homologies $H_d(T; {{\mathbb {R}}})$ and $H_{d-1}(T;{{\mathbb {R}}})$. It is a spanning tree of an ambient d-complex if it also contains the $d-1$-skeleton of this complex. This notion tree is of course more general than that of stacked simplicial complexes.

Stacked simplicial complexes are also not the same as the notion of tree in [6], 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 Fig. 2, is not a tree in the sense of [6], since removing the triangles 234 and 257 one has no facet which is a leaf.

Definition 2.2

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}$). When $p \ge 2$, 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 \le i< j < p$, we can make a shorter walk from $f_1$ to $f_p$. If $f_i \ne f_{j+1}$ then

$$\begin{aligned} f_1, \ldots , f_i, f_{j+1}, \ldots , f_p \end{aligned}$$

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

$$\begin{aligned} f_1, \ldots , f_{i-1}, f_{j+1}, \ldots , f_p \end{aligned}$$

is a shorter walk from $f_1$ to $f_p$.

Definition 2.3

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.1

Let X be a stacked simplicial complex and $f_1,f_2, \ldots , f_p$ a path in X with $p \ge 2$.

• (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 \ge 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 \le j < k \le p$, then $f_j, f_{j+1}, \ldots , f_k$ is also a path and so $f_j$ and $f_k$ must be distinct. $\square$

Definition 2.4

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

$$\begin{aligned} h | f_1, \ldots , f_p | k \end{aligned}$$

is a path $f_1, \ldots , f_p$ such that

$$\begin{aligned} 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}. \end{aligned}$$

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.2

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 \le 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 \ge 2$ and consider the path

$$\begin{aligned} f_1, \ldots , f_r. \end{aligned}$$

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 \ge 2$, then $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$. $\square$

2.2 Existence and Uniqueness of Paths

Proposition 2.1

Given a stacked simplicial complex and let h, k be two of its 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

$$\begin{aligned} f = f_1, \ldots , f_p = f^\prime \end{aligned}$$

be the path between them. Let i be maximal such that $h \subseteq f_i$. Let $j \ge i$ be minimal such that $k \subseteq f_j$. Then we have a path from h to k:

$$\begin{aligned} h | f_i, \ldots , f_j | k. \end{aligned}$$

Uniqueness: Let

$$\begin{aligned} h | f_1, \ldots , f_p | k, \quad h | f_1^\prime , \ldots , f_q^\prime | k \end{aligned}$$

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

Let f be the last of the facets in these paths, in the stacking order, and with free vertex v. By Lemma 2.2, 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 $\ge 2$, say $p = 1$ (and $q \ge 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 \ge 2$. Let

$$\begin{aligned} g:= f \backslash \{v\} = f_1 \cap f_2 = f_1^\prime \cap f_2^\prime . \end{aligned}$$

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

$$\begin{aligned} g | f_2, \ldots , f_p | k, \quad g | f_2^\prime , \ldots , f_q^\prime | k. \end{aligned}$$

By induction on length, these paths are equal. $\square$

The following generalizes the well-known situation for trees.

Proposition 2.2

Let X be a pure simplicial complex of dimension d with n facets and v vertices. Then X is stacked if and only if $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.1 there is a unique path between any two facets.

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

$$\begin{aligned} f = f_1, f_2, \ldots , f_{n} \end{aligned}$$

(2.1)

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

$$\begin{aligned} f = f^1, f^2, \ldots , f^r = f_{p+1}. \end{aligned}$$

Here all facets except the last $f^r$ are in $Y_p$ as they must be listed before $f_{p+1}$ in (2.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, then $f_1, \ldots , f_{n-1}$ is a stacking order for $Y_{n-1}$. So (2.1) gives that $X=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

$$\begin{aligned} f_n = f_t^\prime = (f_t^\prime \cap f_{t-1}^\prime ) \cup (f_t^\prime \cap f^\prime _{t+1}). \end{aligned}$$

The vertices of $f_{t-1}^\prime$ and $f_{t+1}^\prime$ are both contained in the vertices of $Y_{n-1}$. But $f_n$ has one vertex outside of $Y_{n-1}$, and so the path from $f_r$ to $f_s$ must be entirely in $Y_{n-1}$. $\square$

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.2

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 \ge 1$, let $X_m$ be the simplicial complex generated by those facets of X whose face-distance to g is $\le 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 \ge 1$.

Lemma 2.3

Assume X is a stacked simplicial complex. For $m \ge 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

$$\begin{aligned} f_1 | f_1, \ldots , f_r | g \end{aligned}$$

the unique path from $f_1$ to g. We have $r \le m$. Let s be maximal with $v \in f_s$. Then in $X_m$:

$$\begin{aligned} v | f_s, \ldots , f_r | g \end{aligned}$$

is the unique path from v to g. Since $v \in V_{m}\backslash V_{m-1}$ we must have $r-s+1 \ge 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}$. $\square$

Corollary 2.1

$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 \le k \le 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 \ge 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.3, v is in none of the $f_i$ for $i < k$.

Thus $f_1, \ldots , f_r$ is a stacking order for $X_m$. $\square$

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 neighborhood $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 stacked simplicial complex with vertex set V, and s an integer $\ge 1$. A subset $A \subseteq V$ is s-scattered if the face-distance between any two distinct vertices in A is $\ge s$. The vertex set is independent if it is 2-scattered, i.e. no two vertices in A are on the same facet, or equivalently the same edge.

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

We consider partitions of the vertices

$$\begin{aligned} V = V_1 \sqcup V_2 \sqcup \cdots \sqcup V_r \end{aligned}$$

(3.1)

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.1

If the $V_i$ are independent, a partition is a proper coloring up to permuting the colors. 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 (3.1) is an orbit for the action of $S_r$. The set of such orbits, or equivalently of partitions (3.1) are also called non-equivalent vertex colorings, see [10].

We also consider partitions of the facets

$$\begin{aligned} F = F_1 \sqcup F_2 \sqcup \cdots \sqcup F_s. \end{aligned}$$

3.1.1 From Vertex Partitions to Facet Partitions

Now given a stacked simplicial complex X, 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. Define an equivalence relation $\sim _F$ of F as follows. Let f and $f^\prime$ be distinct facets. Consider the unique path in X between them:

$$\begin{aligned} f = f_1, \ldots , f_p = f^\prime , \end{aligned}$$

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$. 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:

$$\begin{aligned} v | f_1, \ldots , f_p | w. \end{aligned}$$

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. The following paragraphs A and B are an outline of the argument for this. The details will be given in the proof of Theorem 3.1.

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

  $$\begin{aligned} v | f_1, \ldots , f_p | w \end{aligned}$$

  where none of $f_2, \ldots , f_{p-1}$ have a blue vertex, then $p \ge 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

  $$\begin{aligned} f_0 \sim _F^\prime f_1 \sim _F^\prime \cdots \sim _F^\prime f_p \end{aligned}$$

  (3.2)

  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 \ge 2$

  $$\begin{aligned} v | f_1, \ldots , f_p | w \end{aligned}$$

  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

  $$\begin{aligned} v_0 \sim _V^\prime v_1 \sim _V^\prime \cdots \sim _V^\prime v_p, \end{aligned}$$

  (3.3)

  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$

Again X is a stacked simplicial complex. We show A, B for the subcomplexes $X_m$ by induction on m. For this we need some lemmata.

Lemma 3.1

Given a partition of the facets F, 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.3, that $f_v$ is the unique facet on $X_m$ containing v.

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

$$\begin{aligned} f_v = f_1, \ldots , f_p = f \end{aligned}$$

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 \ge 2$ be minimal such that $w \in f_r$. We then have a path

$$\begin{aligned} v | f_1, \ldots , f_r | w \end{aligned}$$

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

$$\begin{aligned} v | f_1, \ldots , f_p | u, \quad v | f^\prime _1, \ldots , f^\prime _q | w, \end{aligned}$$

(3.4)

be the unique paths where $f_1 = f_1^\prime$ by Lemma 2.3. 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 \ne f_r^\prime$, and let r be minimal such, so $r \ge 2$. If $r \ge 3$ there is a walk

$$\begin{aligned} u | f_p, \ldots , f_r, f_{r-1} = f_{r-1}^\prime , f_r^\prime , \ldots , f_q^\prime | w \end{aligned}$$

(3.5)

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

$$\begin{aligned} u | f_p, \ldots , f_2, f_2^\prime , \ldots , f_q^\prime | w \end{aligned}$$

(3.6)

where only the end facets are green. By reducing these walks like before Definition 2.3, we get a path giving $u \sim _V^\prime w$. $\square$

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

Lemma 3.2

Given a partition of V into independent sets, and the relation $\sim _F^\prime$ constructed as in Sect. 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.3 any path in $X_m$ starting from f must have left end vertex v. So we have the following paths

$$\begin{aligned} v | f = f_1, \ldots , f_p = g | u, \quad v | f = f_1^\prime , \ldots , f_q^\prime = h | w \end{aligned}$$

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. Neither of these paths is then a subpath of the other, and hence there is $r \ge 2$ such that $f_r \ne f_r^\prime$ and let r be minimal such. If $r \ge 3$, as above (3.5), we get a walk

$$\begin{aligned} w | h = f_q^\prime , \ldots , f_r^\prime , f^\prime _{r-1} = f_{r-1}, f_r, \ldots , f_p = g | u, \end{aligned}$$

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

$$\begin{aligned} u | f_p, \ldots , f_2, f_2^\prime , \ldots , f_q^\prime | w. \end{aligned}$$

(3.7)

Again, as above these walks may be reduced to paths (cut-splice-reduction) and so $g \sim ^\prime _F h$. $\square$

Lemma 3.3

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

$$\begin{aligned} v = v_0 \sim ^\prime _V v_1 \sim ^\prime _V \cdots \sim ^\prime _V v_t = w. \end{aligned}$$

(3.8)

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.1 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 (3.8) 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

$$\begin{aligned} f = f_1 \sim ^\prime _F f_2 \sim ^\prime _F \cdots \sim ^\prime _F = g. \end{aligned}$$

Again, using Lemma 3.2 above we may reduce to all $f_i \in X_m$. $\square$

3.3 The Main Theorem

Theorem 3.1

Let X be a stacked simplicial complex of dimension d, with vertex set V and facet set F, and s an integer $\ge 1$. The correspondences in Sects. 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

We follow the outline A given in Sect. 3.1.2. 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:

$$\begin{aligned} v | f_1, \ldots , f_p | w \end{aligned}$$

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

$$\begin{aligned} v = v_0 \sim ^\prime _V v_1 \sim ^\prime _V \cdots \sim ^\prime _V v_t = w. \end{aligned}$$

(3.9)

By Lemma 3.3 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.1 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 \ge 2$ and consider the path in $X_m$:

$$\begin{aligned} v = v_0 | f_1^\prime , \cdots , f_q^\prime | v_1. \end{aligned}$$

(3.10)

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 \le r \le 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.3, 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 \ge 2$. Recall by Lemma 2.3 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 (3.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 \ge 3$, and $f_2^\prime$ has a blue vertex w, contradicting that no intermediate facet in (3.10) has a blue vertex. The upshot is that w is not in $f_1$, and so $p \ge 2$.

By cut-splice-reducing the sequences,

$$\begin{aligned} 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 ), \end{aligned}$$

(3.11)

as in Lemma 3.2 we reduce to a path

$$\begin{aligned} v_1 | f_q^\prime , \ldots , f_p | w, \end{aligned}$$

(3.12)

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

$$\begin{aligned} f = f^1, f^2, \ldots , f^p = g \end{aligned}$$

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

$$\begin{aligned} v | f^1, \ldots , f^q | w. \end{aligned}$$

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

$$\begin{aligned} v| f^1, \ldots , f^r | v^\prime . \end{aligned}$$

By part A1, $f^1$ and $f^r$ have the same color, which must be green. This is a contradiction, 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$. Consider now the shorter path $f^q, f^{q+1}, \ldots , f^p$. By induction on length of path, there are

$$\begin{aligned} f^q = f_1 \sim _F^\prime \cdots \sim _F^\prime f_r = f^p, \end{aligned}$$

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

$$\begin{aligned} v | f^1, f^2, \ldots , f^p | w \end{aligned}$$

with $p \ge 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 \ge s$. Whence $p \ge s+1$ and the blue vertices are $s+1$-scattered.

Now consider the outline B given in Sect. 3.1.2. 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

$$\begin{aligned} v | f = f_1, \ldots , f_p = g | w \end{aligned}$$

(3.13)

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

$$\begin{aligned} f = f^0 \sim ^\prime _F f^1 \sim ^\prime _F \ldots \sim ^\prime _F f^t = g. \end{aligned}$$

Let m be smallest such that f, g is in $X_m$. By Lemma 3.3 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.2 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 \ge 2$. Since $v \in V_m \backslash V_{m-1}$, by Lemma 2.3 we have $f^0 = f_v$. Now look at at the path from $f^0$ to $f^1$

$$\begin{aligned} v = v^0 | f^0 = f_1^{\prime }, \ldots , f_q^{\prime }= f^1 | v^1, \end{aligned}$$

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 \le r \le q-1$ is maximal such that $f_r^{\prime }$ is green. We have a path

$$\begin{aligned} v^2 | f_r^{\prime }, \cdots , f_q^{\prime } | v^1 \end{aligned}$$

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:

$$\begin{aligned} v | f = f_1, \ldots , f_p = g | w, \quad v = v^0 | f_1 = f_1^\prime , \ldots , f_q^\prime | v^1 \end{aligned}$$

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.2 we may cut-splice-reduce these together to get a path

$$\begin{aligned} v^1 | f_q^\prime , \ldots , f_p | w, \end{aligned}$$

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

$$\begin{aligned} v | f^1, \ldots , f^p | w \end{aligned}$$

be the unique path from v to w. Since v and w are independent, $p \ge 2$. Let $q \ge 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

$$\begin{aligned} v | f^1, \ldots , f^q | v^\prime . \end{aligned}$$

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

$$\begin{aligned} v | f^1, \ldots , f^r | v^{\prime \prime }, \end{aligned}$$

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 \ne w$. Let r be maximal with $q \le r < p$ such that $v^\prime \in f^{r}$. We then get

$$\begin{aligned} v^\prime | f^{r}, \ldots , f^p | w \end{aligned}$$

where both $v^\prime$ and w are blue. By induction on path length there are

$$\begin{aligned} v^\prime = v_1 \sim _V^\prime v_2 \sim _V^\prime \cdots \sim _V^\prime v_s = w, \end{aligned}$$

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

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

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 \ge s+1$. Then $p-1 \ge 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$. Let f be a facet in $X_m \backslash X_{m-1}$, and v the free vertex of f. Let $V^\prime = V \backslash \{v\}$ and $X^\prime$ the subcomplex consisting of all faces of X which to not contain v. Then $X^\prime$ is also stacked (since for any stacking order for X, we can remove f and we get a stacking order for $X^\prime$). 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 no intermediate facet is green, by Lemma 3.2 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. $\square$

Corollary 3.1

Let X be a tree, and $s \ge 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.2

Let X be a triangulation of a polygon and $s \ge 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 path graph. Then it corresponds to studying ordered set partitions, which has a comprehensive theory [13].

Considering longer and longer path 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, [14] considers partitions of intervals [n], but with requirements on the parts which are different from ours here.

Consider the infinite path graph $P_\infty = (V_\infty , E_\infty )$.

The set of edges $E_\infty$ identifies canonically with the natural numbers ${{\mathbb {N}}}$, and the same with the vertices $V_\infty$. Let $P_n= (V_n, E_n)$ be the path subgraph with n edges, with edges $E_n = \{e_1, \ldots , e_n\}$. Note by construction of partitions in Sects. 3.1.1 and 3.1.2, that $\{e_n\}$ is a singleton set of the partition of edges if and only if $\{v_n\}$ is a singleton set of the partition of vertices.

Lemma 4.1

Let $P_{n+1} = (V_{n+1}, E_{n+1})$ and $\{E^i\}$ be a partition of the edges $E_{n+1}$ into r parts and $\{V^j\}$ the corresponding partition of the vertices $V_{n+1}$ into $r+1$ parts.

Let $P_n= (V_n,E_n)$ be the path subgraph obtained by removing $e_{n+1}$ and $v_{n+1}$ from $P_{n+1}$. Then $\{E^i \backslash \{e_{n+1}\}\}$ and $\{V^j \backslash \{v_{n+1}\}\}$ are corresponding partitions of $E_n$ and $V_n$.

Proof

The equivalence relation on $V_{n+1}$ corresponding to the partition $\{E^i \}$ is generated by $v_i \sim ^\prime _{V_{n+1}} v_j$ for $i < j \le n+1$. When $j \le n$ every such pair is also related for $\sim ^\prime _{V_n}$. The vertex $v_{n+1}$ occurs either once in the relation $\sim ^\prime _{V_{n+1}}$, or not at all (in which case $\{v_{n+1}\}$ becomes a singleton set of the partition).

The equivalence relation on $V_{n}$ corresponding to the partition $\{E^i \backslash \{e_{n+1}\}\}$ is generated by $v_i \sim ^\prime _{V_n} v_j$ for $i < j \le n$. Thus $\{V^j \backslash \{v_{n+1}\}\}$ will be the corresponding partition of $V_n$. $\square$

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 \ge 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.

Proof

Given a partition of ${{\mathbb {N}}}$ into r sets, each d-scattered. It corresponds to a partition $\{E^i \}$ of the edges $E_\infty$ of the infinite path graph, into r sets, each d-scattered.

For $n \ge 0$ consider the path subgraphs $P_n = (V_n, E_n)$. Let N be large enough, so that each part $E^i \cap E_N$ is non-empty. Then for each $n \ge N$ the partition $\{E^i \cap E_n\}$ corresponds to a partition $\{V_n^j\}$ into $r+1$ parts, each $d+1-$scattered. By Lemma 4.1 we have each $V^j_n \subseteq V^j_{n+1}$. The unions $V^j = \cup _{n \ge N} V^j_n$ then give a partition of the vertices $V_\infty$ into $r+1$ parts, each $d+1$-scattered when $\{E^i \}$ is d-scattered. Then $\{V^j \}$ corresponds to a partition of ${{\mathbb {N}}}$ into $r+1$ parts, each $d+1$-scattered.

Going the other way, starting from a partition $\{V^j \}$ of vertices, by a similar argument it gives the original partition $\{E^i \}$ of edges. $\square$

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

Corollary 4.1

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.2

For each $d \ge 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.1

For $r = 1$ let the partition be $\{p\} \sqcup {{\mathbb {N}}}\backslash \{p \}$, the first 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:

$$\begin{aligned} \ldots , p-4, p-2,&\,\, p \\&\,\, p+1, p+3, p+5, \ldots \\ \ldots , p-3, p-1,&\, \, p+2, p+4, \ldots \\ \end{aligned}$$

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

$$\begin{aligned} \ldots , p-6, p-3,&\, \, p \\ \ldots , p-5, p-2,&\, \, p+1, p+4, p+7, \ldots \\&\, \, p+2, p+5, \ldots \\ \ldots , p-4, p-1,&\, \, p+3, p+6, \ldots . \end{aligned}$$

Example 4.2

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:

$$\begin{aligned}&\displaystyle \ldots , p-3, \quad p-1, p+2, \quad \ldots \quad q-2, \quad q \\&\displaystyle \ldots , p-4, p-2, \quad p, \quad q+1, q+3,\ldots \\&\displaystyle \, \, p+1, p+3, \quad \ldots \quad q-3, q-1, \quad q+2, q+4, \ldots . \end{aligned}$$

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

$$\begin{aligned}&\displaystyle \, \, p+1, p+3, \quad \ldots \quad q-2, \quad q \\&\displaystyle \ldots , p-4, p-2, \quad p, \quad q+1, q+3, \ldots \\&\displaystyle \ldots , p-3, \quad p-1, p+2, \quad \ldots \quad q-1, \quad q+2, q+4, \ldots \end{aligned}$$