## IMPROVED BOUNDS FOR INDUCED POSET SATURATION

RYAN R. MARTIN, HEATHER C. SMITH, AND SHANISE WALKER

Abstract. Given a finite poset P , a family F of elements in the Boolean lattice is inducedP -saturated if F contains no copy of P as an induced subposet but every proper superset of F contains a copy of P as an induced subposet. The minimum size of an inducedP -saturated family in the n -dimensional Boolean lattice, denoted sat ( ∗ n, P ), was first studied by Ferrara et al. (2017).

Our work focuses on strengthening lower bounds. For the 4point poset known as the diamond, we prove sat ( ∗ n, D 2 ) ≥ √ n , improving upon a logarithmic lower bound. For the antichain with k +1 elements, we prove sat ( ∗ n, A k +1 ) ≥ (1 -o k (1)) kn log 2 k , improving upon a lower bound of 3 n -1 for k ≥ 3.

## 1. Introduction

A partially ordered set , or poset , P = ( P, /precedesequal ) consists of a set P with a binary relation ' /precedesequal ' which is reflexive, antisymmetric, and transitive. For x, y ∈ P , we say x and y are comparable provided x /precedesequal y or y /precedesequal x . Otherwise, we say x and y are incomparable , writing x ‖ y . For posets, P = ( P, /precedesequal ) and P ′ = ( P , ′ /precedesequal ), we say P ′ is a (weak) subposet of P if there exists an injection f : P ′ → P that preserves the partial ordering, i.e. whenever u /precedesequal ′ v , we have f ( u ) /precedesequal f ( v ). The n -dimensional Boolean lattice , B n = (2 [ n ] , ⊆ ) is the poset consisting of all subsets of [ n ] := { 1 , . . . , n } , ordered by inclusion.

The study of P -free families dates back to Sperner's [8] proof that the maximum size of an antichain (a poset in which no two distinct elements are comparable) in B n is ( n /floorleft n/ 2 /floorright ) . In particular, this is the quantity La( n, P 2 ) where P 2 = ( { x, y } ≤ , ) such that x ≤ y . See Griggs and Li [6] for an extensive survey of P -free results.

For a poset Q = ( Q, /precedesequal ) and a family F ⊆ Q , we often refer to F = ( F /precedesequal , ) as the poset induced by F in Q which is obtained by restricting the binary relation /precedesequal to F × F . For any poset P , we say that F is P -free provided P is not a subposet of F . The maximum size of a P -free family in B n is denoted La( n, P ).

Extremal questions about sizes of P -free families are only interesting as maximization problems, however the notion of saturation allows us to formulate corresponding minimization questions. Before defining saturation for posets, we first give some background on the much older problem of graph saturation.

Let G and H be graphs. A spanning subgraph F of G is ( G,H ) -saturated if F contains no copy of H as a subgraph but, for any edge e ∈ E G ( ) -E F ( ), the graph F + e = ( V ( F , E F ) ( ) ∪ { } e ) contains a copy of H as a subgraph. Let sat( G,H ) denote the minimum number of edges in a ( G,H )-saturated graph.

Saturation was introduced by Zykov [10] and Erd˝s, o Hajnal, and Moon [2] independently, when they considered sat( K ,H n ), for K n being the complete graph on n vertices. Erd˝ os, Hajnal, and Moon showed that for n ≥ k ≥ 2, sat( K ,K n k ) = ( k -2) n -( k -1 2 ) . Since its introduction, saturation has been studied extensively. Faudree, Faudree, and Schmitt [3] provide a dynamic survey of saturated graphs.

Saturation for posets was first introduced by Gerbner, et al. [5].

Definition 1. Given a host poset Q = ( Q, ≤ Q ) , a target poset P = ( P, ≤ P ) , and a family F ⊆ Q , we say that F is P -saturated in Q if the following two properties hold:

