# The induced saturation problem for posets

Andrea Freschi, Simón Piga, Maryam Sharifzadeh and Andrew Treglown

###### Abstract.

For a fixed poset $P$, a family $\mathcal{F}$ of subsets of $[n]$ is induced
$P$-saturated if $\mathcal{F}$ does not contain an induced copy of $P$, but
for every subset $S$ of $[n]$ such that $S\not\in\mathcal{F}$, then $P$ is an
induced subposet of $\mathcal{F}\cup\\{S\\}$. The size of the smallest such
family $\mathcal{F}$ is denoted by $\text{sat}^{*}(n,P)$. Keszegh, Lemons,
Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021]
proved that there is a dichotomy of behaviour for this parameter: given any
poset $P$, either $\text{sat}^{*}(n,P)=O(1)$ or
$\text{sat}^{*}(n,P)\geqslant\log_{2}n$. In this paper we improve this general
result showing that either $\text{sat}^{*}(n,P)=O(1)$ or
$\text{sat}^{*}(n,P)\geqslant 2\sqrt{n-2}$. Our proof makes use of a Turán-
type result for digraphs.

Curiously, it remains open as to whether our result is essentially best
possible or not. On the one hand, a conjecture of Ivan states that for the so-
called diamond poset $\Diamond$ we have
$\text{sat}^{*}(n,\Diamond)=\Theta(\sqrt{n})$; so if true this conjecture
implies our result is tight up to a multiplicative constant. On the other
hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states
that given any poset $P$, either $\text{sat}^{*}(n,P)=O(1)$ or
$\text{sat}^{*}(n,P)\geqslant n+1$. We prove that this latter conjecture is
true for a certain class of posets $P$.

AF: University of Birmingham, United Kingdom<EMAIL_ADDRESS>
SP: University of Birmingham, United Kingdom<EMAIL_ADDRESS>research
supported by EPSRC grant EP/V002279/1.
MS: Umeå Universitet, Sweden<EMAIL_ADDRESS>
AT: University of Birmingham, United Kingdom<EMAIL_ADDRESS>research supported by EPSRC grant EP/V002279/1.

##  1\. Introduction

_Saturation_ problems have been well studied in graph theory. A graph $G$ is
_$H$ -saturated_ if it does not contain a copy of the graph $H$, but adding
any edge to $G$ from its complement creates a copy of $H$. Turán’s celebrated
theorem [13] can be stated in the language of saturation: it determines the
maximum number of edges in a $K_{r}$-saturated $n$-vertex graph. In contrast,
Erdős, Hajnal and Moon [4] determined the minimum number of edges in a
$K_{r}$-saturated $n$-vertex graph; see the survey [2] for further results in
this direction.

In recent years there has been an emphasis on developing the theory of
saturation for posets. Turán-type problems have been extensively studied in
this setting (see, e.g., the survey [7]). In this paper we are interested in
_minimum_ saturation questions à la Erdős–Hajnal–Moon. In particular, we
consider _induced saturation_ problems.

All posets we consider will be (implicitly) viewed as finite collections of
finite subsets of $\mathds{N}$. In particular, we say that $P$ is a _poset on
$[p]:=\\{1,2,\dots,p\\}$_ if $P$ consists of subsets of $[p]$. Let $P,Q$ be
posets. A _poset homomorphism_ from $P$ to $Q$ is a function $\phi:\
P\rightarrow Q$ such that for every $A,B\in P$, if $A\subseteq B$ then
$\phi(A)\subseteq\phi(B)$. We say that $P$ is a _subposet_ of $Q$ if there is
an injective poset homomorphism from $P$ to $Q$; otherwise, $Q$ is said to be
_$P$ -free_. Further we say $P$ is an _induced subposet_ of $Q$ if there is an
injective poset homomorphism $\phi$ from $P$ to $Q$ such that for every
$A,B\in P$, $\phi(A)\subseteq\phi(B)$ if and only if $A\subseteq B$;
otherwise, $Q$ is said to be _induced $P$-free_.

For a fixed poset $P$, we say that a family $\mathcal{F}\subseteq 2^{[n]}$ of
subsets of $[n]$ is _$P$ -saturated_ if $\mathcal{F}$ is $P$-free, but for
every subset $S$ of $[n]$ such that $S\not\in\mathcal{F}$, then $P$ is a
subposet of $\mathcal{F}\cup\\{S\\}$. A family $\mathcal{F}\subseteq 2^{[n]}$
of subsets of $[n]$ is _induced $P$-saturated_ if $\mathcal{F}$ is induced
$P$-free, but for every subset $S$ of $[n]$ such that $S\not\in\mathcal{F}$,
then $P$ is an induced subposet of $\mathcal{F}\cup\\{S\\}$.

The study of minimum saturated posets was initiated by Gerbner, Keszegh,
Lemons, Palmer, Pálvölgyi and Patkós [6] in 2013. In their work the relevant
parameter is $\text{sat}(n,P)$, which is defined to be the size of the
smallest $P$-saturated family of subsets of $[n]$. See, e.g., [6, 10, 12] for
various results on $\text{sat}(n,P)$.

The induced analogue of $\text{sat}(n,P)$ – denoted by $\text{sat}^{*}(n,P)$ –
was first considered by Ferrara, Kay, Kramer, Martin, Reiniger, Smith and
Sullivan [5]. Thus, $\text{sat}^{*}(n,P)$ is defined to be the size of the
smallest induced $P$-saturated family of subsets of $[n]$. The following
result from [10] (and implicit in [5]) shows that the parameter
$\text{sat}^{*}(n,P)$ has a dichotomy of behaviour.

######  Theorem 1.1.

[5, 10] For any poset $P$, either there exists a constant $K_{P}$ with
$\text{sat}^{*}(n,P)\leqslant K_{P}$ or
$\text{sat}^{*}(n,P)\geqslant\log_{2}n$, for all $n\in\mathds{N}$.

Probably the most important open problem in the area is to obtain a tight
version of Theorem 1.1; that is, to replace the $\log_{2}n$ in Theorem 1.1
with a term that is as large as possible. In fact, Keszegh, Lemons, Martin,
Pálvölgyi and Patkós [10] made the following conjecture in this direction.

######  Conjecture 1.2.

[10] For any poset $P$, either there exists a constant $K_{P}$ with
$\text{sat}^{*}(n,P)\leqslant K_{P}$ or $\text{sat}^{*}(n,P)\geqslant n+1$,
for all $n\in\mathds{N}$.

Note that the lower bound of $n+1$ is rather natural here. For example, it is
the size of the largest _chain_ in $2^{[n]}$ as well as the smallest possible
size of the union of two ‘layers’ in $2^{[n]}$. Furthermore, such structures
form minimum induced saturated families for the so-called fork poset $\vee$,
i.e., $\text{sat}^{*}(n,\vee)=n+1$ [5]; so the lower bound in Conjecture 1.2
cannot be increased. There are also no known examples of posets $P$ for which
$\text{sat}^{*}(n,P)=\omega(n)$.

In contrast, Ivan [9, Section 3] presented evidence that led her to conjecture
a rather different picture for the _diamond_ poset $\Diamond$ (see Figure 1
for the Hasse diagram of $\Diamond$).

######  Conjecture 1.3.

[9] $\text{sat}^{*}(n,\Diamond)=\Theta(\sqrt{n}).$

Our main result is the following improvement of Theorem 1.1.

