\documentclass[12pt]{article} \usepackage{e-jc} % Packages \usepackage{amssymb,amsmath,amsthm} \usepackage{enumerate} %\usepackage[letterpaper,hmargin=1.0in,vmargin=1.0in]{geometry} %\usepackage{hyperref} %\usepackage[dvips,colorlinks,linkcolor=black,citecolor=black,filecolor=black,urlcolor=black]{hyperref} %\usepackage[colorlinks,linkcolor=black,citecolor=black,filecolor=black,urlcolor=black]{hyperref} %\usepackage[margin=20pt,font=small,labelfont=bf]{caption} \pagestyle{plain} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\beq}[1]{\begin{equation}\label{#1}} \newcommand{\enq}[0]{\end{equation}} %General %\newcommand{\abs}[1]{\left|#1\right|} %\newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\C}[2]{{{#1}\choose{{#2}}}} % \newcommand{\enote}[1]{{\bf {\Large(}Ehud:} {#1}{\bf {\Large)} }} \newcommand{\cnote}[1]{{\bf {\Large(}Clara:} {#1}{\bf {\Large)} }} %Probability \def\E{\mathop{\mathbb E}} \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation \newcommand{\Var}{{\bf Var}} \newcommand{\Cov}{{\bf Cov}} \newcommand{\1}{{\rm 1\hspace*{-0.4ex}% \rule{0.1ex}{1.52ex}\hspace*{0.2ex}}} %Algebraic Structures \newcommand{\A}{\mathcal A} \newcommand{\B}{\mathcal B} \newcommand{\M}{\mathcal M} \newcommand{\U}{\mathbf U} \newcommand{\N}{\mathcal N} \newcommand{\R}{\mathbb R} \newcommand{\Z}{\mathbb Z} %\newcommand{\C}{\mathbb C} \newcommand{\F}{\mathbb F} \newcommand{\GF}{\mathbb{GF}} %\newcommand{\B}{\{ 0,1 \}} \newcommand{\BM}{\{ -1,1 \}} \newcommand{\remove}[1]{} \title{\bf Thresholds and expectation-thresholds \\ of monotone properties with small minterms} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Ehud Friedgut\thanks{ Research supported in part by I.S.F. grant 0398246, BSF grant 2010247 and MINERVA grant 712023.}\\ \small Weizmann Institute of Science, Rehovot, Israel\\[-0.8ex] \small\tt ehud.friedgut@weizmann.ac.il\\ \and Jeff Kahn\thanks{ Research supported in part by BSF grant 2010247.} \\ \small Department of Mathematics and RUTCOR, Rutgers University, \\[-0.8ex] \small New Brunswick NJ 08854, USA \\[-0.8ex] \small\tt Jkahn@math.rutgers.edu\\ \and Clara Shikhelman \\ \small Department of Mathematics, Tel Aviv University, Israel and\\[-0.8ex] \small Department of Mathematics, Weizmann Institute, Israel \\[-0.8ex] \small\tt clara.shikhelman@gmail.com } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ \small Mathematics Subject Classifications: 05C88, 05C89} \begin{document} \maketitle \begin{abstract} Let $N$ be a finite set, let $p \in (0,1)$, and let $N_p$ denote a random binomial subset of $N$ where every element of $N$ is taken to belong to the subset independently with probability $p$ . This defines a product measure $\mu_p$ on the power set of $N$, where for $\A \subseteq 2^N$ $\mu_p(\A) := Pr[N_p \in \A]$. In this paper we study monotone (upward-closed) families $\A$ for which all minimal sets in $\A$ have size at most $k$, for some positive integer $k$. We prove that for such a family $\mu_p(\A) / p^k $ is a decreasing function, which implies a uniform bound on the coarseness of the thresholds of such families. We also prove a structure theorem which enables one to identify in $\A$ either a substantial subfamily $\A_0$ for which the first moment method gives a good approximation of its measure, or a subfamily which can be well approximated by a family with all minimal sets of size strictly smaller than $k$. Finally, we relate the (fractional) expectation threshold and the probability threshold of such a family, using linear programming duality. This is related to the threshold conjecture of \cite{KK}. \end{abstract}\section{Introduction} A family of sets $\A$ is called {\em monotone} if $A \in \A$ and $A \subset B$ implies $B \in \A$. For such a family, a set which is minimal with respect to inclusion is called a {\em minterm}. One of the fundamental phenomena in random graph theory is that of thresholds of monotone properties. This dates back to the seminal papers of Erd\H{o}s and Renyi \cite{ER59,ER60} who defined the notion of thresholds and discovered that for many interesting graph properties the probability of the property appearing in the binomial random graph $G(n,p)$, for large $n$, behaves much like a step function of the edge probability $p$, increasing from close to 0 to close to 1 abruptly as $p$ is varied slightly. The study of thresholds of random structures in general, and in random graphs specifically, has been a thriving area ever since, and thousands of papers have covered related problems. Bollob\'as and Thomason \cite{BT} showed that every monotone property of sets has a threshold function and, using the Kruskal-Katona theorem, gave optimal quantification of such thresholds. In \cite{FK} it was observed that the KKL theorem \cite{KKL}, and its extension in \cite{BKKKL} imply sharp thresholds for properties which are symmetric under the action of a group on the elements of the ground set, in particular for graph properties. For most interesting families of graph properties the threshold function $p(n)$ tends to zero as $n$ tends to infinity. In this case it is of interest to study the sharpness of the threshold. Fixing a graph property $\A$, and a parameter $\epsilon$, one may ask for the width of the interval of values of $p$ in which the probability of $G(n,p)$ having property $\A$ climbs from $\epsilon$ to $1-\epsilon$. This width is measured with respect to the value of $p$ for which the probability of $G(n,p) \in \A$ is, say, 1/2, henceforth {\em the critical } $p$. For a series of properties $\A_n$, of graphs on $n$ vertices, we will say that the threshold is sharp if the ratio between the width of the threshold interval and the critical $p$ tends to 0. We will shortly give a more precise definition of sharp thresholds in a more general setting. In his Ph.D. thesis, the first author \cite{F99} gave a necessary condition for monotone graph properties to have a sharp threshold. Roughly speaking, if a property does not have a sharp threshold it must be well approximable by a {\em local property} (e.g. containing a triangle), as opposed to properties that are {\em global} (e.g. connectivity) and cannot be well approximated by the property of containing a subgraph from a fixed list. In the appendix to \cite{F99} Bourgain proved a similar statement, with a slightly weaker conclusion, in a much more general setting, without the assumption of symmetry. In a recent paper Hatami, \cite{Hatami} gives a common generalization of these two results. Returning to the question of thresholds of local properties, the appearance of any fixed subgraph in $G(n,p)$ has a coarse threshold, and this is well understood, see Bollob\'as' paper \cite{B} for a complete description. Roughly speaking, if a fixed graph $H$ is strictly balanced then the number of copies of $H$ in $G(n,p)$ will be approximately Poisson, and the governing parameter, the expectation of the random variable, will be of order $p^{|E(H)|}n^{|V(H)|}$, which varies smoothly with $p$: when $p$ is multiplied by a constant $c$, the expectation changes by a factor of $c^{|E(H)|}$. When $H$ is not balanced the situation is only slightly more complicated, and appearance of copies of $H$ in $G(n,p)$ can be understood by studying the appearances of the densest subgraphs of $H$. Intuitively, if $H$ has a subgraph $H'$ which is much denser than $H$, then every copy of $H'$ that appears in $G(n,p)$ is extremely likely to be contained in many copies of $H$. Kahn and Kalai, \cite{KK} have a far-reaching conjecture as to what this looks like for general monotone properties. In the graph setting a variant of their conjecture (see \cite[Conj. 2.1]{KK}) says that for a family generated by copies of a single {\em nonfixed} $H$ (e.g. a Hamiltonian cycle) there is at most a logarithmic gap between the actual threshold and the probability that guarantees that the expected number of copies of each subgraph of $H$ is at least (say) 1. (It is an open question---see \cite[Question 2.2]{KK}---whether this variant is implied by the main conjecture of \cite{KK}.) The basic question which led to the writing of this paper was: how specific is this behavior to graphs? The proofs of this behavior use the symmetry of graphs very strongly, yet it seemed possible that something similar should hold also for properties of random binomial subsets of a ground set without any symmetry assumptions. This would imply a converse to the main theorems of \cite{F99} and its appendix: not only does a non-sharp threshold imply that the property in question has local nature, but also any property determined by small minimal sets has a non-sharp threshold. We will prove in this paper that this indeed is the case. \section{Setting and main results} Let $[n] $ denote the set $\{0,1,\ldots,n\}$, and let $[n]_p$ denote a random subset of $[n]$, where each element is chosen independently with probability $p$. Recall that a family of sets $\A$ is called {\em monotone} if $A \in \A$ and $A \subset B$ implies $B \in \A$ For $\A$, a family of subsets of $[n]$ and $p \in [0,1]$ we define $\mu(\A,p)$ to be the probability that $[n]_p \in \A$. Note that if $\A$ is monotone and nontrivial (i.e. neither $\A$ nor its complement are empty) then this function is strictly increasing in $p$. We will also use the notation $\mu_p$ to denote the measure $\mu( \cdot, p)$. For a fixed non-trivial monotone family $\A$ and any $x \in [0,1]$ we define $p_x$ to be the unique number such that $\mu(\A, p_x)=x$. For $0< \epsilon <1/2 $ define $\delta_\epsilon(\A) = \frac{p_{1/2}-p_\epsilon}{p_{1/2}}$. The numerator is the length of the {\em threshold interval}, in which the probability of $\A$ climbs from $\epsilon$ to $1/2$. The denominator, $p_{1/2}$, supplies the correct yardstick with which to measure this length. The slower $\delta_\epsilon (\A)$ tends to 1 as $\epsilon$ tends to 0, the sharper the threshold is (in other words, the smaller the threshold interval is.) Note it would also make sense to study the interval $[p_\epsilon, p_{1-\epsilon}]$, but our choice gives a neater normalization, bounding $\delta_\epsilon (\A)$ between 0 and 1. \begin{theorem}\label{thm:decrease} Let $\A$ be a monotone family of subsets of $[n]$, with all minterms of size at most $k$. Then the function $\frac{\mu(\A,p)}{p^k}$ is monotone decreasing. Consequently $$\delta_\epsilon(\A)\ge 1-(2\epsilon)^\frac{1}{k}.$$ \end{theorem} The simple derivation of this theorem from the Margulis-Russo lemma was pointed out to us by Oliver Riordan. Note that the theorem is tight, e.g., for a family with a single minterm. We present the proof of Theorem \ref{thm:decrease} in Section \ref{sec:lowerbound} below. An upper bound on $\delta_{\epsilon}$ will follow from a different approach which we present in Section \ref{sec:LP}: \begin{theorem}\label{thm:upperbound} Let $\A$ be a monotone family of subsets of $[n]$, with all minterms of size at most $k$, then one has: $$1-2\epsilon \frac {(k-1)^{k-1}}{k^k} \ge\delta_\epsilon(\A) .$$ \end{theorem} To present the results of Section \ref{sec:LP} we first need a definition. As usual, let $P([n])$ denote the power set of $\{1,2,\ldots,n\}$. For a monotone family $\A \subseteq P([n])$ with a set of minterms $\M$ we define $\E_p(\A)$ to be the expected number of minterms of $\A$ that are contained in the random set $[n]_p$. $\E_p(\A)$ is the expectation of the function $f(A) = \sum_{M \in \M} {\bf 1}_{A \subset M}$, which takes positive integer values on all $A$ in $\A$, and consequently gives an upper bound on $\mu(p,\A)$. This upper bound can be tightened by a fractional version, which we call the {\em fractional expectation } of $\A$. \begin{definition} For a monotone family $\A \subset P([n])$, with a set of minterms $\M$, we define the fractional expectation of $\A$ with respect to $\mu_p$ to be $$ {\E}^*_p (\A) =\min \sum \beta(B) p^{|B|}, $$ where the minimum is taken over all functions $\beta : P([n]) \rightarrow \mathbf{R}^{\geq 0}$ such that $$ \sum_{B \subseteq A} \beta(B) \ge 1 \text { for all } A \in \M. $$ \end{definition} If $\beta$ is a function for which the minimum in the definition of the fractional expectation is achieved, then ${\E}^*(\A)$ is the expectation of the function $g(A) = \sum_{B} \beta(B) {\bf 1}_{B \subseteq A}$, which is non negative and assumes values at least 1 on all $A$ in $\A$, hence this too gives a (better) upper bound on $\mu(\A)$, namely $$ {\E}_p(\A) \ge {\E}^*_p(\A) \ge \mu_p(\A). $$ The main result of Section \ref{sec:LP} is that for monotone families with minterms of bounded size this bound is not too far off mark. \begin{theorem}\label{thm:LP} Let $\A$ be a monotone family with all minterms of size at most $k$. Then for any $\alpha >0$ $$ {\E}^*_p(\A) \ge \mu_p(\A) \ge {\E}^*_{\alpha p}(\A)(1+\alpha)^{-k}. $$ \end{theorem} As a corollary we deduce a special case of the expectation-threshold conjecture of \cite{KK}. \begin{corollary} Let $\A$ be a monotone family of subsets of $[n]$, with all minterms of size at most $k$. If $ {\E}^*_p(\mathcal{A}) =1$ then $\mu_{kp}(\mathcal{A}) > 1/e$. \end{corollary} Note that for a family $\A$ with minterms of size at most $k$ the expectation threshold ($p$ for which ${\E}_p(\A)=1$), and the fractional expectation threshold ($p$ for which ${\E}^*_p(\A)=1$), differ only by a multiplicative factor of $2^k$. Talagrand conjectures in \cite{Talagrand} that the gap between the thresholds for families with minterms of size at most $k$, is of order at most $\log(k)$. In Section \ref{sec:structure} we approach the question of understanding the threshold behavior of a monotone family $\A \subseteq P([n])$ via the parameter $\E_p(\A)$, the expected number of minterms of $\A$ in a random set $[n]_p$. If we have good control over the second moment of this random variable, the expectation gives us a good indication as to the probability $\mu_p(\A)$. An example of this setting is, say, the family of all subgraphs of $K_m$ that contain a copy of $K_4$, when $p=\Theta(m^{-2/3})$. It is easy to verify that in this case the expected number of minterms (i.e. the expected number of copies of $K_4$ in $G(m,p)$) is $\Theta(1)$, whereas the variance is also of this order of magnitude, which enables us to get an effective lower bound on the measure of the family using the Payley-Zygmond bound $$ Pr [Z >0] \ge \frac{E[Z^2]}{(E[Z])^2}, $$ which holds for any non-negative random variable $Z$. On the other hand, consider the example where the minterms are all subgraphs of $K_m$ containing a copy of "$K_4$ with a tail'', a graph consisting of $K_4$ with a fifth vertex connected to precisely one of the four. We again set $p=m^{-2/3}$ and a moment of thought shows that although this family is properly contained in the previous one, the measure of their symmetric difference is negligible, as any copy of $K_4$ that appears in $G(m,m^{-2/3})$ is overwhelmingly likely to have many tails. This is reflected by the fact that the expectation now is huge rather than constant. In this case one has to realize that the tail connected to $K_4$ is a red herring, and proper analysis can, and should, focus on the previous family. Such examples are almost canonical in any introductory course on random graphs. Our main theorem in Section \ref{sec:structure} guarantees that something similar to one of these two case should hold in any family $\A$ defined by minterms of bounded size $k$. Either there is a substantial subfamily $\B$ for which the first and second moments are well behaved, or a substantial subfamily $\B$ that may be approximated by a different family with minterms of size strictly smaller than $k$. This structure theorem then allows us to deduce a theorem quite similar to Theorem \ref{thm:decrease}, with a slightly worse rate of decay (e.g. $\mu_{p/2}(\A) \ge \mu_p(\A)/(k8^k)$, as opposed to the truth which is $\mu_{p/2}(\A) \ge \mu_p(\A)/2^k$.) \section{The Margulis-Russo lemma, and proof of Theorem \ref{thm:decrease}}\label{sec:lowerbound} For a monotone family $\A$, the Margulis-Russo lemma, (\cite{M}, \cite{R}) relates the derivative of $\mu(\A,p)$ with respect to $p$ with the {\em edge boundary} of $\A$. If $A \in \A$, but $(A \setminus {a})$ is not in $\A$ we say that $a$ is a pivotal element of $A$ and that there is a boundary edge ''leaving $A$ in the direction of $a$". Let $\mbox{Piv}(A)$ denote the number of pivotal elements in $A$ (which is necessarily 0 if $A \not \in \A$). This quantity is sometimes called the sensitivity of $A$. Let $A$ be a random set chosen according to $\mu(p)$, then $\mbox{Piv}(A)$ is a random variable, and its expectation is a measure of the size of the boundary of $\A$. As the lemma below shows, this is a parameter intimately correlated with the threshold behavior of $\A$. \begin{lemma}\label{MR}[Margulis,Russo] $$ p \frac{d \mu(\A,p)}{d p} = \E[\mbox{Piv}(A)].$$ \end{lemma} This lemma, which is so simple to state, and, as we shall see shortly, very easy to prove, is extremely useful. See, e.g., \cite{FK}, \cite{F99}, \cite{BR} . It is not surprising that this lemma is relevant when studying thresholds, as the expression on the right hand side is clearly related to the ratio between the width of the threshold interval and the value of $p$ within the interval (it is an approximation of its reciprocal). Both Russo and Margulis proved this lemma by induction on $n$, the size of the ground set from which $A$ is chosen. For the sake of being self contained we present a different proof, which is well known folklore, perhaps due to Gil Kalai. {\bf Proof of Lemma \ref{MR}:} Let $\A$ be a monotone family of subsets of $[n]$, and for some fixed $(p_1,p_2,\ldots,p_n)$ consider the following product measure $\mu_{(p_1,p_2,\ldots,p_n)}$ on $P([n])$. The measure of a set $A$ is $\prod_{i \in A} p_i \prod_{j \not \in A} (1-p_j) $. For $i \in [n]$ and a random set $A$ chosen according to $\mu_{(p_1,p_2,\ldots,p_n)}$ let $a_i$ denote the probability that ($A \in \A$ and $(A \setminus \{i\}) \in \A$), and let $b_i$ denote the probability that $i$ is pivotal in $A \cup \{i\}$, i.e. ($(A \cup \{i\}) \in \A$ and $(A \setminus \{i\}) \not \in \A$). This means that the probability that $i$ is pivotal is $p_i b_i$. Recalling that $\A$ is monotone, for all $i$ we have $\mu_{(p_1,p_2,\ldots,p_n)}(A) = a_i + p_ib_i$, and $\E[\mbox{Piv}(A)] = \sum_i p_ib_i.$ We now let all of the $p_i$ depend on a common parameter $p$ in the following trivial way: $p_i(p)=p$, and note that the resulting measure is $\mu_p$. The Margulis-Russo formula now follows from a simple application of the chain rule. $$ \frac{d \mu(\A,p)}{d p} = \sum_i \frac{\partial \mu_{(p_1,p_2,\ldots,p_n)}(\A)}{\partial p_i} \cdot \frac {d p_i}{dp}= \sum b_i =\frac{ \E[\mbox{Piv}(A)]} {p} . $$ \qed The fact that Theorem \ref{thm:decrease} follows immediately from the Margulis-Russo formula, as pointed out to us by Oliver Riordan, is yet another example of how useful this result is. {\bf Proof of Theorem \ref{thm:decrease}:} Let $\A$ be a monotone family with all minterms of size at most $k$. Let $A$ be a random set chosen according to $\mu_p$. Note that $A$ can never have more than $k$ pivotal elements, and that if $A \not \in \A$ then, by definition there are no pivotal elements. Therefor $$ \E[\mbox{Piv}(A)] \leq k\cdot\mu_p(A). $$ Using this in conjunction with the Margulis-Russo formula, and deriving with respect to $p$ gives $$ \left(\frac{\mu_p(\A)}{p^k}\right)' = \frac{\mu'p^k - kp^{k-1}\mu}{p^{2k}} \leq 0. $$ \qed \section{A structure theorem for monotone families with small minterms.}\label{sec:structure} We begin with some notation. Let $\A$ be a monotone family and let $\M(A)$ be the set of its minterms. Throughout this section we will assume that all minterms are of size at most $k$. Let $X^{\A}$ be the random variable that counts the number of minterms of $\A$ in $[n]_p$. For a set $V\subset [n]$ we will define the family of its $m-$supplements with respect to $\A$ to be the family of sets $W$ of size $m$ whose disjoint union with $V$ form a minterm, namely $N^{m}_{\A}(V)=\{W \subset [n] \mbox{ s.t. } |W|=m \mbox{ and } \exists M \in \M(\A) \mbox{ s.t. } W\uplus V= M\}$. We say that $\A$ is \textit{tame} with respect to $p$ if for any $1\leq m\leq k-1$ and for any $V\subset[n]$ one has $|N^{m}_{\B}(V)|
p^{-m}$, furthermore each minterm in $N_{\A'}^{m}(B)$ is of size $m$, so $\E[X^{N_{\A'}^{m}(B)}]\geq 1$. As $N_{\A'}^{m}(B)$ is tame we can apply Lemma \ref{lemma:tameFamily} and get:
$$
\mu_p(N_{\A'}^{m}(B)) \geq \frac{\min\{\E_{p/2}[X^{N_{\A'}^{m}(B)}],1\}}{m2^m}\geq \frac{1}{m2^m}
$$
Finally as $\A'\subset \A$ we get $\mu_p(N_{\A}^{m}(B)) \geq \mu_p(N_{\A'}^{m}(B)) \geq \frac{1}{m2^m}$ as needed.
\end{proof}
Now we are ready to present the structural result and its corollaries.
\begin{theorem} \label{thm:StrTheorem}
Let $\A$ be a monotone with minterms of size at most $k$, and let $p \in [0,1]$. Then at least one of the following two possibilities holds.
\begin{enumerate}
\item
There exists a subfamily $\B \subseteq \A$, with $\mu_{p}(\B) \ge \mu_{p}(\A)/2$, which is tame with respect to $p/2$.
\item
There exists $m$ between 1 and $k-1$, and a family $\B$ which is a tame $m$-approximation of $\A$ at $p/2$ with $\mu_{p}(\B) \ge \mu_{p}(\A)/2^{m+1}.$
\end{enumerate}
\end{theorem}
By induction on the size of the minterms and application of the Theorem \ref{thm:StrTheorem} and corollary
\ref{cor:TameApp} we deduce the following corollary, whose proof we defer until after the proof of the theorem.
\begin{corollary} \label{cor:p/2top}
Let $\A$ be a monotone family of subsets of $[n]$ with all minterms of size at most $k$. Then
$$
\mu_{p/2}(\A)\ge \frac{1}{k2^{3k-1}} \mu_{p}(\A),
$$
\end{corollary}
By repeated application of the corollary above one gets:
\begin{corollary} Let $\A$ be a monotone family of subsets of $[n]$ with minterms of size at most $k$. Then:
$$\delta_\epsilon(\A)\ge 1-(2\epsilon)^\frac{1}{3k+\log k -1}$$
\end{corollary}
Note, again, that this is weaker than what follows from Theorem \ref{thm:decrease}.
\begin{proof}[Proof of Theorem \ref{thm:StrTheorem}]
Let us iteratively define new families, one of which will be either a tame family or a tame approximation. Let $\A_1 := \A$, for each $1\leq m \leq k-1$:
\begin{align*}
\B_{m}&=\{V\subset[n] \mbox{ s.t. } |N^{m}_{\A_{m}}(V)|\geq (p/2)^{-m}\}\\
\M(\A_{m+1})&= \M(\A_{m}) \setminus \{M \mid \exists V\in\B_{m}, V\subset M\}
\end{align*}
and let $\A_{m+1}$ be the family spanned by $\M(\A_{m+1})$.
As $\A=\A_1\supseteq \A_2 \dots \supseteq \A_{k-1} \supseteq \A_{k}$ there are two possible options. Either there is some $m$ for which $\mu_p(\A_m \setminus \A_{m+1})$ is large, or if for all $m$ we have that $\mu_p(\A_m \setminus \A_{m+1})$ is small then $\mu_p(\A_k)$ is large.
Note that $\A_k$ is tame with respect to $p/2$ as we removed all subsets $V\subset [n]$ that have many supplements (of any size.) If $\mu_{p}(\A_{k})\geq \frac{1}{2} \mu_{p}(\A)$ this gives us immediately the first case of the theorem.
If $\mu_{p}(\A_{k})< \frac{1}{2} \mu_{p}(\A)$ then there must be some $m$ for which $\mu_{p}(\A_{m})-\mu_{p}(\A_{m+1})\geq \frac{1}{2^{m+1}}\mu_{p}(\A)$. Let us show that in this case $\B_{m}$ is a tame $m-$approximation as guaranteed in the second case of the theorem.
Taking $\A'$ to be $\A_m\subset \A$ we see that from the definition of $\B_m$ one has that for any $B\in \B_m$ $|N_{\A_m}^{m}(B)|> (p/2)^{-m}$ so we only need to show that $N_{\A_m}^{m}(B)$ is tame.
Indeed, denote $\N$ to be the family spanned by $N^{m}_{\A_m}(B)$ and assume there is some $U\subset [n]$ and some $l