## Set families with forbidden subposets

Linyuan Lu ∗

Kevin G. Milans †

August 5, 2014

## Abstract

Let F be a family of subsets of { 1 , . . . , n } . We say that F is P -free if the inclusion order on F does not contain P as an induced subposet. The Tur´ an function of P , denoted La ( ∗ n, P ), is the maximum size of a P -free family of subsets of { 1 , . . . , n } . We show that La ( ∗ n, P ) ≤ (4 r + O ( √ r )) ( n /floorleft n/ 2 /floorright ) if P is an r -element poset of height at most 2. We also show that La ( ∗ n, S r ) = ( r + O ( √ r )) ( n /floorleft n/ 2 /floorright ) where S r is the standard example on 2 r elements, and that La ( ∗ n, 2 [2] ) ≤ (2 583 + . o (1)) ( n /floorleft n/ 2 /floorright ) , where 2 [2] is the 2-dimensional Boolean lattice.

## 1 Introduction

Tur´ an-type problems ask for the largest objects that do not contain a particular substructure. We seek the largest set families whose inclusion order does not contain a copy of a fixed poset.

A poset P is a subposet of Q if P ⊆ Q and x ≤ P y if and only if x ≤ Q y . We say that Q contains a copy of P if P is a subposet of Q . If P and Q have the same elements and x ≤ P y implies that x ≤ Q y , then Q is an extension of P . An antichain is a set of elements that are pairwise incomparable, and a chain is a set of elements that are pairwise comparable. Let K r denote the r -element chain. The height of a poset P is the maximum size of a chain in P , and the width of P is the maximum size of an antichain.

Let 2 [ n ] denote the n -dimensional Boolean lattice; this is just the inclusion order on the subsets of [ n ], where [ n ] = { 1 , . . . , n } . The levels of the Boolean lattice are the families of the form ( [ n ] k ) , where ( S k ) denotes the subsets of S of size k . If F ⊆ 2 [ n ] , then F is a subposet and also ordered by containment. If F does not contain a copy of P , we say that F is P -free . The Tur´ an function of P , denoted La ( ∗ n, P ), is the maximum size of a P -free family F with F ⊆ 2 [ n ] . In 1928, Sperner [18] proved that the maximum size of an antichain in 2 [ n ] is ( n /floorleft n/ 2 /floorright ) . In our language, Sperner's theorem states that La ( ∗ n, K 2 ) = ( n /floorleft n/ 2 /floorright ) . Erd˝ os [9] extended Sperner's result to longer chains, showing that La ( ∗ n, K r ) is the sum of the r -1 largest binomial coefficients in { ( n 0 ) ( , n 1 ) , . . . , ( n n ) } . Hence La ( ∗ n, K r ) = ( r -1 + o (1)) ( n /floorleft n/ 2 /floorright ) for fixed r and growing n . Except when P is an antichain, La ( ∗ n, P ) is asymptotic to a positive integer multiple of ( n /floorleft n/ 2 /floorright ) in all known cases. It is convenient to define the Tur´ an threshold , denoted π ∗ ( P ), to be lim sup n →∞ La ( ∗ n, P ) / ( n /floorleft n/ 2 /floorright ) whenever the

∗ University of South Carolina, Columbia, SC 29208, ( lu@math.sc.edu ). Research supported in part by NSF grant DMS 1300547 and ONR grant N00014-13-1-0717.

† West Virginia University, Morgantown, WV 26505, ( milans@math.wvu.edu ).

latter is finite. Clearly, La ( ∗ n, P ) ≤ ( π ∗ ( P ) + o (1)) ( n /floorleft n/ 2 /floorright ) for each poset P . Erd˝ os's result implies that π ∗ ( K r ) = r -1.

Aside from the classic results of Sperner and Erd˝s, not much is known about Tur´n thresholds o a in the induced case. In 2008, Carroll and Katona [5] proved that

A well-studied variant of this problem uses a weaker notion of containment. The weak Tur´n a function of P , denoted La( n, P ), is the maximum size of a family of subsets F of [ n ] such that F does not contain an extension of P . Under this weaker notion of containment, one must avoid P as well all proper extensions of P , and so always La( n, P ) ≤ La ( ∗ n, P ). For chains, the two notions of containment coincide and equality holds. Many groups obtained bounds on the weak Tur´n function a for specialized poset families; see [14, 19, 7, 8, 10, 12] for results spanning nearly 25 years. In 2009, Bukh [3] unified many previous results by showing that La( n, P ) ≤ ( k -1) ( n /floorleft n/ 2 /floorright ) (1+ O (1 /n )) when P is tree poset of height k . Perhaps the most celebrated special case is the forbidden diamond problem, where P = 2 [2] . Axenovich, Manske, and Martin [1] proved that La( n, 2 [2] ) ≤ (2 284 + . o (1)) ( n /floorleft n/ 2 /floorright ) . Griggs, Li, and Lu [11] reduced the constant to 2 + 3 / 11, which is approximately 2 273. . The current record of 2 25 is due to Kramer, Martin, and Young [15], and it appears that new tools . will be required to improve the bound further. The two largest levels show that La( n, 2 [2] ) ≥ (2 -o (1)) ( n /floorleft n/ 2 /floorright ) , and it is conjectured that La( n, 2 [2] ) is asymptotic to 2 ( n /floorleft n/ 2 /floorright ) .

