# Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

Paul Bastide, Carla Groenland, Hugo Jacob, Tom Johnston

<figure><img src="image_1.png" /></figure>

## To cite this version:

Paul Bastide, Carla Groenland, Hugo Jacob, Tom Johnston. Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron. Combinatorial Theory, 2024, 4 (1), 10.5070/C64163848. hal-04720670

HAL Id: hal-04720670

https://hal.science/hal-04720670v1

Submitted on 3 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
**Title**

Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

**Permalink**

https://escholarship.org/uc/item/2s4544d9

**Journal**

Combinatorial Theory, 4(1)

**ISSN**

2766-1334

**Authors**

Bastide, Paul
Groenland, Carla
Jacob, Hugo
*et al.*

**Publication Date**

2024

**DOI**

10.5070/C64163848

**Supplemental Material**

https://escholarship.org/uc/item/2s4544d9#supplemental

**Copyright Information**

Copyright 2024 by the author(s). This work is made available under the terms of a Creative Commons Attribution License, available at https://creativecommons.org/licenses/by/4.0/

Peer reviewed
# EXACT ANTICHAIN SATURATION NUMBERS VIA A GENERALISATION OF A RESULT OF LEHMAN–RON

Paul Bastide<fnref n="1" />, Carla Groenland*<fnref n="2" />, Hugo Jacob<fnref n="3" />, and Tom Johnston<fnref n="4" />

Submitted: Sept 9, 2022; Accepted: Jan 12, 2024; Published: Jun 30, 2024

© The authors. Released under the CC BY license (International 4.0).

**Abstract.** For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1, \dots, n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use $\text{sat}^*(n, k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of $\text{sat}^*(n, k)$. Our result implies that $\text{sat}^*(n, k) = n(k-1) - \Theta(k \log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for $\text{sat}^*(n, k)$ were only known for $k$ up to 6.

We also prove a strengthening of a result of Lehman–Ron which may be of independent interest. We show that given $m$ disjoint chains $C^1, \dots, C^m$ in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the elements from $\bigcup_{i=1}^m C^i$ (where we call a chain skipless if any two consecutive elements differ in size by exactly one).

**Keywords.** Skipless chains, poset saturation, antichain saturation, Boolean lattice

**Mathematics Subject Classifications.** 06A07, 05D99

## 1. Introduction

Many powerful results have been proved over the years concerning the structure of chains and antichains in the Boolean lattice, e.g. [Gri82, Kle75, Sak79, Spe28, STW22]. For example, it is well-known that the Boolean lattice admits a symmetric chain decomposition [Aig73, GK76],

<footnote n="1">¹Laboratoire Bordelais de Recherche en Informatique, France — Technische Universiteit Delft, The Netherlands
paul.bastide@ens-rennes.fr</footnote>

<footnote n="2">²Technische Universiteit Delft, The Netherlands

c.e.groenland@tudelft.nl</footnote>

<footnote n="3">³Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, France
hjacob@ens-paris-saclay.fr</footnote>

<footnote n="4">⁴University of Bristol and Heilbronn Institute for Mathematical Research, U.K.
tom.johnston@bristol.ac.uk</footnote>

<footnote>*This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180). Views and opinions expressed are however those of the author(s) only.</footnote>
and in fact these chains may be taken to be *skipless* (or *saturated*): every chain $C_1 \subsetneq \dots \subsetneq C_r \subseteq [n] = \{1, \dots, n\}$ has the property that $|C_{i+1}| = |C_i| + 1$ for all $i \in [r-1]$. Skipless chains have also been studied in other contexts such as in [BS96, DHL19, Log02].

Given sets $X_1, \dots, X_m$ from layer $r$ and sets $Y_1, \dots, Y_m$ from layer $s$ such that $X_i \subseteq Y_i$, it need not be possible to find disjoint skipless chains $C^1, \dots, C^m$ linking $X_1$ to $Y_1, X_2$ to $Y_2$ etc. However, it was shown by Lehman and Ron [LR01] in 2001 that there always exist $m$ disjoint skipless chains that *cover* the sets $X_1, \dots, X_m$ and $Y_1, \dots, Y_m$, where a chain $C$ is said to cover a set $X$ if $X \in C$.

**Theorem 1.1 (Lehman–Ron [LR01]).** Let integers $1 \le s < r \le n$ be given and for all $i \in [m]$, subsets $X_i \subseteq Y_i \subseteq [n]$ with $|X_i| = s$ and $|Y_i| = r$. Then there exist $m$ disjoint skipless chains that cover $\{X_1, \dots, X_m, Y_1, \dots, Y_m\}$.

It is natural to ask if a stronger statement holds. For example, what happens if we allow the sets to come from different layers, or ask that the chains go via some elements from layers between layer $r$ and layer $s$? Is it possible to cover any $m$ disjoint chains with $m$ disjoint skipless chains, or can we force the use of an additional chain? We show that $m$ chains always suffice.

**Theorem 1.2.** Suppose that $\mathcal{F} \subseteq 2^{[n]}$ admits a chain decomposition into $m$ chains. Then there exist disjoint skipless chains $C^1, \dots, C^m \subseteq 2^{[n]}$ such that $\mathcal{F} \subseteq \bigcup_{i=1}^m C^i$.

This was already known in the special case that the union $\mathcal{F}$ of the chains we wish to cover is a convex set system (i.e. if $X, Y \in \mathcal{F}$ and $X \subseteq Z \subseteq Y$, then $Z \in \mathcal{F}$) [DHL19]. In this case, the chains can be taken to partition $\mathcal{F}$ as any additional sets must be at the ends of the chains.

Although we believe Theorem 1.2 to be of interest in its own right, our initial motivation came from the area of induced poset saturation where we use Theorem 1.2 to easily settle various conjectures concerning the asymptotics of antichain saturation numbers. With more work, we are in fact able to go well beyond the conjectures and pinpoint the exact values.

For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $[n]$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but for all $X \subseteq [n]$ with $X \notin \mathcal{F}$, the family $\mathcal{F} \cup \{X\}$ does contain an antichain of size $k$. We denote the size of the smallest such family by $\text{sat}^*(n, k)$.

In the literature, this is also sometimes denoted $\text{sat}^*(n, A_k)$, where $A_k$ is the poset consisting of $k$ incomparable elements. This is called an *induced* saturation number: it is the size of the smallest set system which is saturated in terms of not containing $A_k$ as an *induced* subposet. Saturation numbers for the Boolean lattice were introduced by Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós [GKL+13] (although they did not require the subposets to be induced) and have been investigated for a variety of posets, for example for the butterfly [Iva20], the diamond [Iva22] and the chain [MNS14]. We refer to [KLM+21] for a nice overview.

Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan [FKK+17] were the first to study the particular case of the antichain and made the following conjecture.

**Conjecture 1.3 ([FKK$^+$17]).** For $k \ge 3$, $\text{sat}^*(n, k) \sim (k-1)n$ as $n \to \infty$.

The upper bound is easy to see: for all $i \in [n]$, a $k$-antichain saturated family can contain at most $k-1$ subsets of size $i$ since two subsets of the same size are incomparable. Moreover,
a k-antichain saturated family must always exist since we can start with the empty family and greedily add subsets until it is no longer possible to do so without creating an antichain of size k. Martin, Smith and Walker [MSW20] proved the lower bound

$$ sat^*(n, k) \geq \left(1 - \frac{1}{\log_2(k-1)}\right) \frac{(k-1)n}{\log_2(k-1)} $$

for $k \geq 4$ and $n$ sufficiently large. The exact values for $k = 2, 3$ and $4$ were shown to be $n + 1, 2n$ and $3n - 1$ respectively in [FKK+17], the exact values for $k = 5$ and $k = 6$ were recently determined to be $4n - 2$ and $5n - 5$ respectively by Đanković and Ivan [DI23]. They also strengthened Conjecture 1.3 as follows, and proposed two weaker conjectures implied by this conjecture.

**Conjecture 1.4 ([DI23]).** sat*(n, k) = n(k - 1) - O_k(1).

At the end of this introduction, we will show how all the conjectures mentioned above are an easy corollary of Theorem 1.2.

**Corollary 1.5.** There exist constants $c_1, c_2 > 0$ such that for all $k \geq 4$ and $n$ sufficiently large,

$$ n(k-1) - c_1 k \log k \leq sat^*(n, k) \leq n(k-1) - c_2 k \log k. $$

In general, obtaining exact saturation numbers is a notoriously difficult problem, and for the antichain, exact numbers were only known for $k$ up to $6$. Our main result determines the exact value of sat*(n, k) for all values of $k$ and $n$ where $n$ is large enough relative to $k$. We note that $n$ need not be excessively large compared to $k$ and it certainly suffices to assume $n \geq 6 \log k + 1$ for example. Determining the exact values is considerably more involved than just determining the asymptotics, and we require some more definitions just to state the value of the numbers.

Given a natural number $k$, let $\ell$ be the smallest integer $j$ such that $(\lfloor j/2 \rfloor)^{\frac{j}{k}} \geq k - 1$. Note that when $n < \ell$, there are no antichains of size $k$ in $2^{[n]}$ and $\mathcal{F}$ must contain every set (i.e. sat*(n, k) = $2^n$).

Let $\mathcal{C}(m, t)$ denote the initial segment of layer $t$ of size $m$ when the sets are in colexicographic order. For a family of sets $\mathcal{A}$ from the same layer, let $\nu(\mathcal{A})$ be the size of the maximum matching from $\mathcal{A}$ to its shadow $\partial \mathcal{A}$, and recursively define $c_0, c_1, \dots, c_{\lfloor \ell/2 \rfloor}$ as follows. Let $c_{\lfloor \ell/2 \rfloor} = k - 1$. For $0 \leq t < \lfloor \ell/2 \rfloor$, let $c_t = \nu(\mathcal{C}(c_{t+1}, t+1))$.

**Theorem 1.6.** Let $n, k \geq 4$ be integers and let $\ell$ and $c_0, \dots, c_{\lfloor \ell/2 \rfloor}$ be as defined above. If $n < \ell$, then sat*(n, k) = $2^n$. If $n \geq \ell$, then

$$ sat^*(n, k) \geq 2 \sum_{t=0}^{\lfloor \ell/2 \rfloor} c_t + (k-1)(n-1-2\lfloor \ell/2 \rfloor). $$

Moreover, equality holds when $n \geq 2\ell + 1$.
Given the form of the bound in Theorem 1.6, one might be tempted to suggest that the best approach is to take each layer $t \le \lfloor \ell/2 \rfloor$ to be an initial segment of colex of the appropriate size, but this is not the case in general. While such an example would have the optimal size, it may already contain an antichain of size $k$. For example, one can check there is an antichain of size 262 in $C(261, 5) \cup C(219, 4)$, and this approach would not work for $k = 262$.

For infinitely many values of $k$, a matching upper bound to Theorem 1.6 was already known [FKK$^+$17] (see Section 5.1) which works for all $n \ge \ell + 1$. It gives the following corollary.

**Corollary 1.7.** Let $\ell, k, n$ be integers such that $(\lfloor \ell/2 \rfloor) = k - 1$. If $n \le \ell$ then $\mathrm{sat}^*(n, k) = 2^n$. If $n \ge \ell + 1$, then

$$ \mathrm{sat}^*(n, k) = 2 \sum_{j=0}^{\lfloor \ell/2 \rfloor} \binom{\ell}{j} + (k-1)(n-1-2\lfloor \ell/2 \rfloor). $$

In particular, whenever $k-1$ is a central binomial coefficient (i.e. $k = 3, 4, 7, 11, 21, 36, \dots$) the value of $\mathrm{sat}^*(n, k)$ is determined for all $n$.

We now explain how Corollary 1.5 follows from Theorem 1.2. The upper bound was already known, and we prove a lower bound of $\mathrm{sat}^*(n, k) \ge (n+1-2\ell)(k-1)$ for $n$ sufficiently large. (Recall that $\ell$ is the smallest $j$ such that $(\binom{j}{\lfloor \ell/2 \rfloor}) \ge k-1$, so $\ell = \Theta(\log k)$.)

By Dilworth's theorem [Dil50], having a chain decomposition of size at most $k-1$ is equivalent to not containing any antichain of size $k$. Suppose that $\mathcal{F} \subseteq 2^{[n]}$ is $k$-antichain saturated and so admits a decomposition into $k-1$ chains. By Theorem 1.2, there are $k-1$ disjoint skipless chains $C^1, \dots, C^{k-1}$ that cover the elements of $\mathcal{F}$; since $\mathcal{F}$ is saturated, this must form a chain decomposition of $\mathcal{F}$. It suffices to show that every chain must contain a set of size at most $\ell$ and a set of size at least $n-\ell$. Suppose the smallest element $X$ of some chain $C^i$ has size $|X| > \ell$, then all subsets $Y$ of $X$ must be present in $\mathcal{F}$ since otherwise we may extend $C^i$ to include $Y$ (and that would mean that $\mathcal{F} \cup \{Y\}$ can also be covered by $k-1$ chains, contradicting the fact that $\mathcal{F}$ is $k$-antichain saturated). There are at least $k-1$ subsets of $X$ of size $\lfloor \ell/2 \rfloor$, and these cannot all be covered by the other $k-2$ chains. Since each chain contains an element of size at most $\ell$ and one of size at least $n-\ell$, the bound follows immediately from the fact that the chains are skipless.

In order to prove the exact lower bound of Theorem 1.6, we need to examine what happens on layers $1, \dots, \ell$. This is considerably more delicate and for this we use an auxiliary result concerning the matching number of the colex order (Lemma 2.4), which we give in Section 2.1. Finally, we give an explicit construction of a $k$-antichain saturated system $\mathcal{F}$ which matches our lower bound on each layer provided $n$ is sufficiently large. This construction was already known for the special case $k-1 = (\lfloor \ell/2 \rfloor)$, and we apply it recursively for other values of $k$. The recursion requires special care and depends on a particular way of writing $k-1$ as a sum of binomial coefficients. This notation can be used to write exact values for the matching numbers $c_t$ from Theorem 1.6 (see Section 2.2).

In Section 2, we introduce our notation and the auxiliary results. In Section 3 we prove Theorem 1.2. In Section 4 we give the proofs of the lower bounds of Theorem 1.6 and Corollary 1.7. In Section 5 we finish the proofs of Theorem 1.6 and Corollary 1.7 by giving the upper bound constructions. In Section 6 we give directions for future work.
## 2. Preliminaries

Let $G = (U, V, E)$ be a bipartite graph on vertex sets $U$ and $V$ with edge set $E$. For $X \subseteq U$, we write $N(X)$ for the set of neighbours of $X$. A matching $M$ between $U$ and $V$ is a set of edges $M \subseteq E$ such that the edges are pairwise disjoint (i.e. $m \cap m' = \emptyset$ for all $m, m' \in M$).

We will write $[r, s] = \{r, r+1, \dots, s-1, s\}$ for the set of integers between $r$ and $s$ inclusive, and we will denote $[1, n]$ by $[n]$. The subsets of $[n]$ of size $t$ will be called *layer $t$* and we will denote them by

$$ \binom{[n]}{t} = \{X \subseteq [n] \mid |X| = t\}. $$

Similarly, let $\binom{[n]}{\ge t} = \{X \subseteq [n] \mid |X| \ge t\}$ be the subsets of size at least $t$ and $\binom{[n]}{\le t} = \{X \subseteq [n] \mid |X| \le t\}$ the subsets of size at most $t$. For the set of all subsets of a set $X$, we use the notation $2^X$. For a set system $\mathcal{F} \subseteq 2^{[n]}$, we denote the collection of subsets of size $t$ in $\mathcal{F}$ by $\mathcal{F}_t$.

We will often consider the *Hasse diagram* of $2^{[n]}$ where there is an edge from $X \subseteq [n]$ to $Y \subseteq [n]$ if $X \subseteq Y$ and $|Y| = |X| + 1$.

A *chain* $C \subseteq 2^{[n]}$ is a set system consisting of pairwise comparable elements, that is, $X \subseteq Y$ or $Y \subseteq X$ for all $X, Y \in C$. An *antichain* is a set system consisting of elements that are pairwise incomparable.

We say a chain $C$ in $2^{[n]}$ starts in $R$ and ends in $S$ if the smallest element of $C$ is in $R$ and the largest element of $C$ is in $S$. We say a chain $C_1 \subseteq \dots \subseteq C_m$ is *skipless* if $|C_{i+1}| = |C_i| + 1$ for all $i \in [m-1]$ i.e. the chain does not 'skip' over any layers.

A *chain decomposition* of a set system $\mathcal{F} \subseteq 2^{[n]}$ is a collection of disjoint chains $C^1, \dots, C^m$ in $\mathcal{F}$ such that $\mathcal{F} = \cup_{i=1}^m C^i$, that is, for each $X \in \mathcal{F}$, there is exactly one $i \in [m]$ such that $C^i$ contains the set $X$. The size of the chain decomposition is the number of chains $m$.

We assume the reader is familiar with the following immediate consequence of Dilworth's theorem.

**Theorem 2.1 (Dilworth [Dil50]).** Let $n$ be an integer and $\mathcal{F} \subseteq 2^{[n]}$. The size of the largest antichain in $\mathcal{F}$ is equal to the minimum size of a chain decomposition of $\mathcal{F}$.

The symmetric chain decomposition described in [Aig73, GK76] gives the following result.

**Lemma 2.2.** There is a skipless chain decomposition of $2^{[n]}$ into $\binom{[n]}{\lfloor n/2 \rfloor}$ chains. In particular, there is a matching of size $\binom{n}{s}$ from $\binom{[n]}{s}$ to $\binom{[n]}{r}$ whenever $s < r \le \lfloor n/2 \rfloor$ or $s > r \ge \lfloor n/2 \rfloor$.

### 2.1. Colex for shadows and matchings

In the *colexicographic* or *colex* order on $\binom{[n]}{t}$, we have $A < B$ if $\max(A\Delta B) \in B$, where $\Delta$ denotes the symmetric difference $A\Delta B = (A \setminus B) \cup (B \setminus A)$. Informally, sets with larger elements come later in the order. For $t = 3$ the initial segment of size 8 in colex is given by

$$ \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 5\}, \{1, 3, 5\}, \{2, 3, 5\}, \{1, 4, 5\}. $$