######  Theorem 1.4.

For any poset $P$, either there exists a constant $K_{P}$ with
$\text{sat}^{*}(n,P)\leqslant K_{P}$ or
$\text{sat}^{*}(n,\mathcal{P})\geqslant 2\sqrt{n-2}$, for all
$n\in\mathds{N}$.

Thus, if Conjecture 1.3 is true, the lower bound in Theorem 1.4 would be tight
up to a multiplicative constant.

Figure 1. Hasse diagrams for the posets $N$, $Y$, $\Diamond$ and $X$.

On the other hand, we prove that Conjecture 1.2 does hold for a class of
posets (that does not include $\Diamond$). Given $p\in\mathds{N}$ and a poset
$P$ on $[p]$ we define $\overline{P}:=\\{[p]\setminus F\colon F\in P\\}$. We
say a poset $P$  _has legs_ if there are distinct elements $L_{1},L_{2},H\in
P$ such that $L_{1},L_{2}$ are incomparable, $L_{1},L_{2}\subseteq H$ and for
any other element $A\in P\setminus\\{L_{1},L_{2},H\\}$ we have $A\supseteq H$.
The elements $L_{1}$ and $L_{2}$ are called _legs_ and $H$ is called a _hip_.

######  Theorem 1.5.

Let $P$ be a poset with legs and $n\geqslant 3$. Then
$\text{sat}^{*}(n,P)\geqslant n+1$. Moreover, if both $P$ and $\overline{P}$
have legs, then $\text{sat}^{*}(n,P)\geqslant 2n+2$.

Our results still leave both Conjecture 1.2 and Conjecture 1.3 open, and it is
unclear to us which of these conjectures is true. However, if Conjecture 1.3
is true we believe it highly likely that there will be other posets $P$ for
which $\text{sat}^{*}(n,P)=\Theta(\sqrt{n})$.

It is also natural to seek exact results on $\text{sat}^{*}(n,P)$. However,
despite there already being several papers concerning $\text{sat}^{*}(n,P)$
[3, 5, 8, 9, 10, 11], there are relatively few posets $P$ for which
$\text{sat}^{*}(n,P)$ is known precisely (see Table 1 in [10] for a summary of
most of the known results). Our next result extends this limited pool of
posets, determining $\text{sat}^{*}(n,X)$ and $\text{sat}^{*}(n,Y)$ (see
Figure 1 for the Hasse diagrams of $X$ and $Y$).

######  Theorem 1.6.

Given any $n\in\mathds{N}$ with $n\geqslant 3$,

  1. ( )

$\text{sat}^{*}(n,Y)=n+2$ and

  2. ( )

$\text{sat}^{*}(n,X)=2n+2$.

Note that Theorem 1.6( ) ‣ 1.6 easily follows via Theorem 1.5 and an extremal
construction. An application of Theorem 1.5 to $Y$ only yields that
$\text{sat}^{*}(n,Y)\geqslant n+1$, so we require an extra idea to obtain
Theorem 1.6( ) ‣ 1.6.

In [11] a trick was introduced which can be used to prove lower bounds on
$\text{sat}^{*}(n,P)$ for some posets $P$. The idea is to construct a certain
auxiliary digraph $D$ whose vertex set consists of the elements in an induced
$P$-saturated family $\mathcal{F}$; one then argues that how this digraph is
defined forces $D$ to contain many edges, which in turn forces a bound on the
size of the vertex set of $D$ (i.e., lower bounds $|\mathcal{F}|)$. This trick
has been used to prove that $\text{sat}^{*}(n,\Diamond)\geqslant\sqrt{n}$ [11,
Theorem 6] and $\text{sat}^{*}(n,N)\geqslant\sqrt{n}$ [8, Proposition 4] (see
Figure 1 for the Hasse diagram of $N$).

Our proof of Theorem 1.4 utilises a variant of this digraph trick. In
particular, by introducing an appropriate modification to the auxiliary
digraph $D$ used in [11], we are able to deduce certain Turán-type properties
of $D$. Turán problems in digraphs are classical in extremal combinatorics and
their study can be traced back to the work of Brown and Harary [1]. Here we
prove a Turán-type result concerning _transitive cycles_.

Given $k\geqslant 3$, the _transitive cycle on $k$ vertices_
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{k}$
is a digraph with vertex set $[k]$ and every directed edge from $i$ to $i+1$
for every $i\in[k-1]$, as well as the directed edge from $1$ to $k$. We
establish an upper bound on the number of edges of a digraph not containing
any transitive cycle.

######  Theorem 1.7.

Let $n\in\mathds{N}$ and let $D$ be a digraph on $n$ vertices. If $D$ is
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{k}$-free
for all $k\\!\geqslant\\!3$, then

$e(D)\leqslant\left\lfloor\frac{n^{2}}{4}\right\rfloor+2.$

Note that the bound in Theorem 1.7 is best possible up to an additive
constant. Indeed, consider the $n$-vertex digraph $D$ with vertex classes
$A,B$ of size $\left\lfloor n/2\right\rfloor$ and $\left\lceil
n/2\right\rceil$ respectively and all possible directed edges from $A$ to $B$.
So $D$ has $\left\lfloor n^{2}/4\right\rfloor$ edges and contains no
transitive cycle.

In Section 3 we explain why exploiting the connection between the induced
saturation problem for posets and the Turán problem for digraphs hits a
natural barrier if we wish to further improve the lower bound in Theorem 1.4.

We conclude this introductory section by setting out notation that will be
used in the rest of the paper.

### Notation

Given two elements $A,B$ of a poset $\mathcal{F}\subseteq 2^{[n]}$ we say that
_$A$ dominates $B$_ if $B\subseteq A$. We say $A$ and $B$ are _comparable_ if
one dominates the other; otherwise we say they are _incomparable_. An element
$F$ in $\mathcal{F}$ is _maximal_ if there is no other element in
$\mathcal{F}$ which dominates $F$. We define _minimal_ analogously.

For a digraph $D=(V(D),E(D))$, we write
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{xy}}$
for the edge in $D$ directed from the vertex $x$ to the vertex $y$. We say
that
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{xy}}$
is an out-edge of $x$ and an in-edge of $y$. For brevity, we write
$e(D):=|E(D)|$. Given a set $U\subseteq V(D)$, we denote the induced subgraph
of $D$ with vertex set $U$ as $D[U]$. The _underlying graph of $D$_ is the
graph with vertex set $V(D)$ whose edges are all (unordered) pairs $\\{x,y\\}$
such that
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{xy}}\in
E(D)$ or
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{yx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{yx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{yx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{yx}}\in
E(D)$.

Given $k\geqslant 2$, an _oriented path_ $v_{1}\dots v_{k}$ from $v_{1}$ to
$v_{k}$ consists of the edges
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{i}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{i}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{i}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{i}v}}_{i+1}$
for every $i\in[k-1]$. Similarly, an _oriented cycle_ $v_{1}\dots v_{k}$
consists of the edges
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{i}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{i}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{i}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{i}v}}_{i+1}$
for every $i\in[k-1]$ and
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{k}v_{1}}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{k}v_{1}}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{k}v_{1}}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{k}v_{1}}}$.

##  2\. The proofs

###  2.1. Proof of Theorem 1.7

.

We proceed by induction on $n$. For the base case, it is easy to check that
the statement of the theorem holds for $n\leqslant 3$. Next, we prove the
inductive step.

