An upper bound on the size of diamond-free families of sets
Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,...,n\}$ not containing $P$ as a (weak) subposet. The diamond poset, denoted $B_{2}$, is defined on four elements $x,y,z,w$ with the relations $x<y,z$ and $y,z<w$. $La(n,P)$ has been studied for many posets; one of the major open problems is determining $La(n,B_{2})$.Studying the average number of sets from a family of subsets of $[n]$ on a maximal chain in the Boolean lattice $2^{[n]}$ has been a fruitful method. We use a partitioning of the maximal chains and introduce an induction method to show that $La(n,B_{2})\leq(2.20711+o(1))\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$, improving on the earlier bound of $(2.25+o(1))\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$ by Kramer, Martin and Young.
\section*{\refname}}

\usepackage{chngcntr}

\newenvironment{boldproof}[1][\proofname] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse}

\@ifundefined{showcaptionsetup}{}{%
 \PassOptionsToPackage{caption=false}{subfig}}
\usepackage{subfig}
\makeatother

  \addto\captionsamerican{\renewcommand{\corollaryname}{Corollary}}
  \addto\captionsamerican{\renewcommand{\definitionname}{Definition}}
  \addto\captionsamerican{\renewcommand{\examplename}{Example}}
  \addto\captionsamerican{\renewcommand{\lemmaname}{Lemma}}
  \addto\captionsamerican{\renewcommand{\propositionname}{Proposition}}
  \addto\captionsamerican{\renewcommand{\remarkname}{Remark}}
  \addto\captionsamerican{\renewcommand{\theoremname}{Theorem}}
  \addto\captionsenglish{\renewcommand{\corollaryname}{Corollary}}
  \addto\captionsenglish{\renewcommand{\definitionname}{Definition}}
  \addto\captionsenglish{\renewcommand{\examplename}{Example}}
  \addto\captionsenglish{\renewcommand{\lemmaname}{Lemma}}
  \addto\captionsenglish{\renewcommand{\propositionname}{Proposition}}
  \addto\captionsenglish{\renewcommand{\remarkname}{Remark}}
  \addto\captionsenglish{\renewcommand{\theoremname}{Theorem}}
  \providecommand{\corollaryname}{Corollary}
  \providecommand{\definitionname}{Definition}
  \providecommand{\examplename}{Example}
  \providecommand{\lemmaname}{Lemma}
  \providecommand{\propositionname}{Proposition}
  \providecommand{\remarkname}{Remark}
  \providecommand{\theoremname}{Theorem}
 \addto\captionsamerican{\renewcommand{\observationname}{Observation}}
 \addto\captionsenglish{\renewcommand{\observationname}{Observation}}
 \providecommand{\observationname}{Observation}
\providecommand{\theoremname}{Theorem}

\begin{document}
\begin{comment}
If \pgfversion<3.0.0, UPDATE TikZ. 
\end{comment}

\begin{comment}
GENERATING EXTERNALIZED CHARTS (IF THEY ARE CHANGED):

1. Uncomment the line below

2. Export to tex (plain)

3. Run these commands:

latex \textendash jobname diamond\_free\_families\_figure1 diamond\_free\_families.tex

dvips diamond\_free\_families\_figure1.dvi

ps2eps diamond\_free\_families\_figure1.ps

latex \textendash jobname diamond\_free\_families\_figure2 diamond\_free\_families.tex

dvips diamond\_free\_families\_figure2.dvi

ps2eps diamond\_free\_families\_figure2.ps

4. Delete diamond\_free\_families\_figure1.ps and diamond\_free\_families\_figure2.ps

5. Comment out the line below again, export to tex, and run the regular
latex

CHANGE THE \textbackslash{}pgfrealjobname COMMAND IN THE PREAMBLE
IF YOU CHANGE THE FILE NAME
\end{comment}


\compiletikztrue 

\global\long\def\mathcal{F}{\mathcal{F}}
\global\long\def\mathcal{X}{\mathcal{X}}
\global\long\def\mathcal{\mathcal{\mathcal{B}}}{\mathcal{\mathcal{\mathcal{B}}}}
\global\long\def\mathcal{C}{\mathcal{C}}
\global\long\def\mathcal{Y}{\mathcal{Y}}
\global\long\def\mathcal{Z}{\mathcal{Z}}
\global\long\def\mathcal{A}{\mathcal{A}}
\global\long\def\mathcal{D}{\mathcal{D}}
\global\long\def\mathcal{Q}{\mathcal{Q}}
\global\long\def\mathcal{H}{\mathcal{H}}
\global\long\def\textnormal{if }{\textnormal{if }}
\global\long\def\textnormal{ and }{\textnormal{ and }}
\global\long\def\textnormal{ or }{\textnormal{ or }}
\global\long\def\operatorname{La}{\operatorname{La}}
\global\long\def\mathbf{N}{\mathbf{N}}
\global\long\def\mathbf{R}{\mathbf{R}}
\global\long\def\mathnote#1{}

\author{D\'aniel Gr\'osz\thanks{Department of Mathematics, University of Pisa. e-mail: \protect\href{mailto:groszdanielpub@gmail.com}{groszdanielpub@gmail.com}}\and Abhishek
Methuku\thanks{Department of Mathematics, Central European University, Budapest,
Hungary. e-mail: \protect\href{mailto:abhishekmethuku@gmail.com}{abhishekmethuku@gmail.com}}\and Casey Tompkins\thanks{Alfr\'ed R\'enyi Institute of Mathematics, Hungarian Academy of
Sciences. e-mail: \protect\href{mailto:ctompkins496@gmail.com}{ctompkins496@gmail.com}}}

\title{An upper bound on the size of diamond-free families of sets}
\maketitle
\begin{abstract}
Let $\operatorname{La}(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,\ldots,n\}$
not containing $P$ as a (weak) subposet. The diamond poset, denoted
$\mathcal{Q}_{2}$, is defined on four elements $x,y,z,w$ with the relations
$x<y,z$ and $y,z<w$. $\operatorname{La}(n,P)$ has been studied for many posets;
one of the major open problems is determining $\operatorname{La}(n,\mathcal{Q}_{2})$. It
is conjectured that $\operatorname{La}(n,\mathcal{Q}_{2})=(2+o(1))\binom{n}{\left\lfloor n/2\right\rfloor }$,
and infinitely many significantly different, asymptotically tight
constructions are known.

Studying the average number of sets from a family of subsets of $[n]$
on a maximal chain in the Boolean lattice $2^{[n]}$ has been a fruitful
method. We use a partitioning of the maximal chains and introduce
an induction method to show that $\operatorname{La}(n,\mathcal{Q}_{2})\leq(2.20711+o(1))\binom{n}{\left\lfloor n/2\right\rfloor }$,
improving on the earlier bound of $(2.25+o(1))\binom{n}{\left\lfloor n/2\right\rfloor }$
by Kramer, Martin and Young.
\end{abstract}

\section{Introduction}

Let $[n]=\{1,2,\dots,n\}$. The Boolean lattice $2^{[n]}$ is defined
as the family of all subsets of $[n]=\{1,2,\ldots,n\}$, and the\emph{
$i$th level} of $2^{[n]}$ refers to the collection of all sets of
size $i$. In 1928, Sperner proved the following well-known theorem.
\begin{thm}[Sperner \cite{sperner1928satz}]
\emph{}If $\mathcal{F}$ is a family of subsets of $[n]$ such that no set
contains another ($A,B\in\mathcal{F}$ implies $A\not\subset B$), then $\left|\mathcal{F}\right|\le\binom{n}{\left\lfloor n/2\right\rfloor }$.
Moreover, equality occurs if and only if $\mathcal{F}$ is a level of maximum
size in $2^{[n]}$. 
\end{thm}

\begin{defn}
Let $P$ be a finite poset, and $\mathcal{F}$ be a family of subsets of $[n]$.
We say that $P$ is contained in $\mathcal{F}$ as a (weak) subposet if there
is an injection $\varphi:P\rightarrow\mathcal{F}$ satisfying $x_{1}<_{p}x_{2}\Rightarrow\varphi(x_{1})\subset\varphi(x_{2})$
for every $x_{1},x_{2}\in P$. $\mathcal{F}$ is called $P$-free if $P$ is
not contained in $\mathcal{F}$ as a weak subposet. We define the corresponding
extremal function as $\operatorname{La}(n,P):=\max\{\left|\mathcal{F}\right|:\mathcal{F}\textnormal{ is \ensuremath{P}-free}\}$. 
\end{defn}

A $k$-chain, denoted by $P_{k}$, is defined to be the poset on the
set $\{x_{1},x_{2},\dots,x_{k}\}$ with the relations $x_{1}\le x_{2}\le\dots\le x_{k}$.
Using the above notation, Sperner's theorem can be stated as $\operatorname{La}(n,P_{2})=\binom{n}{\left\lfloor n/2\right\rfloor }$.
Let $\Sigma(n,k)$ denote the sum of the $k$ largest binomial coefficients
of order $n$. An important generalization of Sperner's theorem due
to Erd\H os\emph{ }\cite{erdos1945lemma} states that $\operatorname{La}(n,P_{k+1})=\Sigma(n,k)$.
Moreover, equality occurs if and only if $\mathcal{F}$ is the union of $k$
of the largest levels in $2^{[n]}$.
\begin{defn}[Posets $\mathcal{Q}_{2},V$ and $\Lambda$]
 The diamond poset, denoted $\mathcal{Q}_{2}$ (or $\mathcal{D}_{2}$ or $\mathcal{\mathcal{\mathcal{B}}}_{2}$),
is a poset on four elements $\{x,y,z,w\}$, with the relations $x<y,z$
and $y,z<w$. That is, $\mathcal{Q}_{2}$ is a subposet of a family of sets
$\mathcal{A}$ if there are different sets $A,B,C,D\in\mathcal{A}$ with $A\subset B,C$
and $B,C\subset D$. (Note that $B$ and $C$ are not necessarily
unrelated.) The $V$ poset is a poset on $\{x,y,z\}$ with the relations
$x\leq y,z$; the $\Lambda$ poset is defined on $\{x,y,z\}$ with
the relations $x,y\leq z$. That is, the $\Lambda$ is a subposet
of a family of sets $\mathcal{A}$ if there are different sets $B,C,D\in\mathcal{A}$
with $B,C\subset D$.
\end{defn}

The general study of forbidden poset problems was initiated in the
paper of Katona and Tarj\'an \cite{katona1983extremal} in 1983.
They determined the size of the largest family of sets containing
neither a $V$ nor a $\Lambda$. They also gave an estimate on the
maximum size of $V$-free families: $\left(1+\frac{1}{n}+o\!\left(\frac{1}{n}\right)\right)\binom{n}{\left\lfloor n/2\right\rfloor }\le\operatorname{La}(n,V)\le\left(1+\frac{2}{n}\right)\binom{n}{\left\lfloor n/2\right\rfloor }$.
This result was later generalized by De Bonis and Katona \cite{krfork}
who obtained bounds for the $r$-fork poset, $V_{r}$ defined by the
relations $x\le y_{1},y_{2},\dots,y_{r}$. Other posets for which
$\operatorname{La}(n,P)$ has been studied include complete two level posets, batons
\cite{thanh}, crowns $O_{2k}$ (cycle of length $2k$ on two levels,
asymptotically solved except for $k\in\{3,5\}$ \cite{evencrown,lu2014crown}),
butterfly \cite{de2005largest}, skew-butterfly \cite{methuku2014exact},
the $\mbox{N}$ poset \cite{griggs2008}, harp posets $\mathcal{H}(l_{1},l_{2},\dots,l_{k})$,
defined by $k$ chains of length $l_{i}$ between two fixed elements
\cite{griggs2012diamond}, and recently the complete 3 level poset
$K_{r,s,t}$ \cite{patkos} among others. (See \cite{griggs_survey}
for a nice survey by Griggs and Li.) 

One of the first general results is due to Bukh \cite{bukh2009set}
who determined the asymptotic value of $\operatorname{La}(n,P)$ for all posets
whose Hasse diagram is a tree: If $T$ is a finite poset whose Hasse
diagram is a tree of height $h(T)\ge2$, then $\operatorname{La}(n,T)=(h(T)-1)\binom{n}{\lfloor n/2\rfloor}\left(1+O\!\left(\frac{1}{n}\right)\right).$