$$( 1 + 1 / n + \Omega ( 1 / n ^ { 2 } ) ) \binom { n } { \lfloor n / 2 \rfloor } \leq \Lambda ^ { * } ( n, V _ { 2 } ) \leq ( 1 + 2 / n + O ( 1 / n ^ { 2 } ) \binom { n } { \lfloor n / 2 \rfloor }, \\. \quad. \dots \dots. \quad. \quad. \quad. \dots. \quad. \dots. \quad. \dots. \quad. \dots$$

where V 2 is the poset on elements { a, b 1 , b 2 } with a ≤ b 1 and a ≤ b 2 , and no other relations. It follows that π ∗ ( V 2 ) = 1. A tree poset is a poset whose Hasse diagram is a tree. In 2012, Boehnlein and Jiang [2] gave an induced analogue of Bukh's result. They showed that La ( ∗ n, P ) ≤ ( k -1 + O ( √ ln n/n ) ( n /floorleft n/ 2 /floorright ) when P is a tree poset of height k . Since the largest k -1 levels of 2 [ n ] are P -free when P has height k , it follows that π ∗ ( P ) = k -1.

In this article, we show that series-parallel posets and posets of height 2 have finite Tur´ an thresholds. We believe much more is true.

## Conjecture 1. Every poset has a finite Tur´n threshold. a

Conjecture 1 is equivalent to the statement that for each poset P , the Tur´n function satisfies a La ( ∗ n, P ) = O ( ( n /floorleft n/ 2 /floorright ) ) = O (2 n / √ n ). It is known (see [13]) that for each poset P , there exists α &gt; 0 such that La ( ∗ n, P ) = O (2 n /n α ).

In general, proving upper bounds on La ( ∗ n, P ) appears to be more challenging than proving upper bounds on La( n, P ). For example, the extension-containment analogue of Conjecture 1 follows directly from Erd˝s's result, since La( o n, P ) ≤ La( n, K r ) ≤ ( r -1 + o (1)) ( n /floorleft n/ 2 /floorright ) when P is an r -element poset; see [4] and [6] for improvements for general P .

To establish bounds on the Tur´n function and the Tur´n threshold, it is convenient to use a a a weighting on 2 [ n ] in which the set A ∈ 2 [ n ] has weight 1 / ( n | A | ) . This weighting scheme has a nice probabilistic interpretation. A maximal chain in 2 [ n ] contains one set of each size in { 0 , . . . , n } . If a maximal chain is chosen uniformly at random, then all sets of a particular size are equally likely to appear in the chain. The weight of A ∈ 2 [ n ] is equal to the probability that a randomly chosen maximal chain in 2 [ n ] contains A .

When F ⊆ 2 [ n ] , we define the Lubell function of F , denoted /lscript ( F ), to be the expected number of times that a randomly chosen maximal chain in 2 [ n ] meets F . Since /lscript ( F ) = ∑ A ∈F 1 ( n | A | ) , the

Lubell function may be viewed as an alternative measure of the size of F where sets in the middle of the Boolean lattice have small weight and sets and the ends have large weight. The value of the Lubell function at F is the Lubell mass of F . We define the Lubell threshold , denoted λ ∗ ( P ), to be lim sup n →∞ { /lscript ( F ): F ⊆ 2 [ n ] and F is P -free } . Since /lscript ( F ) ≥ |F| / ( n /floorleft n/ 2 /floorright ) , it follows that λ ∗ ( P ) ≥ π ∗ ( P ). For most of our results on the Lubell mass of P -free families, we do not need n to be large. In these cases, we use the strong Lubell threshold , denoted Λ ( ∗ P ), which is simply sup { /lscript ( F ): F is P -free } . Clearly, Λ ( ∗ P ) ≥ λ ∗ ( P ) for all P , and if λ ∗ ( P ) is finite, then so is Λ ∗ ( P ). In our language, Lubell gave an elegant proof of Erd˝s's result by showing that Λ ( o ∗ K r ) = r -1. To establish our results, we prove that certain posets have finite Lubell thresholds. We propose a strengthening of Conjecture 1.

## Conjecture 2. Every poset has a finite Lubell threshold.

In Section 2, we prove that series-parallel posets have finite Lubell thresholds. In Section 3, we prove that posets of height at most 2 have finite Lubell thresholds. We also show that r -2 ≤ π ∗ ( S r ) ≤ Λ ( ∗ S r ) = r + O ( √ r ), where S r denotes the standard example on 2 r elements. In Section 4, we establish a preliminary upper bound for the induced forbidden diamond, showing that π ∗ (2 [2] ) &lt; . 2 583.

## 2 Series-Parallel Posets

Given posets P and Q , the series construction with P below Q forms a new poset by taking the disjoint union of P and Q and setting each element of P to be less than each element of Q . Similarly, the parallel construction forms a new poset by taking the disjoint union of P and Q in which each element of P is incomparable with each element of Q . The family of series-parallel posets are defined inductively as follows. The single element poset is a series-parallel poset. If P and Q are series-parallel posets, then the posets formed via the series construction and the parallel construction are also series-parallel posets.

To establish these results, we need a refined notion of the Lubell function. In a poset P with x ≤ y , the interval [ x, y ] is { z ∈ P : x ≤ z ≤ y } . When F ⊆ 2 [ n ] and I is an interval in 2 [ n ] , we define /lscript ( F ; I ) to be the expected number of times that a random, maximal chain in I meets F . It is convenient to define /lscript -A ( F ) to be /lscript ( F ; [ ∅ , A ]) and /lscript + A ( F ) to be /lscript ( F ; [ A, n [ ]]).

Proposition 1. Let F be a nonempty family of subsets of [ n ] and let p be the probability that a random maximal chain from ∅ to [ n ] meets at least one set in F . There exists A,A ′ ∈ F such that /lscript + A ( F ) ≥ /lscript ( F ) /p and /lscript -A ′ ( F ) ≥ /lscript ( F ) /p .

Proof. Let X be the number of times that a random maximal chain C from ∅ to [ n ] meets F , and for each A ∈ F , let E A be the event that min { C ∩F} = A , and let E 0 be the event that C ∩F = ∅ .

Note that E 0 and the events in { E A : A ∈ F} partition the space of all maximal chains. Therefore

$$\mathcal { L } _ { 0 } \, \text{and} \, the events in \{ \mathcal { L } _ { A } \colon \, A \in \mathcal { L } \} \, \text{partition the space of all maximal chains.} \\ \ell ( \mathcal { F } ) = E [ X ] & = E [ X | E _ { 0 } ] \cdot \Pr [ E _ { 0 } ] + \sum _ { A \in \mathcal { F } } E [ X | E _ { A } ] \cdot \Pr [ E _ { A } ] \\ & = 0 \cdot ( 1 - p ) + \sum _ { A \in \mathcal { F } } \ell _ { A } ^ { + } ( \mathcal { F } ) \cdot \Pr [ E _ { A } ] \\ & \leq \max _ { A \in \mathcal { F } } \{ \ell _ { A } ^ { + } ( \mathcal { F } ) \} \sum _ { A \in \mathcal { F } } \Pr [ E _ { A } ] \\ & = \max _ { A \in \mathcal { F } } \{ \ell _ { A } ^ { + } ( \mathcal { F } ) \} p. \\ \text{statement follows by symmetry.}$$

The second statement follows by symmetry.

A family F ⊆ 2 [ n ] is upwardly α -shallow if /lscript + A ( F ) ≤ α for each A ∈ F . Similarly, F is downwardly α -shallow if /lscript -A ( F ) ≤ α for each A ∈ F . We say that F is α -shallow if it is upwardly α -shallow or downwardly α -shallow.

## Corollary 1. If F is α -shallow, then /lscript ( F ) ≤ α .

Proof. By symmetry, we may assume that F is upwardly α -shallow. By Proposition 1, there exists A ∈ F such that /lscript + A ( F ) ≥ /lscript ( F ). Since F is upwardly α -shallow, it must be that /lscript + A ( F ) ≤ α .

If x is an element in P , we define the open downset of x , denoted D P ( x ), to be { y ∈ P : y &lt; x } and the closed downset of x , denoted D P [ x ], to be D x ( ) ∪{ } x . Similarly, we denote the open upset of x by U P ( x ) and closed upset of x by U P [ x ]. In each of these, we may omit the subscript when P is clear from context.

Lemma 1. Let P 1 and P 2 be posets and let P be the poset obtained by introducing a new element u , setting all elements of P 1 to be below u , and all elements of P 2 to be above u . If Λ ( ∗ P 1 ) and Λ ( ∗ P 2 ) are finite, then so is Λ ( ∗ P ) and Λ ( ∗ P ) ≤ Λ ( ∗ P 1 ) + Λ ( ∗ P 2 ) + 2 .

Proof. Let α 1 = Λ ( ∗ P 1 ), α 2 = Λ ( ∗ P 2 ), and let F ⊆ 2 [ n ] satisfy /lscript ( F ) &gt; α 1 + α 2 + 2. We show that F contains a copy of P . Let F 1 = { A ∈ F : /lscript -A ( F ) ≤ α 1 + 1 , } and note that F 1 is a downwardly ( α 1 + 1)-shallow set. By Corollary 1, we have that /lscript ( F 1 ) ≤ α 1 + 1. Similarly, let F 2 = { A ∈ F : /lscript + A ( F ) ≤ α 2 +1 , and note that Corollary 1 implies that } /lscript ( F 2 ) ≤ α 2 +1.

Let F ′ = F -( F ∪ F 1 2 ). We have that /lscript ( F ′ ) ≥ /lscript ( F -) /lscript ( F 1 ) -/lscript ( F 2 ) &gt; α ( 1 + α 2 +2) -( α 1 + 1) -( α 2 +1) = 0. It follows that F ′ is nonempty. Let A ∈ F ′ ; we obtain a copy of P in which A is identified with u .

/negationslash

Since A ∈ F 1 , we have that /lscript -A ( F ) &gt; α 1 +1 and hence /lscript -A ( F - { A } ) = /lscript -A ( F ) -1 &gt; α 1 . Since Λ ( ∗ P 1 ) = α 1 , it follows that D F ( A ) contains a copy of P 1 . Similarly, U F ( A ) contains a copy of P 2 .

Note that Lemma 1 is sharp when P 1 and P 2 are chains. We say that F ⊆ 2 [ n ] is balanced if /lscript ( F ; I ) ≤ /lscript ( F ) for each interval I in 2 [ n ] . When we wish to find induced subposets of F under the assumption /lscript ( F ) &gt; α , we may assume that F is balanced. Indeed, for a general family F ⊆ 2 [ n ] , choose an interval [ A,B ] to maximize /lscript ( F ; [ A,B ]), and let F ′ = { C -A : C ∈ F ∩ [ A,B ] } . Note that F ′ ⊆ 2 B -A , and relative to this subcube, F ′ has Lubell mass /lscript ( F , [ A,B ]), which is at least /lscript ( F ). By the selection of [ A,B ], the family F ′ is balanced relative to 2 B -A .

For disjoint sets A,B ⊆ [ n ], we define R B A to be the collection of all sets in 2 [ n ] that contain A but are disjoint from B . Note that R B A is just the interval [ A, n [ ] -B ] and is hence a subcube of dimension n -| A | - | B | . When A or B is small, we may omit the set notation and write R k ij for R { k } { i,j } or simply R i for R ∅ { } i .

Lemma 2. Let P 1 and P 2 be posets and let P be the disjoint union of P 1 and P 2 with each element of P 1 incomparable with each element of P 2 . If Λ ( ∗ P 1 ) and Λ ( ∗ P 2 ) are well defined, then Λ ( ∗ P ) ≤ max Λ ( { ∗ P 1 ) , Λ ( ∗ P 2 ) } +8 .

Proof. Let α = max Λ ( { ∗ P 1 ) , Λ ( ∗ P 2 ) } . Let F be a family of subsets of [ n ] with /lscript ( F ) &gt; α + 8; we may assume without loss of generality that F is balanced. We show that for some pair { i, j } ∈ ( [ n ] 2 ) , both /lscript ( F ; R j i ) and /lscript ( F ; R i j ) are larger than α . Since z 1 and z 2 are incomparable when z 1 ∈ R j i and z 2 ∈ R i j , we obtain an induced copy of P with elements in P 1 represented by elements in F ∩ R j i and elements in P 2 represented by elements in F ∩ R i j .

For { i, j } ∈ ( [ n ] 2 ) , let θ ij = ( /lscript F ; R ij )+ ( /lscript F ; R j i )+ ( /lscript F ; R i j )+ ( /lscript F ; R ij ), and let θ = ∑ { i,j }∈ ( [ n ] 2 ) θ ij . Note that { R ,R ,R ,R ij j i i j ij } is a partition of 2 [ n ] and therefore each A ∈ F contributes to exactly one term in θ ij .

Consider A ∈ F , and let k = | A | . We compute the contribution of A to θ . There are ( ) k 2 pairs { i, j } such that A ∈ R ij , and each such term contributes 1 / ( n -2 k -2 ) to θ . There k n ( -k ) pairs { i, j } such that A ∈ R j i ∪ R i j , and each such term contributes 1 / ( n -2 k -1 ) to θ . There are ( n -k 2 ) pairs { i, j } such that A ∈ R ij and each such term contributes 1 / ( n -2 k ) to θ . Adding these, we find that the contribution of A to θ is

$$\binom { k } { 2 } \cdot \frac { 1 } { \binom { n - 2 } { k - 2 } } + k ( n - k ) \cdot \frac { 1 } { \binom { n - 2 } { k - 1 } } + \binom { n - k } { 2 } \cdot \frac { 1 } { \binom { n - 2 } { k } }. \\ n - 2, \, \text{this readily simplifies to } 4 \binom { n } { 2 } \cdot 1 / \binom { n } { 1 }, \, \text{which is } 4 \binom { n } { 2 } \, \text{ times the } \, \cdot$$

When 2 ≤ k ≤ n -2, this readily simplifies to 4 ( n 2 ) · 1 / ( n k ) , which is 4 ( n 2 ) times the contribution of A to /lscript ( F ). When k is outside this range, some of the coefficients are zero (and the corresponding contributions are undefined). If k ∈ { 1 , n - } 1 , the sum simplifies to 3 ( n 2 ) · 1 / ( n 1 ) , which is 3 ( n 2 ) times the contribution of A to /lscript ( F ). Finally, when k ∈ { 0 , n } , the sum simplifies to ( n 2 ) · 1 / ( n 0 ) , which is ( n 2 ) times the contribution of A to /lscript ( F ). Since { A ∈ F : | A | ∈ { 0 , n }} contributes at most 2 to /lscript ( F ) and { A ∈ F : | A | ∈ { 1 , n - }} 1 also contributes at most 2 to /lscript ( F ), it follows that

$$\theta & \geq 2 \cdot \binom { n } { 2 } + 2 \cdot 3 \binom { n } { 2 } + ( \ell ( \mathcal { F } ) - 4 ) \cdot 4 \binom { n } { 2 } \\ & = \binom { n } { 2 } ( 4 \ell ( \mathcal { F } ) - 8 ).$$

Choose a pair { i, j } so that θ ij ≥ 4 ( /lscript F ) -8. Because F is balanced, we have that each of the 4 terms in the sum defining θ ij is at most /lscript ( F ). It follows that each term is at least /lscript ( F ) -8, and /lscript ( F -) 8 &gt; α .

## 3 Posets of Height 2

In this section, we show that Conjecture 2 holds for posets of height 2. To do so, we need a special family of posets. Let U r be the poset with antichains { a , . . . , a 1 r } and { b S : S ⊆ [ r ] } where a j ≤ b S

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0646v1-figure-b4122a39-3349-42ad-b335-255b7b89bc8e.jpg)