Let $D$ be a digraph on $n\geqslant 4$ vertices which is
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{k}$-free
for all $k\geqslant 3$.

######  Claim 2.1.

If $D$ contains an induced oriented cycle then
$e(D)\leqslant\left\lfloor\frac{n^{2}}{4}\right\rfloor+2$.

Proof of the claim.  Suppose $D$ contains an induced oriented cycle $C$. For
every $v\in V(D)\setminus V(C)$, it is straightforward to check that, since
$D[V(C)\cup\\{v\\}]$ contains no transitive cycle, then

  1. ( )

there is at most one in-edge of $v$ incident to $V(C)$ and

  2. ( )

there is at most one out-edge of $v$ incident to $V(C)$.

Let $D^{\prime}$ be the digraph obtained by contracting the cycle $C$ into one
vertex $c$. Namely, $D^{\prime}$ has vertex set
$V(D^{\prime})=(V(D)\cup\\{c\\})\setminus V(C)$ and $E(D^{\prime})$ is the
union of the following sets:

  * •

$E(D[V(D)\setminus V(C)])$,

  * •

$\\{\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{xc}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{xc}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{xc}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{xc}}:\exists\
\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{xy}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{xy}}\in
E(D),x\notin V(C),y\in V(C)\\}$ and

  * •

$\\{\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{cx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{cx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{cx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{cx}}:\exists\
\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{yx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{yx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{yx}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{yx}}\in
E(D),x\notin V(C),y\in V(C)\\}$.

Note that properties ( ) ‣ 2.1 and ( ) ‣ 2.1 imply that
$e(D^{\prime})=e(D)-e(C)=e(D)-|V(C)|$.

Suppose $D^{\prime}$ contains a transitive cycle
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{k}$
on vertices $v_{1},\dots,v_{k}$ for some $k\geqslant 3$. Namely,
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{j}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{j}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{j}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{j}v}}_{j+1}\in
E(D^{\prime})$ for every $j\in[k-1]$ and
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{1}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{1}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{1}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{1}v}}_{k}\in
E(D^{\prime})$. If $c\not=v_{i}$ for every $i\in[k]$ then $v_{1},\dots,v_{k}$
form a transitive cycle in $D$, a contradiction. Therefore, $c=v_{i}$ for some
$i\in[k]$.

For brevity we only consider the case $i\not=1,k$ (the cases $i=1$ and $i=k$
can be handled with a similar argument). By the definition of $D^{\prime}$,
there exist $c_{1},c_{2}\in V(C)$ such that
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{i-1}c}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{i-1}c}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{i-1}c}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{i-1}c}}_{1},\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{c_{2}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{c_{2}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{c_{2}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{c_{2}v}}_{i+1}\in
E(D)$. Furthermore, there exists an oriented path $u_{1}\dots u_{\ell}$ from
$u_{1}$ to $u_{\ell}$ such that $u_{1}=c_{1}$, $u_{\ell}=c_{2}$ and $u_{j}\in
E(C)$ for all $j\in[\ell]$. Then $v_{1}\dots v_{i-1}u_{1}\dots
u_{\ell}v_{i+1}\dots v_{k}$ is an oriented path from $v_{1}$ to $v_{k}$ in
$D$. Together with
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{v_{1}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{v_{1}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{v_{1}v}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{v_{1}v}}_{k}\in
E(D)$, this forms a transitive cycle in $D$, a contradiction.

Therefore, $D^{\prime}$ is
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{k}$-free
for all $k\geqslant 3$; so by the induction hypothesis we have
$e(D^{\prime})\leqslant\left\lfloor\frac{|V(D^{\prime})|^{2}}{4}\right\rfloor+2$.
It follows that

$e(D)=e(D^{\prime})+|V(C)|\leqslant\left\lfloor\frac{(n-|V(C)|+1)^{2}}{4}\right\rfloor+2+|V(C)|\leqslant\left\lfloor\frac{n^{2}}{4}\right\rfloor+2,$

where the last inequality holds for $n\geqslant 4$. This concludes the proof
of the claim.  $\blacksquare$

Because of Claim 2.1 we may assume that $D$ contains no double edges (which
are induced oriented cycles on two vertices). Additionally, we may assume that
the underlying graph of $D$ contains no triangle, since such a triangle would
either correspond to an induced oriented cycle or a transitive cycle
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{3}$
in $D$. By Mantel’s theorem, a triangle-free graph on $n$ vertices has at most
$\lfloor n^{2}/4\rfloor$ edges, hence

$e(D)\leqslant\left\lfloor\frac{n^{2}}{4}\right\rfloor\leqslant\left\lfloor\frac{n^{2}}{4}\right\rfloor+2.$

This concludes the inductive step. ∎

###  2.2. Proof of Theorem 1.4

.

We prove Theorem 1.4 using the following two lemmata.

######  Lemma 2.2.

Let $\mathcal{F}\subseteq 2^{[n]}$. If for every $i\in[n]$ there are elements
$A,B\in\mathcal{F}$ such that $A\setminus B=\\{i\\}$ then
$|\mathcal{F}|\geqslant 2\sqrt{n-2}$.

Notice that Lemma 2.2 is not specifically about induced saturated families. We
will discuss this further in Section 3.

######  Lemma 2.3.

Given a poset $P$, let $\mathcal{F}_{0}\subseteq 2^{[n_{0}]}$ be an induced
$P$-saturated family. Suppose there is an $i\in[n_{0}]$ such that there are no
elements $A,B\in\mathcal{F}_{0}$ satisfying $A\setminus B=\\{i\\}$. Then
$\text{sat}^{*}(n,P)\leqslant|\mathcal{F}_{0}|$ for every $n\geqslant n_{0}$.

###### Proof of Theorem 1.4.

Let $P$ be a poset. Suppose that for every $n\in\mathds{N}$ and every induced
$P$-saturated family $\mathcal{F}\subseteq 2^{[n]}$ we have that for every
$i\in[n]$ there are elements $A,B\in\mathcal{F}$ such that $A\setminus
B=\\{i\\}$. Then Lemma 2.2 implies $|\mathcal{F}|\geqslant 2\sqrt{n-2}$, and
thus $\text{sat}^{*}(n,P)\geqslant 2\sqrt{n-2}$.

Otherwise, there exists some $n_{0}\in\mathds{N}$ and $i\in[n_{0}]$ so that
there is an induced $P$-saturated family $\mathcal{F}_{0}\subseteq
2^{[n_{0}]}$ such that there are no elements $A,B\in\mathcal{F}_{0}$ with
$A\setminus B=\\{i\\}$. Then Lemma 2.3 implies that
$\text{sat}^{*}(n,P)\leqslant K_{P}$ for every $n\in\mathds{N}$ where

$K_{P}:=\max\\{|\mathcal{F}_{0}|,\,\text{sat}^{*}(m,P):m<n_{0}\\}.$

$\square$

The rest of this subsection covers the proofs of Lemmata 2.2 and 2.3. For the
proof of Lemma 2.2 we apply Theorem 1.7.

###### Proof of Lemma 2.2.

Let $D$ be a digraph with vertex set $\mathcal{F}$ and edge set $E(D)$ defined
as follows: for every $i\in[n]$, choose precisely one pair $A,B\in\mathcal{F}$
with $A\setminus B=\\{i\\}$; add the edge
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{AB}}$
to $E(D)$. Thus $D$ has exactly $n$ edges. Note that the hypothesis of the
lemma ensures $D$ is well-defined.

######  Claim 2.4.

For every $k\geqslant 3$, $D$ is
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{TC}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{TC}}_{k}$-free.

Proof of the claim.  It suffices to show that given
$\\{A_{1},\dots,A_{k}\\}\subseteq\mathcal{F}$ such that
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{A_{j}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{A_{j}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{A_{j}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{A_{j}A}}_{j+1}\in
E(D)$ for every $j\in[k-1]$ then
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{A_{1}A}}_{k}\notin
E(D)$. By definition of $D$, there are distinct $i_{1},\dots,i_{k-1}\in[n]$
such that

(1) $\displaystyle A_{j}\setminus A_{j+1}=\\{i_{j}\\}\qquad\text{for every
}j\in[k-1].$

This implies $A_{j}\subseteq A_{j+1}\cup\\{i_{j}\\}$ for every $j\in[k-1]$,
and thus $A_{1}\subseteq A_{k}\cup\\{i_{1},\dots,i_{k-1}\\}$. Hence,

(2) $\displaystyle A_{1}\setminus A_{k}\subseteq\\{i_{1}\dots,i_{k-1}\\}.$

Note that if
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{A_{1}A}}_{k}\in
E(D)$ then (2) implies that $A_{1}\setminus A_{k}=\\{i_{j}\\}$ for some
$j\in[k-1]$. However, recall that for every $i\in[n]$ there is exactly one
edge
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{AB}}$
in $D$ such that $A\setminus B=\\{i\\}$; so (1) implies that
$\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{A_{1}A}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{A_{1}A}}_{k}\notin
E(D)$, as desired.  $\blacksquare$