- · the poset induced by F in Q is P -free, and
- · for any S ∈ Q -F , the poset P is a subposet of the poset induced by F ∪ { S } in Q .

Given n &gt; 0 and a poset P , the saturation number , denoted sat( n, P ), is the minimum size of a P -saturated family in B n . Let P k denote the chain consisting of k elements in which each pair is comparable. Gerbner et al. proved the following:

Theorem 2 (Gerbner et al. [5]) . For n sufficiently large,

$$2 ^ { k / 2 - 1 } \leq \text{sat} ( n, \mathcal { P } _ { k + 1 } ) \leq 2 ^ { k - 1 }. \\. \quad. \, \quad. \, \quad. \,. \quad. \quad.$$

Morrison, Noel, and Scott [7] improved the upper bound when they found a smaller construction for a P 7 -saturated family and used an iterative process to obtain the following upper bound:

Theorem 3 (Morrison, Noel, Scott [7]) . There exists ε &gt; 0 such that for all k &gt; 0 and n sufficiently large,

$$\text{sat} ( n, \mathcal { P } _ { k + 1 } ) \leq 2 ^ { ( 1 - \varepsilon ) k }. \\. \quad \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{} \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{$$

$$I n \ p a r t i c u l a r, \, \epsilon = \left ( 1 - \frac { \log _ { 2 } 1 5 } { 4 } \right ) \approx 0. 0 2 3 2 7 7 \ s u f f i c e s.$$

Ferrara et al. [4] found that the saturation number sat( n, P ) was constant in n for many posets P , so they introduced the notion of induced-saturation.

A poset P ′ = ( P , ′ /precedesequal ′ ) is an induced-subposet of P = ( P, /precedesequal ) if there exists an injective function f : P ′ → P such that u /precedesequal ′ v if and only if f ( u ) /precedesequal f ( v ).

Definition 4 (Ferrara et al. [4]) . Given a host poset Q = ( Q, ≤ Q ) , a target poset P = ( P, ≤ P ) , and a family F ⊆ Q , we say that F is inducedP -saturated in Q if the following two properties hold:

- · for any S ∈ Q -F , the poset induced by F∪{ } S in Q contains an induced copy of P .
- · the poset induced by F in Q does not contain an induced copy of P , and

Given n &gt; 0 and a poset P , the induced saturation number , denoted sat ( ∗ n, P ), is the minimum size of a family F that is inducedP -saturated in B n .

To summarize some of the results of Ferrara et al. [4], we first define several posets. Let A k denote the antichain with k elements. The Hasse diagrams for V 2 , the butterfly /triangleright /triangleleft , and the diamond D 2 are given in Figure 1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01108v1-figure-a0b0aa9a-aeaf-4fb4-9436-1ac2d627855b.jpg)

V

the diamond, D 2

Figure 1. Hasse diagrams for three named posets.

Ferrara et al. proved the following regarding inducedP -saturation for particular posets.

Theorem 5 (Ferrara et al. [4]) .

- (a) If n ≥ 2 , then sat ( ∗ n, V 2 ) = n +1 .
- (c) If n ≥ 2 , then /ceilingleft log 2 n /ceilingright ≤ sat ( ∗ n, D 2 ) ≤ n +1 .
- (b) If n ≥ 3 , then /ceilingleft log 2 n /ceilingright ≤ sat ( ∗ n, /triangleright /triangleleft ) ≤ ( ) n 2 +2 n -1 .
- (d) If n &gt; k ≥ 3 , then

$$3 n - 1 \leq \text{sat} ^ { * } ( n, \mathcal { A } _ { k + 1 } ) \leq ( n - 1 ) k - \left ( \frac { 1 } { 2 } \log _ { 2 } k + \frac { 1 } { 2 } \log _ { 2 } \log _ { 2 } k + O ( 1 ) \right ).$$

In this paper, we improve lower bounds for induced saturation numbers for the k -antichain and the diamond. In particular, Theorem 6 improves the lower bound in Theorem 5 (c) and Theorem 7 improves the lower bound in Theorem 5 (d) .