Using more general structures instead of chains for double counting,
Burcsi and Nagy \cite{burcsi2013method} obtained a weaker version
of this theorem for general posets showing that $\operatorname{La}(n,P)\le\left(\frac{\left|P\right|+h(P)}{2}-1\right)\binom{n}{\lfloor n/2\rfloor}$.
Later this was generalized by Chen and Li \cite{chen2014note} and
recently this general bound was improved by the authors of the present
article \cite{GrMeToGeneral}. 

The most investigated poset for which even the asymptotic value of
$\operatorname{La}(n,P)$ has yet to be determined is the diamond $\mathcal{Q}_{2}$ which
is the topic of our paper. The two middle levels of the Boolean lattice
do not contain a diamond, so $\operatorname{La}(n,\mathcal{Q}_{2})\geq(2-o(1))\binom{n}{\left\lfloor n/2\right\rfloor }$.
Czabarka, Dutle, Johnston and Sz\'ekely \cite{diamond_constructions}
gave infinitely many asymptotically tight constructions by using random
set families defined from posets based on Abelian groups. Such constructions
suggest that the diamond problem is hard. Using a simple and elegant
argument, Griggs, Li and Lu \cite{griggs2012diamond} showed that
$\operatorname{La}(n,\mathcal{Q}_{2})<2.296\mbox{\ensuremath{\binom{n}{\left\lfloor n/2\right\rfloor }}}$.
Some time after they had announced this bound, Axenovich, Manske and
Martin \cite{diamond_228} improved the upper bound to $2.283\mbox{\ensuremath{\binom{n}{\left\lfloor n/2\right\rfloor }}}$.
This bound was further improved to $2.273\binom{n}{\left\lfloor n/2\right\rfloor }$
by Griggs, Li and Lu \cite{griggs2012diamond}. The best known upper
bound on $\operatorname{La}(n,\mathcal{Q}_{2})$ is $(2.25+o(1))\binom{n}{\left\lfloor n/2\right\rfloor }$
due to Kramer, Martin and Young \cite{diamond225}.
\begin{defn}
A \emph{maximal chain} or, for the rest of this article, simply a
\emph{chain} of the Boolean lattice is a sequence of sets $\emptyset,\{x_{1}\},\{x_{1},x_{2}\},\{x_{1},x_{2},x_{3}\},\dots,[n]$
with $x_{1},x_{2},x_{3}\ldots\in[n]$. We refer to $\{x_{1},\ldots,x_{i}\}$
as the $i$th set on the chain. In particular, we refer to $\{x_{1}\}$
as the first set on the chain, or just say that the chain starts with
the element $x_{1}$ (as a singleton). We refer to $x_{i}$ as the
$i$th element added to form the chain.
\end{defn}

\begin{defn}
The \emph{Lubell function} of a family of sets $\mathcal{F}\subseteq2^{[n]}$
is defined as 
\[
l(n,\mathcal{F})=\sum_{F\in\mathcal{F}}\frac{1}{\binom{n}{\left|F\right|}}.
\]
 The notation is shortened to just $l(\mathcal{F})$ when there is no ambiguity
as to the dimension of the Boolean lattice.
\end{defn}

\begin{observation}
The Lubell function of a family $\mathcal{F}$ is the average number of sets
from $\mathcal{F}$ on a chain, taken over all $n!$ chains. In particular,
the Lubell function of a level is 1, and the Lubell function of an
antichain $\mathcal{F}$ is the number of chains containing a set from $\mathcal{F}$
divided by $n!$. The Lubell function is additive across a union of
disjoint families of sets. Furthermore, $\left|\mathcal{F}\right|\leq l(\mathcal{F})\binom{n}{\left\lfloor n/2\right\rfloor }$
(\cite{LYMlubell}).
\end{observation}

The Lubell function was derived from the celebrated YMBL inequality
which was independently discovered by Yamamoto, Meshalkin, Bollob\'as
and Lubell. Using the Lubell function terminology, it states that
\begin{namedthm}[YMBL inequality \textup{\textmd{(Yamamoto, Meshalkin, Bollob\'as,
Lubell \cite{yamamoto1954logarithmic,meshalkin1963generalization,bollobas1965generalized,LYMlubell})}}]
If $\mathcal{F}\subseteq2^{[n]}$ is an antichain, then $l(\mathcal{F})\leq1$.
\end{namedthm}
For a poset $P$, let $\overline{l}(n,P)$ be the maximum of $l(n,\mathcal{F})$
over all families $\mathcal{F}\subseteq2^{[n]}$ which are both $P$-free and
contain the empty set. Let $\overline{l}(P)=\limsup_{n\to\infty}\overline{l}(n,P)$.
Griggs, Li and Lu proved that 
\begin{lem}[Griggs, Li and Lu \cite{griggs2012diamond}]
\label{lem:minpartition}
\[
\operatorname{La}(n,\mathcal{Q}_{2})\leq\left(\overline{l}(\mathcal{Q}_{2})+o(1)\right)\binom{n}{\left\lfloor n/2\right\rfloor }.
\]
\end{lem}

Kramer, Martin and Young used flag algebras to prove that
\begin{lem}[Kramer, Martin and Young \cite{diamond225}]
\label{lem:lubell2.25}$\overline{l}(\mathcal{Q}_{2})=2.25$
\end{lem}

thereby proving
\begin{thm}[Kramer, Martin and Young \cite{diamond225}]
\label{thm:La2.25}
\[
\operatorname{La}(n,\mathcal{Q}_{2})\leq(2.25+o(1))\binom{n}{\left\lfloor n/2\right\rfloor }.
\]
\end{thm}

The following construction shows that $\bar{l}(\mathcal{Q}_{2})\ge2.25$ in
Lemma \ref{lem:lubell2.25}. There are other constructions known as
well.
\begin{example}
Let $\mathcal{F}\subseteq2^{[n]}$ consist of all the sets of the following
forms: $\emptyset,\{e\},\{e,o\},\{o_{1},o_{2}\}$ where $e$ denotes
any even number in $[n]$, and $o$, $o_{1}$ and $o_{2}$ denote
any odd numbers in $[n]$. This family is diamond-free, and $l(\mathcal{F})=2.25\pm o(1)$.
\end{example}

\begin{example}
\label{exa:canonical}This construction is a generalization of the
previous one. Let $A\subseteq[n]$ with $\left|A\right|=an$. Let
$\mathcal{F}\subseteq2^{[n]}$ consist of all the sets of the following forms:
$\emptyset,\{e\},\{e,o\},\{o_{1},o_{2}\}$ where now $e$ denotes
any element of $A$, while $o$, $o_{1}$ and $o_{2}$ denote any
elements of $[n]\setminus A$. This family is diamond-free, and $l(\mathcal{F})=2+a-a^{2}\pm o(1)$.
This family contains all size 2 sets that do not form a diamond with
$\emptyset$ and the singletons, so all maximal diamond-free families
on levels 0, 1 and 2 that contain $\emptyset$ are of this form.
\end{example}

The following restriction of the problem of diamond-free families
has been investigated: How big can a diamond-free family be if it
can only contain sets from the middle three levels of $2^{[n]}$ (denoted
$\mathcal{\mathcal{\mathcal{B}}}(n,3)$)? Better bounds are known with this restriction. Axenovich,
Manske and Martin showed that
\begin{thm}[Axenovich, Manske and Martin \cite{diamond_228}]
\label{thm:3levels2.207}If $\mathcal{F}\subseteq\mathcal{\mathcal{\mathcal{B}}}(n,3)$ is diamond-free,
then $\left|\mathcal{F}\right|\leq\bigl(2.20711+o(1)\bigr)\binom{n}{\left\lfloor n/2\right\rfloor }$.
\end{thm}

Later, Manske and Shen improved it to $2.1547\mbox{\ensuremath{\binom{n}{\left\lfloor n/2\right\rfloor }}}$
in \cite{manske2013three} and recently, Balogh, Hu, Lidick\'y and
Liu gave the best known bound of $2.15121\binom{n}{\left\lfloor n/2\right\rfloor }$
in \cite{diamond21512} using flag algebras.
\begin{defn}
We call a chain \emph{maximal\textendash non-maximal (MNM)} with respect
to (w.r.t.) $\mathcal{F}$ if it contains a set from $\mathcal{F}$, and the biggest
set contained in $\mathcal{F}$ on the chain is not maximal in $\mathcal{F}$ (i.e.,
there are other sets from $\mathcal{F}$ containing it on some other chains).
\end{defn}