By Claim 2.4, we can apply Theorem 1.7 to the digraph $D$. This yields

$n=|E(D)|\leqslant\frac{|\mathcal{F}|^{2}}{4}+2\,,$

which implies $|\mathcal{F}|\geqslant 2\sqrt{n-2}$.  $\square$

We now present the proof of Lemma 2.3.

###### Proof of Lemma 2.3.

Observe that it is enough to prove that for every $n\\!\geqslant\\!n_{0}$
there exists a family $\mathcal{F}\subseteq 2^{[n]}$ such that

  1. ( )

$|\mathcal{F}|=|\mathcal{F}_{0}|$,

  2. ( )

$\mathcal{F}$ is induced $P$-saturated and

  3. ( )

there are no elements $A,B\in\mathcal{F}$ satisfying $A\setminus B=\\{i\\}$.

We proceed by induction on $n$ and observe that the base case ($n=n_{0}$)
follows directly from the statement of the lemma.

Given an induced $P$-saturated family $\mathcal{F}\subseteq 2^{[n]}$
satisfying ( ) ‣ 2.2-( ) ‣ 2.2 we consider the following function $f$ from
$2^{[n]}$ to $2^{[n+1]}$:

$f(A):=\begin{cases}A&\text{if $i\not\in A$ and}\\\ A\cup\\{n+1\\}&\text{if
$i\in A$.}\end{cases}$

We shall prove that the family $\mathcal{F}^{\prime}:=f(\mathcal{F})\subseteq
2^{[n+1]}$ satisfies ( ) ‣ 2.2-( ) ‣ 2.2.

First, note that ( ) ‣ 2.2 follows directly since $f$ is injective. Second, (
) ‣ 2.2 also follows easily, since every element $f(A)$ either contains both
$i$ and $n+1$ or neither of them. Actually, because of this last property one
might say that $n+1$ behaves as a ‘copy’ of $i$ in $f(2^{[n]})$. We need to
prove ( ) ‣ 2.2, i.e., that $\mathcal{F}^{\prime}$ is induced $P$-saturated.

It is easy to check that $f$ preserves the inclusion/incomparable relations
between elements. More precisely, for every $A,B\in 2^{[n]}$ we have

(3) $\displaystyle A\subseteq B\quad\Longleftrightarrow\quad f(A)\subseteq
f(B).$

Therefore, if $P^{\prime}$ forms an induced copy of $P$ in
$\mathcal{F}^{\prime}$, then $f^{-1}(P^{\prime})\subseteq\mathcal{F}$ forms an
induced copy of $P$ in $\mathcal{F}$. This means that, since $\mathcal{F}$ is
induced $P$-free, $\mathcal{F}^{\prime}$ must be induced $P$-free as well. It
is left to prove that for any $S\in 2^{[n+1]}\setminus\mathcal{F}^{\prime}$,
there is an induced copy of $P$ in $\mathcal{F^{\prime}}\cup\\{S\\}$. There
are four cases to consider depending on $S$. The first two cases are short and
the fourth case is an easy consequence of the third. Let $S\in
2^{[n+1]}\setminus\mathcal{F}^{\prime}$.

First case: $i,n+1\notin S$. Note that $S\subseteq 2^{[n]}$ and $f(S)=S$, thus
$S\not\in\mathcal{F}$ (as otherwise we would have $S\in\mathcal{F}^{\prime}$).
As $\mathcal{F}$ is induced $P$-saturated, there exists an induced copy
$P^{\prime}$ of $P$ in $\mathcal{F}\cup\\{S\\}$. By (3) the set $\\{f(F):F\in
P^{\prime}\\}$ is an induced copy of $P$ in $\mathcal{F^{\prime}}\cup\\{S\\}$.

Second case: $i,n+1\in S$. Set $S^{\star}:=S\setminus\\{n+1\\}$. Note that
$S^{\star}\subseteq 2^{[n]}$ and $f(S^{\star})=S$, thus
$S^{\star}\not\in\mathcal{F}$ (as otherwise we would have
$S\in\mathcal{F}^{\prime}$). As $\mathcal{F}$ is induced $P$-saturated, there
exists an induced copy $P^{\prime}$ of $P$ in
$\mathcal{F}\cup\\{S^{\star}\\}$. By (3) the set $\\{f(F):F\in P^{\prime}\\}$
is an induced copy of $P$ in $\mathcal{F^{\prime}}\cup{S}$.

Third case: $i\in S$ and $n+1\notin S$. For this case we use the assumption
that there are no elements $A,B\in\mathcal{F}$ such that $A\setminus
B=\\{i\\}$. Let $S^{\star}:=S\setminus\\{i\\}\in 2^{[n]}$. We use the sets $S$
and $S^{\star}$ to find elements $A,B\in\mathcal{F}$ that will contradict ( )
‣ 2.2 (for the family $\mathcal{F}$).

######  Claim 2.5.

Either $\mathcal{F^{\prime}}\cup\\{S\\}$ contains an induced copy of $P$ or
there exists an element $A\in\mathcal{F}$ such that $A\subseteq S$ and $i\in
A$.

Proof of the claim.  Assume that there is no $A\in\mathcal{F}$ satisfying the
properties of the claim; notice that this implies $S\notin\mathcal{F}$. We
need to prove that $\mathcal{F}^{\prime}\cup\\{S\\}$ contains an induced copy
of $P$.

Since $\mathcal{F}$ is induced $P$-saturated, there exists an induced copy
$P^{\prime}$ of $P$ in $\mathcal{F}\cup\\{S\\}$ that contains $S$. We shall
prove that $\\{f(F):F\in P^{\prime},F\neq S\\}\cup\\{S\\}$ is an induced copy
of $P$ in $\mathcal{F}^{\prime}\cup\\{S\\}$.