Theorem 6. For n &gt; 0 , sat ( ∗ n, D 2 ) ≥ /ceilingleft √ n /ceilingright .

Theorem 7. For k ≥ 3 and n sufficiently large, sat ( ∗ n, A k +1 ) ≥ ( 1 -1 log 2 k ) kn log 2 k .

We note at the end of Section 3 that n ≥ log 3 2 k suffices to satisfy the bound in Theorem 7.

In Section 2 we prove Theorem 6 while Section 3 contains the proof of Theorem 7.

## 2. InducedD 2 -saturated results

Theorem 5 (c) gives a lower bound of /ceilingleft log 2 n /ceilingright for sat ∗ ( n, D 2 ), which is far from the upper bound of n +1. As presented in [4], this logarithmic lower bound holds for sat ( ∗ n, P ) for a much larger class of posets, however they did obtain the following partial result for sat ( ∗ n, D 2 ) which is specific to the diamond:

Theorem 8 (Ferrara et al. [4]) . Let F be an inducedD 2 -saturated family in B n . If ∅ ∈ F or [ n ] ∈ F , then |F| ≥ n +1 .

We prove that any inducedD 2 -saturated family must have size at least √ n . To establish this, we first need the following technical lemma.

This led to the conjecture sat ( ∗ n, D 2 ) = Θ( n ) [4].

Lemma 9. For n ≥ 1 , let F be an inducedD 2 -saturated family in B n and let F ∗ be an arbitrary member of F .

/negationslash

- (1) For each i ∈ F ∗ , there exist F , G i i ∈ F such that F i ⊆ F ∗ and F i -G i = { } i .
- (2) For each j ∈ F ∗ , there exist G , F j j ∈ F such that G j ⊇ F ∗ and F j -G j = { } j .

Proof. We will prove (1) and the proof for (2) follows similarly.

For (1) , first observe that if F ∗ = ∅ , then the statement is trivially true. Assume F ∗ = ∅ and fix i ∈ F ∗ .

/negationslash

If there is F ∈ F such that { } ⊆ i F ⊆ F ∗ and F -{ } ∈ F i , then F i = F and G i = F - { } i have the desired properties to satisfy the lemma.

Now suppose no such pair exists in F . Choose F to be a set of minimum size in { F ∈ F : { } ⊆ i F ⊆ F ∗ } . Since F - { } /negationslash∈ i F and

F is an inducedD 2 -saturated family, the family F ∪ { F - { }} i must contain an induced copy of a diamond. This diamond will have F -{ } i as a top element, a bottom element, or a side element. We examine each possibility separately.

In the case where F -{ } i forms the top element of a diamond, there exist distinct S, T , T 1 2 ∈ F such that T 1 and T 2 are incomparable while S ⊂ T j ⊂ F - { } i for each j ∈ { 1 2 , } . Thus, F ∈ F forms the top element of the diamond { S, T , T 1 2 , F } , a contradiction to F being diamond-free.

/negationslash

In the case where F -{ } i forms the bottom element of the diamond, there exist distinct T , T , U 1 2 ∈ F such that T 1 and T 2 are incomparable while F -{ } ⊂ i T j ⊂ U for each j ∈ { 1 2 , } . Since F, T , T 1 2 , U does not form a diamond, we conclude i ∈ T j for some j ∈ { 1 2 , } . Without loss of generality, F - { } ⊂ i T 1 but F ⊂ T 1 . So, we can set F i = F and G i = T 1 to satisfy the conclusion of the lemma in this case.

/negationslash

Finally, in the case where F -{ } i forms the side element of a diamond, there exist distinct S, T, U ∈ F such that T and F - { } i are incomparable while S ⊂ T ⊂ U and S ⊂ F - { } i ⊂ U . Now we consider two subcases based on the relationship of F to U .