{ }

{ }

{ }

{

}

{

}

{

}

{

}

Figure 1: U ′ 3

if and only if j ∈ S . The dual of a poset P is the poset Q on the same elements with x ≤ Q y if and only if y ≤ P x . Let U ′ r be the dual of U r ; this poset has the same elements but now b S ≤ a j if and only if j ∈ S .

Next, we show that both U r and U ′ r are universal for posets of height 2.

Lemma 3. If P is an r -element poset of height at most 2 , then P is a subposet of both U r and U ′ r .

Proof. It suffices to show that P is a subposet of U ′ r , since P ′ ⊆ U ′ r implies that P ⊆ U r , where P ′ is the dual of P . Let x , . . . , x 1 r be the elements of P , indexed so that the set of maximal elements of P is { x , . . . , x 1 m } . For 1 ≤ i ≤ m , we identify x i in P with a i in U ′ r . For m + 1 ≤ i ≤ r , let S i = { j ∈ [ m ] : x i ≤ x j } ∪ { } i , and we identify x i in P with b S i in U ′ r . For m + 1 ≤ i, j ≤ r , we have that i ∈ S j if and only if i = , and therefore the sets j S m +1 , . . . , S r are distinct.

/negationslash

By Lemma 3, to establish Conjecture 2 for posets of height 2, it suffices to show that each family with sufficiently large Lubell mass contains U r or U ′ r . The following concept is key. Let F ⊆ 2 [ n ] and let A ∈ F . An element i ∈ A is a pivot of A if there exists j ∈ A such that A -{ } ∪ { } ∈ F i j . We say that A is γ -flexible if it has at least γ A | | pivots. As it turns out, if each set in F is not too large and F has no γ -flexible sets, then the Lubell function of F is bounded.

Lemma 4. Let γ and δ be a real numbers in the range [0 , 1) and let F be a family of subsets of [ n ] such that | A | ≤ δn for each A ∈ F . If F does not contain a γ -flexible set, then /lscript ( F ) &lt; 1+ 1 1 -γ ln 1 1 -δ .

/negationslash

$$A \, \text{sun} \, \tan A \, \text{is} \, \text{the only set in} \, L _ { k } \, \text{containing} \\ \ell ( \mathcal { F } ) & = \sum _ { 0 \leq k \leq \delta n } | L _ { k } | \cdot \frac { 1 } { \binom { n } { k } } \\ & \leq 1 + \sum _ { 1 \leq k \leq \delta n } | L _ { k } | \cdot \frac { 1 } { \binom { n } { k } } \\ & \leq 1 + \sum _ { 1 \leq k \leq \delta n } \frac { 1 } { 1 - \gamma } \cdot k \frac { \binom { n - 1 } { k - 1 } } { \binom { n } { k } } \\ & = 1 + \frac { 1 } { 1 - \gamma } \sum _ { 1 \leq k \leq \delta n } \frac { 1 } { n - k + 1 } \\ & < 1 + \frac { 1 } { 1 - \gamma } \ln \frac { 1 } { 1 - \delta }. \\ & 6$$

Proof. Let L k = F ∩ ( [ n ] k ) . If A ∈ L k and i ∈ A but A -B = { } i for each B ∈ L k , then A is the only set in L k that contains A -{ } i . Since no set in F is γ -flexible, for each A ∈ L k , there are at least (1 -γ k ) indices i ∈ A such that A is the only set in L k containing the ( k -1)-set A -{ } i . It follows that | L k | · (1 -γ k ) ≤ ( n k -1 ) . Therefore

In most applications of Lemma 4, we set δ = 1 2. / Let F ⊆ 2 [ n ] . For a set of indices T , the projection of F onto T is the family { A ∩ T : A ∈ F} . To find a copy of U ′ r in F , we first find a γ -flexible set A such that /lscript -A ( F ) is large. Then, we will find a particular structure in the projection of F onto T . To force this structure, we will need the projection to have large Lubell mass.

Lemma 5. Let F be a family of subsets of [ n ] , let T ⊆ [ n ] with | T | = t , and let F ′ be the projection of F onto T . We have that /lscript -T ( F ′ ) ≥ t +1 n +1 /lscript ( F ) .