First, observe that (3) implies the set $\\{f(F):F\in P^{\prime},F\not=S\\}$
is an induced copy of the poset $P^{\prime}\setminus\\{S\\}$. If for every
$F\in P^{\prime}\setminus\\{S\\}$ the relation (inclusion/incomparability)
between $F$ and $S$ is the same as the one between $f(F)$ and $S$ then we are
done. Thus, for every $F\in P^{\prime}\setminus\\{S\\}$ we prove that

  1. ( )

if $S$ and $F$ are incomparable then $S$ and $f(F)$ are incomparable,

  2. ( )

if $S\subseteq F$ then $S\subseteq f(F)$ and

  3. ( )

if $S\supseteq F$ then $S\supseteq f(F)$.

Notice that ( ) ‣ 2.2 follows directly from $F\subseteq f(F)$. It is easy to
check that ( ) ‣ 2.2 also holds by recalling that $i\in S$ and $n+1\notin S$.
So finally, for $F\in P^{\prime}\setminus\\{S\\}$ as in ( ) ‣ 2.2, observe
that $i\notin F$ otherwise $F$ would satisfy the properties of $A$ in the
statement of the claim. Then $f(F)=F$ and ( ) ‣ 2.2 holds.  $\blacksquare$

The proof of the following claim is very similar. We include it for
completeness.

######  Claim 2.6.

Either $\mathcal{F^{\prime}}\cup\\{S\\}$ contains an induced copy of $P$ or
there exists an element $B\in\mathcal{F}$ such that $S^{\star}\subseteq B$ and
$i\not\in B$.

Proof of the claim.  Assume that there is no $B\in\mathcal{F}$ satisfying the
properties of the claim; notice that this implies
$S^{\star}\notin\mathcal{F}$. It remains to show that
$\mathcal{F}^{\prime}\cup\\{S\\}$ contains an induced copy of $P$.

Since $\mathcal{F}$ is induced $P$-saturated, there exists an induced copy
$P^{\prime}$ of $P$ in $\mathcal{F}\cup\\{S^{\star}\\}$ that contains
$S^{\star}$. We shall prove that $\\{f(F):F\in
P^{\prime},F\not=S^{\star}\\}\cup\\{S\\}$ is an induced copy of $P$ in
$\mathcal{F}^{\prime}\cup\\{S\\}$.

First, observe that (3) implies the set $\\{f(F):F\in
P^{\prime},F\not=S^{\star}\\}$ is an induced copy of the poset
$P^{\prime}\setminus\\{S^{\star}\\}$. If for every $F\in
P^{\prime}\setminus\\{S^{\star}\\}$ the relation (inclusion/incomparability)
between $F$ and $S^{\star}$ is the same as the one between $f(F)$ and $S$ then
we are done. Thus, for every $F\in P^{\prime}\setminus\\{S^{\star}\\}$ we must
prove that

  1. ( )

if $S^{\star}$ and $F$ are incomparable then $S$ and $f(F)$ are incomparable,

  2. ( )

if $S^{\star}\supseteq F$ then $S\supseteq f(F)$ and

  3. ( )

if $S^{\star}\subseteq F$ then $S\subseteq f(F)$.

For ( ) ‣ 2.2, notice that $S^{\star}\supseteq F$ implies $i\not\in F$ and
thus $S\supseteq S^{\star}\supseteq F=f(F)$. It is easy to check that ( ) ‣
2.2 also holds by recalling that $i\in S$ and $n+1\notin S$. Finally, for
$F\in P^{\prime}\setminus\\{S^{\star}\\}$ as in ( ) ‣ 2.2, observe that $i\in
F$ otherwise $F$ would satisfy the properties of $B$ in the statement of the
claim. Then $f(F)=F\cup\\{n+1\\}$ and ( ) ‣ 2.2 holds.  $\blacksquare$

To finish the proof of this case, suppose that
$\mathcal{F^{\prime}}\cup\\{S\\}$ does not contain an induced copy of $P$. By
Claims 2.5 and 2.6 there are elements $A,B\in\mathcal{F}$ such that
$A\subseteq S$, $i\in A$ and $S\setminus\\{i\\}\subseteq B$, $i\not\in B$. In
particular, we have $A\setminus B=\\{i\\}$, a contradiction.

Fourth case: $i\notin S$ and $n+1\in S$. Let
$S^{\prime}:=(S\setminus\\{n+1\\})\cup\\{i\\}$. Recall that every element of
$\mathcal{F}^{\prime}$ either contains both $i$ and $n+1$ or neither of them.
This property ensures that

  1. ()

$S^{\prime}\not\in\mathcal{F}^{\prime}$;

  2. ()

for any $A\in\mathcal{F}^{\prime}$, $A\subseteq S$ if and only if $A\subseteq
S^{\prime}$;

  3. ()

for any $A\in\mathcal{F}^{\prime}$, $S\subseteq A$ if and only if
$S^{\prime}\subseteq A$.

By the third case we have that $\mathcal{F}^{\prime}\cup\\{S^{\prime}\\}$
contains an induced copy of $P$. Clearly () ‣ 2.2 and () ‣ 2.2 then imply
that $\mathcal{F}^{\prime}\cup\\{S\\}$ contains an induced copy of $P$.
$\square$

###  2.3. Proof of Theorems 1.5 and 1.6

.

Given a poset $P$ with legs and an induced $P$-saturated family
$\mathcal{F}\subseteq 2^{[n]}$, the following lemma already implies that
$\mathcal{F}$ has size at least $n$.

######  Lemma 2.7.

Let $P$ be a poset with legs and $\mathcal{F}\subseteq 2^{[n]}$ be an induced
$P$-saturated family. Then, there is an injective function
$f\colon[n]\longrightarrow\mathcal{F}\setminus\\{\emptyset\\}$ such that

$f(i)=\begin{cases}\\{i\\}&\text{if }\\{i\\}\in\mathcal{F}\text{ and}\\\
H(i)&\text{if }\\{i\\}\notin\mathcal{F},\text{ where $H(i)$ is the hip of an
induced copy of $P$ in $\mathcal{F}\cup\\{\\{i\\}\\}$}.\end{cases}$

###### Proof.

Let $\mathcal{F}$ be an induced $P$-saturated family. For
$\\{i\\}\notin\mathcal{F}$ we shall choose a suitable $f(i)=H(i)$ in such a
way that $f$ is injective. Given $i\in[n]$ with $\\{i\\}\notin\mathcal{F}$,
let $P^{\prime}$ be an induced copy of $P$ in $\mathcal{F}\cup\\{\\{i\\}\\}$
that contains $\\{i\\}$. Observe that $\\{i\\}$ can only be a leg of
$P^{\prime}$. Among all possible choices for $P^{\prime}$, we pick it under
the following conditions.

  1. ( )

The leg $L^{\prime}$ of $P^{\prime}$ which is not $\\{i\\}$ is taken so that
$|L^{\prime}|$ is as large as possible;

  2. ( )

under ( ) ‣ 2.3, the hip $H^{\prime}$ of $P^{\prime}$ is taken so that
$|H^{\prime}|$ is as small as possible.

Thus we define $f(i):=H^{\prime}$. Note that since $L^{\prime}$ and $\\{i\\}$
are incomparable, $i\notin L^{\prime}$.