/negationslash

Otherwise F ⊆ U . Since F is inducedD 2 -saturated, S, F, T, U does not form a diamond, so F and T must be comparable. Since F -{ } i and T are incomparable, we must have T ⊂ F and thus { } ⊆ i T ⊂ F ⊆ F ∗ . But this contradicts the choice of F as a minimum-sized subset of F ∗ in F that contains i . /square

If F ⊆ U , then we can set F i = F and G i = U since F -{ } ⊂ i U while F ⊂ U .

/negationslash

Now we have the tools to prove our main result for inducedD 2 -saturation.

Proof of Theorem 6. Construct a simple directed graph D as follows: The vertex set will be F and we include arc ( A, B ) if and only if | B -A | = 1. Thus D has at most one arc for each ordered pair of vertices.

On the other hand, Lemma 9 gives a lower bound on the number arcs in our digraph. Fix any F ∗ ∈ F .

For each i ∈ F ∗ there is an arc ( F , G i i ), and for each j ∈ [ n ] -F ∗ there is an arc ( F , G j j ). Consequently, there are at least n distinct arcs in D .

Because the total number of arcs in this graph is at most |F| |F|-( 1), it is the case that |F| |F| -( 1) ≥ n and so |F| ≥ /ceilingleft √ n /ceilingright . /square

We can obtain a much better lower bound when the inducedD 2 -saturated family exhibits certain properties. Let F be an inducedD 2 -saturated family. If ∅ ∈ F or [ n ] ∈ F , then Theorem 8 gives a lower bound of n +1 for |F| . On the other hand, Proposition 10 shows that |F| is also large whenever F contains a large minimal element or a small maximal element.

## Proposition 10. Let F be an inducedD 2 -saturated family in B n .

- (2) If U ∗ is maximal in F , then n -| U ∗ | +1 ≤ |F| .
- (1) If S ∗ is minimal in F , then | S ∗ | +1 ≤ |F| .

Proof. For (1) , the result is trivial if ∅ ∈ F , so assume otherwise and fix a non-empty, minimal S ∗ in F and i ∈ S ∗ . Because S ∗ is minimal in F , we know S ∗ -{ } /negationslash∈ i F and F ∪{ S ∗ -{ }} i must contain an induced diamond. In particular, there exist distinct U, T , T 1 2 ∈ F such that T 1 and T 2 are incomparable while S ∗ -{ } ⊂ i T j ⊂ U for each j ∈ { 1 2 , } . ∗

/negationslash

Since U, T , T 1 2 , S ∈ F do not induce a diamond, i ∈ T j for some j ∈ { 1 2 , } . Without loss of generality, i ∈ T 1 , and thus S ∗ -T 1 = { } i . In particular, for each i ∈ S ∗ , there exists a unique T i ( ) ∈ F such that S ∗ -T i ( ) = { } i . These sets in F , together with S ∗ , imply |F| ≥ | S ∗ | +1. Part (2) follows from duality and Part (1) . /square

/negationslash

## 3. InducedA k +1 -saturated results

Now we turn our attention to antichains. The values sat ( ∗ n, A 2 ) = n +1 and sat ( ∗ n, A 3 ) = 2 n are proven in [4]. While the first is clear, the lower bound for the second requires a non-trivial proof. Theorem 5 (d) gives that 3 n -1 ≤ sat ( ∗ n, A 4 ) ≤ 3 n + O (1). For k ≥ 4, Theorem 5 (d) gives a lower bound of sat ( ∗ n, A k ) ≥ 3 n -1 which is far from the upper bound of approximately kn .

To establish sat ( ∗ n, A k +1 ) ≥ (1 -o k (1)) kn log 2 k , we prove a more technical statement in Theorem 11 below, using two different counting arguments, and Theorem 7 will follow as a corollary. While two bounds are proven, at the end of this section a discussion is included about which of them is best for fixed k and sufficiently large n .