We write $C(m, t)$ for the initial segment of colex on layer $t$ of size $m$.
For a family of sets $A \subseteq \binom{[n]}{t}$, the shadow of $A$ is given by

$$ \partial A = \{ X \in \binom{[n]}{t-1} \mid X \subseteq Y \text{ for some } Y \in A \}. $$

The well-known Kruskal–Katona theorem below shows that the shadow of a family of subsets of size $t$ is minimised by taking the family to be an initial segment of colex, and we will prove an analogous result about matchings between a family and its shadow.

**Theorem 2.3 (Kruskal–Katona [Kru63]).** Let $1 \le t \le n$ be integers. Let $\mathcal{B} \subseteq \binom{[n]}{t}$ and let $\mathcal{C}$ be the initial segment of colex on $\binom{[n]}{t}$ of size $|\mathcal{B}|$. Then $|\partial \mathcal{B}| \ge |\partial \mathcal{C}|$.

For $\mathcal{B} \subseteq \binom{[n]}{t}$, let $\nu(\mathcal{B})$ denote the size of the maximum matching in the bipartite graph between $\mathcal{B}$ and $\partial \mathcal{B}$, where $X \in \mathcal{B}$ is adjacent to $Y \in \partial \mathcal{B}$ if $Y \subseteq X$.

**Lemma 2.4.** Let $1 \le t \le n$ be integers. Let $\mathcal{B} \subseteq \binom{[n]}{t}$ and let $\mathcal{C}$ be the initial segment of colex on $\binom{[n]}{t}$ of size $|\mathcal{B}|$. Then $\nu(\mathcal{B}) \ge \nu(\mathcal{C})$.

We could not find a reference for this result, so we will provide a proof for completeness. Our proof relies on the Kruskal–Katona theorem and the following variant of Hall’s theorem.

**Lemma 2.5.** Let $G = (U, V, E)$ be a bipartite graph. The largest matching in $G$ between $U$ and $V$ has size $|U| - d$, where

$$ d = \max_{X \subseteq U} (|X| - |N(X)|). $$

*Proof of Lemma 2.4.* We prove the lemma by induction on $|\mathcal{B}|$. When $|\mathcal{B}| = 1$, $\nu(\mathcal{B}) = 1$ for all $\mathcal{B} \subseteq \binom{[n]}{t}$. If $\nu(\mathcal{B}) = |\partial \mathcal{B}|$, then the Kruskal–Katona theorem (Theorem 2.3) gives

$$ \nu(\mathcal{B}) = |\partial \mathcal{B}| \ge |\partial \mathcal{C}| \ge \nu(\mathcal{C}). $$

We now assume that $\nu(\mathcal{B}) < |\partial \mathcal{B}|$, and show that there is a $B \in \mathcal{B}$ for which $\nu(\mathcal{B} \setminus \{B\}) < \nu(\mathcal{B})$. The lemma then follows by induction. Indeed, let $B$ denote the element for which $\nu(\mathcal{B} \setminus \{B\}) < \nu(\mathcal{B})$. Let $C \in \mathcal{C}$ denote the last element of $\mathcal{C}$ in the colex order. Then $\mathcal{C} \setminus \{C\}$ is an initial segment of colex so the induction hypothesis shows that $\nu(\mathcal{B} \setminus \{B\}) \ge \nu(\mathcal{C} \setminus \{C\})$. Hence

$$ \nu(\mathcal{B}) > \nu(\mathcal{B} \setminus \{B\}) \ge \nu(\mathcal{C} \setminus \{C\}) \ge \nu(\mathcal{C}) - 1. $$

Since all numbers are integers, we find $\nu(\mathcal{B}) \ge \nu(\mathcal{C})$ as desired.

It remains to show the claim that there is a $B \in \mathcal{B}$ for which $\nu(\mathcal{B} \setminus \{B\}) < \nu(\mathcal{B})$ when $\nu(\mathcal{B}) < |\partial \mathcal{B}|$. Consider the bipartite graph $G$ between $U = \partial \mathcal{B}$ and $V = \mathcal{B}$ (where $u \in U$ is adjacent to $v \in V$ if $u \subseteq v$). By Lemma 2.5, $\nu(\mathcal{B}) = |\partial \mathcal{B}| - d$ where

$$ d = \max_{\mathcal{X} \subseteq \partial \mathcal{B}} |\mathcal{X}| - |N(\mathcal{X})|. $$

Pick $\mathcal{X} \subseteq \partial \mathcal{B}$ such that $|\mathcal{X}| - |N(\mathcal{X})| = d$, and note that $d \ge 1$ by assumption. This means $\mathcal{X}$ is non-empty and there is some set $B \in N(\mathcal{X})$. Consider the largest matching when we remove $B$ from $G$. In this graph $|\mathcal{X}| - |N(\mathcal{X})|$ is $d+1$ and so applying Lemma 2.5 shows that the largest matching between $\partial \mathcal{B}$ and $\mathcal{B} \setminus \{B\}$ is of size at most $|\partial \mathcal{B}| - d - 1$. This proves that $\nu(\mathcal{B} \setminus \{B\}) < \nu(\mathcal{B})$, as desired. $\square$
## 2.2. Cascade notation

Let $m, r$ be integers. For our upper bound construction, we need a result which gives the value of $\nu(C(m, r))$.

There is a unique way of writing $m$ as

$$m = \binom{a_r}{r} + \binom{a_{r-1}}{r-1} + \dots + \binom{a_s}{s}$$