######  Claim 2.8.

$H^{\prime}=L^{\prime}\cup\\{i\\}$.

Proof of the claim.  Suppose for a contradiction that
$L^{\prime}\cup\\{i\\}\subset H^{\prime}$. If
$L^{\prime}\cup\\{i\\}\in\mathcal{F}$ then the poset
$(P^{\prime}\cup\\{L^{\prime}\cup\\{i\\}\\})\setminus\\{H^{\prime}\\}$ is an
induced copy of $P$, which contradicts ( ) ‣ 2.3. Therefore
$L^{\prime}\cup\\{i\\}$ is not in $\mathcal{F}$ and so
$\mathcal{F}\cup\\{L^{\prime}\cup\\{i\\}\\}$ contains an induced copy
$P^{\prime\prime}$ of $P$ which uses the set $L^{\prime}\cup\\{i\\}$.

Denote the legs of $P^{\prime\prime}$ by
$L_{1}^{\prime\prime},L_{2}^{\prime\prime}$. If $L^{\prime}\cup\\{i\\}$ is not
a leg in $P^{\prime\prime}$ then
$L_{1}^{\prime\prime},L_{2}^{\prime\prime}\subset L^{\prime}\cup\\{i\\}$. This
implies that
$(P^{\prime}\cup\\{L_{1}^{\prime\prime},L_{2}^{\prime\prime}\\})\setminus\\{\\{i\\},L^{\prime}\\}$
is an induced copy of $P$ in $\mathcal{F}$, a contradiction. Thus,
$L^{\prime}\cup\\{i\\}$ is a leg, and we may assume
$L_{1}^{\prime\prime}=L^{\prime}\cup\\{i\\}$.

Note that if $L^{\prime}$ and $L_{2}^{\prime\prime}$ are incomparable, then
$(P^{\prime\prime}\cup\\{L^{\prime}\\})\setminus\\{L_{1}^{\prime\prime}\\}$
would be an induced copy of $P$ in $\mathcal{F}$, a contradiction. Thus,
$L^{\prime}$ is comparable with $L_{2}^{\prime\prime}$. In particular
$L^{\prime}\subset L_{2}^{\prime\prime}$, otherwise we would have that
$L_{2}^{\prime\prime}\subseteq L^{\prime}\cup\\{i\\}=L_{1}^{\prime\prime}$,
which contradicts the fact that $L_{1}^{\prime\prime}$ and
$L_{2}^{\prime\prime}$ are incomparable. Moreover, again because
$L_{1}^{\prime\prime}$ and $L_{2}^{\prime\prime}$ are incomparable, we have
that $i\notin L_{2}^{\prime\prime}$.

Finally, observe that
$(P^{\prime\prime}\cup\\{\\{i\\}\\})\setminus\\{L_{1}^{\prime\prime}\\}$ is an
induced copy of $P$ in $\mathcal{F}\cup\\{\\{i\\}\\}$ with legs $\\{i\\}$ and
$L_{2}^{\prime\prime}\supset L^{\prime}$, which contradicts ( ) ‣ 2.3.
$\blacksquare$

Recall $f(i):=H^{\prime}=H(i)$. We shall prove that $f$ is injective. Suppose
not, namely $f(i)=f(j)$ for some $i\not=j$. If either $\\{i\\}\in\mathcal{F}$
or $\\{j\\}\in\mathcal{F}$ then we get a contradiction. Thus, we have
$\\{i\\},\\{j\\}\notin\mathcal{F}$, and hence there exist induced copies
$P^{\prime}\subseteq\mathcal{F}\cup\\{\\{i\\}\\}$ and
$P^{\prime\prime}\subseteq\mathcal{F}\cup\\{\\{j\\}\\}$ of $P$ such that $H$
is the hip of both and $f(i)=f(j)=H$. Say $\\{i\\}$ and $L^{\prime}$ are the
legs of $P^{\prime}$ while $\\{j\\}$ and $L^{\prime\prime}$ are the legs of
$P^{\prime\prime}$. Because of Claim 2.8 we have that
$H=L^{\prime}\cup\\{i\\}=L^{\prime\prime}\cup\\{j\\}$, and hence $L^{\prime}$
and $L^{\prime\prime}$ are incomparable. This implies that
$(P^{\prime}\cup\\{L^{\prime\prime}\\})\setminus\\{\\{i\\}\\}$ is an induced
copy of $P$ in $\mathcal{F}$, a contradiction.  $\square$

Now we are ready to prove Theorem 1.5.

###### Proof of Theorem 1.5.

Observe that for a poset $P$ with legs, the inequality
$\text{sat}^{*}(n,P)\geqslant n+1$ follows directly by applying Lemma 2.7 and
by noticing that the empty set is in every induced $P$-saturated family.

For $P$ such that $P$ and $\overline{P}$ have legs, we proceed as follows. Let
$\mathcal{F}\subseteq 2^{[n]}$ be an induced $P$-saturated family and observe
that $\emptyset,[n]\in\mathcal{F}$. The poset $\overline{\mathcal{F}}\subseteq
2^{[n]}$ is induced $\overline{P}$-saturated and therefore we can apply Lemma
2.7 to both $\mathcal{F}$ and $\overline{\mathcal{F}}$ to obtain injective
functions $f$ and $\overline{f}$ respectively. Since both $P$ and
$\overline{P}$ have legs, it is easy to see that the hip of $P$ is not a
maximal element of $P$. It follows that $f(i)\neq[n]$ for every $i\in[n]$.
That is, $f([n])\subseteq\mathcal{F}\setminus\\{\emptyset,[n]\\}$; similarly
$\overline{f}([n])\subseteq\overline{\mathcal{F}}\setminus\\{\emptyset,[n]\\}$.

By taking $[n]\setminus\overline{f}(i)$ for every $i\in[n]$ we define a new
injective function $\tilde{f}$ from $[n]$ to
$\mathcal{F}\setminus\\{\emptyset,[n]\\}$:

$\tilde{f}(i):=\begin{cases}[n]\setminus\\{i\\}&\text{if
}\\{i\\}\in\overline{\mathcal{F}},\text{ and}\\\ H(i)&\text{if
}\\{i\\}\notin\overline{\mathcal{F}},\text{ where $[n]\setminus H(i)$ is the
hip of an induced copy of~{}$\overline{P}$
in~{}$\overline{\mathcal{F}}\cup\\{\\{i\\}\\}$}\,.\end{cases}$

Now, since $f$ and $\tilde{f}$ are injective, proving that
$f([n])\cap\tilde{f}([n])=\emptyset$ yields that $|\mathcal{F}|\geqslant 2n+2$
by recalling that the sets $\emptyset$ and $[n]$ belong to $\mathcal{F}$.

Suppose $f(i)=\tilde{f}(j)$ for $i,j\in[n]$. If $\\{i\\}\in\mathcal{F}$ or
$[n]\setminus\\{j\\}\in\mathcal{F}$ then it is easy to check that such an
identity is not possible. Hence, we have that $f(i)=\tilde{f}(j)=H$ where: $H$
is the hip of an induced copy $P_{1}$ of $P$ in $\mathcal{F}\cup\\{\\{i\\}\\}$
and $[n]\setminus H$ is the hip of an induced copy $\overline{P}_{2}$ of
$\overline{P}$ in $\overline{\mathcal{F}}\cup\\{\\{j\\}\\}$. In particular,
this means that there is an induced copy $P_{2}$ of $P$ in
${\mathcal{F}}\cup\\{[n]\setminus\\{j\\}\\}$ where $[n]\setminus\\{j\\}$ plays
the role in $P_{2}$ of one of the two maximal elements of $P$; $H$ is in
$P_{2}$ and dominates all elements of $P_{2}$ except for the two maximal
elements.