Proof. We show that /lscript ( F ) ≤ /lscript -T ( F ′ ) n +1 t +1 . For each B ⊆ T , let G B = { A ⊆ [ n ] : A ∩ T = B } . Note that B ∈ F ′ if and only if G B ∩F is non-empty, and when G B ∩F is non-empty, adding additional members of G B to F does not change F ′ . Hence we may assume that F is the union of some of the families in {G B : B ⊆ T } .

Next, we compute /lscript ( G B ). Let | B | = k , let X be the number of times that a random full chain meets G B , and consider the corresponding permutation σ of [ n ]. Let σ ′ be the restriction of σ to T . Note that σ determines X as follows. If the first k elements of σ ′ are not exactly the elements of B , then X = 0. So, consider the case where the first k elements of σ ′ are the elements of B . The k th element in σ ′ contributes 1 to X and additional contributions arise as follows. The elements of T partition [ n ] -T into t +1 intervals in σ , and each element in [ n ] -T between the k th element of σ ′ and the ( k +1)st element of σ ′ contributes 1 to X . Since each element in [ n ] -T is equally likely to occur in any of the t +1 intervals, the expected size of each interval is ( n -t ) / t ( +1). Therefore

It follows that

$$\ell ( \mathcal { G } _ { B } ) = \frac { 1 } { \binom { t } { k } } \left ( 1 + \frac { n - t } { t + 1 } \right ) = \frac { 1 } { \binom { t } { k } } \frac { n + 1 } { t + 1 }.$$

$$\ell ( \mathcal { F } ) \leq \sum _ { B \in \mathcal { F } ^ { \prime } } \ell ( \mathcal { G } _ { B } ) = \frac { n + 1 } { t + 1 } \sum _ { B \in \mathcal { F } ^ { \prime } } \frac { 1 } { \binom { t } { | B | } } = \frac { n + 1 } { t + 1 } \ell _ { T } ^ { - } ( \mathcal { F } ^ { \prime } ).$$

For R ⊆ [ n ], the family F shatters R if the projection of F onto R is R . The VC-dimension of F , denoted VCdim( F ), is the maximum size of a shattered subset of [ n ]. The following classical lemma has been known since the introduction of the VC-dimension (see [20, 16, 17]).

Lemma 6 (Shatter Function Lemma) . If F ⊆ 2 [ n ] and VCdim( F ) &lt; d , then |F| ≤ ∑ d -1 k =0 ( n k ) .

Corollary 2. If F ⊆ 2 [ n ] and VCdim( F ) &lt; d , then /lscript ( F ) &lt; d 2 .

The bound in Lemma 6 is best possible, since { A ⊆ [ n ] : | A | ≤ d -1 } has VC-dimension d -1. Obtaining the largest Lubell mass of a family F with VCdim( F ) &lt; d is more subtle. Since |F| ≤ ∑ d -1 k =0 ( n k ) implies that /lscript ( F ) &lt; d 2 , we obtain the following corollary.

Perhaps surprisingly, the bound in Corollary 2 is essentially best possible. For a positive integer t , partition [ n ] into sets Z , . . . , Z 1 t of nearly equal size. Let G = { A ⊆ [ n ] : | A &gt; n | -/floorleft (1 -1 /t d ) /floorright } , let H be the family of all sets A ⊆ [ n ] such that | A ∩ Z i | &lt; d/t for all i , and let F = G ∪ H . First, we claim that VCdim( F ) &lt; d . Indeed, if R ∈ ( [ n ] d ) , then for some part Z i , we have that

/negationslash

/negationslash

/negationslash

| R ∩ Z i | ≥ d/t . Let S be a subset of R ∩ Z i of size /ceilingleft d/t /ceilingright . We show that if A ∈ F , then A ∩ R = S , which implies that F does not shatter R . Suppose that A ⊆ [ n ] and A ∩ R = S . We show that A ∈ F . Indeed, since A ∩ R = S , we have that S ⊆ A . Hence | A ∩ Z i | ≥ | S ∩ Z i | ≥ d/t , and so A ∈ H . On the other hand, A is disjoint from R -S , and | R -S | ≥ d - /ceilingleft d/t /ceilingright . Therefore | A | ≤ n -( d -/ceilingleft d/t /ceilingright ) = n -/floorleft (1 -1 /t d ) /floorright and hence also A ∈ G . Hence, VCdim( F ) &lt; d .

/negationslash

Note that /lscript ( G ) = /floorleft (1 -1 /t d ) /floorright and that /lscript ( H ) = ∑ k p k , where p k is the probability that a random k -set is in H . For k &lt; d/t , we have that p k = 1. Also, p k ≥ 1 -tq k , where q k is the probability that a random k -set meets a fixed set U of size /ceilingleft n/t /ceilingright in at least d/t points. Here, we need a concentration inequality.

Lemma 7. Let U ⊆ [ n ] , let γ = | U /n | , and let δ ≥ 0 . If A is a random k -set and X = | A ∩ U | , then

$$\Pr [ X \geq ( 1 + \delta ) \gamma k ] & \leq e ^ { - \frac { ( \delta \gamma ) ^ { 2 } } { 2 } k }. \\ \cdot \quad \cdot \quad \cdot \quad \cdot$$

Proof. We select A by iteratively choosing elements a , . . . , a 1 k from those in [ n ] not already selected. Define X i to be the random variable E[ X a , . . . , a | 1 i ]. Note that X k = | A U ∩ | = X X , 0 = E[ X ] = γk , and X ,.. . , X 0 k is a martingale. Also, since altering any one of a , . . . , a 1 k changes | A ∩ U | by at most 1, we have | X i -X i -1 | ≤ 1. The lemma now follows from Azuma's inequality.

Suppose that n ≥ 2 t 2 and k ≤ (1 -1 /t d ) . Let γ = | U /n | = /ceilingleft n/t /n /ceilingright , and note that γ ≤ 1 t + 1 n . Since k ≤ (1 -1 /t d ) ≤ 1 1+ t/n d , we may set δ = d/ tγk ( ) -1 so that δ ≥ 0 and (1 + δ γk ) = d/t . Now, we compute that δγ = d tk -γ ≥ d t (1 -1 /t d ) -γ = 1 t -1 -γ ≥ 1 t -1 -( 1 t + 1 n ) ≥ 1 2 t 2 . Therefore Lemma 7 shows that q k ≤ e -( δγ ) 2 2 k ≤ e -1 8 4 t k . When k ≥ d/t , this reduces to q k ≤ e -1 8 5 t d . Hence, we have that