Theorem 11. Let k ≥ 3 be an integer and let A k +1 be an antichain of size k +1 . Then for all n ≥ k ,

$$( 2 ) & \text{sat} ^ { * } ( n, \mathcal { A } _ { k + 1 } ) \geq 2 n + \sum _ { j = 3 } ^ { k } \left \lceil \frac { n } { d ^ { * } ( j ) } \right \rceil - k + 2 \text{ where } d ^ { * } ( j ) \text{ is the largest} \\ & d \text{ such that } \left ( \stackrel { d } { \sim } j - 1.$$

$$\psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psigma \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \PSi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi\psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \PSigma \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi\PSi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psigma$$

Proof. We will use the following classical theorem of Dilworth:

Theorem 12 (Dilworth [1]) . Let P = ( P, ≤ ) be a (finite) poset. If k is the size of the largest antichain in P , then there exists a family of disjoint chains {C 1 , C 2 , . . . , C } k such that P = C 1 ∪C ∪ ·· · ∪ C 2 k .

For i ∈ [ k ] and X,Y ∈ C i , we call the open interval ( X,Y ) = { Z ∈ 2 [ n ] : X ⊂ Z ⊂ Y } a gap provided there is no Z ∈ C i with X ⊂ Z ⊂ Y . We define the size of the gap ( X,Y ) to be | Y -X | .

Let F be an inducedA k +1 -saturated family in B n . Because adding either ∅ or [ n ] to a nonempty family will not increase the size of the largest antichain, F must contain both ∅ and [ n ]. In addition, the largest antichain in F - {∅ , [ n ] } has size k . By Dilworth's theorem, F - {∅ , [ n ] } can be partitioned into k disjoint chains C 1 , C 2 , . . . , C k . There may be many such partitions, we choose an arbitrary one. We then add both ∅ and [ n ] to each of the chains. Therefore, for all distinct i, j in [ k ], it is the case that C ∩ C i j = {∅ , [ n ] } .

For all i ∈ [ k ], the following observations will be needed in both parts of the proof:

- (i) If d is the maximum size of a gap in C i , then the number of elements in C i is at least /ceilingleft n/d /ceilingright +1.

Item (i) follows from the observation that {∅ , [ n ] } ⊂ C i and item (ii) follows from the fact that if this were not the case, then F ∪ { Z } can be partitioned into k chains, which means that the largest antichain has size k , a contradiction to induced saturation.

- (ii) If ( X,Y ) is a gap in C i , then every Z ∈ ( X,Y ) must be in F .

Part (1) : For any i ∈ [ k ], we say a gap ( X,Y ) in C i is wide if there exists j = i such that |C j ∩ ( X,Y ) | ≥ 3.

/negationslash

/negationslash

Further, note that any gap in some C i ′ containing X,T,Y must also contain S, T, U . So since ¯ was the maximum size of a wide gap, the d number of wide gaps with size ¯ has decreased by at least one. d Consequently, performing this operation on wide gaps of maximum size, one

In the case where there is at least one wide gap, let ¯ be the maximum d size among all wide gaps which is realized by gap ( X,Y ) in C i with S, T, U ∈ C j ∩ ( X,Y ) for j = i . Without loss of generality, assume ( S, T ) and ( T, U ) are gaps in C j . By removing T from C j and assigning it to C i , we obtain a new set of k chains that partition F - {∅ , [ n ] } such that the maximum size among wide gaps has not increased. In particular, the gap ( X,Y ) has been replaced with gaps ( X,T ) and ( T, Y ), each with size at most ¯ d -2. On the other hand, gaps ( S, T ) and ( T, U ) have been replaced with ( S, U ) which has size at most ¯ d -2 since X ⊂ S ⊂ U ⊂ Y .

at a time, the process eventually terminates with a chain partition of F - {∅ , [ n ] } in which no gaps are wide.

Now we may assume there are no wide gaps in our k chains, so each gap will contain at most two elements from each other chain. Recall from item (ii) that each element of B n in a gap must be in F , so if d is the maximum gap size, then we have 2( k -1) ≥ 2 d -2. This implies log 2 k +1 ≥ d , which gives

$$\text{sat} ^ { * } ( n, \mathcal { A } _ { k + 1 } ) \geq k \left ( \left \lceil \frac { n } { d } \right \rceil - 1 \right ) + 2 \geq k \left \lceil \frac { n } { \left [ \log _ { 2 } k \right ] + 1 } \right ] - k + 2, \\ \text{commuting the proof of non-} / 1 \right )$$