Let $L^{1}$ be the leg of $P_{1}$ other than $\\{i\\}$. Let
$L_{1}^{2},L_{2}^{2}\in\mathcal{F}$ be the legs of $P_{2}$; in particular,
$L_{1}^{2}$ and $L_{2}^{2}$ are incomparable and $L_{1}^{2},L_{2}^{2}\subset
H$. This implies that for every $A\in P_{1}\setminus\\{L^{1},\\{i\\}\\}$,
$L_{1}^{2},L_{2}^{2}\subset A$. Thus,
$(P_{1}\cup\\{L_{1}^{2},L_{2}^{2}\\})\setminus\\{L^{1},\\{i\\}\\}$ is an
induced copy of $P$ in $\mathcal{F}$, a contradiction.  $\square$

Theorem 1.6 now follows by a simple application of Lemma 2.7 and Theorem 1.5,
together with two upper bound constructions.

###### Proof of Theorem 1.6.

Observe that
$\text{sat}^{*}(n,Y)=\text{sat}^{*}(n,\rotatebox[origin={c}]{180.0}{Y})$ where
$\rotatebox[origin={c}]{180.0}{Y}:=\overline{Y}$. Let $\mathcal{F}\subseteq
2^{[n]}$ be an induced  Y -saturated family. Since  Y has legs, Lemma 2.7
yields an injective function $f$ from $[n]$ to
$\mathcal{F}\setminus\\{\emptyset\\}$ with $f(i)=\\{i\\}$ if
$\\{i\\}\in\mathcal{F}$ and $f(i)=H$ otherwise, where $H$ is the hip of an
induced copy of  Y in $\mathcal{F}\cup\\{\\{i\\}\\}$. This already implies
$|\mathcal{F}|\geqslant n+1$ as $\emptyset\in\mathcal{F}$.

Observe that $f(i)\neq[n]$ for every $i\in[n]$, therefore, if
$[n]\in\mathcal{F}$ then $|\mathcal{F}|\geqslant n+2$, as desired. Hence,
assume that $[n]\notin\mathcal{F}$, which means that
$\mathcal{F}\cup\\{[n]\\}$ contains an induced copy of  Y that uses $[n]$. Let
$L_{1},L_{2}$ be the legs of this copy of  Y and $H$ be the hip. Assume there
is an $i\in[n]$ such that $f(i)=H$; so $H$ is the hip of an induced copy of  Y
contained in $\mathcal{F}\cup\\{\\{i\\}\\}$. Let $M$ be the maximal element of
this copy of  Y and observe that $\\{L_{1},L_{2},H,M\\}$ forms an induced copy
of  Y in $\mathcal{F}$, a contradiction. Hence, $f(i)\neq H$ for every
$i\in[n]$, which means that $H$ was not counted before and therefore
$|\mathcal{F}|\geqslant n+2$. This argument implies that
$\text{sat}^{*}(n,Y)\geqslant n+2$.

For the poset $X$ observe that $X$ and $\overline{X}=X$ have legs, therefore
Theorem 1.5 directly implies that $\text{sat}^{*}(n,X)\geqslant 2n+2$. For the
upper bounds, consider the posets

$P:=\\{F\in 2^{[n]}\colon|F|\geqslant n-1\text{ or
}F=\emptyset\\}\quad\quad\text{and}\quad\quad Q:=\\{F\in
2^{[n]}\colon|F|\geqslant n-1\text{ or }|F|\leqslant 1\\}\,,$

and notice that they are respectively induced $Y$-saturated and induced
$X$-saturated. Furthermore, $|P|=n+2$ and $|Q|=2n+2$.  $\square$

We conclude this subsection by exhibiting a class of posets for which the
bound in Theorem 1.5 is sharp up to an additive constant.

For any $\ell\in\mathds{N}$, let $\wedge_{\ell}$ denote the poset with the
following properties:

  * -

$\wedge_{\ell}$ has legs $L_{1},L_{2}$ and hip $H_{1}$;

  * -

$\wedge_{\ell}\setminus\\{L_{1},L_{2}\\}=\\{H_{1},\dots,H_{\ell}\\}$ where
$H_{j}\subset H_{j+1}$ for every $j\in[\ell-1]$.

Similarly, for any $\ell\in\mathds{N}$, let $X_{\ell}$ denote the poset with
the following properties:

  * -

$X_{\ell}$ has legs $L_{1}^{\prime},L_{2}^{\prime}$ and
$X_{\ell}\setminus\\{L_{1}^{\prime},L_{2}^{\prime}\\}=\vee_{\ell}$ where
$\vee_{\ell}:=\overline{\wedge_{\ell}}$.

Clearly $X_{1}=X$ and $\wedge_{2}=\rotatebox[origin={c}]{180.0}{Y}$. Moreover,
$\wedge_{\ell},X_{\ell}$ and $\overline{X}_{\ell}$ have legs for every
$\ell\in\mathds{N}$, and therefore Theorem 1.5 implies that
$\text{sat}^{*}(n,\wedge_{\ell})\geqslant n+1$ and
$\text{sat}^{*}(n,X_{\ell})\geqslant 2n+2$. The next proposition states that
these bounds are close to the exact values of
$\text{sat}^{*}(n,\wedge_{\ell})$ and $\text{sat}^{*}(n,X_{\ell})$.

######  Proposition 2.9.

For all integers $n-1>\ell\geqslant 2$ we have,111Note that the case $\ell=1$
is covered by Theorem 1.6 since $\wedge_{2}=\rotatebox[origin={c}]{180.0}{Y}$
and $X_{1}=X$.

$\displaystyle n+1$ $\displaystyle\leqslant\text{sat}^{*}(n,\wedge_{\ell+1})$
$\displaystyle\leqslant n+2^{\ell+1}-\ell-1\text{ and}$ $\displaystyle 2n+2$
$\displaystyle\leqslant\text{sat}^{*}(n,X_{\ell})$ $\displaystyle\leqslant
2n+2^{\ell+1}-2\ell.$

###### Proof.

First, we consider $\wedge_{\ell+1}$. Let $\mathcal{F}\subseteq 2^{[n]}$ be
the family containing precisely the following sets:

  * -

the empty set $\emptyset$;

  * -

$\\{i\\}$ for every $i\in[n]$;

  * -

all subsets of $\\{1,2,\dots,\ell\\}$;

  * -

all proper supersets of $[n]\setminus\\{1,2,\dots,\ell\\}$.

It is straightforward to check that $\mathcal{F}$ has $n+2^{\ell+1}-\ell-1$
elements and is induced $\wedge_{\ell+1}$-saturated. Similarly, the family
$\mathcal{F}^{\prime}:=\mathcal{F}\cup\overline{\mathcal{F}}\subseteq 2^{[n]}$
has $2n+2^{\ell+1}-2\ell$ elements and is induced $X_{\ell}$-saturated.
$\square$

##  3\. Concluding remarks

The following example shows that the bound in Lemma 2.2 is essentially tight.

######  Example 3.1.