where $r \ge s \ge 1$, $a_r > \dots > a_s > 0$ and $a_i \ge i$ for all $i \in [s]$. The initial segment of colex $C(m, r)$ of size $m$ on layer $r$ is the union of the set $\binom{[a_r]}{r}$, the set containing all elements of the form $A \cup \{a_r + 1\}$ with $A \in \binom{[a_{r-1}]}{r-1}$, the set containing all elements of the form $A \cup \{a_r + 1, a_{r-1} + 1\}$ where $A \in \binom{[a_{r-2}]}{r-2}$, and so on until the sets containing all the elements of the form $A \cup \{a_r + 1, a_{r-1} + 1, \dots, a_{s+1} + 1\}$ where $A \in \binom{[a_s]}{s}$.

The expansion above is also called the r-cascade notation of $m$ and may be built recursively as follows. Take $a_r$ to be the largest $j$ such that $\binom{j}{r} \le m$, and set $m' = m - \binom{j}{r}$. If $m' = 0$, the recursion ends. Otherwise append the expansion for $m'$ and $r' = r - 1$.

This expansion can be used to compute the size of the shadow $|\partial C(m, r)|$, but we are interested in using it to give the precise value of $\nu(C(m, r))$ as follows.

**Lemma 2.6.** Let $r \ge s \ge 1$ and $a_r > \dots > a_s > 0$ be such that

$$m = \binom{a_r}{r} + \binom{a_{r-1}}{r-1} + \dots + \binom{a_s}{s}. \qquad (2.1)$$

If $i \le \lceil a_i/2 \rceil$ for all $i \in [s, r]$, then $\nu(C(m, r)) = \sum_{i=s}^{r} \binom{a_i}{i-1}$. Otherwise, let $j \in [s, r]$ be maximal such that $j > \lceil a_j/2 \rceil$. Then

$$\nu(C(m, r)) = \binom{a_r}{r-1} + \dots + \binom{a_{j+1}}{j} + \binom{a_j}{j} + \dots + \binom{a_s}{s}.$$

*Proof.* The first claim follows from the fact that there is a matching of size $\binom{a_i}{i-1}$ between $\binom{[a_i]}{i}$ and $\partial \binom{[a_i]}{i} = \binom{[a_i]}{i-1}$ when $i \le \lceil a_i/2 \rceil$ (see Lemma 2.2).

We prove the second claim by induction on $r - j$, starting with $r - j = 0$. Note that $C(m, r) \subseteq \binom{[a_{r+1}]}{r}$, and that $\lceil a_r/2 \rceil < r$ implies that $\lfloor (a_r + 1)/2 \rfloor \le r - 1$. By Lemma 2.2, there is a matching from $\binom{[a_{r+1}]}{r}$ to $\binom{[a_{r+1}]}{r-1}$ of size $\binom{a_r}{r}$ and this induces a matching of size $|C(m, r)|$ from $C(m, r)$ to $\partial C(m, r)$, as required.

Now let $r - j \ge 1$. The sets in $C(m, r)$ which do not contain $a_r + 1$ are exactly $\binom{[a_r]}{r}$ and these can only be matched to sets in $\partial C(m, r)$ which do not contain $a_r + 1$, namely to sets in $\binom{[a_r]}{r-1}$. Since $r \le \lceil a_r/2 \rceil$, there is a matching $M'$ of size $\binom{a_r}{r-1}$ between $\binom{[a_r]}{r}$ and $\binom{[a_r]}{r-1}$ by Lemma 2.2. Moreover, there exists a maximum matching $M$ from $C(m, r)$ to $\partial C(m, r)$ such that $M' \subseteq M$ since elements in $\binom{[a_r]}{r}$ cannot be matched outside of $\binom{[a_r]}{r-1}$. Therefore, from any maximum matching $M''$ we can replace the set of all edges with an endpoint in $\binom{[a_r]}{r-1}$ with $M'$ and obtain a new matching $M$ with the same cardinality. Let $C'$ be obtained from $C(m, r) \setminus \binom{[a_r]}{r}$ by deleting the element $a_r + 1$ from every set. Then $C'$ is an initial segment of colex of size $m - \binom{a_r}{r}$ from layer $r - 1$, and we apply the induction hypothesis to $C'$ to get the result. $\square$
<figure><img src="image_3.png" /><figcaption>Figure 3.1: Representation of Lemma 3.1 (case $r = s + 2$ and $m = 4$).</figcaption></figure>

**3. Generalisation of a result of Lehman-Ron**

We will prove Theorem 1.2 from the following lemma using an inductive argument.

**Lemma 3.1.** Let $s \le r \le n$ be integers. Let $C^1, \dots, C^m$ be disjoint chains, such that for all $i \in [m-1]$, the chain $C^i$ starts in layer $s$ and ends in layer $r$. Suppose that $C^m$ starts in $A \in \binom{[n]}{\le s}$ and ends in $B \in \binom{[n]}{r}$. Then there exist $m$ disjoint chains $D^1, \dots, D^m$ with the following three properties.

1. For $i \in [m-1]$, the chain $D^i$ starts in the $s$th layer, ends in the $r$th layer and is skipless.

2. The chain $D^m$ starts at $A$ and intersects the $i$th layer for all $i \in [s+1, r]$.

3. The chains $D^1, \dots, D^m$ cover the elements in $C^1, \dots, C^m$.

Note that our lemma allows the element $A$ to appear on a lower layer than the others (illustrated in Figure 3.1) and that it may be impossible to add an element on layer $s$ to the chain $D^m$.

The overall structure of the proof of Lemma 3.1 is very similar to that of Lehman-Ron [LR01]. We first consider the special case in which $s = r - 2$. As in the proof of Lehman-Ron [LR01], the first step is to show that there are at least $m$ elements in the $(r-1)$th layer that could be elements of the chains $D^1, \dots, D^m$.

**Lemma 3.2.** Let $a, r, n$ be integers satisfying $a \le r-2 \le n-2$, let $\mathcal{R} \subseteq \binom{[n]}{r}$ be of size $m$, let $\mathcal{S} \subseteq \binom{[n]}{r-2}$ be of size $m-1$ and let $A \in \binom{[n]}{a}$. Suppose that there exists a bijection $f: \mathcal{R} \to \mathcal{S} \cup \{A\}$ with $f(X) \subseteq X$ for all $X \in \mathcal{R}$. Let $\mathcal{Q}$ denote the set of $Q \in \binom{[n]}{r-1}$ with $S \subseteq Q \subseteq \mathcal{R}$ for some $(S, \mathcal{R}) \in (S \cup \{A\}) \times \mathcal{R}$. Then $|\mathcal{Q}| \ge m$.

*Proof.* We prove the claim by contradiction. Consider a counterexample to the claim for which $m$ is minimal. If $m=1$, then we are given elements $A \subseteq \mathcal{R}$ with $|A| \le r-2$ and $|\mathcal{R}| = r$. Then there exists at least one element $Q \in \mathcal{Q}$ such that $A \subseteq Q \subseteq \mathcal{R}$: simply remove one of the elements in $\mathcal{R} \setminus A$ from $\mathcal{R}$ to obtain $Q$. We therefore assume $m \ge 2$.

We consider the Hasse diagram $H = (V, E)$ of $2^{[n]}$. Note that $Q$ can be seen as the set of all elements of cardinality $r-1$ lying on a path between an element of $S \cup \{A\}$ and an element of $\mathcal{R}$.
We consider the 'restriction' $H' = (V', E')$ which is obtained by taking the subgraph of $H$ on vertex set $V' = \mathcal{R} \cup \mathcal{S} \cup \mathcal{Q} \cup \{A\}$, removing all arcs containing $A$ and then adding an arc from $A$ to $Q$ for all $Q \in \mathcal{Q}$ with $A \subseteq Q$. We denote by $N^+(X)$ (resp. $N^-(X)$) the set of vertices $Y$ with an arc $X \to Y$ (resp. with an arc $Y \to X$) in $H'$, and define $d^+(X) = |N^+(Y)|$ and $d^-(X) = |N^-(X)|$. We first prove the following three claims.

**Claim 3.3.** For every $R \in \mathcal{R}$ and every $Q \in N^-(R)$, we have $d^-(R) \ge d^-(Q)$.

*Proof.* In order to prove the claim, for any $R$ in $\mathcal{R}$, and any $Q$ in $N^-(R)$, we exhibit an injective function $\pi : N^-(Q) \to N^-(R)$.

We denote by $j$ the unique element of the set $R \setminus Q$. For $S \in \mathcal{S} \cap N^-(Q)$, we denote by $i$ the unique element in $Q \setminus S$ and set $\pi(S) = R \setminus \{i\} = S \cup \{j\}$. Note that $\pi(S) \in \mathcal{Q}$ as $S, \pi(S), R$ is a path in $H'$. By doing so, we specified a unique $\pi(S) \in N^-(R)$ for all $S \in N^-(Q)$ except for possibly $A$ if $A \in N^-(Q)$. However, there is one element in $N^-(R)$ that we have not yet used: the element $Q = R \setminus \{j\} \in N^-(R)$ and we may map this element to $A$ to finish the definition of our injection $\pi$ if needed. $\square$

**Claim 3.4.** For every $Q \in \mathcal{Q}$ and every $S \in N^-(Q)$, we have $d^+(Q) < d^+(S)$.

*Proof.* The proof of this claim is similar to the proof of the previous claim. Let $Q \in \mathcal{Q}$ and $S \in N^-(Q)$. Once again we exhibit an injective function $\pi' : N^+(Q) \to N^+(S)$. We define $\pi'(R) = S \cup (R \setminus Q)$ for $R \in N^+(Q)$. Note that $Q$ itself is never an image of $\pi'$ thus a strict inequality holds. $\square$

**Claim 3.5.**

$$ \sum_{R \in \mathcal{R}} d^-(R) \ge \sum_{Q \in \mathcal{Q}} d^-(Q) \quad \text{and} \quad \sum_{Q \in \mathcal{Q}} d^+(Q) < \sum_{S \in \mathcal{S} \cup \{A\}} d^+(S). $$

*Proof.* We start by showing the first inequality. For $c \in \mathbb{N}$, let us define $\mathcal{R}_c = \{R \in \mathcal{R} \mid d^-(R) = c\}$ and distinguish two cases. Suppose first that there exists a $c \in \mathbb{N}$ such that $\mathcal{R}_c = \mathcal{R}$. Then we have $\sum_{R \in \mathcal{R}} d^-(R) = cm$. By Claim 3.3, $\forall Q \in \mathcal{Q}$, $d^-(Q) \le c$ and therefore $\sum_{Q \in \mathcal{Q}} d^-(Q) \le c(m-1) \le \sum_{R \in \mathcal{R}} d^-(R)$.

Otherwise, $\mathcal{R}_c \ne \mathcal{R}$ for every choice of $c$. In this case, we define, for any integer $d < \max_{R \in \mathcal{R}} d^-(R)$, $\mathcal{R}_{\le d} = \cup_{c \le d} \mathcal{R}_c$ and remark that $\mathcal{R}_{\le d} \ne \mathcal{R}$. Since we chose $(\mathcal{R}, S \cup \{A\})$ to be minimal, Lemma 3.2 holds for the pair $(\mathcal{R}_{\le d}, f(\mathcal{R}_{\le d}))$. In particular, we can find a set $Q_{\le d}$ of size exactly $|\mathcal{R}_{\le d}|$ such that $Q_{\le d} \subseteq Q$ and every element in $Q_{\le d}$ lies on a path between an element of $\mathcal{R}_{\le d}$ and an element of $f(\mathcal{R}_{\le d})$. By definition, each $Q \in Q_{\le d}$ is in the in-neighbourhood of some $R \in \mathcal{R}_{\le d}$, and therefore $d^-(Q) \le d$ by Claim 3.3. We conclude that for any $d < \max_{R \in \mathcal{R}} d^-(R)$ there exist $|Q_{\le d}| = |\mathcal{R}_{\le d}|$ vertices in $Q$ of in degree at most $d$.