completing the proof of part (1) .

Part (2) : Return to the original chain partition C 1 , . . . , C k of F -{∅ , [ n ] } guaranteed by Dilworth's Theorem. Now we use an recursive process to obtain a coloring of F - {∅ , [ n ] } with k colors. To begin, all elements of F - {∅ , [ n ] } are considered to be uncolored. Build a maximal chain in F -{∅ , [ n ] } by starting with C 1 and add elements of F-{∅ , [ n ] } , one at a time, provided the result is still a chain. Continue until no more elements of F-{∅ , [ n ] } can be added. The elements in the final chain will form color class 1. Now for some 1 ≤ j &lt; k , suppose that we have already defined color classes 1 , . . . , j . To obtain color class j +1, start with C j +1 , remove any elements that have already been colored from F-{∅ , [ n ] } and add uncolored elements from F-{∅ , [ n ] } , one at a time, provided the result is still a chain. Continue until this process terminates. The elements in the resulting chain will form color class j +1. Finally add ∅ and [ n ] to every color class.

For each j ∈ N , let d ∗ ( j ) be the largest integer d for which ( d /floorleft d/ 2 /floorright ) ≤ j -1. Therefore, each gap in the chain for color class j has size at most d ∗ ( j ) and by item (i), color class j has at least /ceilingleft n/d ∗ ( j ) /ceilingright + 1 elements. Correcting for ∅ and [ n ] being in every color class and noting that d ∗ (1) = d ∗ (2) = 1, we obtain the desired bound:

By item (ii), each element of B n in a gap must be in F , thus the structure of our color classes guarantees that each element in ( X,Y ) has a color from the set { 1 , . . . , j - } 1 . Since each color class forms a chain, every element in the largest antichain in ( X,Y ) must have a different color. For a gap ( X,Y ) which has size d , note that ( X,Y ) ∪{ X,Y } is isomorphic to B d . Sperner's theorem [8] gives that the maximum size of an antichain in B d is ( d /floorleft d/ 2 /floorright ) , therefore ( d /floorleft d/ 2 /floorright ) ≤ j -1.

$$\text{sat} ^ { * } ( n, \mathcal { A } _ { k + 1 } ) \geq \sum _ { j = 1 } ^ { k } \left ( \left \lceil \frac { n } { d ^ { * } ( j ) } \right \rceil - 1 \right ) + 2 = 2 n + \sum _ { j = 3 } ^ { k } \left \lceil \frac { n } { d ^ { * } ( j ) } \right \rceil - k + 2.$$

/square

A table of values of k , 1 ≤ k ≤ 300, is given in [9] which determines whether Theorem 11 (1) or Theorem 11 (2) is the better lower bound for sat ∗ ( n, A k +1 ) when n is sufficiently large.

For n sufficiently large and k ≤ 243 the lower bound provided by (2) is larger than the bound provided by (1) . However, for large k ( k ≥ 2 64 suffices), (1) is larger than (2) . Some straightforward calculations show that (1) is at least ( 1 -1 log 2 k ) kn log 2 k for n ≥ log 3 2 k and that suffices for our main result. For further discussion of the comparison between (1) and (2) see [9, Section 3.2].

## 4. Conclusion