Let $n\in\mathds{N}$ be a perfect square, i.e., $\sqrt{n}\in\mathds{N}$. Let
$A_{s},B_{t}\subseteq[n]$ be defined as follows.

  * •

$A_{s}:=\\{s\sqrt{n}+1,s\sqrt{n}+2,\dots,s\sqrt{n}+\sqrt{n}\\}$ for every
$s\in[\sqrt{n}-1]\cup\\{0\\}$;

  * •

$B_{t}:=[n]\setminus\\{t,t+\sqrt{n},t+2\sqrt{n},\dots,t+(\sqrt{n}-1)\sqrt{n}\\}$
for every $t\in[\sqrt{n}]$.

Let
$\mathcal{F}^{\star}:=\\{A_{s}:s\in[\sqrt{n}-1]\cup\\{0\\}\\}\cup\\{B_{t}:t\in[\sqrt{n}]\\}\subseteq
2^{[n]}$.

Observe that $\mathcal{F}^{\star}$ has $2\sqrt{n}$ elements. Furthermore, for
every $i\in[n]$, there exists exactly one pair of elements
$A,B\in\mathcal{F}^{\star}$ such that $A\setminus B=\\{i\\}$. Namely, if
$i=s\sqrt{n}+t$ where $s\in[\sqrt{n}-1]\cup\\{0\\}$ and $t\in[\sqrt{n}]$ then
$A_{s}\setminus B_{t}=\\{i\\}$.

Note that the digraph $D$ with $V(D)=\mathcal{F}^{\star}$ and edge set
$E(D)=\\{\mathchoice{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\displaystyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\textstyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptstyle{AB}}{\overarrow@\arrowfill@\relbar\relbar\rightharpoonup\scriptscriptstyle{AB}}:A\setminus
B=\\{i\\},i\in[n]\\}$ is precisely the balanced oriented bipartite graph
(i.e., the extremal example for Theorem 1.7).

This example shows that if one can improve the lower bound in Theorem 1.4 by
using the auxiliary digraph approach, then one will really need to use the
fact that the digraph is generated by an induced $P$-saturated family (recall
this was not assumed in the statement of Lemma 2.2). On the other hand, if
Theorem 1.4 is close to being best possible, then Example 3.1 points in the
direction of potential extremal examples. That is, is there some poset $P$
such that there is a minimum induced $P$-saturated family
$\mathcal{F}\subseteq 2^{[n]}$ that is ‘close’ to the family
$\mathcal{F}^{\star}$ in Example 3.1?

Another natural question is to characterise those posets $P$ for which
$\text{sat}^{*}(n,P)$ is bounded by a constant. Observe that Lemma 2.3
provides a method for determining such posets. That is, if one can exhibit an
$n_{0}\in\mathbb{N}$ and an induced $P$-saturated family $\mathcal{F}\subseteq
2^{[n_{0}]}$ such that for some $i\in[n_{0}]$ there are no elements
$A,B\in\mathcal{F}$ with $A\setminus B=\\{i\\}$, then
$\text{sat}^{*}(n,P)=O(1)$.

Along the lines of this research direction, Keszegh, Lemons, Martin, Pálvölgyi
and Patkós [10] conjectured the following. Given a poset $P$ on $[p]$, let
$\dot{P}$ denote the poset on $[p+1]$ where $\dot{P}:=P\cup\\{[p+1]\\}$ (i.e.,
$\dot{P}$ is obtained by adding an element to $P$ which dominates all elements
in $P$).

######  Conjecture 3.2.

[10] $\text{sat}^{*}(n,P)=O(1)$ if and only if
$\text{sat}^{*}(n,\dot{P})=O(1)$.

Note that neither direction of Conjecture 3.2 has been verified except for
some special cases (see [10, Theorem 3.6]). It would be interesting to
investigate if Lemma 2.3 can help tackle Conjecture 3.2.

Finally, it is natural to consider induced saturation problems for families of
posets. Given a family of posets $\mathcal{P}$, we say that
$\mathcal{F}\subseteq 2^{[n]}$ is _induced $\mathcal{P}$-saturated_ if
$\mathcal{F}$ contains no induced copy of any poset $P\in\mathcal{P}$ and for
every $S\in 2^{[n]}\setminus\mathcal{F}$ there exists an induced copy of some
poset $P\in\mathcal{P}$ in $\mathcal{F}\cup\\{S\\}$. We denote the size of the
smallest such family by $\text{sat}^{*}(n,\mathcal{P})$. By following the
proof of Theorem 1.4 precisely, one obtains the following result.

######  Theorem 3.3.

For any family of posets $\mathcal{P}$, either there exists a constant
$K_{\mathcal{P}}$ with $\text{sat}^{*}(n,\mathcal{P})\leqslant
K_{\mathcal{P}}$ or $\text{sat}^{*}(n,\mathcal{P})\geqslant 2\sqrt{n-2}$, for
all $n\in\mathds{N}$.

In light of Theorem 3.3 it is natural to ask whether an analogue of Conjecture
1.2 is true in this more general setting, or whether (for example) the lower
bound on $\text{sat}^{*}(n,\mathcal{P})$ in Theorem 3.3 is best possible up to
a multiplicative constant.

## References

  * [1] W.G. Brown and F. Harary, Extremal digraphs, _Coll. Math. Soc. J. Bolyai_ 4 (1969), 135–198.
  * [2] B.L. Currie, J.R. Faudree, R.J. Faudree and J.R. Schmitt, A survey of minimum saturated graphs, _Electron. J. Combin._ (2011), DS19.
  * [3] I. Đanković, M.-R. Ivan, Saturation for Small Antichains, arXiv:2205.07392.
  * [4] P. Erdős, A. Hajnal and J.W. Moon, A problem in graph theory, _Amer. Math. Monthly_ 71 (1964), 1107–1110.
  * [5] M. Ferrara, B. Kay, L. Kramer, R.R. Martin, B. Reiniger, H.C. Smith and E. Sullivan, The saturation number of induced subposets of the Boolean lattice, _Discr. Math._ 340 (2017), 2479–2487.
  * [6] D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. Pálvölgyi and B. Patkós, Saturating Sperner families, _Graphs Combin._ 29 (2013), 1355–1364.
  * [7] J.R. Griggs and W.T. Li, Progress on Poset-free Families of Subsets, _Recent Trends in Combinatorics_ , the IMA Volumes in Mathematics and its Applications 159. Springer, New York, 2016.
  * [8] M.-R. Ivan, Saturation for the butterfly poset, _Mathematika_ 66 (2020), 806–817.
  * [9] M.-R. Ivan, Minimal Diamond-Saturated Families, _Contemporary Mathematics_ 3 (2022), 81–87.
  * [10] B. Keszegh, N. Lemons, R.R. Martin, D. Pálvölgyi and B. Patkós, Induced and non-induced poset saturation problems, _J. Combin. Theory Ser. A_ 184 (2021), article 105497.
  * [11] R.R. Martin, H.C. Smith and S. Walker, Improved bounds for induced poset saturation, _Electron. J. Combin._ 27 (2020), P2.31.
  * [12] N. Morrison, J.A. Noel and A. Scott, On Saturated $k$-Sperner Systems, _Electron. J. Combin._ 21 (2014), P3.22.
  * [13] P. Turán, On an extremal problem in graph theory, _Matematikai és Fizikai Lapok_ 48 (1941), 436–452.