If we denote by $d_0 < d_1 < \dots < d_k$ the in-degree sequence of $\mathcal{R}$, then the result of the last paragraph induces an injective function $\pi'' : \mathcal{R}_{\le d_{k-1}} \to \mathcal{Q}$ as follows: we map $\mathcal{R}_{d_0}$ to $Q_{\le d_0}$, then map $\mathcal{R}_{d_1}$ to $Q_{\le d_1} \setminus Q_{\le d_0}$ and continue to map $\mathcal{R}_{d_i}$ to $Q_{\le d_i} \setminus Q_{\le d_{i-1}}$ for all $i \in [2, k-1]$. We argued in the previous paragraph that such injections exist. By construction, $\forall R \in \mathcal{R}_{\le d_{k-1}}$, $d^-(\pi''(R)) \le d^-(R)$.
All vertices in $\mathcal{Q}$ are in the in-neighbourhood of some element of $\mathcal{R}$ and therefore $d^-(Q) \le d_k$ for all $Q \in \mathcal{Q}$ by Claim 3.3. Since by assumption $|\mathcal{Q}| < |\mathcal{R}|$, this proves $\sum_{R \in \mathcal{R}} d^-(R) \ge \sum_{Q \in \mathcal{Q}} d^-(Q)$ since we can associate each term in the second sum to an element that is at least as large in the first sum (and all terms are non-negative).

The proof of the inequality $\sum_{Q \in \mathcal{Q}} d^+(Q) < \sum_{S \in \mathcal{S} \cup \{A\}} d^+(S)$ is analogous, but now the strict inequality follows from the strict inequality in Claim 3.4 instead of the weak inequality of Claim 3.3. $\square$

We are now fully equipped to conclude the proof of Lemma 3.2. By double counting, $\sum_{Q \in \mathcal{Q}} d^-(Q) = \sum_{S \in \mathcal{S} \cup \{A\}} d^+(S)$ and $\sum_{R \in \mathcal{R}} d^-(R) = \sum_{Q \in \mathcal{Q}} d^+(Q)$. Using Claim 3.5 we deduce the following contradiction,

$$ \sum_{Q \in \mathcal{Q}} d^-(Q) = \sum_{S \in \mathcal{S} \cup \{A\}} d^+(S) > \sum_{Q \in \mathcal{Q}} d^+(Q) = \sum_{R \in \mathcal{R}} d^-(R) \ge \sum_{Q \in \mathcal{Q}} d^-(Q). $$

This proves the lemma. $\square$

<figure><img src="image_4.png" /></figure>

Using Lemma 3.2 we can now prove the following special case of Lemma 3.1, which we will use to push through an inductive argument.

**Lemma 3.6.** Let $3 \le r \le n$ be integers. Let $C^1, \dots, C^{m-1}$ be skipless disjoint chains between the $(r-2)$th and the $r$th layers. Let $B \in \binom{[n]}{r}$ and let $A$ be a subset of $B$ of size at most $r-2$, such that $A, B \notin \cup_{i=1}^{m-1} C^i$.

Then there exist $m$ disjoint chains $D^1, \dots, D^m$ with the following three properties.

* For $i \in [m-1]$, the chain $D^i$ starts in the $(r-2)$th layer, ends in the $r$th layer and is skipless.

* The chain $D^m$ starts in $A$ and intersects both the $(r-1)$th and the $r$th layer.

* The chains $D^1, \dots, D^m$ cover the elements in $C^1, \dots, C^{m-1}$ and $A, B$.

*Proof.* We prove the claim by induction on $m$. The case $m=1$ is immediate.

We let $\mathcal{R}, \mathcal{T}, \mathcal{S}$ denote the restriction of the chains to layers $r, r-1, r-2$ respectively, and add $A$ to $\mathcal{S}$ and $B$ to $\mathcal{R}$. That is,

$$ \mathcal{R} = \left( \bigcup_i C^i \cap \binom{[n]}{r} \right) \cup \{B\}, $$

$$ \mathcal{T} = \bigcup_i C^i \cap \binom{[n]}{r-1}, $$

$$ \mathcal{S} = \left( \bigcup_i C^i \cap \binom{[n]}{r-2} \right) \cup \{A\}. $$

Let $\mathcal{Q}$ denote the set of all elements $Q \in \binom{[n]}{r-1}$ such that there exists $(R, S) \in \mathcal{R} \times \mathcal{S}$ satisfying $R \subseteq Q \subseteq S$. We define a bijection $f: \mathcal{R} \to \mathcal{S}$ with $f(B) = A$ and $f(X) \subseteq X$ for
all $X \in \mathcal{R}$ using the given chains. Lemma 3.2 shows that $|\mathcal{Q}| \ge m$. Since $|\mathcal{T}| = m-1$, $\mathcal{T}$ is a strict subset of $\mathcal{Q}$.

We consider the poset as a directed graph $H'$ via an adjusted Hasse diagram as before: the vertex set consists of $V = \mathcal{R} \cup \mathcal{Q} \cup \mathcal{S}$, and $X \to Y$ is an arc in $E(H')$ if and only if $X \subsetneq Y$ and either $|Y| = |X| + 1$ or $X = A$ and $Y \in \mathcal{Q}$. Finding the desired chains $D^1, \dots, D^m$, is equivalent to finding $m$ vertex-disjoint paths between $\mathcal{R}$ and $\mathcal{S}$ in the induced subgraph $H_Q = H'[\mathcal{R} \cup \mathcal{T} \cup \mathcal{S} \cup \{\mathcal{Q}\}]$ for some $\mathcal{Q} \in \mathcal{Q}$. By Menger's theorem [Men27], there exist $m$ vertex-disjoint paths if and only if there is no $(\mathcal{R}, \mathcal{S})$-cut of size $m-1$, that is, there is no subset $\mathcal{C} \subseteq \mathcal{V}$ with $|\mathcal{C}| = m-1$ such that, for all pairs $(R, S) \in \mathcal{R} \times \mathcal{S}$, every path from $R$ to $S$ contains a vertex of $\mathcal{C}$.

Since $|\mathcal{T}| < |\mathcal{Q}|$, there is an element $Q_0 \in \mathcal{Q} \setminus \mathcal{T}$. By the discussion above, we may assume that an $(\mathcal{R}, \mathcal{S})$-cut $\mathcal{C}$ of size $m-1$ exists in $H_{Q_0}$. We first show that $\mathcal{C} \not\subseteq \mathcal{Q}$. Indeed, for any $Q \in \mathcal{Q}$ there exists a pair $(R, S) \in \mathcal{R} \times \mathcal{S}$ such that $S \to Q \to R$ is a path in $H'$. When $\mathcal{C} \subseteq \mathcal{Q}$, all such paths in $H_{Q_0}$ are cut off only when $\mathcal{C}$ contains all elements of $\mathcal{T} \cup \{Q_0\}$; but $|\mathcal{C}| = m-1 < m = |\mathcal{T} \cup \{Q_0\}|$. So $\mathcal{C}$ must contain at least one element which is not in $\mathcal{Q}$.

We partition the size of the cut in three parts

$$m_1 = |\mathcal{R} \cap \mathcal{C}|, \quad m_2 = |\mathcal{Q} \cap \mathcal{C}|, \quad m_3 = |\mathcal{S} \cap \mathcal{C}|.$$

Consider the chains whose endpoints have not been touched by the cut. That is, let $\mathcal{R}^* \subseteq \mathcal{R}$ consist of the $R \in \mathcal{R}$ for which $R, f(R) \notin \mathcal{C}$, and let $\mathcal{S}^* = f(\mathcal{R}^*)$. Then $\mathcal{Q} \cap \mathcal{C}$ is an $(\mathcal{R}^*, \mathcal{S}^*)$-cut. Moreover,

$$m_2 = |\mathcal{Q} \cap \mathcal{C}| = (m-1) - m_1 - m_3 < m - m_1 - m_3 \le |\mathcal{R}^*|.$$

Let $\mathcal{T}^* \subseteq \mathcal{T}$ consist of the elements that lie on some chain $C^i$ between $\mathcal{S}^*$ and $\mathcal{R}^*$. Since $\mathcal{Q} \cap \mathcal{C}$ is an $\mathcal{R}^*, \mathcal{S}^*$-cut of $H_{Q_0}$, it must in particular contain all elements of $\mathcal{T}^*$. Since $m_2 < |\mathcal{R}^*|$, this means that $(A, B) \in (\mathcal{S}^* \times \mathcal{R}^*)$. Moreover, we may apply the induction hypothesis since $|\mathcal{R}^*| < |\mathcal{R}|$ (because $m_1 + m_3 > 0$). This gives us $|\mathcal{R}^*|$ chains which cover all elements in $\mathcal{T}^*$ and all intersect layer $r-1$, so in particular we obtain some element $Q_1 \in \mathcal{Q} \setminus \mathcal{T}^*$ such that there are $|\mathcal{R}^*| > m_2$ vertex-disjoint $\mathcal{S}^* - \mathcal{R}^*$ paths in $H^* = H'[\mathcal{R}^* \cup \mathcal{T}^* \cup \{Q_0, Q_1\} \cup \mathcal{S}^*]$. We distinguish two cases.

* Suppose that $Q_1 \notin \mathcal{T}$. In this case we have obtained our desired chain decomposition. Indeed, we keep the chains between $\mathcal{S} \setminus \mathcal{S}^*$ and $\mathcal{R} \setminus \mathcal{R}^*$ as they are and since $\mathcal{T}^* \cup \{Q_1\}$ is disjoint from those chains, we may use the $|\mathcal{R}^*|$ chains between $\mathcal{R}^*$ and $\mathcal{S}^*$ that we obtained by induction in order to define the remaining chains.

* Suppose that $Q_1 \in \mathcal{T}$. In that case, $H^*$ is an induced subgraph of $H_{Q_0}$. This gives a contradiction: $H^*$ has $|\mathcal{R}^*| > m_2$ vertex disjoint paths between $\mathcal{R}^*$ and $\mathcal{S}^*$, whereas $\mathcal{Q} \cap \mathcal{C}$ gives an $(\mathcal{R}^*, \mathcal{S}^*)$-cut of size $m_2$ in $H_{Q_0}$. $\square$

From this, we will deduce the case of general $s$.

*Proof of Lemma 3.1.* We prove the lemma by induction on $m$. The case $m=1$ is immediate. Suppose the claim has been shown for all $m' < m$.
Let $C^1, \dots, C^m$ be the given chain decomposition, where $C^m$ starts in $A \in \binom{[n]}{\le s}$ and ends in $B \in \binom{[n]}{r}$, and the first $m-1$ chains are between layers $s$ and $r$. Let $t \in [s+1, r]$. We say the chains $D^1, \dots, D^m$ are $t$-good if the first $m-1$ chains are skipless and between layers $s$ and $r$, $D^m$ is between $A$ and $B$ and intersects layers $t, \dots, r$, and $\cup_{i=1}^m C^i \subseteq \cup_{i=1}^m D^i$.

We first argue that there exists an $r$-good decomposition. Indeed, applying the induction hypothesis to the first $m' = m - 1$ chains, we can find chains $D^1, \dots, D^{m-1}$ between layers $s$ and $r$ that are skipless and such that $\cup_{i=1}^{m-1} C^i \subseteq \cup_{i=1}^{m-1} D^i$. By removing the elements from $C^m$ that also appear in some $D^i$, we have obtained an $r$-good decomposition for $C^1, \dots, C^m$.

Let $t \le r$ be minimal for which a $t$-good decomposition $D^1, \dots, D^m$ exists. Suppose towards a contradiction that $t > s+1$. Let $B'$ be the element of $D^m$ in layer $t$. Since $t > s+1$, we find $t-2 \ge s$ and so the chains $D^1, \dots, D^{m-1}$ all intersect layer $t-2$. We can apply Lemma 3.6 on the chains $D^1, \dots, D^{m-1}$ restricted to layers $s' = t-2$ and $r' = t$, and elements $A$ and $B'$. This produces a set $C_1$ of chains. Let $C_0$ and $C_2$ be the restrictions of $D^1, \dots, D^m$ to layers $s, \dots, t-2$ and to layers $t, \dots, r$ respectively. Then each chain of $C_1$ shares a vertex with exactly one chain of $C_0$ and exactly one chain of $C_2$. Hence, there is only one way to merge these chains in a chain decomposition $E^1, \dots, E^m$. This chain decomposition is $(t-1)$-good, contradicting the minimality of $t$. Therefore, there exists an $(s+1)$-good decomposition $D^1, \dots, D^m$, as claimed by the lemma. $\square$