Despite the significant improvement over the results in [4], we still believe that sat ( ∗ n, D 2 ) = n +1 and sat ( ∗ n, A k +1 ) = kn -o k ( ).

As seen in Theorem 5, there are still many open questions with induced saturation and other poset families to be explored.

For the case of sat ( ∗ n, A k +1 ) for k ≥ 3, we note that Theorem 5 (d) shows that sat ( ∗ n, A k +1 ) &lt; ( n -1) k -(1 / 2 + o (1)) log 2 k , so a lower bound of ( k -1) n is not possible.

Martin was partially supported by a grant from the Simons Foundation (#353292). Smith acknowledges partial support from NSF-DMS grant #1344199. Most of the work for this project was completed while Walker was affiliated with Iowa State University.

## References

- [1] R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics , 51 (1): 161-166, 1950.
- [2] P. Erd¨s, A. Hajnal, and J. W. Moon. A problem in graph theory. o The American Mathematical Monthly , 71 (10): 1107-1110, 1964.
- [3] J. R. Faudree, R. J. Faudree, and J. R. Schmitt. A survey of minimum saturated graphs. The Electronic Journal of Combinatorics , Dynamic Survey, DS19, accessed 14 March 2019.
- [4] 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. Discrete Mathematics , 340 (10): 2479-2487, 2017.
- [5] D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. P´lv¨lgyi, and B. Patk´s. a o o Saturating Sperner Families. Graphs and Combinatorics , 29 (5): 1355-1364, 2013.
- [6] J. R. Griggs and W.-T. Li. Progress on poset-free families of subsets. In Recent Trends in Combinatorics , pages 317-338. Springer, 2016.
- [7] N. Morrison, J. A. Noel, and A. Scott. On saturated k -Sperner systems. The Electronic Journal of Combinatorics , 21 (3): P3-22, 2014.
- 10 RYAN R. MARTIN, HEATHER C. SMITH, AND SHANISE WALKER
- [8] E. Sperner. Ein satz ¨ber untermengen einer endlichen menge. u Mathematische Zeitschrift , 27 (1): 544-548, 1928.
- [9] S. Walker. Problems in extremal graphs and poset theory (2018). Graduate Theses and Dissertations. 16482.
- [10] A. A. Zykov. On some properties of linear complexes. Matematicheskii Sbornik , 66 (2): 163-188, 1949.

(Martin) Department of Mathematics, Iowa State University, Ames, Iowa, 50011

E-mail address :

rymartin@iastate.edu

(Smith) Department of Mathematics and Computer Science, Davidson College, Davidson, NC 28035

E-mail address : hcsmith@davidson.edu

(Walker) Department of Mathematics, University of Wisconsin-Eau Claire, Eau Claire, WI 54702

E-mail address : walkersg@uwec.edu
Ryan R. Martin Heather C. Smith Shanise Walker
Improved bounds for induced poset saturation
Given a finite poset $\mathcal{P}$, a family $\mathcal{F}$ of elements in the
Boolean lattice is induced-$\mathcal{P}$-saturated if $\mathcal{F}$ contains no
copy of $\mathcal{P}$ as an induced subposet but every proper superset of
$\mathcal{F}$ contains a copy of $\mathcal{P}$ as an induced subposet. The
minimum size of an induced-$\mathcal{P}$-saturated family in the
$n$-dimensional Boolean lattice, denoted $\operatorname{sat}^*(n,\mathcal{P})$,
was first studied by Ferrara et al. (2017).
  Our work focuses on strengthening lower bounds. For the 4-point poset known
as the diamond, we prove $\operatorname{sat}^*(n,\mathcal{D}_2)\geq\sqrt{n}$,
improving upon a logarithmic lower bound. For the antichain with $k+1$
elements, we prove $\operatorname{sat}^*(n,\mathcal{A}_{k+1})\geq
(1-o_k(1))\frac{kn}{\log_2 k}$, improving upon a lower bound of $3n-1$ for
$k\geq 3$.