It is easy to see that an $\emptyset$-free family is $\Lambda$-free
if and only if the family we get by adding $\emptyset$ is diamond-free;
adding $\emptyset$ increases the Lubell function by 1. In Section
\ref{sec:invertedV} of this paper, we prove the following lemma:
\begin{lem}
\label{lem:lubell}Let $\mathcal{F}\subseteq2^{[n]}$ be a $\Lambda$-free
family that does \emph{not} contain the empty set, nor any set of
size bigger than $n-n'$ for some $n'\in\mathbf{N}$ (that can be chosen
independently of $n$). Assume that there are $cn!$ MNM chains w.r.t.\ $\mathcal{F}$.
Then $l(\mathcal{F})\leq1-\min\!\left(c+\frac{1}{n'},\frac{1}{4}\right)+\sqrt{\min\!\left(c+\frac{1}{n'},\frac{1}{4}\right)}+\frac{3}{n'}$.
\end{lem}

It is easy to see that in Example \ref{exa:canonical} the number
of MNM-chains is approximately $a^{2}n!$ (so $a\approx\sqrt{c}$):
these are the chains whose second set is $\{e_{1},e_{2}\}$ with $e_{1},e_{2}\in A$.
Thus, this lemma is (asymptotically) sharp, and states that for a
given number of MNM chains, Example \ref{exa:canonical} cannot be
beaten (with some restriction on the sizes of the sets). Barring the
requirement that the topmost $n'$ levels be empty, Lemma \ref{lem:lubell}
is a generalization of Lemma \ref{lem:lubell2.25}. The proof of Lemma
\ref{lem:minpartition} in \cite{diamond225} actually works with
the restriction of Lemma \ref{lem:lubell} concerning the topmost
sets (that there is no set of size bigger than $n-n'$) with $n'=n/2-n^{2/3}$,
immediately giving a new proof of Theorem \ref{thm:La2.25}. Our proof
of Lemma \ref{lem:lubell} includes an intricate induction step and
a (non-combinatorial) lemma about functions involving a lot of elementary
algebra and calculus; but it does not require flag algebras, and it
does not use details of the structure of $\mathcal{F}$ above the second level
(except inside the induction).

Section \ref{sec:diamond} of this paper uses Lemma \ref{lem:lubell}
to prove our main theorem:
\begin{thm}
\label{thm:main}$\operatorname{La}(n,\mathcal{Q}_{2})\leq\left(\frac{\sqrt{2}+3}{2}+o(1)\right)\binom{n}{\left\lfloor n/2\right\rfloor }<\bigl(2.20711+o(1)\bigr)\binom{n}{\left\lfloor n/2\right\rfloor }$.
\end{thm}

The proof is inspired by the proof of Theorem \ref{thm:3levels2.207}
(the same bound when restricted to 3 levels) as in \cite{diamond_228},
using the idea of grouping chains by the smallest set contained in
$\mathcal{F}$ on a chain (as developed in \cite{griggs2012diamond} and \cite{diamond225}).\global\let\addcontentslinesave\addcontentsline\renewcommand{\addcontentsline}[3]{}

\section{$\Lambda$-free families \textendash{} Proof of Lemma \ref{lem:lubell}\label{sec:invertedV}\addcontentslinesave{toc}{section}{\ref{sec:invertedV}
Inverted V-free families \textendash{} Proof of Lemma \ref{lem:lubell}}}

\subsection{Definitions and main lemma}
\begin{defn}
\global\let\addcontentsline\addcontentslinesave\label{def:functions}We
define the following functions:%
\begin{comment}
For $x,c\in[0,\infty)$, 
\[
f(x,c)=\begin{cases}
1-x & \textnormal{if }\frac{1}{2}\leq x\textnormal{ or } c\leq x^{2}\\
x^{2}-2x+1-c+\sqrt{c} & \textnormal{if } x\leq\frac{1}{2}\textnormal{ and } x^{2}\leq c\leq\frac{1}{4}\\
x^{2}-2x+1.25 & \textnormal{if } x\leq\frac{1}{2}\textnormal{ and }\frac{1}{4}\leq c
\end{cases}
\]
\begin{tikzwhenenabled}
\begin{figure}
\subfloat[Values of $f(x,c)$ plotted in $x$, for $c=0,0.0125,0.025,\ldots,0.25$.
Note that the $1-x$ part of the plots coincide.]{\tikz
\datavisualization
	[scientific axes, x axis={length=6cm,ticks and grid={step=0.25}}, y axis={length=8.5cm,ticks and grid={step=0.25}}, visualize as smooth line/.list={100,201.0,202.0,....0,220.0}]
data [set=100,format=function] {
	var c : {0};
	var x_ : interval [0:0.6] samples 2;
	func x = \value{x_};
	func y = 1-\value{x_};
}
data [format=function] {
	var i : {1,2,...,20};
	func c = \value i/80;
	var x_ : interval [0:sqrt(\value c)] samples 11;
	func x = \value{x_};
	func y = \value{x_}^2-2*\value{x_}+1-\value c+sqrt(\value c);
	func set = 200+\value i;
};}\hspace*{\fill}\subfloat[Values of $f(x,c)$ plotted in $c$, for $x=0,0.05,0.01,\ldots,1$.]{\tikz
\datavisualization
	[scientific axes, x axis={length=8cm,ticks and grid={step=0.25}}, y axis={length=10cm,ticks and grid={step=0.25}}, visualize as smooth line/.list={100.0,101.0,....0,120.0,200.0,201.0,....0,209.0,300.0,301.0,....0,309.0}]
data [format=function] {
	var i : {0,1,...,20};
	func x_ = \value i/20;
	var c : {0,((\value{x_}<0.5)?\value{x_}^2:1)};
	func x = \value{c};
	func y = 1-\value{x_};
	func set = 100+\value i;
}
data [format=function] {
	var i : {0,1,...,9};
	func x_ = \value i/20;
	var c : interval[\value{x_}^2:0.25] samples 20-2*\value i;
	func x = \value{c};
	func y = \value{x_}^2-2*\value{x_}+1-\value c+sqrt(\value c);
	func set = 200+\value i;
}
data [format=function] {
	var i : {0,1,...,9};
	func x_ = \value i/20;
	var c : interval[0.25:1] samples 2;
	func x = \value{c};
	func y = \value{x_}^2-2*\value{x_}+1.25;
	func set = 300+\value i;
};}
\end{figure}
\end{tikzwhenenabled}
\end{comment}

\begin{itemize}
\item For $x\in[0,1],c\in[0,\infty)$,
\[
f(x,c)=\begin{cases}
1-x+\left(\frac{1}{4\left(x-x^{2}\right)}-1\right)c & \textnormal{if } x\leq\frac{1}{2}\textnormal{ and } c<4\left(x-x^{2}\right)^{2}\\
x^{2}-2x+1-c+\sqrt{c} & \textnormal{if } x\leq\frac{1}{2}\tand4\left(x-x^{2}\right)^{2}\leq c\leq\frac{1}{4}\\
x^{2}-2x+1.25 & \textnormal{if } x\leq\frac{1}{2}\textnormal{ and }\frac{1}{4}\leq c\\
1-x & \textnormal{if }\frac{1}{2}\leq x.
\end{cases}
\]
\begin{tikzwhenenabled}
\begin{figure}
\subfloat[Values of $f(x,c)$ plotted in $x$, for $c=0,0.0125,0.025,\ldots,0.25$
(bottom to top). Note that the $x\geq0.5$ part of the plots coincide.]{\beginpgfgraphicnamed{diamond_free_families_figure1}
\tikz
\datavisualization
	[scientific axes, x axis={length=6cm,ticks and grid={step=0.25}}, y axis={length=8.5cm,ticks and grid={step=0.25}}, visualize as smooth line/.list={100,201.0,202.0,....0,220.0,301.0,302.0,....0,319.0}]
data [set=100,format=function] {
	var c : {0};
	var x_ : interval [0:0.6] samples 2;
	func x = \value{x_};
	func y = 1-\value{x_};
}
data [format=function] {
	var i : {1,2,...,20};
	func c = \value i/80;
	var x_ : interval [0:(1-sqrt(1-2*sqrt(\value c)))/2] samples 11;
	func x = \value{x_};
	func y = \value{x_}^2-2*\value{x_}+1-\value c+sqrt(\value c);
	func set = 200+\value i;
}
data [format=function] {
	var i : {1,2,...,19};
	func c = \value i/80;
	var x_ : interval [(1-sqrt(1-2*sqrt(\value c)))/2:0.5] samples 11;
	func x = \value{x_};
	func y = 1-\value{x_}+(1/(4*(\value{x_}-\value{x_}^2))-1)*\value c;
	func set = 300+\value i;
};
\endpgfgraphicnamed}\hspace*{\fill}\subfloat[Values of $f(x,c)$ plotted in $c$, for $x=0,0.05,0.01,\ldots,1$
(top to bottom).]{\beginpgfgraphicnamed{diamond_free_families_figure2}
\tikz
\datavisualization
	[scientific axes, x axis={length=8cm,ticks and grid={step=0.25}}, y axis={length=10cm,ticks and grid={step=0.25}}, visualize as smooth line/.list={110.0,111.0,....0,120.0,200.0,201.0,....0,209.0,300.0,301.0,....0,309.0,401.0,402.0,....0,409.0}]
data [format=function] {
	var i : {10,11,...,20};
	func x_ = \value i/20;
	var c : {0,1)};
	func x = \value{c};
	func y = 1-\value{x_};
	func set = 100+\value i;
}
data [format=function] {
	var i : {1,2,...,9};
	func x_ = \value i/20;
	var c : {0,4*(\value{x_}-\value{x_}^2)^2};
	func x = \value{c};
	func y = 1-\value{x_}+(1/(4*(\value{x_}-\value{x_}^2))-1)*\value c;
	func set = 400+\value i;
}
data [format=function] {
	var i : {0,1,...,9};
	func x_ = \value i/20;
	var c : interval[4*(\value{x_}-\value{x_}^2)^2:0.25] samples 20-2*\value i;
	func x = \value{c};
	func y = \value{x_}^2-2*\value{x_}+1-\value c+sqrt(\value c);
	func set = 200+\value i;
}
data [format=function] {
	var i : {0,1,...,9};
	func x_ = \value i/20;
	var c : interval[0.25:1] samples 2;
	func x = \value{c};
	func y = \value{x_}^2-2*\value{x_}+1.25;
	func set = 300+\value i;
};
\endpgfgraphicnamed}
\end{figure}
\end{tikzwhenenabled}
\item For $x\in[0,1),c\in[0,\infty),a\in[0,1-x),\tilde{a}\in\left[0,\min\!\left(a,\frac{c}{x+a}\right)\right]$,
\[
g(x,c,a,\tilde{a})=a+(1-x-a)f\!\left(x+a,\frac{c-\tilde{a}(x+a)}{1-x-a}\right)+2\tilde{a}(1-x-a).
\]
\item For $x\in[0,1),c\in[0,\infty),a\in[0,1-x),\tilde{a}\in\left[0,\min\!\left(a,\frac{c}{x+a}-x\right)\right]$,
\[
h(x,c,a,\tilde{a})=a+(1-x-a)f\!\left(x+a,\frac{c-(x+\tilde{a})(x+a)}{1-x-a}\right)+2\tilde{a}(1-x-a)+x-3x(x+a).
\]
\end{itemize}
\end{defn}

\begin{lem}
\label{lem:functions}The functions above satisfy the following conditions:

\begin{enumerate}
\item \label{enu:x=00003D0}For all $c\in[0,\infty)$, if $\tilde{c}=\min\!\left(c,\frac{1}{4}\right)$,
then $f(0,c)=1-\tilde{c}+\sqrt{\tilde{c}}$.
\item \label{enu:concave}$f(x,c)$ is concave and monotonously increasing
in $c$, and monotonously decreasing in $x$.
\item \label{enu:g}For all $x\in[0,1],c\in[0,\infty),a\in[0,1-x),\tilde{a}\in\left[0,\min\!\left(a,\frac{c}{x+a}\right)\right]:g(x,c,a,\tilde{a})\leq f(x,c)$.
\item \label{enu:h}For all $x\in[0,1],c\in[0,\infty),a\in[0,1-x),\tilde{a}\in\left[0,\min\!\left(a,\frac{c}{x+a}-x\right)\right]:h(x,c,a,\tilde{a})\leq f(x,c)$.
\item \label{enu:1-x}For all $c\in[0,\infty):1-x\leq f(x,c)$.
\end{enumerate}
\end{lem}

We prove Lemma \ref{lem:functions} in Appendix \ref{sec:functions_proof}.

Rather that proving Lemma \ref{lem:lubell} directly, we prove a strengthening
of it \textendash{} Lemma \ref{lem:ind}. This strengthened version
involves additional parameters, $X$ and $\mathcal{X}$, and their functions
$x$, $\alpha$ and $\mu$, which we introduce in order to make the
inductive proof possible. Lemma \ref{lem:lubell} is a special case
of Lemma \ref{lem:ind} with $X=\mathcal{X}=\emptyset$. In the rest of Section
\ref{sec:invertedV}, we prove Lemma \ref{lem:ind}.

\begin{lem}
\label{lem:ind}Let $\mathcal{F}\subseteq2^{[n]}$ be a $\Lambda$-free family
which does not contain $\emptyset$, nor any set larger than $n-n'$
for some $n'\in\mathbf{N}$. Let us assume that we are given a ``forbidden''
set $X\subseteq[n]$, with $x=\frac{\left|X\right|}{n}$. Also, let
$\mathcal{X}\subset2^{[n]}$ be a ``forbidden'' antichain in which each set
contains exactly one element of $X$ (and may or may not be a singleton).
Let us assume that the sets in $\mathcal{F}$ are disjoint from $X$, and unrelated
to every set in $\mathcal{X}$. Let $\alpha=l(\mathcal{X})$, and let $\mu n!$ be the
number of chains which start with an element of $X$ as a singleton,
but do not contain any set in $\mathcal{X}$. Assume, furthermore, that there
are $cn!$ MNM chains w.r.t.\ $\mathcal{F}$. Then $l(\mathcal{F})\leq f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x)+\frac{3}{n'}$.
\end{lem}

First we verify the base case of the induction.
\begin{prop}
\label{prop:indbase}Lemma \ref{lem:ind} holds for $n\leq n'$.
\end{prop}

\begin{proof}
$\mathcal{F}=\emptyset$. $\mathcal{X}$ is an antichain, so, by the YMBL inequality,
$\alpha\leq1$. By Lemma \ref{lem:functions} Point \ref{enu:concave}\ and
Point \ref{enu:1-x}, $f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x)+\frac{3}{n'}\geq f(x,c+\mu)-(\alpha-\mu-x)\geq1-x-(\alpha-x)\geq0=l(\mathcal{F})$.
\end{proof}
From now on we assume $n'\leq n-1$.
\begin{nameddef}[Notation]
Let $A\subseteq[n]\setminus X$ be the set of elements of $[n]$
that appear as singletons in $\mathcal{F}$, and let $a=\frac{\left|A\right|}{n}$.
Let $\mathcal{\mathcal{\mathcal{B}}}$ be the family of those sets in $\mathcal{F}$ which contain at least
one element of $A$, but which are not singletons. Let $\beta$ be
the Lubell function of $\mathcal{\mathcal{\mathcal{B}}}$. Let $\mathcal{C}$ be the family of
those sets in $\mathcal{F}$ which only contain elements of $[n]\setminus X\setminus A$.

Let $\tilde{A}=\bigl\{ e\in A:(\exists B\in\mathcal{\mathcal{\mathcal{B}}}:e\in B)\bigr\}$, and
let $\tilde{a}=\frac{\left|\tilde{A}\right|}{n}$. Let $c_{0}n!$
be the number of chains that start with $\{e\}$ as a singleton for
some $e\in\tilde{A}$, but do not contain any set from $\mathcal{\mathcal{\mathcal{B}}}$. Let
$\nu n!$ be the number of chains that start with $\{e\}$ as a singleton
for some $e\in\tilde{A}$, continue with an element of $[n]\setminus X\setminus A$
as the second element added to form the chain, yet do not contain
any set from $\mathcal{\mathcal{\mathcal{B}}}$.

\global\long\def\overline{1}{\overline{1}}
\global\long\def\underline{1}{\underline{1}}
Let $\overline{1}=\frac{n}{n-1}>1$ and $\underline{1}=\frac{(x+a)n-1}{(x+a)(n-1)}\leq1$.
These correction factors will account for the difference from the
asymptotic behavior. (They are both typically close to 1. If $x+a=0$,
let $\underline{1}=1$; it is irrelevant as it will always be multiplied by
$x+a$.)%
\begin{comment}
Unfortunately we have to be precise because we use induction. Asymptotically
$n\approx n-1,n-1\approx n-2,\ldots,\left\lfloor n/2\right\rfloor +1\approx\left\lfloor n/2\right\rfloor $.
\end{comment}
\end{nameddef}

\begin{table}
\caption{Summary of notation}
\centering{}%
\begin{tabular}{cll|l}
$X$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}|}{``Forbidden'' set (sets in $\mathcal{F}$ are disjoint from it \textendash{}
parameter of Lemma \ref{lem:ind})} & $x=\left|X\right|/n$\tabularnewline
$\mathcal{X}$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}|}{``Forbidden'' antichain (sets in $\mathcal{F}$ are unrelated to sets in
it \textendash{} parameter of Lemma \ref{lem:ind})} & $\alpha=l(\mathcal{X})$\tabularnewline
$\mu$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}}{$\#\left\{ \text{chains containing \ensuremath{\{d\}} for \ensuremath{d\in X} but no set from \ensuremath{\mathcal{X}}}\right\} /n!$} & \tabularnewline
$c$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}}{$\#\{\text{MNM chains}\}/n!$ (parameter of Lemma \ref{lem:lubell}
/ Lemma \ref{lem:ind})} & \tabularnewline
\hline 
$A$ & $\text{\ensuremath{\left\{ e\in[n]:\{e\}\in\mathcal{F}\right\} }}$ & \multirow{3}{*}{$\left.\vphantom{\mbox{\begin{tabular}{c}
 \ensuremath{\left\{  \right\} } \\
 \ensuremath{\left\{  \right\} } \\
 \ensuremath{\left\{  \right\} } 
\end{tabular}}}\right\} \left\{ \{e\}:e\in A\right\} \cup\mathcal{\mathcal{\mathcal{B}}}\cup\mathcal{C}=\mathcal{F}$} & $a=\left|A\right|/n$\tabularnewline
$\mathcal{\mathcal{\mathcal{B}}}$ & $\left\{ B\in\mathcal{F}:(\left|B\right|\geq2,A\cap B\neq\emptyset)\right\} $ &  & $\beta=l(\mathcal{\mathcal{\mathcal{B}}})$\tabularnewline
$\mathcal{C}$ & $\left\{ C\in\mathcal{F}:C\subseteq[n]\setminus X\setminus A\right\} $ &  & \tabularnewline
$\tilde{A}$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}|}{$\bigl\{ e\in A:(\exists B\in\mathcal{\mathcal{\mathcal{B}}}:e\in B)\bigr\}$} & $\tilde{a}=\bigl|\tilde{A}\bigr|/n$\tabularnewline
$\nu$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}}{$\#\bigl\{\text{chains containing }\ensuremath{\{e\}}\text{ and }\ensuremath{\{e,o\}}\text{ for }\ensuremath{e\in\tilde{A},o\in[n]\setminus X\setminus A}\text{ but no set from }\mathcal{\mathcal{\mathcal{B}}}\bigr\}/n!$} & \tabularnewline
$c_{0}$ & \multicolumn{2}{>{\raggedright}p{0.7\columnwidth}}{$\#\bigl\{\text{chains containing \ensuremath{\{e\}} for \ensuremath{e\in\tilde{A}} but no set from \ensuremath{\mathcal{\mathcal{\mathcal{B}}}}}\bigr\}/n!$} & \tabularnewline
\end{tabular}
\end{table}

\emph{Outline of the proof:} In Subsection \ref{subsec:On-the-structure},
we make some observations on the structure of $\mathcal{X}$ and $\mathcal{\mathcal{\mathcal{B}}}$. In
Subsection \ref{subsec:Induction}, we will finish the proof by applying
induction to the Boolean lattices $\bigl[\{o_{i}\},[n]\bigr]$ where
$o_{i}\in[n]\setminus X\setminus A$. When applying Lemma \ref{lem:ind}
by induction, we will use $X\cup A$ in the place of $X$, while sets
from $\mathcal{X}$ and $\mathcal{\mathcal{\mathcal{B}}}$ will contribute to the family we use in the place
of $\mathcal{X}$ (which we will denote by $\mathcal{X}'_{i}$). We know little about
the parameters of each $\mathcal{X}'_{i}$, but we will be able to bound their
sums. The relevant calculations are done in Subsection \ref{subsec:Chain-calculations}.

\subsection{\label{subsec:On-the-structure}On the structure of $\protect\mathcal{X}$
and $\protect\mathcal{\mathcal{\mathcal{B}}}$}
\begin{prop}
\label{prop:Xform}Every $D\in\mathcal{X}$ is of the form $\{d,o_{1},\ldots,o_{k}\}$
with $d\in X,o_{1},\ldots,o_{k}\in[n]\setminus X\setminus A$ (where
$k$ may be 0).
\end{prop}

\begin{proof}
$D$ contains exactly one element of $X$ by definition. Let $e\in A$;
then $e\notin D$ for otherwise $D$ and $\{e\}\in\mathcal{F}$ would be related.
\end{proof}
\begin{prop}
\label{prop:Bform}Sets in $\mathcal{\mathcal{\mathcal{B}}}$ only contain one element of $A$.
$\mathcal{\mathcal{\mathcal{B}}}$ is an antichain, and the sets in $\mathcal{\mathcal{\mathcal{B}}}$ are also unrelated to
every set in $\mathcal{C}$.
\end{prop}

\begin{proof}
If $e_{1}\in B\in\mathcal{\mathcal{\mathcal{B}}}$ with $e_{1}\in A$, and B was related to another
set $S\in\mathcal{F}$, then $\{e_{1}\}$, $B$ and $S$ would form a $\Lambda$.
This applies to any $S\in\mathcal{\mathcal{\mathcal{B}}}\cup\mathcal{C}$, as well as $S=\{e_{2}\}$ for
any $e_{1}\neq e_{2}\in A$.
\end{proof}
\begin{prop}
\label{prop:cbound}$\tilde{a}(x+a)\underline{1}\leq\tilde{a}(x+a)\underline{1}+\nu=c_{0}\leq c$,
and thus $\tilde{a}\leq\frac{c}{(x+a)\underline{1}}$.
\end{prop}

\begin{proof}
Any chain on which the singleton is $\{e\}$ and the second set is
$\{e,d\}$ with $e\in\tilde{A}$ and $d\in X\cup A$ is always an
MNM chain: $\{e,d\}$ and any set that contains it is forbidden from
being in $\mathcal{\mathcal{\mathcal{B}}}$ either because it is not disjoint from $X$ (when $d\in X$),
or because it would contain two elements of $A$ (when $d\in A$).
The number of such chains is $\tilde{a}n\cdot(an+xn-1)\cdot(n-2)!=\tilde{a}(x+a)n!\underline{1}$.
And out of the chains which start with $\{e\}$, and whose second
set is $\{e,o\}$ with some $o\in[n]\setminus X\setminus A$, $\nu n!$
do not contain any set from $\mathcal{\mathcal{\mathcal{B}}}$.

We have $c_{0}\leq c$ because a chain whose first set is $\{e\}$
for some $e\in\tilde{A}$, but does not contain any set from $\mathcal{\mathcal{\mathcal{B}}}$,
is an MNM chain.
\end{proof}
For a family of sets $\mathcal{A}\subseteq2^{[n]}$, let $m(\mathcal{A})n!$ be the
number of chains which start with an element of $X$ as a singleton
and do not contain any set from $\mathcal{A}$. (For example, $m(\mathcal{X})=\mu$,
and therefore $l(\mathcal{X})-m(\mathcal{X})=\alpha-\mu.)$ For a fixed $d\in X$, let
$m_{d}(\mathcal{A})n!$ be the number of chains on which the singleton is $\{d\}$,
and do not contain any element of $\mathcal{A}$.
\begin{prop}
\label{prop:uniform}For any $d\in X$, let $\mathcal{X}_{d}=\{D\in\mathcal{X}:d\in D\}$.
We can assume without loss of generality that for any $d_{1},d_{2}\in X$,
$\left\{ D\setminus\left\{ d_{1}\right\} :D\in\mathcal{X}_{d_{1}}\right\} =\left\{ D\setminus\left\{ d_{2}\right\} :D\in\mathcal{X}_{d_{2}}\right\} $.
That is, if $\mathcal{X}$ does not satisfy this condition, we show a family
$\hat{\mathcal{X}}$ which does, and also satisfies the conditions of Lemma
\ref{lem:ind}'s statement (each set contains exactly one element
of $X$, the sets are unrelated to each other and to every set in
$\mathcal{F}$), and for which $f\!\left(x,c+m(\hat{\mathcal{X}})+\frac{1}{n'}\right)-\bigl(l(\hat{\mathcal{X}})-m(\hat{\mathcal{X}})-x\bigr)\leq f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x)$.
\end{prop}

\begin{proof}
Let $d_{0}\in X$ be such that 
\begin{gather*}
f\!\left(x,c+\left|X\right|m_{d_{0}}\!\left(\mathcal{X}_{d_{0}}\right)+\frac{1}{n'}\right)-\bigl(\left|X\right|l\!\left(\mathcal{X}_{d_{0}}\right)-\left|X\right|m_{d_{0}}\!\left(\mathcal{X}_{d_{0}}\right)-x\bigr)\\
=\min_{d\in X}\!\left[f\!\left(x,c+\left|X\right|m_{d}\!\left(\mathcal{X}_{d}\right)+\frac{1}{n'}\right)-\bigl(\left|X\right|l\!\left(\mathcal{X}_{d}\right)-\left|X\right|m_{d}\!\left(\mathcal{X}_{d}\right)-x\bigr)\right].
\end{gather*}
 Let $\hat{\mathcal{X}}=\bigl\{ D\setminus\{d_{0}\}\cup\{d\}:d\in X,D\in\mathcal{X}_{d_{0}}\bigr\}$.

$\mathcal{X}=\bigsqcup_{d\in X}\mathcal{X}_{d}$, so $\alpha=\sum_{d\in X}l(\mathcal{X}_{d})$.
It immediately follows from the definition of $\mathcal{X}_{d}$ that if a
chain has $\{d\}$ as a singleton, and does not contain any set from
$\mathcal{X}_{d}$, then it does not contain any set from $\mathcal{X}$. So $\mu=\sum_{d\in X}m_{d}(\mathcal{X}_{d})$.
Similarly, $l(\hat{\mathcal{X}})=\left|X\right|l\!\left(\mathcal{X}_{d_{0}}\right)$
and $m(\hat{\mathcal{X}})=\left|X\right|m_{d_{0}}\!\left(\mathcal{X}_{d_{0}}\right)$.
Since $f(x,c)$ is monotonously increasing and concave in $c$, using
Jensen's inequality 
\begin{gather*}
f\!\left(x,c+\left|X\right|m_{d_{0}}\!\left(\mathcal{X}_{d_{0}}\right)+\frac{1}{n'}\right)-\bigl(\left|X\right|l\!\left(\mathcal{X}_{d_{0}}\right)-\left|X\right|m_{d_{0}}\!\left(\mathcal{X}_{d_{0}}\right)-x\bigr)\\
\leq\frac{1}{\left|X\right|}\left[\sum_{d\in X}f\!\left(x,c+\left|X\right|m_{d}\!\left(\mathcal{X}_{d}\right)+\frac{1}{n'}\right)-\bigl(\left|X\right|\sum_{d\in X}l\!\left(\mathcal{X}_{d}\right)-\left|X\right|\sum_{d\in X}m_{d}\!\left(\mathcal{X}_{d}\right)-\left|X\right|x\bigr)\right]\\
\leq f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x).
\end{gather*}

Sets in $\hat{\mathcal{X}}$ contain exactly one element of $X$, and form
an antichain. They are also unrelated to every set $S\in\mathcal{F}$: $S$
cannot contain any element of $X$, so it could only be related to
a set in $\hat{\mathcal{X}}$ by being its subset. But $S$ must also be unrelated
to every $D\in\mathcal{X}_{d_{0}}\subseteq\mathcal{X}$, so it cannot be a subset of
$D\setminus\{d_{0}\}\cup\{d\}$ either.
\end{proof}
In fact we will only use the following simple corollary of Proposition
\ref{prop:uniform}. In many parts of the rest of this section we
will treat the two cases of the corollary below separately.
\begin{cor}
With the assumption of Proposition \ref{prop:uniform},

\begin{itemize}
\item either $\mathcal{X}=\bigl\{\{d\}:d\in X\bigr\}$ (we refer to it as the \textbf{singletons
case}),
\item or $\mathcal{X}$ does not contain any singleton (referred to as the \textbf{no
singleton case}).
\end{itemize}
\end{cor}

\begin{proof}
Let $d_{1}\in X$. (If $X=\emptyset$, both statements trivially hold.)
If $\{d_{1}\}\in\mathcal{X}_{d_{1}}=\{D\in\mathcal{X}:d_{1}\in D\}$, then $\mathcal{X}_{d_{1}}=\left\{ \{d_{1}\}\right\} $,
because sets in $\mathcal{X}_{d_{1}}$ are unrelated. So either $\mathcal{X}_{d_{1}}=\left\{ \{d_{1}\}\right\} $
or $\mathcal{X}_{d_{1}}$ does not contain any singleton, yielding the two
cases above by Proposition \ref{prop:uniform}.
\end{proof}
\begin{rem*}
The fact that sets in $\mathcal{X}$ contain an element of $X$ implies that
sets in $\mathcal{F}$ do not contain sets in $\mathcal{X}$. Now, let us consider what
restrictions are imposed on $\mathcal{F}$ by the fact that sets in $\mathcal{F}$ are
not contained in the sets in $\mathcal{X}$, beyond the other conditions of
Lemma \ref{lem:ind} (namely that all the sets in $\mathcal{F}$ are disjoint
from $X$).

In the singletons case, clearly there are no such additional restrictions.
However, in the no singleton case, there are two additional restrictions
that are not already implied by the set $X$:

\begin{itemize}
\item The union of singletons in $\mathcal{F}$, $A\subseteq[n]\setminus\bigcup\mathcal{X}$.
\item Sets in $\mathcal{C}$ must not be contained in sets in $\mathcal{X}$. Clearly this
imposes a restriction only if $\mathcal{X}$ contains sets bigger than 2.
\end{itemize}
\end{rem*}
\begin{example}
\label{exa:nosingleton}Let $C\subseteq[n]\setminus X$, and let $\mathcal{X}=\bigl\{\{d,o\}:d\in X,o\in C\bigr\}$.
Then $\alpha=l(\mathcal{X})=\frac{2\cdot xn\cdot\left|C\right|\cdot(n-2)!}{n!}=2x\frac{\left|C\right|}{n}\overline{1}$,
and $\mu=\frac{xn\cdot(xn+an-1)\cdot(n-2)!}{n!}=x(x+a)\underline{1}$. The
only restriction on $\mathcal{F}$ that this $\mathcal{X}$ creates is that the union
of singletons $A\subseteq[n]\setminus X\setminus C$.

In other words, let us assume that $\alpha=l(\mathcal{X})=2x\gamma\overline{1}$ for
$\gamma\in\mathbf{R}$ (without assuming that $\mathcal{X}$ is of the above form).
Then it is possible that $a=\frac{\left|A\right|}{n}$ can be as big
as $1-x-\gamma$ with $\mathcal{X}$ not creating any restrictions on $\mathcal{C}$
(depending on the actual structure of $\mathcal{X}$, namely, if it is made
up of sets of size $2$ as above; then $\alpha=2x(1-x-a)\overline{1}$ and
$\mu=x(x+a)\underline{1}$). But if $a>1-x-\gamma$, then $\alpha=2x\gamma\overline{1}$
implies that $\mathcal{X}$ contains sets bigger than 2, and thus it creates
restrictions on $\mathcal{C}$. So, in the no singleton case, one way to understand
the calculations that follow is to check them for $\mathcal{X}=\bigl\{\{d,o\}:d\in X,o\in C\bigr\}$;
then check what happens if $x$, $c$ and $a$ are fixed, but $\mathcal{X}$
is changed.
\end{example}


\subsection{\label{subsec:Chain-calculations}Chain calculations}

Now we estimate the numbers of certain types of chains, in preparation
for applying induction.
\begin{prop}
\label{prop:Xchainbound}In the no singleton case, $\left(\alpha-x+\mu\right)n!$
chains start with $\{o\}$ for some $o\in[n]\setminus X\setminus A$,
and contain a set from $\mathcal{X}$.
\end{prop}

\begin{proof}
A total of $\alpha n!$ chains contain a set $D\in\mathcal{X}$. By Proposition
\ref{prop:Xform}, the singleton on such a chain is either from $X$
or $[n]\setminus X\setminus A$. The number of chains which start
with an element of $X$ as their singleton and do not contain a set
from $\mathcal{X}$ is $\mu n!$, so the number of chains which contain a set
from $\mathcal{X}$, and which start with an element of $X$, is $(x-\mu)n!$.
On the rest, the singleton is from $[n]\setminus X\setminus A$.
\end{proof}
\begin{prop}
\label{prop:Bchainbound}$\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)n!$
chains start with $\{o\}$ for some $o\in[n]\setminus X\setminus A$,
and contain a set from $\mathcal{\mathcal{\mathcal{B}}}$.
\end{prop}

\begin{proof}
A total of $\beta n!$ chains contain a set from $\mathcal{\mathcal{\mathcal{B}}}$. A set in $\mathcal{\mathcal{\mathcal{B}}}$
is of the form $\{e,o_{1},\ldots,o_{k}\}$ with $e\in\tilde{A},o_{1},\ldots,o_{k}\in[n]\setminus X\setminus A,k\geq1$.
A chain that contains a $B\in\mathcal{\mathcal{\mathcal{B}}}$, and does not start with $\{o\}$
for some $o\in[n]\setminus X\setminus A$, must start with an element
of $\tilde{A}$, and continue with an element of $[n]\setminus X\setminus A$
as the second element added to form the chain. There are $\tilde{a}n\cdot(1-x-a)n\cdot(n-2)!=\tilde{a}(1-x-a)\overline{1} n!$
such chains, out of which $\nu n!$ do not contain any set from $\mathcal{\mathcal{\mathcal{B}}}$.
So $\left(\tilde{a}(1-x-a)\overline{1}-\nu\right)n!$ chains contain a set
from $\mathcal{\mathcal{\mathcal{B}}}$ and start with an element of $\tilde{A}$. The rest start
with $\{o\}$ for some $o\in[n]\setminus X\setminus A$.
\end{proof}
\begin{prop}
\label{prop:mubound}In the no singleton case, $\mu\geq x(x+a)\underline{1}$;
and the number of chains of the form $\emptyset,\{d\},\{d,o\},\ldots$
with $d\in X,o\in[n]\setminus X\setminus A$, which do not contain
any set from $\mathcal{X}$, is $\bigl(\mu-x(x+a)\underline{1}\bigr)n!$.
\end{prop}

\begin{proof}
A total of $\mu n!$ chains start with an element of $X$ and do not
contain any set from $\mathcal{X}$. The chains of the form $\emptyset,\{d_{1}\},\{d_{1},d_{2}\},\ldots$
with $d_{1}\in X,d_{2}\in X\cup A$ never contain a set from $\mathcal{X}$
when $\mathcal{X}$ contains no singleton. The number of these chains is $xn\cdot(xn+an-1)\cdot(n-2)!=\bigl(x(x+a)\underline{1}\bigr)n!$.
For the rest, the second element added to form the chain is from $[n]\setminus X\setminus A$.
\end{proof}
\begin{nameddef}[Notation]
Let $X'=X\cup A$. Let $\mathcal{Y}=\bigl\{\{d,o\}:d\in X,o\in[n]\setminus X\setminus A\bigr\}$,
and let $\mathcal{Z}=\bigl\{\{e,o\}:e\in A\setminus\tilde{A},o\in[n]\setminus X\setminus A\bigr\}\bigr\}$.
In the \emph{singletons case}, let $\mathcal{X}'=\mathcal{Y}\sqcup\mathcal{\mathcal{\mathcal{B}}}\sqcup\mathcal{Z}$. (Note
that here and in the rest of the paper, $\sqcup$ stands for a union
of sets which are pairwise disjoint.) In the \emph{no singleton case},
let $\mathcal{X}'=\mathcal{X}\sqcup\mathcal{\mathcal{\mathcal{B}}}\sqcup\mathcal{Z}$.
\end{nameddef}

\begin{prop}
The three families which make up $\mathcal{X}'$ are indeed disjoint in each
case, and their union forms an antichain.
\end{prop}

\begin{proof}
$\mathcal{\mathcal{\mathcal{B}}}$ is an antichain by Proposition \ref{prop:Bform}; $\mathcal{X}$ is an
antichain by definition; and $\mathcal{Y}$ and $\mathcal{Z}$ are antichains because
both consist of size 2 sets only. Let $D=\{d,o_{1},\ldots,o_{k}\}\in\mathcal{X}$,
$Y=\{d,o\}\in\mathcal{Y}$, $B=\{e_{1},p_{1},\ldots,p_{l}\}\in\mathcal{\mathcal{\mathcal{B}}}$ and $Z=\{e_{2},q\}\in\mathcal{Z}$
with $d\in X$, $e_{1}\in\tilde{A}$, $e_{2}\in A\setminus\tilde{A}$,
$o_{i},o,p_{i},q\in[n]\setminus X\setminus A$, and $l\geq1$. $B$
is unrelated to $D$ by definition, and to $Y$ because $d\notin B$
and $\left|B\right|\geq2$. $Z$ is unrelated to $D$ and $Y$ because
$d\notin Z$ and $e_{2}\notin D,Y$; $Z$ is unrelated to $B$ because
$e_{1}\notin Z$ and $e_{2}\notin B$.
\end{proof}
\begin{prop}
\label{prop:indcondition}Sets in $\mathcal{C}$ are disjoint from $X'$, and
they are unrelated to every set in $\mathcal{X}'$ (in both cases).
\end{prop}

\begin{proof}
For every $C\in\mathcal{C}$, $C\subseteq[n]\setminus X'$ and it is unrelated
to every set in $\mathcal{X}$ by definition. $C$ is unrelated to every set
in $\mathcal{\mathcal{\mathcal{B}}}$ by Proposition \ref{prop:Bform}. It also cannot be a superset
of a $Y\in\mathcal{Y}$ or a $Z\in\mathcal{Z}$, since those contain an element of $X$
or $A$; neither a proper subset of $Y$ or $Z$ because $\left|Y\right|=\left|Z\right|=2\leq\left|C\right|$.
\end{proof}
\begin{prop}
\label{prop:indchainbound}The number of chains that start with an
element of $[n]\setminus X'$ and contain a set from $\mathcal{X}'$ is

\begin{itemize}
\item at least $\left[x(1-x-a)\overline{1}+\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)+(1-x-a)\left(a-\tilde{a}\right)\overline{1}\right]n!$
in the \emph{singletons case}, and
\item at least $\left[\left(\alpha-x+\mu\right)+\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)+(1-x-a)\left(a-\tilde{a}\right)\overline{1}\right]n!$
in the \emph{no singleton case}.
\end{itemize}
\end{prop}

\begin{proof}
The number of chains on which the singleton is $\{o\}$ with $o\in[n]\setminus X'=[n]\setminus X\setminus A$,
and the second set is $\{o,d\}\in\mathcal{Y}$ with $d\in X$, is $xn\cdot(1-x-a)n\cdot(n-2)!=x(1-x-a)\overline{1} n!$.
The number of chains on which the singleton is $\{o\}$, and the second
set is $\{o,e\}\in\mathcal{Z}$ with $e\in A\setminus\tilde{A}$, is $(1-x-a)n\cdot(a-\tilde{a})n\cdot(n-2)!=(1-x-a)\left(a-\tilde{a}\right)\overline{1} n!$.
The rest follows from Proposition \ref{prop:Xchainbound} and Proposition
\ref{prop:Bchainbound}.
\end{proof}
\begin{prop}
\label{prop:indmubound}The number of chains on which the singleton
is $\{o\}$ with $o\in[n]\setminus X'$, the second set is $\{o,d\}$
with $d\in X'=X\cup A$, and which do not contain any set from $\mathcal{X}'$,
is

\begin{itemize}
\item $\nu n!$ in the \emph{singletons case}, and
\item $\bigl(\mu-x(x+a)\underline{1}+\nu\bigr)n!$ in the \emph{no singleton case}.
\end{itemize}
\end{prop}

\begin{proof}
Let $\mathcal{A}=\emptyset,A_{1},A_{2},\ldots,A_{n-1},[n]$ be a chain with
$\emptyset\subset A_{1}\subset A_{2}\subset\ldots\subset A_{n-1}\subset[n]$.
Let $\varphi(\mathcal{A})$ be the chain $\emptyset,A_{2}\setminus A_{1},A_{2},A_{3},\ldots,A_{n-1},[n]$.
(In other words, in the order in which elements of $[n]$ are added
to form the chain, the first two are swapped.) $\varphi$ is a bijection.

It is easy to check that $\mathcal{X}'$ does not contain singletons. $\varphi$
is a bijection between chains of the form $\emptyset,\{o\},\{o,d\},\ldots$
containing no set from $\mathcal{X}'$, and chains of the form $\emptyset,\{d\},\{o,d\},\ldots$
containing no set from $\mathcal{X}'$, with $o\in[n]\setminus X'$ and $d\in X\cup A$.
Below we classify the chains $\emptyset,\{d\},\{o,d\},\ldots$ based
on what set $d$ belongs to and count them separately.

\begin{itemize}
\item For $d\in X$, $\{o,d\}\in\mathcal{Y}$ in the singletons case. In the no singleton
case, $\bigl(\mu-x(x+a)\underline{1}\bigr)n!$ chains of the form $\emptyset,\{d\},\{o,d\},\ldots$
contain no set from $\mathcal{X}$ by Proposition \ref{prop:mubound}; these
chains also contain no set from $\mathcal{\mathcal{\mathcal{B}}}$ or $\mathcal{Z}$, since sets from those
do not contain any element of $X$.
\item For $d\in\tilde{A}$, the number of chains of this form which contain
no set from $\mathcal{\mathcal{\mathcal{B}}}$ is $\nu n!$; these chains also contain no set from
$\mathcal{X},\mathcal{Y}$ or $\mathcal{Z}$, since sets from those contain no element of $\tilde{A}$.
\item For $d\in A\setminus\tilde{A}$, $\{o,d\}\in\mathcal{Z}$.
\end{itemize}
Summing these cases, we get the statement of the proposition.
\end{proof}

\subsection{\label{subsec:Induction}Inductive step}
\begin{nameddef}[Notation]
Using standard notation for intervals, let $\left[A,[n]\right]$
denote the Boolean lattice $\left\{ S\subseteq[n]:A\subseteq S\right\} $.
Let $[n]\setminus X'=[n]\setminus X\setminus A=\{o_{1},o_{2},\ldots,o_{(1-x-a)n}\}$;
and for a family of sets $\mathcal{A}$, let $\mathcal{A}-o_{i}=\left\{ S\setminus\{o_{i}\}:S\in\mathcal{A}\right\} $.
Let $\mathcal{C}'_{i}=\left(\mathcal{C}\cap\bigl[\{o_{i}\},[n]\bigr]\right)-o_{i}$,
and $\mathcal{X}'_{i}=\left(\mathcal{X}'\cap\bigl[\{o_{i}\},[n]\bigr]\right)-o_{i}$.
Let $\alpha'_{i}=l(n-1,\mathcal{X}'_{i})$. (Here the Lubell function on the
Boolean lattice $2^{[n]\setminus\{o_{i}\}}$ of order $n-1$ is used.)
\end{nameddef}

$\mathcal{C}'_{i}\subseteq2^{[n]\setminus\{o_{i}\}}$ is a $\Lambda$-free
family which does not contain $\emptyset$ (since $o_{i}\notin A$,
so $\{o_{i}\}\notin\mathcal{F}$), nor any set larger than $n-1-n'$. Sets
in $\mathcal{C}'_{i}$ are disjoint from $X'$, and are unrelated to sets in
$\mathcal{X}'_{i}$ by Proposition \ref{prop:indcondition}. Moreover, every
set in $\mathcal{X}'_{i}$ contains exactly one element of $X'$. Therefore,
the conditions of Lemma \ref{lem:ind} are satisfied for the family
$\mathcal{C}'_{i}\subseteq2^{[n]\setminus\{o_{i}\}}$ where the corresponding
``forbidden'' set is $X'\subseteq[n]\setminus\{o_{i}\}$, with $\frac{\left|X'\right|}{n-1}=(x+a)\overline{1}$
and the corresponding ``forbidden'' antichain is $\mathcal{X}'_{i}$.

Since $\mathcal{X}'_{i}$ is an antichain, $\alpha'_{i}(n-1)!$ is the number
of chains in $2^{[n]\setminus\{o_{i}\}}$ that contain a set from
$\mathcal{X}'_{i}$. Chains of $2^{[n]\setminus\{o_{i}\}}$ correspond to chains
of $2^{[n]}$ that start with $\{o_{i}\}$. So by Proposition \ref{prop:indchainbound},
in the \emph{singletons case} 
\[
\sum_{i=1}^{(1-x-a)n}\alpha'_{i}\geq\left[x(1-x-a)\overline{1}+\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)+(1-x-a)\left(a-\tilde{a}\right)\overline{1}\right]n,
\]
 and in the \emph{no singleton case} 
\[
\sum_{i=1}^{(1-x-a)n}\alpha'_{i}\geq\left[\left(\alpha-x+\mu\right)+\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)+(1-x-a)\left(a-\tilde{a}\right)\overline{1}\right]n.
\]

Let $\mu'_{i}(n-1)!$ be the number of chains in the Boolean lattice
$2^{[n]\setminus\{o_{i}\}}$ which start with an element of $X'$
as a singleton, but do not contain any set from $\mathcal{X}'_{i}$. By Proposition
\ref{prop:indmubound}, in the \emph{singletons case }
\[
\sum_{i=1}^{(1-x-a)n}\mu'_{i}=\nu n,
\]
 and in the \emph{no singleton case} 
\[
\sum_{i=1}^{(1-x-a)n}\mu'_{i}=\bigl(\mu-x(x+a)\underline{1}+\nu\bigr)n.
\]

Let $c'_{i}(n-1)!$ be the number of MNM chains w.r.t.\ $\mathcal{C}'_{i}$
in $2^{[n]\setminus\{o_{i}\}}$. The corresponding $2^{[n]}$-chains,
starting with $\{o_{i}\}$, are MNM chains w.r.t.\ $\mathcal{F}$. The total
number of MNM chains w.r.t.\ $\mathcal{F}$ is $cn!$, out of which $c_{0}n!$
start with an element of $A$ as a singleton. By Proposition \ref{prop:cbound},
\[
\sum_{i=1}^{(1-x-a)n}c'_{i}=(c-c_{0})n=\left(c-\tilde{a}(x+a)\underline{1}-\nu\right)n.
\]

The following two examples are typical cases where, in the induction
step for the $\mathcal{C}'_{i}$'s, we will get the singletons case and the
no singleton case respectively.
\begin{example}
Let $X=\mathcal{X}=\emptyset$ and $\mathcal{\mathcal{\mathcal{B}}}=\bigl\{\{e,o\}:e\in A,o\in[n]\setminus A\bigr\}$.
Then $\tilde{A}=A$, $\beta=2a(1-a)\overline{1}$, and $\nu=0$. $X'=A$,
and $\mathcal{X}'_{i}=\bigl\{\{e\}:e\in A\bigr\}$. $\sum_{i=1}^{(1-a)n}\alpha'_{i}=a(1-a)\overline{1} n$,
$\alpha'_{i}=a\overline{1}=\frac{\left|X'\right|}{n-1}$ and $\mu'_{i}=0$.
$\sum_{i=1}^{(1-x-a)n}c'_{i}=\left(c-a^{2}\right)n$ and the average
of the $c'_{i}$'s is $\frac{c-a^{2}}{1-a}$.
\end{example}

\begin{example}
Let $X=\mathcal{X}=\emptyset$ and $\mathcal{\mathcal{\mathcal{B}}}\subseteq\hat{\mathcal{\mathcal{\mathcal{B}}}}:=\bigl\{\{e,o_{1},o_{2}\}:e\in A,o_{1},o_{2}\in[n]\setminus A\bigr\}$.
Then $X'=A$, and $\mathcal{X}'_{i}\subseteq\bigl\{\{e,o\}:e\in A,o\in[n]\setminus A\setminus\{o_{i}\}\bigr\}$.
Chains on $2^{[n]}$ of the form $\emptyset,\{e_{1}\},\{e_{1},o\},\{e_{1},o,e_{2}\},\ldots$
do not intersect $\mathcal{\mathcal{\mathcal{B}}}$. So $\sum_{i=1}^{(1-a)n}\mu'_{i}=\nu\geq a^{2}(1-a)\overline{1}^{2}\frac{\overline{1} a(n-1)-1}{\overline{1} a(n-2)}n$
(greater if $\mathcal{\mathcal{\mathcal{B}}}\subsetneqq\hat{\mathcal{\mathcal{\mathcal{B}}}}$), and the average of the $\mu'_{i}$'s
is $\geq a^{2}\overline{1}^{2}\frac{\overline{1} a(n-1)-1}{\overline{1} a(n-2)}={x'}^{2}\frac{x'(n-1)-1}{x'((n-1)-1)}$
where $x'=\frac{\left|X'\right|}{n-1}$. In the case of $\mathcal{\mathcal{\mathcal{B}}}=\hat{\mathcal{\mathcal{\mathcal{B}}}}$,
the size of the sets in $\mathcal{C}$ is at least 3, and the size of those
in $\mathcal{C}'_{i}$ is at least 2.

\begin{comment}
TODO: EXPAND ON EXAMPLES? Yea, maybe expand or remove them althogether...
\end{comment}
\end{example}

\begin{prop}
\label{prop:lubell_induction}
\[
l(\mathcal{C})=\frac{1}{n}\sum_{i=1}^{(1-x-a)n}l(n-1,\mathcal{C}'_{i})\quad\textnormal{and}\quad l(\mathcal{F})=a+\beta+l(\mathcal{C})=a+\beta+\frac{1}{n}\sum_{i=1}^{(1-x-a)n}l(n-1,\mathcal{C}'_{i}).
\]
 (Still understanding the one parameter version $l(\mathcal{F})$ as $l(n,\mathcal{F})$
for a family $\mathcal{F}\subseteq2^{[n]}$.)
\end{prop}

\begin{proof}
Every chain in the Boolean lattice $2^{[n]}$ that intersects $\mathcal{C}$
has an $\{o_{i}\}$ as a singleton, and thus corresponds to a chain
in the Boolean lattice $\left[\{o_{i}\},[n]\right]-o_{i}$ that intersects
$\mathcal{C}'_{i}$. 
\[
l(\mathcal{C})=\frac{1}{n!}\sum_{\mathcal{H}\text{ is a chain in }2^{[n]}}\left|\mathcal{H}\cap\mathcal{C}\right|=\frac{1}{n!}\sum_{i=1}^{(1-x-a)n}\sum_{\mathcal{H}\text{ is a chain in }\left[\{o_{i}\},[n]\right]-o_{i}}\left|\mathcal{H}\cap\mathcal{C}'_{i}\right|=\frac{1}{n}\sum_{i=1}^{(1-x-a)n}l(n-1,\mathcal{C}'_{i}).
\]

Let $\mathcal{A}=\bigl\{\{e\}:e\in A\bigr\}$. Then $\mathcal{F}=\mathcal{A}\sqcup\mathcal{\mathcal{\mathcal{B}}}\sqcup\mathcal{C}$.
So $l(\mathcal{F})=l(\mathcal{A})+l(\mathcal{\mathcal{\mathcal{B}}})+l(\mathcal{C})$ with $l(\mathcal{A})=\frac{\left|A\right|}{n}=a$
and $l(\mathcal{\mathcal{\mathcal{B}}})=\beta$.
\end{proof}
We now prove Lemma \ref{lem:ind} (and thus Lemma \ref{lem:lubell})
using induction on $n$. According to Proposition \ref{prop:indbase},
Lemma \ref{lem:ind} holds for $n\leq n'$. By induction and Lemma
\ref{lem:functions} Point \ref{enu:concave}, 
\begin{align*}
l(n-1,\mathcal{C}'_{i}) & \leq f\!\left((x+a)\overline{1},c'_{i}+\mu'_{i}+\frac{1}{n'}\right)-\left(\alpha'_{i}-\mu'_{i}-(x+a)\overline{1}\right)+\frac{3}{n'}\\
 & \leq f\!\left(x+a,c'_{i}+\mu'_{i}+\frac{1}{n'}\right)-\left(\alpha'_{i}-\mu'_{i}-(x+a)\overline{1}\right)+\frac{3}{n'}.
\end{align*}
So, by Proposition \ref{prop:lubell_induction}, we have
\begin{align*}
l(\mathcal{C}) & =\frac{1}{n}\sum_{i=1}^{(1-x-a)n}l(n-1,\mathcal{C}'_{i})\leq\frac{1}{n}\sum_{i=1}^{(1-x-a)n}f\!\left(x+a,c'_{i}+\mu'_{i}+\frac{1}{n'}\right)\\
 & {}-\frac{1}{n}\left(\sum_{i=1}^{(1-x-a)n}\alpha'_{i}-\sum_{i=1}^{(1-x-a)n}\mu'_{i}-\sum_{i=1}^{(1-x-a)n}(x+a)\overline{1}\right)+\frac{1}{n}\cdot\frac{3(1-x-a)n}{n'}.
\end{align*}

We handle the case of $1-x-a=0$ separately. If $1-x-a=0$, $A=[n]\setminus X$
and, since any non-singleton $\{e_{1},e_{2},\ldots\}\in\mathcal{F}$ would
form a $\Lambda$ with the singletons $\{e_{1}\},\{e_{2}\}\in\mathcal{F}$,
we have $\mathcal{F}=\mathcal{A}$ and $l(\mathcal{F})=a=1-x$. This is only possible in the
singletons case, since a non-singleton in $\mathcal{X}$ would have to contain
elements of $[n]\setminus X\setminus A$. In the singletons case $\alpha=x$
and $\mu=0$, so $l(\mathcal{F})=1-x\leq f(x,c)\leq f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x)+\frac{3}{n'}$
by Lemma \ref{lem:functions} Point \ref{enu:1-x}. From now on, we
assume that $1-x-a>0$.

Since $f$ is concave in $c$, by Jensen's inequality, and since $f$
is monotonously decreasing in $x$, 
\begin{align*}
l(\mathcal{C}) & \leq(1-x-a)f\!\left(x+a,\frac{\sum_{i=1}^{(1-x-a)n}c'_{i}+\sum_{i=1}^{(1-x-a)n}\mu'_{i}}{(1-x-a)n}+\frac{1}{n'}\right)\\
 & {}-\left(\frac{1}{n}\sum_{i=1}^{(1-x-a)n}\alpha'_{i}-\frac{1}{n}\sum_{i=1}^{(1-x-a)n}\mu'_{i}-(1-x-a)(x+a)\overline{1}\right)+\frac{3(1-x-a)}{n'}.
\end{align*}

\emph{Correction term calculations} that we will use later (assuming
$n'\leq n-1$):\emph{ }
\begin{equation}
\begin{gathered}(1-\underline{1})(x+\tilde{a})(x+a)+\frac{1-x-a}{n'}=\frac{(x+\tilde{a})(1-x-a)}{n-1}+\frac{1-x-a}{n'}\\
\leq\frac{(1+x+\tilde{a})(1-x-a)}{n'}\leq\frac{1-(x+a)^{2}}{n'}\leq\frac{1}{n'}.
\end{gathered}
\label{eq:correction_nosing_c}
\end{equation}
\emph{
\begin{equation}
(1-\underline{1})\tilde{a}(x+a)+\frac{1-x-a}{n'}\leq(1-\underline{1})(x+\tilde{a})(x+a)+\frac{1-x-a}{n'}\leq\frac{1}{n'}.\label{eq:correction_singletons_c}
\end{equation}
\begin{equation}
\begin{gathered}2\tilde{a}(1-x-a)(\overline{1}-1)+2(\overline{1}-1)x-\left(2(\overline{1}-1)+(\underline{1}-1)\right)x(x+a)+\frac{3(1-x-a)}{n'}\\
\leq\frac{2a+3x}{n-1}+\frac{3(1-x-a)}{n'}\leq\frac{3}{n'}.
\end{gathered}
\label{eq:correction_nosing}
\end{equation}
\begin{equation}
2\tilde{a}(1-x-a)(\overline{1}-1)+\frac{3(1-x-a)}{n'}\leq\frac{2a}{n-1}+\frac{3(1-x-a)}{n'}\leq\frac{3}{n'}.\label{eq:correction_singletons}
\end{equation}
}

\emph{In the singletons case:} 
\begin{align*}
l(\mathcal{F}) & \leq a+\beta+(1-x-a)f\!\left(x+a,\frac{\left(c-\tilde{a}(x+a)\underline{1}-\nu\right)+\nu}{1-x-a}+\frac{1}{n'}\right)\\
 & {}-\Bigl(\left[x(1-x-a)\overline{1}+\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)+(1-x-a)\left(a-\tilde{a}\right)\overline{1}\right]\\
 & {}-\nu-(1-x-a)(x+a)\overline{1}\Bigr)+\frac{3(1-x-a)}{n'}\displaybreak[0]\\
 & =a+(1-x-a)f\!\left(x+a,\frac{c-\tilde{a}(x+a)\underline{1}}{1-x-a}+\frac{1}{n'}\right)+2\tilde{a}(1-x-a)\overline{1}+\frac{3(1-x-a)}{n'}\displaybreak[0]\\
 & =a+(1-x-a)f\!\left(x+a,\frac{c-\tilde{a}(x+a)+(1-\underline{1})\tilde{a}(x+a)+\frac{1-x-a}{n'}}{1-x-a}\right)+2\tilde{a}(1-x-a)\\
 & {}+2\tilde{a}(1-x-a)(\overline{1}-1)+\frac{3(1-x-a)}{n'}.
\end{align*}
 By Lemma \ref{lem:functions} Point \ref{enu:concave}~and Point
\ref{enu:g}, and \eqref{eq:correction_singletons_c} and \eqref{eq:correction_singletons}
in the Correction term calculations (note that in this case $\alpha=x$
and $\mu=0$), 
\[
l(\mathcal{F})\leq g\!\left(x,c+\frac{1}{n'},a,\tilde{a}\right)+\frac{3}{n'}\leq f\!\left(x,c+\frac{1}{n'}\right)+\frac{3}{n'}=f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x)+\frac{3}{n'}.
\]
(Note that $\tilde{a}\leq\frac{c}{(x+a)\underline{1}}$, so $0\leq\frac{c-\tilde{a}(x+a)\underline{1}}{1-x-a}\leq\frac{c+\frac{1}{n'}-\tilde{a}(x+a)}{1-x-a}$,
and $\tilde{a}\leq\frac{c+\frac{1}{n'}}{x+a}$.)

\emph{In the no singleton case:} 
\begin{align*}
l(\mathcal{F}) & \leq a+\beta+(1-x-a)f\!\left(x+a,\frac{\left(c-\tilde{a}(x+a)\underline{1}-\nu\right)+\mu-x(x+a)\underline{1}+\nu}{1-x-a}+\frac{1}{n'}\right)\\
 & {}-\Bigl(\left[\left(\alpha-x+\mu\mathnote{here}\right)+\left(\beta-\tilde{a}(1-x-a)\overline{1}+\nu\right)+(1-x-a)\left(a-\tilde{a}\right)\overline{1}\right]\\
 & {}-\left[\mu-x(x+a)\underline{1}+\nu\right]-(1-x-a)(x+a)\overline{1}\Bigr)+\frac{3(1-x-a)}{n'}\displaybreak[0]\\
 & =a+(1-x-a)f\!\left(x+a,\frac{c+\mu-(x+\tilde{a})(x+a)\underline{1}}{1-x-a}+\frac{1}{n'}\right)-(\alpha-x(x+a)\underline{1}\mathnote{here}-x)\\
 & {}+2\tilde{a}(1-x-a)\overline{1}+(2\cdot\overline{1}-1)x-(2\cdot\overline{1}+\underline{1})x(x+a)+\frac{3(1-x-a)}{n'}\displaybreak[0]\\
 & =a+(1-x-a)f\!\left(x+a,\frac{c+\mu-(x+\tilde{a})(x+a)+(1-\underline{1})(x+\tilde{a})(x+a)+\frac{1-x-a}{n'}}{1-x-a}\right)\\
 & {}+2\tilde{a}(1-x-a)+x-3x(x+a)-(\alpha-x(x+a)\underline{1}\mathnote{here}-x)\\
 & {}+2\tilde{a}(1-x-a)(\overline{1}-1)+2(\overline{1}-1)x-\left(2(\overline{1}-1)+(\underline{1}-1)\right)x(x+a)+\frac{3(1-x-a)}{n'}.
\end{align*}
 By Lemma \ref{lem:functions} Point \ref{enu:concave}~and Point
\ref{enu:h}, Proposition \ref{prop:mubound}. and \eqref{eq:correction_nosing_c}
and \eqref{eq:correction_nosing} in the Correction term calculations,
\[
l(\mathcal{F})\leq h\!\left(x,c+\mu+\frac{1}{n'},a,\tilde{a}\right)-(\alpha-\mu-x)+\frac{3}{n'}\leq f\!\left(x,c+\mu+\frac{1}{n'}\right)-(\alpha-\mu-x)+\frac{3}{n'}.
\]
(Note that $\tilde{a}\leq\frac{c}{(x+a)\underline{1}}$, so $0\leq\frac{c-\tilde{a}(x+a)\underline{1}}{1-x-a}\leq\frac{c+\mu+\frac{1}{n'}-(x+\tilde{a})(x+a)}{1-x-a}$,
and $\tilde{a}\leq\frac{c+\mu+\frac{1}{n'}}{x+a}-x$.)

\section{Diamond-free families \textendash{} Proof of Theorem \ref{thm:main}\label{sec:diamond}}

Let $\mathcal{F}$ be a diamond-free family on $2^{[n]}$.

We cite Lemma 1 from \cite{diamond_228}:
\begin{lem}[Axenovich, Manske, Martin \cite{diamond_228}]
\[
\sum_{\substack{k\in\{0,1,\ldots,n\}\\
\left|k-n/2\right|\geq n^{2/3}
}
}\binom{n}{k}\leq2^{n-\Omega(n^{1/3})}=2^{-\Omega(n^{1/3})}\binom{n}{\left\lfloor n/2\right\rfloor }.
\]
\end{lem}

By this lemma, the number of sets in $\mathcal{F}$ in the top and bottom $n':=n/2-n^{\frac{2}{3}}$
levels is $o(1)\binom{n}{\left\lfloor n/2\right\rfloor }$, so, since
we are bounding the cardinality of $\mathcal{F}$, we may assume that those
levels do not contain any set from $\mathcal{F}$.
\begin{nameddef}[Notation]
For $c\in[0,1]$, let $\tilde{c}=\min\!\left(c,\frac{1}{4}\right)$,
and let $f(c)=1-\tilde{c}+\sqrt{\tilde{c}}$. (This is equal to $f(0,c)$
as defined in Definition \ref{def:functions}.) For $A\in\mathcal{F}$, recall
that $\left[A,[n]\right]$ denotes the Boolean lattice $\left\{ S\subseteq[n]:A\subseteq S\right\} $.
A chain of this lattice is of the form $A\subset A_{\left|A\right|+1}\subset A_{\left|A\right|+2}\subset\ldots\subset A_{n-1}\subset[n]$.
(When saying just ``chain'', we continue to mean a maximal chain
in the Boolean lattice $2^{[n]}$.) Let 
\[
c(A)=\frac{1}{\left(n-\left|A\right|\right)!}\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain in \ensuremath{\left[A,[n]\right]}}:\\
\mathcal{C}\textnormal{ is MNM w.r.t.\ }\mathcal{F}\cap\left[A,[n]\right]
\end{gathered}
\right\} .
\]
 Further, we can assume without loss of generality that 
\[
C:=\frac{1}{n!}\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain: \ensuremath{\mathcal{C}\cap\mathcal{F}=\emptyset} or }\\
\min(\mathcal{C}\cap\mathcal{F})\textnormal{ is not minimal in }\mathcal{F}
\end{gathered}
\right\} \geq\frac{1}{n!}\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain: \ensuremath{\mathcal{C}\cap\mathcal{F}=\emptyset} or }\\
\mathcal{C}\textnormal{ is MNM w.r.t.\ }\mathcal{F}
\end{gathered}
\right\} .
\]
\end{nameddef}

(If this does not hold, we can replace $\mathcal{F}$ with $\left\{ [n]\setminus A:A\in\mathcal{F}\right\} $:
this family is diamond-free, has the same cardinality, and the opposite
inequality holds.) Clearly $C\geq\dfrac{1}{n!}\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain:}\\
\mathcal{C}\textnormal{ is MNM w.r.t.\ }\mathcal{F}
\end{gathered}
\right\} $.

\[
l(\mathcal{F})=\frac{1}{n!}\sum_{\mathcal{C}\textnormal{ is a chain}}\#(\mathcal{C}\cap\mathcal{F})=\frac{1}{n!}\sum_{A\in\mathcal{F}}\sum_{\substack{\mathcal{C}\textnormal{ is a chain}\\
A=\min(\mathcal{C}\cap\mathcal{F})
}
}\#(\mathcal{C}\cap\mathcal{F}),
\]
 since each chain $\mathcal{C}$ will be counted when $A=\min(\mathcal{C}\cap\mathcal{F})$ \textendash{}
except if $\mathcal{C}\cap\mathcal{F}=\emptyset$, but then $\#(\mathcal{C}\cap\mathcal{F})=0$. Continuing,
\[
l(\mathcal{F})=\frac{1}{n!}\sum_{\substack{A\in\mathcal{F}\\
\exists\textnormal{ a chain \ensuremath{\mathcal{C}}: }A=\min(\mathcal{C}\cap\mathcal{F})
}
}\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain containing }A:\\
A=\min(\mathcal{C}\cap\mathcal{F})
\end{gathered}
\right\} \frac{{\displaystyle \sum_{\substack{\mathcal{C}\textnormal{ is a chain}\\
A=\min(\mathcal{C}\cap\mathcal{F})
}
}\#(\mathcal{C}\cap\mathcal{F}})}{\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain containing }A:\\
A=\min(\mathcal{C}\cap\mathcal{F})
\end{gathered}
\right\} }.
\]
 Each chain on $\left[A,[n]\right]$ can be extended to a full $2^{[n]}$-chain
in $\left|A\right|!$ ways. Furthermore, the Boolean lattice $\left[A,[n]\right]$
can be made equivalent to the Boolean lattice $2^{[n]\setminus A}$
by subtracting $A$ from each set; for $\mathcal{A}\subseteq\left[A,[n]\right]$,
we denote $\mathcal{A}-A=\left\{ S\setminus A:S\in\mathcal{A}\right\} $. If $A=\min(\mathcal{C}\cap\mathcal{F})$,
$\#(\mathcal{C}\cap\mathcal{F})=\#(\mathcal{C}\cap\left[A,[n]\right]\cap\mathcal{F})$. If $A$ is minimal
in $\mathcal{F}$ (that is, on every chain), 
\begin{gather*}
\frac{{\displaystyle \sum_{\substack{\mathcal{C}\textnormal{ is a chain}\\
A=\min(\mathcal{C}\cap\mathcal{F})
}
}\#(\mathcal{C}\cap\mathcal{F})}}{\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain containing }A:\\
A=\min(\mathcal{C}\cap\mathcal{F})
\end{gathered}
\right\} }=\frac{\left|A\right|!{\displaystyle \sum_{\mathcal{C}\textnormal{ is a chain in }\left[A,[n]\right]}\#(\mathcal{C}\cap\mathcal{F}\cap\left[A,[n]\right])}}{\left|A\right|!\left(n-\left|A\right|\right)!}\\
=\frac{{\displaystyle \sum_{\mathcal{C}\textnormal{ is a chain in }2^{[n]\setminus A}}\#(\mathcal{C}\cap((\mathcal{F}\cap\left[A,[n]\right])-A))}}{\left(n-\left|A\right|\right)!}=l(n-\left|A\right|,(\mathcal{F}\cap\left[A,[n]\right])-A).
\end{gather*}
 $(\mathcal{F}\cap\left[A,[n]\right])-A$ is diamond-free, so $((\mathcal{F}\cap\left[A,[n]\right])-A)\setminus\emptyset$
is $\Lambda$-free; and the top $n'$ levels are assumed to be empty.
Using Lemma \ref{lem:lubell} as well as that $\frac{1}{n'}=\frac{1}{\Omega(n)}=o(1)$
and the subadditivity of the square root function,
\begin{gather*}
l\bigl(n-\left|A\right|,\bigl((\mathcal{F}\cap\left[A,[n]\right])-A\bigr)\setminus\emptyset\bigr)\leq1-\min\!\left(c(A)+\frac{1}{n'},\frac{1}{4}\right)+\sqrt{\min\!\left(c(A)+\frac{1}{n'},\frac{1}{4}\right)}+\frac{3}{n'}\\
\leq f(c(A))+\sqrt{\frac{1}{n'}}+\frac{3}{n'}=f(c(A))+o(1),
\end{gather*}
so $l\bigl(n-\left|A\right|,(\mathcal{F}\cap\left[A,[n]\right])-A\bigr)\leq1+f(c(A))+o(1)$.
Whereas if $A$ is not minimal in $\mathcal{F}$, i.e. $\exists S\in\mathcal{F}$ such
that $A\supsetneqq S$, then for any chain $\mathcal{C}$ for which $\min(\mathcal{C}\cap\mathcal{F})=A$,
we have $\#(\mathcal{C}\cap\mathcal{F})\leq2$ (otherwise $S$ and three sets in $\mathcal{C}\cap\mathcal{F}$
would form a diamond), so $\frac{\sum_{\substack{\mathcal{C}\textnormal{ is a chain}\\
A=\min(\mathcal{C}\cap\mathcal{F})
}
}\#(\mathcal{C}\cap\mathcal{F})}{\#\left\{ \substack{\mathcal{C}\textnormal{ is a chain through }A:\\
A=\min(\mathcal{C}\cap\mathcal{F})
}
\right\} }\leq2$.

\begin{align*}
l(\mathcal{F}) & \leq\frac{1}{n!}\sum_{\substack{A\in\mathcal{F}\\
A\textnormal{ is minimal in }\mathcal{F}
}
}\#\left\{ \mathcal{C}\textnormal{ is a chain containing }A\right\} \left(1+f(c(A))+o(1)\right)\\
 & {}+\frac{1}{n!}\sum_{\substack{A\in\mathcal{F}\\
A\textnormal{ is not minimal in }\mathcal{F}
}
}\#\left\{ \begin{gathered}\mathcal{C}\textnormal{ is a chain containing }A:\\
A=\min(\mathcal{C}\cap\mathcal{F})
\end{gathered}
\right\} \cdot2\\
 & \le2+\frac{1}{n!}\sum_{\substack{A\in\mathcal{F}\\
A\textnormal{ is minimal in }\mathcal{F}
}
}\#\left\{ \mathcal{C}\textnormal{ is a chain containing }A\right\} \left(f\left(c\left(A\right)\right)-1+o(1)\right).
\end{align*}
 Since $f$ is concave, we can use Jensen's inequality with the weights
$\frac{\#\left\{ \mathcal{C}\textnormal{ is a chain containing }A\right\} }{(1-C)n!}$
(where $A$ is minimal in $\mathcal{F}$). Notice that the sum of all the weights
is $1$ because the sum of numerators is the total number of chains
$\mathcal{C}$ where $\min(\mathcal{C}\cap\mathcal{F})$ is minimal in $\mathcal{F}$, that is, $(1-C)n!$.
\begin{gather*}
l(\mathcal{F})\leq2+(1-C)\left(f\!\left(\frac{{\displaystyle \sum_{\substack{A\in\mathcal{F}\\
A\textnormal{ is minimal in }\mathcal{F}
}
}\#\left\{ \mathcal{C}\textnormal{ is a chain containing }A\right\} c(A)}}{(1-C)n!}\right)-1+o(1)\right).
\end{gather*}
 $c(A)$ is the fraction of the chains containing $A$ which are MNM,
so $\#\left\{ \mathcal{C}\textnormal{ is a chain containing }A\right\} c(A)$
is the number of MNM chains through $A$. In the numerator, each MNM
chain in the whole Boolean lattice is counted once, except if the
minimal element on it is not a global minimal, then it is not counted.
So the numerator is less than or equal to the total number of MNM
chains in the Boolean lattice, which is at most $Cn!$. Substituting,
we get 
\[
l(\mathcal{F})\leq2+(1-C)\left(f\!\left(\frac{n!C}{n!(1-C)}\right)-1+o(1)\right)=1+C+(1-C)f\!\left(\frac{C}{1-C}\right)+o(1).
\]
 $C$ varies between 0 and 1. $\frac{C}{1-C}$ is increasing in $C$.
Above $\frac{C}{1-C}=\frac{1}{4}$ (corresponding to $C=\frac{1}{5}$),
$f(\frac{C}{1-C})$ is constant $\frac{5}{4}$, so $1+C+(1-C)f\!\left(\frac{C}{1-C}\right)=\frac{9}{4}-\frac{C}{4}$
is decreasing in C. So it is enough to take the maximum in the interval
$\left[0,\frac{1}{5}\right]$: 
\begin{align*}
\frac{\left|\mathcal{F}\right|}{\binom{n}{\left\lfloor n/2\right\rfloor }} & \leq l(\mathcal{F})\leq\max_{C\in\left[0,\frac{1}{5}\right]}\left(1+C+(1-C)\left(1-\frac{C}{1-C}+\sqrt{\frac{C}{1-C}}\right)\right)+o(1)\\
 & =\frac{\sqrt{2}+3}{2}+o(1)<2.20711+o(1).
\end{align*}

\section*{Acknowledgments\phantomsection\addcontentsline{toc}{section}{Acknowledgements}}

We thank the anonymous referees for their detailed comments which
helped improve the presentation of our paper. We would also like to
thank D\"om\"ot\"or P\'alv\"olgyi for helpful discussions concerning
the $3$-level version of this problem. The research of the second
and third authors was supported by the National Research, Development
and Innovation Office \textendash{} NKFIH, grant K 116769.

\bibliographystyle{plain}
\phantomsection\addcontentsline{toc}{section}{\refname}
2017-11-27T02:06:43.000
1601
1601.06332
en
https://arxiv.org/abs/1601.06332
Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,...,n\}$ not containing $P$ as a (weak) subposet. The diamond poset, denoted $B_{2}$, is defined on four elements $x,y,z,w$ with the relations $x<y,z$ and $y,z<w$. $La(n,P)$ has been studied for many posets; one of the major open problems is determining $La(n,B_{2})$.Studying the average number of sets from a family of subsets of $[n]$ on a maximal chain in the Boolean lattice $2^{[n]}$ has been a fruitful method. We use a partitioning of the maximal chains and introduce an induction method to show that $La(n,B_{2})\leq(2.20711+o(1))\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$, improving on the earlier bound of $(2.25+o(1))\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$ by Kramer, Martin and Young.
Combinatorics (math.CO)
An upper bound on the size of diamond-free families of sets
Qwen/Qwen-72B
1. YES
2. YES