We will obtain Theorem 1.2 as a corollary of the following lemma. The lemma is stated in the way that we wish to apply it in the proof of Theorem 1.6.

**Lemma 3.7.** Let $\mathcal{F} \subsetneq 2^{[n]}$ be $k$-antichain saturated. Then $\mathcal{F}$ has a chain decomposition into $k-1$ skipless chains.

*Proof.* Suppose, towards a contradiction, that $\mathcal{F}$ has no chain decomposition $C^1, \dots, C^{k-1}$ for which the first $i+1$ chains are skipless, but it does have one for which the first $i$ are skipless. Note that, we can always rearrange the chain decomposition such that $C^1$ is skipless, else $\mathcal{F}$ would not be saturated. This means we have $1 \le i < k-1$.

Amongst the decompositions for which the first $i$ chains are skipless, we choose a decomposition $C^1, \dots, C^{k-1}$ which minimises the 'number of layers the $(i+1)$th chain skips'. That is, the decomposition which minimises

$$ \max_{X \in C^{i+1}} |X| - \min_{Y \in C^{i+1}} |Y| + 1 - |C^{i+1}|. $$

By assumption, we can find $A \subseteq B$ consecutive in $C^{i+1}$ with $|B| > |A| + 1$ such that $C^{i+1}$ is skipless between $B$ and its maximal element. After renumbering, we can assume that for some $j \in [0, i]$, the chains $C^1, \dots, C^j$ have elements present on layers $|B| - 2, |B| - 1$ and $|B|$, whereas $C^{j+1}, \dots, C^i$ miss an element either on layer $|B| - 2$ or on layer $|B|$. (Here we use that $C^1, \dots, C^i$ are skipless.) In particular, if $C^a$ where $a \in [j+1, i]$ has an element on layer $|B| - 1$, then it is its minimal or maximal element, and so we can move it to another chain without creating any skips in the chain $C^a$.

We apply Lemma 3.1 to the chains $C^1, \dots, C^j$ restricted to layers $|B| - 2, |B| - 1, |B|$, and $A \subseteq B$ to obtain disjoint chains $D^1, \dots, D^{j+1}$ with the following properties:
<figure><img src="image_5.png" /><figcaption>Figure 3.2: An example of a possible rearrangement as done in the proof of Lemma 3.7 (for $j = 3$ and $i = 6$). The sets $A$ and $B$ are part of the chain $C_7$.</figcaption></figure>

• $\cup_{a=1}^j C^a \cup \{A, B\} \subseteq \cup_{a=1}^{j+1} D^a$;

• $D^1, \dots, D^j$ are skipless, start in layer $|B| - 2$ and end in layer $|B|$;

• $D^{j+1}$ contains $A$ and elements on layers $|B| - 1$ and $|B|$.

Since the chains $C^1, \dots, C^j$ have an element on layer $|B| - 1$, there is a unique $X \in \cup_{a=1}^{j+1} D^a$ with $|X| = |B| - 1$ such that $X \notin \cup_{a=1}^j C^a$.

The chains $D^1, \dots, D^{j+1}$ define a matching $M$ between layer $|B|$ and layer $|B| - 1$ of size $j + 1$. We will use this to reroute the chains into a 'better' chain decomposition and arrive at a contradiction. A possible configuration is depicted in Figure 3.1. We define the chain decomposition $E^1, \dots, E^{k-1}$ as follows.

For $a \in [j]$, let $b \in [j]$ be such that $D^b$ contains the unique element in $C^a$ of size $|B| - 2$. Let $a' \in [j] \cup \{i+1\}$ be the index such that $D^b$ contains the unique element in $C^{a'}$ of size $|B|$. We set