$$\omega _ { \mu \kappa } \geq \cdots \, \tilde { \ } = \, \sum _ { k = 0 } ^ { n } p _ { k } \\ \ell ( \mathcal { H } ) & = \sum _ { k = 0 } ^ { n } p _ { k } \\ & \geq \left ( \sum _ { k < d / t } ^ { n } \right ) + \left ( \sum _ { d / t \leq k \leq ( 1 - 1 / t ) d } 1 - t q _ { k } \right ) \\ & \geq ( 1 - 1 / t ) d - t \left ( \sum _ { d / t \leq k \leq ( 1 - 1 / t ) d } e ^ { - \frac { 1 } { 8 t 5 } d } \right ) \\ & \geq ( 1 - 1 / t ) d - t d e ^ { - \frac { 1 } { 8 t 5 } d }. \\ \arg e, \mathcal { G } \text{ and } \mathcal { H } \text{ are disjoint, and hence } \ell ( \mathcal { F } ) = \ell ( \mathcal { G } ) + \ell ( \mathcal { H } ) \geq \lfloor \sum _ { \mathcal { C } \text{ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + += + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
 \arg e, \mathcal { G } \text{ and } \mathcal { H } \text{ are disjoint, and hence } \ell ( \mathcal { F } ) = \ell ( \mathcal { G } ) + \ell ( \mathcal { H } ) \geq \lfloor \sum _ { \mathcal { C } \text{ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + += + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + += + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + += + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + += + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + += + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +........................................................................................................................................................................................................
 \end{matrix}$$

For n sufficiently large, G and H are disjoint, and hence /lscript ( F ) = /lscript ( G ) + /lscript ( H ≥ /floorleft ) (1 -1 /t d ) /floorright +(1 -1 /t d ) -tde -1 8 5 t d . Setting, for example, t = d 1 6 / , we have that /lscript ( F ) ≥ (2 -o (1)) d as d →∞ .

Lemma 8. Let γ be a constant satisfying 0 &lt; γ &lt; 1 . If F is a family of subsets of [ n ] and /lscript ( F ) &gt; r/γ 4 +2ln(2) (1 / -γ ) + 2 , then F contains U r or F contains U ′ r .

Proof. Let F be a family of subsets of [ n ] with /lscript ( F ) &gt; 4 r/γ + 2ln(2) / (1 -γ ) + 2. We define F = { [ n ] -A : A ∈ F} . Note that F is the dual of F and /lscript ( F ) = /lscript ( F ). At least one of { A ∈ F : | A | ≤ n/ 2 } and { A ∈ F : | A | ≤ n/ 2 } has Lubell mass at least /lscript ( F ) / 2. If the former occurs, then we obtain a copy of U ′ r in F . If the latter occurs, then we obtain a copy of U ′ r in F ,

which immediately yields a copy of U r in F . Let F 1 = { A ∈ F : | A | ≤ n/ 2 . } We may assume that /lscript ( F 1 ) ≥ /lscript ( F ) / 2.

Let F 2 be the set of all A in F 1 that are not γ -flexible, and let F 3 be the set of all A in F 1 such that /lscript -A ( F 1 ) ≤ 2 r/γ . By Lemma 4, we have that /lscript ( F 2 ) &lt; 1 + ln 2 / (1 -γ ). By Corollary 1, we have that /lscript ( F 3 ) ≤ 2 r/γ . Note that

$$\ell ( \mathcal { F } _ { 1 } ) - ( \ell ( \mathcal { F } _ { 2 } ) + \ell ( \mathcal { F } _ { 3 } ) ) & > \ell ( \mathcal { F } ) / 2 - \left ( 1 + \frac { \ln 2 } { 1 - \gamma } + \frac { 2 r } { \gamma } \right ) > 0 \\ \nu = \cdots \cdots$$

Hence F - F ∪F 1 ( 2 3 ) is non-empty.

/negationslash

Choose A ∈ F 1 - F ∪ F ( 2 3 ) and let T be the set of all pivots in A . Note that | T | ≥ γ A | | since A ∈ F 2 . Let F ′ be the projection of the closed downset D F 1 [ A ] onto T . Since A ∈ F 3 , we have that /lscript -A ( F 1 ) &gt; 2 r/γ . By Lemma 5, we have that /lscript -T ( F ′ ) ≥ | T | +1 | A | +1 /lscript -A ( F 1 ) &gt; γ/lscript -A ( F 1 ) ≥ 2 . r By Corollary 2, we have that VCdim( F ′ ) ≥ r , and hence there is an r -set R such that R ⊆ T and F ′ shatters R . For each S ⊆ R , there exists a set B ′ S ∈ F ′ such that B ′ S ∩ R = S , and B ′ S extends to a set B S ∈ D F 1 [ A ] such that B S ∩ T = B ′ S .

/negationslash

/negationslash

Note that R ⊆ T and each element in T is a pivot of A . For each i ∈ R , find A i ∈ F 1 such that A i = ( A -{ } i ) ∪ { } j for some j ∈ [ n ]. Since B S ⊆ A , and A -A i = { } i , we have that B S ⊆ A i if and only if i ∈ S . Therefore we obtain a copy of U ′ r in which the maximal elements are { A i : i ∈ R } and the minimal elements are { B S : S ⊆ R } .

We are now able to prove our main theorem.

Theorem 1. If P is an r -element poset of height at most 2 , then Λ ( ∗ P ) ≤ 4 r + √ (32 ln 2) r +6 .

Proof. With c = √ (ln 2) / 2 ≈ 0 589 and . γ = 1 -c/ √ r , some algebra shows that 4 r + √ (32 ln 2) r +6 &gt; 4 r/γ +2ln(2) (1 / -γ ) + 2. Hence if F ⊆ 2 [ n ] and /lscript ( F ) &gt; r 4 + √ (32 ln 2) r +6, then it follows from Lemma 8 that F contains a copy of U r or a copy of U ′ r , and by Lemma 3 both of these contain a copy of P .

We do not expect that Theorem 1 is sharp, and indeed, this technique sometimes gives better bounds when specialized to particular posets. We examine one such family which shows that the coefficient on the linear term cannot be reduced beyond 1 / 2.

## 3.1 Lubell and Tur´n Thresholds of Standard Examples a

/negationslash

The standard example , denoted S r , is a poset on 2 r elements a , . . . , a 1 r and b 1 , . . . , b r such that { a , . . . , a 1 r } and { b 1 , . . . , b r } are antichains and b j ≤ a i if and only if i = . Note that the dual of j the standard example is itself.

To find copies of S r , the full power of Corollary 2 is not necessary. Let F ⊆ 2 [ n ] and let R ⊆ [ n ]. We say that F contains an R -system of private elements if F contains sets ( B i ) i ∈ R such that for each i, j ∈ R , we have i ∈ B j if and only if i = . Of course, if j F shatters R , then one easily obtains an R -system of private elements. As our next lemma shows, if we need only a system of private elements, the required Lubell mass is reduced by a factor of 2.

Lemma 9. If F ⊆ 2 [ n ] and /lscript ( F ) &gt; r , then there exists an r -set R such that F contains an R -system of private elements.

Proof. By induction on r + . If there exists a proper subcube [ n A,B ] of 2 [ n ] with /lscript ( F , [ A,B ]) ≥ /lscript ( F ), then we apply induction to the family F ∩ [ A,B ] in [ A,B ], and the obtained R -system of private elements in [ A,B ] is valid in 2 [ n ] . Hence, we may assume that /lscript ( F , [ A,B ]) &lt; /lscript ( F ) for each subcube [ A,B ]. In particular, for each i ∈ [ n ], there is a set A ∈ F containing i , as otherwise we would have /lscript ( F , Q i ) ≥ /lscript ( F ), where Q i is the subcube [ ∅ , [ n ] -{ } i ].

If n = 0 or r = 0, then the statement holds trivially, so suppose that n ≥ 1 and r ≥ 1. Note that /lscript ( F ) = /epsilon1 + ∑ i ∈ [ n ] /lscript ( F , Q i ) where /epsilon1 = 1 if [ n ] ∈ F and /epsilon1 = 0 otherwise. It follows that there exists j ∈ [ n ] such that /lscript ( F , Q j ) ≥ /lscript ( F ) -1 &gt; r -1. Applied to the subcube Q j , it follows by induction that F ∩ Q j contains an R ′ -system of private elements ( B i ) i ∈ R ′ with | R ′ | = r -1. Setting R = R ′ ∪{ } j and choosing B j ∈ F so that j ∈ B j , we obtain an R -system of private elements with | R | = . r

Lemma 9 is sharp, since the family { ∅ } ∪ { A ⊆ [ n ] : | A &gt; n | -( r -1) } has Lubell mass r but does not contain an R -system of private elements with | R | = . r

Lemma 10. Let γ and δ be constants satisfying 0 &lt; γ,δ &lt; 1 . If F ⊆ { A ⊆ [ n ] : | A | ≤ δn } and /lscript ( F ) &gt; r/γ + 1 1 -γ ln 1 1 -δ +1 , then F contains S r .

Proof. The proof is the same as in Lemma 8 with slight modifications. Let F 1 be the set of all A in F that are not γ -flexible, and let F 2 be the set of all A in F such that /lscript -A ( F ) ≤ r/γ . By Lemma 4, we have that /lscript ( F 1 ) &lt; 1 + 1 1 -γ ln 1 1 -δ . By Corollary 1, we have that /lscript ( F 2 ) ≤ r/γ . Since /lscript ( F -) /lscript ( F 1 ) -/lscript ( F 2 ) &gt; 0, there exists A ∈ F -( F ∪F 1 2 ).

/negationslash

Let T be the set of all pivots in A . Note that | T | ≥ γ A | | since A ∈ F 1 . Let F ′ be the projection of the closed downset D F [ A ] onto T . Since A ∈ F 2 , we have that /lscript -A ( F ) &gt; r/γ . By Lemma 5, we have that /lscript -T ( F ′ ) ≥ | T | +1 | A | +1 /lscript -A ( F ) &gt; γ/lscript -A ( F ) ≥ r . By Lemma 9, there is an R -system of private elements ( B ′ j ) j ∈ R in F ′ . Each B ′ j ∈ F ′ extends to a set B j ∈ D F [ A ] such that B j ∩ T = B ′ j .

/negationslash

/negationslash

Note that R ⊆ T and each element in T is a pivot of A . For each i ∈ R , find A i ∈ F 1 such that A i = ( A -{ } i ) ∪ { } j for some j ∈ [ n ]. Since B j ⊆ A and A -A i = { } i , we have that B j ⊆ A i if and only if i ∈ B j . Hence B j ⊆ A i if and only if j = i and { A i : i ∈ R } and { B j : j ∈ R } form a copy of S r .

/negationslash

$$& \text{Theorem $2$. $r-2\leq\pi^{*}($$

Proof. For the upper bound, let F be a subfamily of 2 [ n ] with /lscript ( F ) &gt; 2 r + √ (16 ln 2) r +11, and define F + = { A ∈ F : | A | ≥ √ n/ 2 } and F -= { A ∈ F √ | : A | ≤ n/ 2 . } Note that /lscript ( F + ) ≥ /lscript ( F ) / 2 or /lscript ( F -) ≥ /lscript ( F ) / 2. Set c = ln 2 ≈ 0 833, . γ = 1 -c/ r , and δ = 1 2. / Some algebra shows that /lscript ( F ) / 2 ≥ r + √ (4 ln 2) r +5 5 . &gt; r/γ + 1 1 -γ ln 1 1 -δ +1. If /lscript ( F -) ≥ /lscript ( F ) / 2, then F -contains a copy of S r by Lemma 10. Otherwise, we set F ′ = [ ] { n -A : A ∈ F + } and apply Lemma 10 to obtain a copy of S r in F ′ . Since S r is self-dual, this implies that F + also contains a copy of S r .

/negationslash

/negationslash

/negationslash

/negationslash

For the lower bound, we may assume that r ≥ 2. We show that if F is the union of r -2 contiguous levels, then F does not contain a copy of S r . Choosing the largest r -2 levels, we obtain the lower bound. Suppose that A , . . . , A 1 r and B , . . . , B 1 r are subsets of [ n ] such that B j ⊆ A i if and only i = . Note that for each j B j , there exists an element b j ∈ [ n ] such that b j ∈ B j but b j ∈ B k for k = , as otherwise j B j ⊆ ⋃ k = j B k ⊆ A j . Since B 1 ⊆ A 2 and { b 3 , . . . , b r } ⊆ A 2 -B 1 , it follows that | A 2 | - | B 1 | = | A 2 -B 1 | ≥ r -2. Thus, it is not possible for both B , A 1 2 ∈ F if F is the union of r -2 contiguous levels.

Since S r is a 2 -element r poset of height 2, the lower bound in Theorem 2 shows that the linear coefficient in Theorem 1 cannot be reduced beyond 1 / 2. While a large gap remains in our bounds on the Lubell threshold of standard examples, we are able to determine the Tur´n threshold a asymptotically using one additional observation.

$$\begin{array} {$$

Proof. Let X be the size of a randomly chosen subset of [ n ]. By Azuma's inequality, Pr[ X ≥ n/ 2 + t ] ≤ e -t 2 2 n . It follows that |F| = 2 n Pr[ X ≥ n/ 2 + √ 2 n ln n } ] ≤ 2 n /n .

$$\text{Theorem } 3. \ r - 2 \leq \pi ^ { * } ($$

Proof. The lower bound is the same as in Theorem 2. For the upper bound, the case that r = 1 is trivial since S 1 is a 2-element antichain. Suppose that r ≥ 2 and that n is sufficiently large so that n/ 2+ √ 2 n ln n ≤ (1 -1 /e n ) ≈ 0 632 . n . Let F be a subfamily of 2 [ n ] with |F| ≥ ( r +2 √ r +6) ( n /floorleft n/ 2 /floorright ) . We show that F contains a copy of S r .

With δ = 1 - √ 1 /e , let F ′ = { A ∈ F : | A | ≤ δn } . By Lemma 11, we have that |F | ′ ≥ |F| 2 n /n ≥ ( r +2 r +5) ( n /floorleft n/ 2 /floorright ) and therefore /lscript ( F ′ ) ≥ r +2 √ r +5. Let γ = 1 -1 / √ r and note that r +2 √ r +5 &gt; r/γ + 1 1 -γ ln 1 1 -δ +1 for r ≥ 2. By Lemma 10, it follows that F ′ contains a copy of S r .

## 4 Lubell and Tur´n Thresholds of Small Boolean Lattices a

Each n -element poset P is contained in the subset lattice with ground set P . Indeed, since x ≤ y if and only if D x [ ] ⊆ D y [ ], the subset lattice contains a copy of P in which x ∈ P is represented by D x [ ]. Consequently, Conjecture 1 is equivalent to the assertion that every Boolean lattice has a finite Tur´n threshold, and Conjecture 2 is equivalent to the assertion that every Boolean lattice a has a finite Lubell threshold. In this section, we establish a finite Lubell threshold for 2 [3] and provide an preliminary bound on the Tur´n threshold for 2 a [2] . It is open whether or not 2 [4] has a finite Tur´n or Lubell threshold. a Our next bound follows naturally from our results on standard examples.

## Corollary 3. Λ (2 ∗ [3] ) ≤ 16 .

Proof. First, we show that Λ (2 ∗ [3] ) = Λ ( ∗ S 3 ). Since S 3 is a subposet of 2 [3] , it is immediate that Λ ( ∗ S 3 ) ≤ Λ (2 ∗ [3] ). Note that if F ⊆ 2 [ n ] and F is S 3 -free, then F ∪ { ∅ , [ n ] } is also S 3 -free. It follows that if F is an S 3 -free family of subsets of [ n ] and F contains neither ∅ nor [ n ], then /lscript ( F ) ≤ Λ ( ∗ S 3 ) -2. Let F be a 2 [3] -free family of subsets of [ n ]. By Proposition 1, there exist A,B ∈ F such that A ⊆ B and /lscript ( F , I ) ≥ /lscript ( F ), where I = [ A,B ]. Let F ′ = { C -A : C ∈ F ∩ I } , and note that F ′ is a subset of an n ′ -dimensional Boolean lattice, where n ′ = | B | - | A | . Obtain F ′′ from F ′ by removing the minimum and maximum elements. Since F is 2 [3] -free, it follows that F ′′ is S 3 -free. It follows that /lscript ( F -) 2 ≤ /lscript ( F ′ ) -2 = /lscript ( F ′′ ) ≤ Λ ( ∗ S 3 ) -2 and therefore /lscript ( F ) ≤ Λ ( ∗ S 3 ).

It remains to show that Λ ( ∗ S 3 ) ≤ 16. The bound in Theorem 2 is optimized for large r ; in the case r = 3, we obtain a better bound directly from Lemma 10. Let F ⊆ 2 [ n ] with /lscript ( F ) &gt; 16. At least one of { A ∈ F : | A | ≤ n/ 2 } and { A ∈ F : | A | ≥ n/ 2 } has Lubell mass larger than 8. In either case, we may apply Lemma 10 with δ = 1 2 and / γ = 2 3 to obtain a copy of / S 3 in F .

We make no effort to optimize the bound in Corollary 3 further. From below, only the trivial bounds λ ∗ (2 [3] ) ≥ π ∗ (2 [3] ) ≥ π ∗ ( K 4 ) = 3 are known. It is conceivable that π ∗ (2 [3] ) = 3 or even λ ∗ (2 [3] ) = 3. (The strong Lubell threshold satisfies Λ (2 ∗ [3] ) ≥ 3 + 2 / 3, since the family 2 [3] -{ } 1 is 2 [3] -free.)

Our next goal is to establish the strong Lubell threshold of 2 [2] exactly. Let a n = ∑ n k =0 1 / ( n k ) . We present initial values of this sequence the table below.

| n       |   0 |   1 | 2       | 3       | 4       | 5       | 6         | 7          | 8         |
|---------|-----|-----|---------|---------|---------|---------|-----------|------------|-----------|
| a n     |   1 |   2 | 2 + 1 2 | 2 + 2 3 | 2 + 2 3 | 2 + 3 5 | 2 + 31 60 | 2 + 46 105 | 2 + 13 35 |
| approx. |   1 |   2 | 2.5     | 2 . 667 | 2 . 667 | 2 . 6   | 2 . 517   | 2 . 438    | 2 . 371   |

It is easy to show that ( a n n ) ≥ 0 is a unimodal sequence that achieves its maximum value 2 + 2 / 3 at n = 3 and n = 4.

## Proposition 2. Λ (2 ∗ [2] ) = 2 + 2 / 3 .

Proof. Let F ⊆ 2 [ n ] and suppose that F is 2 [2] -free. By two applications of Proposition 1, there exists a subcube [ A,B ] with A,B ∈ F such that /lscript ( F , [ A,B ]) ≥ /lscript ( F ). Let F ′ = { C -A : C ∈ F∩ [ A,B ] } and note that F ′ is a subfamily of an n ′ -dimensional Boolean lattice, where n ′ = | B |-| A | . Since F ′ contains its minimum and maximum elements and also F ′ is 2 [2] -free, it follows that F ′ is a chain. Therefore F ′ contains at most one set of each size, which implies that /lscript ( F ′ ) ≤ a n ′ ≤ 2+2 3. / Hence /lscript ( F ) ≤ /lscript ( F , [ A,B ]) = /lscript ( F ′ ) ≤ 2 + 2 / 3, and therefore Λ (2 ∗ [2] ) ≤ 2 + 2 / 3.

For the lower bound, let F n be a maximal chain in 2 [ n ] . Clearly, F n is 2 [2] -free and /lscript ( F n ) = a n . By choosing n = 3 or n = 4, we obtain the desired lower bound.

As we have seen, to prove upper bounds on the strong Lubell threshold of P , it suffices to consider P -free families F ⊆ 2 [ n ] with ∅ , [ n ] ∈ F . While the analogue for the Lubell threshold does not generally hold, a weaker variant does hold for the Tur´n threshold, where we may a assume that ∅ ∈ F . Griggs, Li, and Lu [11] proved the analogous statement for the extension variant. In the induced case, the proof is the same; we include it for completeness. Let ρ ∗ ( P ) = lim sup n →∞ { /lscript ( F ): ∅ ∈ F ⊆ 2 [ n ] and F is P -free } .

## Lemma 12. π ∗ ( P ) ≤ ρ ∗ ( P ) ≤ λ ∗ ( P ) .

Proof. Since an additional restriction is imposed on P -free families in the definition of ρ ∗ ( P ), it is immediate that ρ ∗ ( P ) ≤ λ ∗ ( P ).

For the other inequality, let ( F n n ) ≥ 1 be a sequence of P -free families such that F n ⊆ 2 [ n ] and lim sup n →∞ |F| / ( n /floorleft n/ 2 /floorright ) = π ∗ ( P ). Let F ′ n be the subfamily of F n consisting of all sets A ∈ F n with | A | ≤ n/ 2 + √ 2 n ln n . By Lemma 11, we have that |F n | - |F ′ n | ≤ 2 n /n = o ( ( n /floorleft n/ 2 /floorright ) ). It follows that /lscript ( F ′ n ) ≥ |F ′ n | / ( n /floorleft n/ 2 /floorright ) ≥ |F n | / ( n /floorleft n/ 2 /floorright ) -o (1). By Proposition 1, there exists A n ∈ F ′ n such that /lscript ( F ′ , I n ) ≥ /lscript ( F ′ ), where I n is the subcube [ A , n n [ ]]. Let F ′′ n = { C -A n : C ∈ F ′ n ∩ I n } , and note that ∅ ∈ F ′′ n and F ′′ n is subfamily of an n ′′ -dimensional cube with n ′′ = n -| A | ≥ n -( n/ 2 + √ 2 n ln n ). Therefore ( F ′′ n ) n ≥ 1 is a sequence of P -free families in Boolean lattices of unbounded dimension and /lscript ( F ′′ n ) = /lscript ( F ′ n , I n ) ≥ /lscript ( F ′ n ) ≥ |F | n / ( n /floorleft n/ 2 /floorright ) -o (1). It follows that ρ ∗ ( P ) ≥ lim sup n →∞ /lscript ( F ′′ n ) ≥ π ∗ ( P ).

Using ρ ∗ ( P ), we improve the bound π ∗ (2 [2] ) ≤ 2 + 2 / 3 that follows from Proposition 2. This gives a preliminary upper bound on π ∗ (2 [2] ). We expect that additional improvements are possible,

and we hope this motivates additional work on the induced variant of the diamond-free poset problem.

$$\text{Theorem } 4. \ 2. 2 8 1 8 5 6 4 < \rho$$

Proof. The lower bound is due to the following construction. Partition [ n ] into sets S , T , and R . For families G and H , let G ∨ H = { A ∪ B : A ∈ G and B ∈ H} . Let F be the set family that is the union of the following subfamilies:

- 1. { ∅ } ,
- 2. ( S 1 ) ,
- 4. ( S 1 ) ∨ ( T 1 ) ∨ ( R 1 ) ,
- 3. ( S 1 ) ∨ ( T 1 ) ,
- 5. ( T 2 ) ,
- 7. ( T 2 ) ∨ ( R 1 ) , and
- 6. ( R 2 ) ,
- 8. ( T 1 ) ∨ ( R 2 ) .

It is clear that F contains no induced copy of 2 [2] . Set | S | = x n 1 , | T | = x n 2 , and | R | = x n 3 , where x 1 + x 2 + x 3 = 1. We have

$$\ell ( \mathcal { F } ) & = 1 + \frac { | S | } {$$

This polynomial achieves the maximum value 428 243 + 40 243 √ 10 ≈ 2 281856404 at . x 1 = x 3 = √ 10 -1 9 ≈ . 2402530734 and x 2 = 11+2 √ 10 9 ≈ . 5194938532. Hence, ρ ∗ (2 [2] ) &gt; . 2 2818564.

Choose a maximal chain C in 2 [ n ] uniformly at random. For each A ∈ F , let C A be the event that A is the maximum set in F ∩ C . Then we have

The upper bound follows from the first moment method. Let F be a 2 [2] -free subset of 2 [ n ] with ∅ ∈ F . Note that for each A ∈ F , we have that F ∩ [ ∅ , A ] is a chain, and therefore F ∩ [ ∅ , A ] contains at most one set of each size in { 0 , . . . , | A |} . Let G be the subfamily of all A ∈ F such that F ∩ [ ∅ , A ] does not contain a set of size 1. For k ≥ 1, let M k = ( F - G ) ∩ ( [ n ] k ) . Note that G and ( M k ) k ≥ 1 form a partition of F .

$$\ell ( \mathcal { F } ) = \sum _ { A \in \mathcal { F } } \ell _ { A } ^ { - } ( \mathcal { F } ) \Pr ( \mathcal { C } _ { A } ) \quad & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &  & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ; & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & } & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & - & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & _ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &. & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & = & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & + & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &, & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & | & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &

 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & b & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ^ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &$$

$$= \sum _ { A \in \mathcal { G } } \ell _ { A } ^ { - } ( \mathcal { F } ) \Pr ( \mathcal { C } _ { A } ) + \sum _ { k \geq 1 } \left ( \sum _ { A \in \mathcal { M } _ { k } } \ell _ { A } ^ { - } ( \mathcal { F } ) \Pr ( \mathcal { C } _ { A } ) \right )$$

Since F ∩ [ ∅ , A ] contains at most one set of each size for each A ∈ F , it follows that /lscript -A ( F ) ≤ a k , where k = | A | . Moreover, if A ∈ G , then /lscript -A ( F ) ≤ a k -1 /k . It is easy to check that the sequence ( a k -1 /k ) k ≥ 1 achieves its maximum value 2 + 5 / 12 at k = 4. Let α = 2 + 5 / 12. Setting E 0 to be the event that the maximum set in F ∩ C belongs to G and E k to be the event that the maximum set in F ∩ C belongs to M k , it follows that

$$\ell ( \mathcal { F } ) & \leq \sum _ { A \in \mathcal { G } } \alpha \Pr ( \mathcal { C } _ { A } ) + \sum _ { k \geq 1 } \left ( \sum _ { A \in \mathcal { M } _ { k } } a _ { k } \Pr ( \mathcal { C } _ { A } ) \right ) \\ & = \alpha \Pr ( \mathcal { E } _ { \alpha } ) + \sum _ { a _ { a _ { b } } } a _ { a _ { b } } \Pr ( \mathcal { E } _ { a _ { b } } ).$$

$$& = \alpha \Pr ( \mathcal { E } _ { 0 } ) + \sum _ { k \geq 1 } a _ { k } \Pr ( \mathcal { E } _ { k } ). & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &  & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & ; & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & _ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & } & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & - & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &. & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &   & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \\ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \ & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &.. & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &. } & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &$$

Note that the sequence ( a k ) k ≥ 0 satisfies a 3 = a 4 &gt; a 5 &gt; a 6 &gt; a 2 &gt; a 7 &gt; α and a k &lt; α when k ≤ 1 or k ≥ 8. With E i,j = ⋃ i ≤ ≤ k j E k , we rewrite Equation 4:

$$\ell ( \mathcal { F } ) & \leq \ ( a _ { 3 } - a _ { 5 } ) \Pr ( \mathcal { E } _ { 3, 4 } ) + ( a _ { 5 } - a _ { 6 } ) \Pr ( \mathcal { E } _ { 3, 5 } ) + ( a _ { 6 } - a _ { 2 } ) \Pr ( \mathcal { E } _ { 3, 6 } ) + \\ & \ ( a _ { 2 } - a _ { 7 } ) \Pr ( \mathcal { E } _ { 2, 6 } ) + ( a _ { 7 } - \alpha ) \Pr ( \mathcal { E } _ { 2, 7 } ) + \alpha. \\ c _ { 1 } \quad ( \dots \ ( \nu ) \sim \ \mathcal { T } \in \ \mathcal { T } \quad \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \quad \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathcal { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \ \left ( \dots \ \mathbb { T } \quad \right ) \quad \left ( \dots \ \mathbb { T } \quad \right )$$

Let S = { s : { } ∈ F} s , let T = [ n ] -S , and let x = | T /n | . Recall that C is a random maximal chain in 2 [ n ] . If the event E i,j occurs, then the maximum set A in F ∩ C belongs to ⋃ i ≤ ≤ k j M k . For each k , let C k be the unique set in C of size k . Since i ≤ | A | ≤ j , it follows that C i ⊆ A ⊆ C j . Since | A ∩ S | = 1, it is not possible that | C i ∩ S | ≥ 2. Nor is it possible that | C j ∩ S | = 0. As these are disjoint events, we have that

$$\Pr ( \mathcal { E } _ { i, j } ) & \leq 1 - \Pr ( | C _ { i } \cap S | \geq 2 ) - \Pr ( | C _ { j } \cap S | = 0 ) \\ & \leq 1 - ( 1 - \Pr ( | C _ { i } \cap S | = 0 ) - \Pr ( | C _ { i } \cap S | = 1 ) ) - \Pr ( | C _ { j } \cap S | = 0 ) \\ & \leq \Pr ( | C _ { i } \cap S | = 0 ) + \Pr ( | C _ { i } \cap S | = 1 ) - \Pr ( | C _ { j } \cap S | = 0 ). \\ \text{When $i$ and $i$ are fixed and $n$ is large $this$ becomes}$$

When i and j are fixed and n is large, this becomes

$$\Pr ( \mathcal { E } _ { i, j } ) \leq x ^ { i } + i ( 1 - x ) x ^ { i - 1 } - x ^ { j } + O ( 1 / n ).$$

Substituting into our bound and simplifying shows that

$$\ell ( \mathcal { F } ) \leq \frac { 2 9 } { 1 2 } + \frac { 1 } { 6 } x + \frac { 5 } { 1 2 } x ^ { 2 } - \frac { 1 } { 3 } x ^ { 3 } - \frac { 1 } { 1 5 } x ^ { 4 } - \frac { 1 } { 1 2 } x ^ { 5 } - \frac { 1 1 } { 1 4 0 } x ^ { 6 } - \frac { 3 } { 1 4 0 } x ^ { 7 } + O ( 1 / n ).$$

Using calculus, it is easy to check that the maximum value of the above polynomial for x ∈ [0 , 1] is 2 5823283024 . · · · , which is reached at x = 0 6870021578 . · · · . Thus, ρ ∗ (2 [2] ) ≤ 2 5823284. .

For the extension variant, Kramer, Martin, and Young [15] proved that La( n, 2 [2] ) ≤ (2 25 + . o (1)) ( n /floorleft n/ 2 /floorright ) . In fact, they prove that if ∅ ∈ F ⊆ 2 [ n ] and F does not contain an extension of 2 [2] , then /lscript ( F ) ≤ 2 25 + . o (1). Since there are 2 [2] -free families with Lubell mass 2 25 . -o (1), it is not possible to improve the upper bound La( n, 2 [2] ) ≤ (2 25 + . o (1)) ( n /floorleft n/ 2 /floorright ) using Lubell-type arguments exclusively.

The lower bound in Theorem 4 shows that the Lubell threshold of 2 [2] is strictly larger in the induced variant than it is in the extension variant, providing additional evidence that the two problems are fundamentally different. Just as known constructions show that 2 25 is a natural . barrier in the extension variant, the construction in Theorem 4 shows that one cannot improve the bound π ∗ (2 [2] ) &lt; . 2 583 beyond 2 28 using Lubell-type arguments exclusively. .

## References

- [1] M. Axenovich, J. Manske, and R. Martin. Q 2 -free families in the Boolean lattice. Order , 29(1):177-191, 2012.
- [2] E. Boehnlein and T. Jiang. Set families with a forbidden induced subposet. Combin. Probab. Comput. , 21(4):496-511, 2012.
- [3] B. Bukh. Set families with a forbidden subposet. Electron. J. Combin. , 16(1):Research Paper 142, 11, 2009.
- [4] P. Burcsi and D. T. Nagy. The method of double chains for largest families with excluded subposets. Electron. J. Graph Theory Appl. (EJGTA) , 1(1):40-49, 2013.
- [5] T. Carroll and G. O. H. Katona. Bounds on maximal families of sets not containing three sets with A ∩ B ⊂ C, A ⊂ B . Order , 25(3):229-236, 2008.

/negationslash

- [6] H.-B. Chen and W.-T. Li. A note on the largest size of families of sets with a forbidden poset. Order , 31(1):137-142, 2014.
- [7] A. De Bonis and G. O. H. Katona. Largest families without an r -fork. Order , 24(3):181-191, 2007.
- [8] A. De Bonis, G. O. H. Katona, and K. J. Swanepoel. Largest family without A ∪ B ⊆ C ∩ D . J. Combin. Theory Ser. A , 111(2):331-336, 2005.
- [9] P. Erd¨s. On a lemma of Littlewood and Offord. o Bull. Amer. Math. Soc. , 51:898-902, 1945.
- [10] J. R. Griggs and G. O. H. Katona. No four subsets forming an N . J. Combin. Theory Ser. A , 115(4):677-685, 2008.
- [11] J. R. Griggs, W.-T. Li, and L. Lu. Diamond-free families. J. Combin. Theory Ser. A , 119(2):310-322, 2012.
- [12] J. R. Griggs and L. Lu. On families of subsets with a forbidden subposet. Combin. Probab. Comput. , 18(5):731-748, 2009.
- [13] T. Johnston, L. Lu, and K. Milans. Boolean algebras and Lubell functions. Submitted.
- [14] G. O. H. Katona and T. G. Tarj´n. Extremal problems with excluded subgraphs in the a n -cube. In Graph theory (/suppress Lag´ ow, 1981) , volume 1018 of Lecture Notes in Math. , pages 84-93. Springer, Berlin, 1983.
- [15] L. Kramer, R. R. Martin, and M. Young. On diamond-free subposets of the Boolean lattice. J. Combin. Theory Ser. A , 120(3):545-560, 2013.
- [16] N. Sauer. On the density of families of sets. J. Combinatorial Theory Ser. A , 13:145-147, 1972.
- [17] S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math. , 41:247-261, 1972.

- [18] E. Sperner. Ein Satz ¨ber Untermengen einer endlichen Menge. u Math. Z. , 27(1):544-548, 1928.
- [19] H. T. Thanh. An extremal problem with excluded subposet in the Boolean lattice. Order , 15(1):51-57, 1998.
- [20] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability &amp; Its Applications , 16(2):264-280, 1971.
Linyuan Lu Kevin G. Milans
Set families with forbidden subposets
Let $F$ be a family of subsets of $\{1,\ldots,n\}$. We say that $F$ is
$P$-free if the inclusion order on $F$ does not contain $P$ as an induced
subposet. The \emph{Tur\'an function} of $P$, denoted $\pi^*(n,P)$, is the
maximum size of a $P$-free family of subsets of $\{1,\ldots,n\}$. We show that
$\pi^*(n,P) \le (4r + O(\sqrt{r}))\binom{n}{n/2}$ if $P$ is an $r$-element
poset of height at most $2$. We also show that $\pi^*(n,S_r) =
(r+O(\sqrt{r}))\binom{n}{n/2}$ where $S_r$ is the standard example on $2r$
elements, and that $\pi^*(n,B_2) \le (2.583+o(1))\binom{n}{n/2}$, where $B_2$
is the $2$-dimensional Boolean lattice.