$$E^a = \left[ C^a \cap \left( \begin{array}{c} [n] \\ \le |B| - 2 \end{array} \right) \right] \cup D^b \cup \left[ C^{a'} \cap \left( \begin{array}{c} [n] \\ \ge |B| \end{array} \right) \right].$$

Note that our assumption that $C^1, \dots, C^{i+1}$ are skipless from layer $|B|$ upwards means the chain $E^a$ must be skipless as well.

For $a \in [j+1, i]$, we let $E^a = C^a \setminus \{X\}$. Either we kept the chain the same, or we removed the minimal or maximal element, so these chains are also skipless. For $a \in [i+2, n]$, we also set $E^a = C^a \setminus \{X\}$.

For $a = i+1$, let $C^{a'}$ be the unique chain which contains the element of $D^{j+1}$ of size $|B|$. We set

$$E^{i+1} = \left[ C^{i+1} \cap \left( \begin{array}{c} [n] \\ \le |A| \end{array} \right) \right] \cup D^{j+1} \cup \left[ C^{a'} \cap \left( \begin{array}{c} [n] \\ \ge |B| \end{array} \right) \right].$$

The chains $E^1, \dots, E^{k-1}$ form a chain decomposition of $\mathcal{F} \cup \{X\}$ (which must equal $\mathcal{F}$ in this case because $\mathcal{F}$ is $k$-antichain saturated). The chains $E^1, \dots, E^i$ are skipless and the chain $E^{i+1}$ skips one fewer layers than the chain $C^{i+1}$, contradicting the optimality of $C^1, \dots, C^{k-1}$. $\square$

We recall the statement of Theorem 1.2: if $\mathcal{F}$ admits a chain decomposition into $m$ chains, then it can be covered by $m$ skipless chains.
**Proof of Theorem 1.2.** By assumption, $\mathcal{F}$ does not contain an antichain of size $m+1$. Let $\mathcal{F}'$ be obtained from $\mathcal{F}$ by greedily adding sets until the set system has become $(m+1)$-antichain saturated. If $\mathcal{F}' = 2^{[n]}$, then we find a skipless chain decomposition for $\mathcal{F}'$ by Lemma 2.2. Otherwise, we can find a chain decomposition for $\mathcal{F}'$ into $m+1-1=m$ skipless chains by Lemma 3.7. These chains cover $\mathcal{F}$ as desired. $\square$

**4. Lower bounds for antichain saturation numbers**

In this section, we prove the lower bound of Theorem 1.6. We first recall the set-up. Given a natural number $k$, let $\ell$ be the smallest integer $j$ such that $\binom{j}{\lfloor j/2 \rfloor} \ge k-1$. We may assume that $n \ge \ell$. Let $C(m,t)$ denote the initial segment of layer $t$ of size $m$ under the colexicographic order. Let $c_t = k-1$ for all $t \in [\lfloor \ell/2 \rfloor, \lfloor n/2 \rfloor]$. For $0 \le t < \lfloor \ell/2 \rfloor$, we define $c_t = \nu(C(c_{t+1}, t+1))$. (Recall that $\nu(\mathcal{B})$ is the size of the largest of a matching between $\mathcal{B}$ and its shadow, as defined in Section 2.1.)

The lower bound of Theorem 1.6 follows directly from the lemma below, since the desired lower bound for the upper layers follows by symmetry.

**Lemma 4.1.** For any $k$-antichain saturated set system $\mathcal{F} \subsetneq 2^{[n]}$, $|\mathcal{F}_t| \ge c_t$ for any $t \le \lfloor n/2 \rfloor$.

*Proof.* Suppose that $\mathcal{F} \subsetneq 2^{[n]}$ is $k$-antichain saturated. By Lemma 3.7, there is a skipless chain decomposition $C^1, \dots, C^{k-1}$ for $\mathcal{F}$. Let $\mathcal{F}_t = \mathcal{F} \cap \binom{[n]}{t}$. We define $\mathcal{D}(\mathcal{F}_t)$ as the sets $A \in \mathcal{F}_{t-1}$ for which the chain $C^i$ that contains $A$ also contains an element of $\mathcal{F}_t$. The following claim is key to our proof.

**Claim 4.2.** For all $t \in [n]$, $|\mathcal{D}(\mathcal{F}_t)| = \nu(\mathcal{F}_t)$.

*Proof.* By definition, there is a matching from $\mathcal{F}_t$ to $\mathcal{D}(\mathcal{F}_t) \subseteq \partial \mathcal{F}_t$ of size $|\mathcal{D}(\mathcal{F}_t)|$, and hence, $\nu(\mathcal{F}_t) \ge |\mathcal{D}(\mathcal{F}_t)|$. We now focus on the opposite inequality.

Suppose, towards a contradiction, that there is a $t$ for which $|\mathcal{D}(\mathcal{F}_t)| < \nu(\mathcal{F}_t)$. Let $M$ be a matching between $\mathcal{F}_t$ and $\partial \mathcal{F}_t$ of size $\nu(\mathcal{F}_t)$, and let $M'$ be the matching between $\mathcal{F}_t$ and $C(\mathcal{F}_t)$ corresponding to the inclusions in the chains (i.e. $X$ is matched to $Y$ if $X$ and $Y$ are in the same chain). Consider the multigraph where the vertices are $\binom{[n]}{t} \cup \binom{[n]}{t-1}$ and the edge set is $M \cup M'$. The non-empty components of this graph are paths and even cycles which alternate between edges from $M$ and $M'$ (with no multiedges), and multiedges which have one edge from $M$ and one edge from $M'$. Since $|M| > |M'|$ there must be some component $P$ which is a path that starts and ends with edges from $M$. We will reroute some of the chains so that they use the edges from $M$ instead of the edges from $M'$, increasing the size of $\mathcal{D}(\mathcal{F}_t)$.

If a chain $C^a$ is not incident with an edge in this path, let $D^a = C^a$ (i.e. the chain is unchanged). One end of $P$ must be in layer $t$ and one end in layer $t-1$, and we order the edges starting from the end in layer $t$. If $e \in M$ is not the last edge in the path, then it connects a set $X \in C^a$ of size $t$ to a set $Y \in C^b$ of size $t-1$, and we replace $C^a$ by

$$D^a = \left( C^a \cap \binom{[n]}{\ge t} \right) \cup \left( C^b \cap \binom{[n]}{\le t-1} \right).$$
If $e \in M$ is the last edge in the path, there are two cases. The edge may connect a set $X \in C^a$ of size $t$ to a set $Y$ of size $t-1$ which is not in any other chain, in which case we set $D^a = (C^a \cap (\begin{smallmatrix} [n] \\ \geq t \end{smallmatrix})) \cup \{Y\}$. Then $D^1, \dots, D^{k-1}$ gives a decomposition of $\mathcal{F} \cup \{Y\}$ into $k-1$ chains and this contradicts the assumption that $\mathcal{F}$ is $k$-antichain saturated. The other case is where the edge connects a set $X \in C^a$ of size $t$ to a set $Y \in C^b$ of size $t-1$. Since there is no edge in $M'$ incident to $Y$, it must be the largest set in $C^b$. In this case, we set $D^a = (C^a \cap (\begin{smallmatrix} [n] \\ \geq t \end{smallmatrix})) \cup C^b$. The $k-2$ chains $D^1, \dots, D^{b-1}, D^{b+1}, \dots, D^{k-1}$ now cover all the elements of $\mathcal{F}$ and we may still define the chain $D^b$ freely. We can choose any set $A$ which is not in $\mathcal{F}$ and set $D^b = \{A\}$. Then $D^1, \dots, D^{k-1}$ is a chain decomposition of $\mathcal{F} \cup \{A\}$ into $k-1$ chains, a contradiction. $\square$

Lemma 2.2 shows that, for all $t > \lfloor n/2 \rfloor$ there is a matching between $\mathcal{F}_t$ and $\partial \mathcal{F}_t$ of size $|\mathcal{F}_t|$, which implies $\nu(\mathcal{F}_t) = |\mathcal{F}_t|$. Using the claim above, every chain with a set in layer $t$ must have a set in layer $t-1$ for all $t > \lfloor n/2 \rfloor$. The set system $\bar{\mathcal{F}} = \{[n] \setminus F : F \in \mathcal{F}\}$ is also $k$-antichain saturated. Applying Claim 4.2 to $\bar{\mathcal{F}}$, we find that every chain with a set of size $s < \lfloor n/2 \rfloor$ must have a set of size $s+1$ as well. Putting these together gives the following claim.

**Claim 4.3.** For all $i \in [k-1]$, $C^i$ contains an element from layer $\lfloor n/2 \rfloor$.

An immediate consequence of Claim 4.2 is that $|\mathcal{F}_{t-1}| \geq \nu(\mathcal{F}_t)$. Together with Lemma 2.4, this shows

$$|\mathcal{F}_{t-1}| \geq \nu(\mathcal{F}_t) \geq \nu(C), \qquad (4.1)$$

where $C$ is an initial segment of colex on $(\begin{smallmatrix} [n] \\ t \end{smallmatrix})$ of size $|\mathcal{F}_t|$. We already have $|\mathcal{F}_{\lfloor n/2 \rfloor}| = k-1$ (by Claim 4.3) and we want this for $\mathcal{F}_t$ down to $t = \lfloor \ell/2 \rfloor$. From (4.1), we can push this downwards at least when $\nu(C) = |C|$, and the following claim shows that this holds for all $t > \lfloor \ell/2 \rfloor$.

**Claim 4.4.** For $t > \lfloor \ell/2 \rfloor$, an initial segment of colex $C$ on layer $t$ of size at most $k-1$ has $\nu(C) = |C|$, and so $|\mathcal{F}_{t-1}| \geq |\mathcal{F}_t|$.

*Proof.* Let $\ell^*$ be the largest element in any set in $C$ i.e. $\ell^* = \max(\bigcup_{A \in C} A)$. If $t > \lfloor \ell^*/2 \rfloor$, then applying Lemma 2.2 to $[\ell^*]$ shows that there is a matching from $|C|$ to layer $t-1$ of $[\ell^*]$ of size $|C|$, and we are done. Suppose instead that $t \leq \lfloor \ell^*/2 \rfloor$. Since $C$ is an initial segment of colex, it must contain all subsets of $[\ell^* - 1]$ of size $t$ as well as a set containing $\ell^*$, but this means $C$ contains too many sets. Indeed,

$$1 + \binom{\ell^* - 1}{t} \geq 1 + \binom{2t - 1}{t} \geq 1 + \binom{\ell}{\lfloor \ell/2 \rfloor} \geq k. \quad \square$$

Combined with Claim 4.3, we find that layers $\lfloor \ell/2 \rfloor$ up to $\lfloor n/2 \rfloor$ all contain $k-1$ elements of $\mathcal{F}$.

For $t < \lfloor \ell/2 \rfloor$, if $|\mathcal{F}_{t+1}| \geq c_{t+1}$ then (4.1) shows that

$$|\mathcal{F}_t| \geq \nu(C(|\mathcal{F}_{t+1}|, t+1)) \geq \nu(C(c_{t+1}, t+1)) = c_t,$$

which concludes the proof of Lemma 4.1. $\square$
Note that, by complementing every set, Lemma 4.1 can be used to deduce lower bounds for layers close to $n$. Theorem 1.6 follows from using this observation and summing over every layer.

The lower bound in Corollary 1.7 is implied by the above using the simple observation that $\nu(\binom{[m]}{r}) = \binom{m}{r-1}$ provided $r \le \lfloor m/2 \rfloor$.

When $k-1 = \binom{\ell}{\lfloor \ell/2 \rfloor}$, we remark that all minimal $k$-antichain saturated set systems have a similar shape: layer $\lfloor \ell/2 \rfloor$ is the lowest layer with $k-1$ elements and induces an isomorphic copy of colex, layer $n - \lfloor \ell/2 \rfloor$ is the highest layer with $k-1$ elements and contains the complements of an isomorphic copy of an initial segment of colex, and the elements in between these two layers can be covered by $k-1$ skipless chains.

# 5. Upper bound constructions

We first describe the known upper bound construction in the case where $k-1$ is a central binomial coefficient. Combining this construction with the lower bound above gives Corollary 1.7. We then give the upper bound construction for Theorem 1.6 which works for all values of $k$, but requires a slightly larger value of $n$. Ignoring the minor changes we make to allow for smaller $n$, the first construction is a special case of the second construction.

## 5.1. The upper bound construction of Corollary 1.7

Let $\ell, k, n$ be integers such that $\binom{\ell}{\lfloor \ell/2 \rfloor} = k-1$ and $n \ge \ell + 1$. For the sake of completeness, we give a precise description of the construction from [FKK$^+$17], which shows

$$ \mathrm{sat}^*(n, k) \le 2 \sum_{j=0}^{\lfloor \ell/2 \rfloor} \binom{\ell}{j} + (k-1)(n-1-2\lfloor \ell/2 \rfloor). \quad (5.1) $$

We define a set system $\mathcal{F} \subseteq 2^{[n]}$ that is $k$-antichain saturated.

For $t \le \lfloor \ell/2 \rfloor$, the sets of size $t$ in $\mathcal{F}$ are exactly the subsets of $[\ell]$ of size $t$, and for $t \ge n - \lfloor \ell/2 \rfloor$, we add to $\mathcal{F}$ all subsets $X \subseteq [n]$ of size $t$ for which $[n] \setminus X$ is a subset of $[\ell]$. There are $k-1$ sets $\mathcal{F}$ of size $\lfloor \ell/2 \rfloor$ and $n - \lfloor \ell/2 \rfloor$, and we will join these up using Theorem 1.2.

For $\ell$ odd, we first fix a matching $M$ between $\binom{[\ell]}{\lfloor \ell/2 \rfloor}$ and $\binom{[\ell]}{\lfloor \ell/2 \rfloor}$, which exists by Lemma 2.2. When $\ell$ is even, we let $M$ be the identity. We denote by $M(X)$ the element matched to $X$ by $M$. Let $f: \mathcal{F}_{\lfloor \ell/2 \rfloor} \to \mathcal{F}_{n-\lfloor \ell/2 \rfloor}$ be given by

$$ f(X) = M(X) \cup [\ell + 1, n], $$

and note that $X \subseteq f(X)$ for all $X \in \mathcal{F}_{\lfloor \ell/2 \rfloor}$. To complete the family $\mathcal{F}$, we take any set of $k-1$ disjoint skipless chains between $\mathcal{F}_{\lfloor \ell/2 \rfloor}$ and $\mathcal{F}_{n-\lfloor \ell/2 \rfloor}$, which we know exist by Theorem 1.2 (or the result of Lehman and Ron).

To see that $\mathcal{F}$ has no antichain of size $k$, we note that it allows a decomposition into $k-1$ chains. Indeed, we may extend the previously obtained $k-1$ chains between layers $\lfloor \ell/2 \rfloor$
and $n - \lfloor \ell/2 \rfloor$, using any chain decomposition of $\lfloor \ell \rfloor$ restricted to the lowest $\lfloor \ell/2 \rfloor$ layers. We can similarly extend the chains to the layers $n - \lfloor \ell/2 \rfloor + 1, \dots, n$.

To see that $\mathcal{F}$ is saturated, note that we clearly cannot add any subset of size $t \in [\lfloor \ell/2 \rfloor, n - \lfloor \ell/2 \rfloor]$ since $\mathcal{F}$ already contains $k-1$ subsets of size $t$. For $t < \lfloor \ell/2 \rfloor$, any subset of size $t$ that is not yet in $\mathcal{F}$ must contain some element $i > \ell$ and is therefore incomparable to the $k-1$ elements of $\mathcal{F} \cap (\lfloor \frac{n}{\ell/2} \rfloor)$. A similar argument holds for $t > n - \lfloor \ell/2 \rfloor$.

By counting the number of sets in each layer, we find that

$$|\mathcal{F}| = 2 \sum_{j=0}^{\lfloor \ell/2 \rfloor} \binom{\ell}{j} + (k-1)(n-1-2\lfloor \ell/2 \rfloor),$$

as required.

## 5.2. Upper bound for Theorem 1.6

In this subsection, we prove the following lemma, which is the upper bound of Theorem 1.6. Recall that for a given $k \ge 1$, we let $\ell$ be the smallest integer $j$ such that $\binom{j}{\lfloor j/2 \rfloor} \ge k-1$, and we recursively define $c_0, c_1, \dots, c_{\lfloor \ell/2 \rfloor}$ as follows. Let $c_{\lfloor \ell/2 \rfloor} = k-1$ and, for $0 \le t < \lfloor \ell/2 \rfloor$, let $c_t = \nu(C(c_{t+1}, t+1))$. We will show that there is a $k$-antichain saturated set system $\mathcal{F}$ where $\mathcal{F}_t$ and $\mathcal{F}_{n-t}$ contain $c_t$ sets for all $t \le \lfloor \ell/2 \rfloor$, which gives the following result.

**Lemma 5.1.** *Using the notation above,*

$$\mathrm{sat}^*(n, k) \le 2 \sum_{t=0}^{\lfloor \ell/2 \rfloor} c_t + (k-1)(n-1-2\lfloor \ell/2 \rfloor)$$

provided $n \ge 2\ell + 1$.

Lemma 2.4 shows that $\nu(\mathcal{B})$ with $\mathcal{B} \in (\lfloor \frac{n}{t} \rfloor)$ is minimised when taking $\mathcal{B}$ to be an initial segment of colex. We wish to construct a set system $\mathcal{F}$, such that $\nu(\mathcal{F}_t) = \nu(C(|\mathcal{F}_t|, t))$ for all $t \le \lfloor \ell/2 \rfloor$, yet $\mathcal{F}$ can be covered by $k-1$ chains.

Suppose that each set in $C(m, r)$ is in a chain and consider how many continue to the layer below. Lemma 2.6 shows that the only ‘savings’ $m - \nu(C(m, r))$ come from the initial sequence where $j \le \lceil a_j/2 \rceil$, and that we need to continue the chains for the remaining terms to the layer below. This gives us some freedom to not use the initial segment of colex for these continuing chains, and we will instead take them so that we have a suitable initial segment of colex on a smaller layer. To do this, we will change the later terms in the $r$-cascade notation of $m$, so that they are part of the expansion of a later layer and use the new expansion to define $\mathcal{F}$. We now introduce this different way of writing of $m$ as a sum of binomial coefficients that gives our new expansion.

Given $m, r \ge 1$ such that $m \ge \binom{2r-1}{r}$. Let the $r$-expansion of $m$ be

$$m = \binom{a_{r_1}}{r_1} + \dots + \binom{a_{r_s}}{r_s}$$
recursively formed as follows. Let $r_1 = r$ and define $a_{r_1}$ as the maximum $j$ such that $\binom{j}{r_1} \le m$. Note that $a_{r_1} \ge 2r_1 - 1$. Set $m' = m - \binom{a_{r_1}}{r_1}$. If $m' = 0$, we are done. Otherwise, let $r'$ be the maximum $j \le r - 1$ such that $\binom{2j-1}{j} \le m'$ and form the $r$-expansion of $m$ by appending to $\binom{a_{r_1}}{r_1}$ the $r'$-expansion of $m'$. It is easy to see that this is well-defined and must terminate.

As an example, let us consider the 5-expansion of $m = 1011$. Since $\binom{12}{5} < 1011 < \binom{13}{5}$, we take $a_{r_1} = 12$ (and $r_1 = 5$). This means $m' = 219$, and the largest integer $j \le 4$ such that $\binom{2j-1}{j} \ge m'$ is $j = 4$ (we also have $\binom{9}{5} \le m'$, but this is not allowed). We therefore append the 4-expansion of 219. Calculating this recursively in the same manner, we see $a_{r_2} = 10$ (and $r_2 = 4$), which leaves a remainder of 9. Since $\binom{4}{2} \le 9 < \binom{5}{3}$, we append the 2-expansion of 9, which is $\binom{4}{2} + \binom{3}{1}$. This gives the 5 expansion of 1011 as

$$1011 = \binom{12}{5} + \binom{10}{4} + \binom{4}{2} + \binom{3}{1}.$$

The following lemma gives some properties of the $r$-expansion of an integer $m$.

**Lemma 5.2.** Let $m, r \ge 1$ be such that $m \ge \binom{2r-1}{r}$. Let the $r$-expansion of $m$ be

$$m = \binom{a_{r_1}}{r_1} + \dots + \binom{a_{r_s}}{r_s}.$$

Then the following statements hold:

1. $r = r_1 > \dots > r_s \ge 1$;

2. $a_{r_1} > \dots > a_{r_s} \ge 1$;

3. for all $i \in [s]$, we have $r_i \le \lfloor a_{r_i} / 2 \rfloor$.

*Proof.* We prove this by induction on $s$. There is nothing to prove for the base case $s = 1$. Suppose that $s \ge 2$. Using $m'$ and $r'$ as in the definition of the $r$-expansion and applying the induction hypothesis to the $r$-expansion of $m'$ (which has $s-1$ terms), the following must hold:

* $r' = r_2 > \dots > r_s \ge 1$;

* $a_{r_2} > \dots > a_{r_s} \ge 1$;

* for all $i \in [2, s]$, we have $r_i \le \lfloor a_{r_i} / 2 \rfloor$.

By definition we have $r = r_1 > r_2$ and it follows from $m \ge \binom{2r-1}{r}$, that $r_1 \le \lfloor a_{r_1} / 2 \rfloor$. Hence, we only need to check that $a_{r_1} > a_{r_2}$.

Suppose first that $r' = r - 1$. If $a_{r_2} \ge a_{r_1}$, we have

$$m \ge \binom{a_{r_1}}{r_1} + \binom{a_{r_1}}{r_1-1} = \binom{a_{r_1}+1}{r_1}$$

which contradicts the definition of $a_{r_1}$. If $r' \le r - 2$, then $a_{r_2} \ge a_{r_1} \ge 2r' + 3$, and so

$$\binom{2r' + 3}{r'} \ge \binom{2r' + 1}{r'} = \binom{2(r' + 1) - 1}{r' + 1}.$$

This contradicts our choice of $r'$.

□
By the lemma, $r_1 \ge r_2 + 1 \ge r_3 + 2 \ge \dots \ge r_s + (s-1)$. Using the observation that $\binom{m+1}{r} = \sum_{i=0}^{r} \binom{m-i}{r-i}$, we obtain the following simple lemma.

**Lemma 5.3.** Suppose that $m, r \ge 1$ satisfy $m \ge \binom{2r-1}{r}$. Let the $r$-expansion of $m$ be

$$m = \binom{a_{r_1}}{r_1} + \dots + \binom{a_{r_s}}{r_s}.$$

Fix $t \in [r]$ and let $i$ be the unique integer such that $r_i + (i-1) \ge t > r_{i+1} + i$ (where we take $r_{s+1} = -s-1$). Suppose that $i \le s-1$ and define $m'$ by

$$m' = \binom{a_{r_1}}{t} + \dots + \binom{a_{r_i}}{t-(i-1)} + \binom{a_{r_{i+1}}}{r_{i+1}} + \dots + \binom{a_{r_s}}{r_s}.$$

Then the expression above gives the $t$-expansion of $m'$.

*Proof.* Suppose that the $t$-expansion of $m'$ is not as claimed, but that instead the $t$-expansion of $m'$ is

$$m' = \binom{a'_{r_1}}{r_1'} + \dots + \binom{a'_{r_p}}{r_p'}.$$

Let $j$ be the first point at which this expansion differs from the claimed expansion. If $j \ge i+1$ then

$$\binom{a_{r_{i+1}}}{r_{i+1}} + \dots + \binom{a_{r_s}}{r_s} = \binom{a'_{r'_{i+1}}}{r'_{i+1}} + \dots + \binom{a'_{r'_p}}{r'_p},$$

but looking at the definition of the $r$-expansion, both of these come from exactly the same recursion.

Instead, we must have $j \le i$. We first prove $r'_j = t - (j-1)$. Note that $r'_1 = t$ so $j > 1$ and $r'_{j-1} = t - (j-2)$. This implies $r'_j \le t - (j-1)$. From the definition of $i$, we find that $r_j + (j-1) \ge r_i + (i-1) \ge t$ and so $r_j \ge t - (j-1)$. Let $m'' = m' - \binom{a_{r_1}}{t} - \dots - \binom{a_{r_{j-1}}}{t-(j-2)}$. Then $m'' \ge \binom{a_{r_j}}{t-j+1} \ge \binom{2(t-j)+1}{t-j+1}$ and so $r'_j \ge t - (j-1)$.

Since $r'_j = t - (j-1)$, it must be the case that $a_{r_j} \ne a'_{r'_j}$. However,

$$\begin{align*}
m'' &= \binom{a_{r_j}}{t-(j-1)} + \dots + \binom{a_{r_i}}{t-(i-1)} + \binom{a_{r_{i+1}}}{r_{i+1}} + \dots + \binom{a_{r_s}}{r_s} \\
&\le \binom{a_{r_j}}{t-(j-1)} + \binom{a_{r_j}-1}{t-j} + \dots + \binom{a_{r_j}-(t-j)}{1} \\
&< 1 + \binom{a_{r_j}}{t-(j-1)} + \binom{a_{r_j}-1}{t-j} + \dots + \binom{a_{r_j}-(t-j)}{1} \\
&= \binom{a_{r_j}+1}{t-(j-1)}.
\end{align*}$$

That is

$$\binom{a_{r_j}}{t-(j-1)} \le m'' < \binom{a_{r_j}+1}{t-(j-1)},$$

and $a'_{r'_j} = a_{r_j}$ by definition. $\square$
We are now ready to prove Lemma 5.1.

*Proof of Lemma 5.1.* Let $\ell$ be the smallest integer $j$ such that $\binom{j}{\lfloor j/2 \rfloor} \ge k-1$. We have

$$k-1 \ge \binom{\ell-1}{\lfloor(\ell-1)/2\rfloor} = \binom{\ell-1}{\lfloor(\ell-1)/2\rfloor} = \binom{\ell-1}{\lfloor\ell/2\rfloor} \ge \binom{2\lfloor\ell/2\rfloor-1}{\lfloor\ell/2\rfloor}.$$

Let the $\lfloor\ell/2\rfloor$-expansion of $k-1$ be

$$k-1 = \binom{a_{r_1}}{r_1} + \dots + \binom{a_{r_s}}{r_s}$$

where $\lfloor\ell/2\rfloor = r_1 > \dots > r_s \ge 1$, $a_{r_1} > \dots > a_{r_s} > 0$ and $r_i \le \lfloor a_{r_i}/2 \rfloor$ for all $i \in [s]$. These facts are guaranteed by Lemma 5.2. The specific case where $a_{r_1} = \ell$ has been treated previously in Section 5.1, so we can suppose that $a_{r_1} \le \ell-1$.

We now define our construction by processing each of the terms in this expansion. Initialize $\mathcal{I}$ as an empty set of chains. For each $i \in [s]$, let $\mathcal{A}_i$ be the set system consisting of sets of the form

$$A = X \cup \{a_{r_1} + 1, a_{r_2} + 1, \dots, a_{r_{i-1}} + 1\}$$

where $X$ is a subset of $[a_{r_i}]$ of size at most $r_i$. Note that the largest element in any of these sets is either $a_{r_1}$ or $a_{r_1} + 1$, and hence all sets are contained in $[\ell]$.

Since $r_i \le \lfloor a_{r_i}/2 \rfloor$, we can cover $\mathcal{A}_i$ with $\binom{a_{r_i}}{r_i}$ disjoint chains, and we add these chains to our collection of chains $\mathcal{I}$. Indeed, we may start with the chains from a symmetric chain decomposition of $2^{[a_{r_i}]}$ and add the elements $a_{r_1} + 1, a_{r_2} + 1, \dots, a_{r_{i-1}} + 1$ to every set. Then we discard any sets which are not in $\mathcal{A}_i$ and remove any empty chains to leave the required chain covering.

Define $f: 2^{[n]} \to 2^{[n]}$ by $f(A) = \{i \in [n] : n+1-i \notin A\}$. Form a second set of chains $\mathcal{I}'$ by replacing each chain $C \in \mathcal{I}$ by $\{f(A) : A \in C\}$. Since we have assumed that $n \ge 2\ell+1$, we have that $A \subseteq f(A)$ for any set $A \subseteq [\ell]$, and these are indeed chains. The chains in $\mathcal{I}'$ are also disjoint and we can apply Theorem 1.2 to find disjoint chains $D^1, \dots, D^{k-1}$ which cover all sets in $\mathcal{I} \cup \mathcal{I}'$ and are skipless. We take $\mathcal{F}$ to be the union of $D^1, \dots, D^{k-1}$. See Figure 5.1 for a depiction of a set system constructed as above.

The set system $\mathcal{F}$ is the union of $k-1$ chains, so cannot contain an antichain of size $k$. We now argue that adding any set $X$ to $\mathcal{F}$ creates an antichain of size $k$. Let $|X| = t$. If $\lfloor\ell/2\rfloor \le t \le n - \lfloor\ell/2\rfloor$, then adding $X$ creates an antichain of size $k$ as $\mathcal{F}$ already contains $k-1$ sets in layer $t$. We can assume that $1 \le t < \lfloor\ell/2\rfloor$, else we can consider adding the set $f(X) = \{i \in [n] : n+1-i \notin X\}$ instead. Set $r_{s+1} = -s-1$. The sequence $\lfloor\ell/2\rfloor = r_1, r_2+1, \dots, r_{s+1}+s = -1$ is non-increasing so there is a unique $i$ such that $r_i + (i-1) \ge t > r_{i+1} + i$. Let $\mathcal{D}_j = \{A \cup \{a_{r_1} + 1, \dots, a_{r_{j-1}} + 1\} : A \in \binom{[a_{r_j}]}{r_j}\}$ and let $\mathcal{D}$ be the set of all sets in $\mathcal{F}_t$ which contain $a_{r_1} + 1, \dots, a_{r_i} + 1$. Note that for $1 \le j \le i$, sets in $\mathcal{D}_j$ have size $r_j + (j-1) \ge t = |X|$.

We claim that the following subset of $\mathcal{F} \cup \{X\}$ is an antichain of size $k$:

$$\left( \bigcup_{j=1}^{i} \mathcal{D}_j \right) \cup \{X\} \cup \mathcal{D}.$$
<figure><img src="image_6.png" /><figcaption>Figure 5.1: The shape of our upper bound construction is depicted. We represent layers horizontally (starting with the lowest at the bottom). For some, we indicated the number of the layer (e.g. layer $n - r_3 - 2$).</figcaption></figure>

By definition, $|\mathcal{D}_j| = \binom{a_j}{r_j}$ for $j \in [i]$ and $|\mathcal{D}| = \sum_{j=i+1}^{s} \binom{a_j}{r_j}$ so indeed the collection has size $k$. It is immediate that $\mathcal{D} \cup \{X\}$ forms an antichain since all sets have the same size. We note that for $A, B \in (\bigcup_{j=1}^{i} \mathcal{D}_j) \cup \mathcal{D}$ with $|A| < |B|$, we must have $B \in \mathcal{D}_j$ for some $j$ and $A \in (\bigcup_{r=j+1}^{i} \mathcal{D}_r) \cup \mathcal{D}$. Hence, the element $a_{r_j} + 1 \in A \setminus B$, and $(\bigcup_{j=1}^{i} \mathcal{D}_j) \cup \mathcal{D}$ is an antichain. It remains to check that $\{X\} \cup (\bigcup_{j=1}^{i} \mathcal{D}_j)$ is an antichain as well. For $j \in [i]$ and $A \in \mathcal{D}_j$, the set $A$ cannot be a subset of $X$ as $|A| = r_j + (j-1) \ge t$. Suppose towards a contradiction that $X \subseteq A \in \mathcal{D}_j$. Then $X \subseteq [a_{r_j}] \cup \{a_{r_1} + 1, \dots, a_{r_{j-1}+1}\}$. Let $x \in [j]$ be the smallest integer such that $a_{r_x} + 1 \notin X$, and note $x < j$. Then, since $a_{r_y} < a_{r_x}$ for all $y > x$, we find that

$$X \setminus \{a_{r_1} + 1, \dots, a_{r_{x-1}} + 1\} \subseteq [a_{r_j}] \cup \{a_{r_{x+1}} + 1, \dots, a_{r_{j-1}+1}\} \subseteq [a_{r_x}],$$

and so $X \in \mathcal{A}_x \subseteq \mathcal{F}$, contradicting our choice $X \notin \mathcal{F}$. This shows the set system is indeed an antichain.

We have shown that $\mathcal{F}$ is $k$-antichain saturated, and it remains to check that $\mathcal{F}$ has the claimed size. By construction, we have

$$\mathcal{F} = 2 \sum_{t=0}^{\lfloor \ell/2 \rfloor} |\mathcal{F}_t| + (k-1)(n-1-2\lfloor \ell/2 \rfloor),$$
so we need to show that $|\mathcal{F}_t| = c_t$ for all $t \le c_t$. We have that $|\mathcal{F}_{\lfloor \ell/2 \rfloor}| = k-1 = c_{\lfloor \ell/2 \rfloor}$, and let us suppose that $|\mathcal{F}_t| = c_t$. We will show that $|\mathcal{F}_{t-1}| = c_{t-1}$. Define $i$ to be the unique integer such that $r_i + (i-1) \ge t > r_{i+1} + i$ (where we again take $r_{s+1} = -s-1$). Suppose first that $i \le s-1$. First, note that we have

$$|\mathcal{F}_t| = \binom{a_{r_1}}{t} + \dots + \binom{a_{r_i}}{t-(i-1)} + \binom{a_{r_{i+1}}}{r_{i+1}} + \dots + \binom{a_{r_s}}{r_s}. \quad (5.2)$$

Indeed, the family $\mathcal{F}_t$ consists of the sets in $A_1, \dots, A_i$ of size $t$ (there are $\binom{a_{r_j}}{t-(j-1)}$ such sets in $A_j$) and one set from each chain containing a maximal set of $A_{i+1}, \dots, A_s$ (and there are $\binom{a_{r_j}}{r_j}$ maximal sets in $A_j$). By Lemma 5.3, the expansion in (5.2) is the $t$-expansion of $|\mathcal{F}_t|$. We may also write $|\mathcal{F}_t|$ in its $t$-cascade notation (see (2.1)) as

$$|\mathcal{F}_t| = \binom{b_t}{t} + \binom{b_{t-1}}{t-1} + \dots + \binom{b_{s'}}{s'}$$

where $b_t > \dots > b_{s'}$, $s' \ge 1$ and $b_j \ge j$ for all $j \in [s', t]$. Note that both $a_{r_j}$ and $b_j$ are defined, we must have $b_t = a_{r_1}$, $b_{t-1} = a_{r_2}$, and so on until $b_{t-i+1} = a_{r_i}$. That is,

$$|\mathcal{F}_t| = \binom{a_{r_1}}{t} + \dots + \binom{a_{r_i}}{t-(i-1)} + \binom{b_{t-i}}{t-i} + \dots + \binom{b_{s'}}{s'}.$$

If $t-i \le \lceil b_{t-i}/2 \rceil$, then we would take $r_{i+1} = t-i$ in the $t$-expansion of $|\mathcal{F}_t|$, but this contradicts the value of $i$. Hence, $t-i > \lceil b_{t-i}/2 \rceil$ and Lemma 2.6 shows that $c_{t-1}$ is given by

$$c_{t-1} = \binom{a_{r_1}}{t-1} + \dots + \binom{a_{r_i}}{t-i} + \binom{b_{t-i}}{t-i} + \dots + \binom{b_{s'}}{s'}$$

and this is exactly $|\mathcal{F}_{t-1}|$.

If $i=s$, then $\mathcal{F}_t$ is actually an initial segment of colex. Indeed, all the elements of $\mathcal{F}_t$ come from the $A_j$ and no sets are added to layer $t$ when we apply Theorem 1.2. This means $\mathcal{F}_t$ consists of all sets of the form

$$X \cup \{a_{r_1} + 1, a_{r_2} + 1, \dots, a_{r_{j-1}} + 1\}$$

where $X$ is a subset of $[a_{r_j}]$ of size exactly $t-(j-1)$ where $j \in [s]$. This is exactly the initial segment of colex of size $|\mathcal{F}_t|$, and we have $|\mathcal{F}_{t-1}| = |\nu(\mathcal{F}_t)| = c_{t-1}$. Hence, $|\mathcal{F}_{t-1}| = c_{t-1}$, as required. The result now follows by induction. $\square$

# 6. Open problems

Theorem 1.6 gives the exact value of $\mathrm{sat}^*(n, k)$ for most values of $n$ and $k$, but it leaves a range $\ell \le n \le 2\ell$ for which the exact value is not known. For these values of $n$, the upper bound construction works separately on the lower half of the Boolean lattice and on the upper half, but it is not clear that we can join these constructions up. With a little more care, we believe we can reduce this gap by proving the upper bound for slightly smaller values of $n$, but we do not know how to reduce this all the way down to $\ell$.
**Problem 6.1.** Is the lower bound of Theorem 1.6 correct for all $\ell \le n \le 2\ell$?

Several other interesting questions concerning induced poset saturation number remain open, amongst which the question of which asymptotical behaviours are possible. Let $sat^*(n, \mathcal{P})$ denote the smallest size of a set system $\mathcal{F} \subseteq 2^{[n]}$ which is (induced) $\mathcal{P}$-saturated. A recent result of [FPST23] shows that either $sat^*(n, \mathcal{P}) = O(1)$ or $sat^*(n, \mathcal{P}) \ge 2\sqrt{n-2}$. This result has been conjectured to be tight for the diamond [Iva22] but it has also been conjectured by [KLM$^+$21] that the general lower bound can be improved to $sat^*(n, \mathcal{P}) \ge n+1$ for any poset $\mathcal{P}$.

A natural question that one could ask is whether Theorem 1.2 extends to other posets. The result of Lehman and Ron has already been generalised to a vast class of posets including geometric lattices by Logan and Shahriari [LS04], and our generalisation may also extend. Note that, following the proof of Theorem 1.2, it would suffice to prove an analogue of Lemma 3.2. An extension of Theorem 1.2 to other posets might also make it possible to determine the asymptotics of their antichain saturation numbers.

**References**

[Aig73] Martin Aigner. Lexicographic matching in Boolean algebras. *Journal of Combinatorial Theory, Series B*, 14(3):187–194, 1973. doi:10.1016/0095-8956(73)90001-4.

[BS96] Béla Bajnok and Shahriar Shahriari. Long symmetric chains in the boolean lattice. *Journal of Combinatorial Theory, Series A*, 75(1):44–54, 1996. doi:10.1006/jcta.1996.0062.

[DHL19] Dwight Duffus, David Howard, and Imre Leader. The width of downsets. *European Journal of Combinatorics*, 79:46–59, 2019. doi:10.1016/j.ejc.2018.11.005.

[Dil50] Robert P. Dilworth. A decomposition theorem for partially ordered sets. *Annals of Mathematics*, 51(1):161–166, 1950. doi:10.2307/1969503.

[FKK$^+$17] Michael Ferrara, Bill Kay, Lucas Kramer, Ryan R. Martin, Benjamin Reiniger, Heather C. Smith, and Eric Sullivan. The saturation number of induced subposets of the Boolean lattice. *Discrete Mathematics*, 340(10):2479–2487, 2017. doi:10.1016/j.disc.2017.06.010.

[FPST23] Andrea Freschi, Simón Piga, Maryam Sharifzadeh, and Andrew Treglown. The induced saturation problem for posets. *Combinatorial Theory*, 3(3), 2023. doi:10.5070/c63362792.

[GK76] Curtis Greene and Daniel J. Kleitman. Strong versions of Sperner's theorem. *Journal of Combinatorial Theory, Series A*, 20(1):80–88, 1976. doi:10.1016/0097-3165(76)90079-0.

[GKL$^+$13] Dániel Gerbner, Balázs Keszegh, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, and Balázs Patkós. Saturating Sperner families. *Graphs and Combinatorics*, 29(5):1355–1364, 2013. doi:10.1007/s00373-012-1195-6.
[Gri82] Jerrold R. Griggs. Collections of subsets with the Sperner property. *Transactions of the American Mathematical Society*, 269(2):575-591, 1982. doi:10.1090/ s0002-9947-1982-0637711-2.

[ĐI23] Irina Đanković and Maria-Romina Ivan. Saturation for small antichains. *The Electronic Journal of Combinatorics*, 20(1):P1-3, 2023. doi:10.37236/11262.

[Iva20] Maria-Romina Ivan. Saturation for the butterfly poset. *Mathematika*, 66(2):806-817, 2020. doi:10.1112/mtk.12044.

[Iva22] Maria-Romina Ivan. Minimal diamond-saturated families. *Contemporary Mathematics*, 3(2), 2022. doi:10.37256/cm.3220221333.

[Kle75] D. J. Kleitman. On an extremal property of antichains in partial orders. the lym property and some of its implications and applications. In M. Hall and J. H. van Lint, editors, *Combinatorics*, pages 277-290. Springer Netherlands, 1975.

[KLM$^{+}$21] Balázs Keszegh, Nathan Lemons, Ryan R. Martin, Dömötör Pálvölgyi, and Balázs Patkós. Induced and non-induced poset saturation problems. *Journal of Combinatorial Theory, Series A*, 184:105497, 2021. doi:10.1016/j.jcta.2021.105497.

[Kru63] Joseph B. Kruskal. The number of simplices in a complex. *Mathematical optimization techniques*, 10:251-278, 1963.

[Log02] Mark J. Logan. Sperner theory in a difference of boolean lattices. *Discrete Mathematics*, 257(2-3):501-512, 2002. doi:10.1016/s0012-365x(02)00509-5.

[LR01] Eric Lehman and Dana Ron. On disjoint chains of subsets. *Journal of Combinatorial Theory, Series A*, 94(2):399-404, 2001. doi:10.1006/jcta.2000.3148.

[LS04] Mark J. Logan and Shahriar Shahriari. A new matching property for posets and existence of disjoint chains. *Journal of Combinatorial Theory, Series A*, 108(1):77-87, 2004. doi:10.1016/j.jcta.2004.06.002.

[Men27] Karl Menger. Zur allgemeinen kurventheorie. *Fundamenta Mathematicae*, 10(1):96-115, 1927. doi:10.4064/fm-10-1-96-115.

[MNS14] Natasha Morrison, Jonathan A. Noel, and Alex Scott. On saturated *k*-Sperner systems. *The Electronic Journal of Combinatorics*, 21(3):P3.22, 2014. doi: 10.37236/4136.

[MSW20] Ryan R. Martin, Heather C. Smith, and Shanise Walker. Improved bounds for induced poset saturation. *The Electronic Journal of Combinatorics*, 27(2):P2.31, 2020. doi:10.37236/8949.

[Sak79] Michael Saks. A short proof of the existence of *k*-saturated partitions of partially ordered sets. *Advances in Mathematics*, 33(3):207-2011, 1979. doi:10.1016/ 0001-8708(79)90010-0.

[Spe28] Emanuel Sperner. Ein Satz über Untermengen einer endlichen Menge. *Mathematische Zeitschrift*, 27(1):544-548, 1928. doi:10.1007/BF01171114.

[STW22] Benny Sudakov, István Tomon, and Adam Zsolt Wagner. Uniform chain decompositions and applications. *Random Structures & Algorithms*, 60(2):261-286, 2022. doi:10.1002/rsa.21034.