\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.15}{22(4)}{2015}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
\usepackage{ifthen,latexsym,fixmath,bbm}

% we recommend the graphicx package for importing figures
%\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf The maximal length of a gap between\\ $r$-graph Tur\'an densities}


% 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{Oleg Pikhurko\footnote{Supported by ERC
grant~306493 and EPSRC grant~EP/K012045/1.}\\
\small Mathematics Institute and DIMAP\\[-0.8ex]
\small University of Warwick\\[-0.8ex] 
\small Coventry CV4 7AL, UK\\
\small\tt O.Pikhurko@warwick.ac.uk\\
}




% \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{Apr 7, 2015}{Oct 5, 2015}{Oct 30, 2015}\\
\small Mathematics Subject Classifications: 05D05}


\newcommand{\C}[1]{{\protect\cal #1}}
\newcommand{\B}[1]{\mathbold{#1}}
\newcommand{\I}[1]{{\mathbb #1}}
\renewcommand{\O}[1]{\overline{#1}}
\newcommand{\ceil}[1]{\lceil #1\rceil}
\newcommand{\e}{\varepsilon}
\newcommand{\floor}[1]{\lfloor #1\rfloor}
\newcommand{\me}{{\mathrm e}}
\renewcommand{\mid}{:}
\renewcommand{\ge}{\geqslant}
\renewcommand{\le}{\leqslant}
\renewcommand{\preceq}{\preccurlyeq}
\renewcommand{\succeq}{\succcurlyeq}

%text specific macros 

\newcommand{\IS}{\I S} % standard simplex
\newcommand{\ex}{\mathrm{ex}}
\newcommand{\FinPi}[1]{\Pi^{(#1)}_{\mathrm{fin}}}
\newcommand{\InfPi}[1]{\Pi_{\infty}^{(#1)}}
\newcommand{\branch}[2]{\mathrm{br}_{#1}(#2)}
\newcommand{\blow}[2]{#1(\!(#2)\!)}
\newcommand{\density}[1]{\Lambda_{#1}}
\newcommand{\multiset}[1]{\{\hspace{-0.25em}\{\hspace{0.1em}#1\hspace{0.1em}\}\hspace{-0.25em}\}}
\newcommand{\E}[1]{\mathbf{E}\left[\hspace{0.5mm}#1\hspace{0.5mm}\right]}
\newcommand{\ind}{{}_{\mathrm{ind}}}
\newcommand{\LIM}[1]{\mathrm{LIM}^{(#1)}}
\newcommand{\CG}{\C G}
\newcommand{\cl}[1]{\mathrm{cl}(#1)}
\newcommand{\rep}[2]{{#1}^{(#2)}}
\newcommand{\order}[1]{\langle #1\rangle}
\newcommand{\ins}[2]{\order{\B{#1},#2}}
\newcommand{\minus}[2]{#1\setminus #2}





\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.


\begin{abstract}
The \emph{Tur\'an density} $\pi(\C F)$ of a family $\C F$ of
$r$-graphs is the limit as $n\to\infty$ 
of the maximum edge density 
of an $\C F$-free $r$-graph on $n$ vertices.  Erd\H os [%
%\emph{On extremal problems of graphs and generalized graphs} 
Israel J. Math \textbf{2} (1964):183--190] proved
that no Tur\'an density can lie in the open interval $(0,r!/r^r)$. Here we show that any other
open subinterval of $[0,1]$ avoiding Tur\'an densities has strictly smaller 
length. In particular, this implies a conjecture of Grosu~[%
%\emph{On the algebraic and topological structure of the set of Tur\'an densities}, 
\arxiv{1403.4653}, 2014].

  % keywords are optional
  %\bigskip\noindent \textbf{Keywords:} hypergraph, Tur\'an density, Tur\'an problem. 
\end{abstract}







\section{Introduction}


Let $\C F$ be a (possibly infinite) family of \emph{$r$-graphs} (that is,
$r$-uniform set systems). We call elements of $\C F$ \emph{forbidden}. An
$r$-graph $G$ is \emph{$\C F$-free} if no member $F\in \C F$ is 
a subgraph of~$G$, that is, we cannot obtain $F$
by deleting some vertices and edges from $G$. The \emph{Tur\'an
function $\ex(n,\C F)$} is the maximum number of edges that an $\C F$-free
$r$-graph on $n$ vertices can have. This is one of the central questions of
extremal combinatorics that goes back to the fundamental
paper of Tur\'an~\cite{turan:41}. We refer the reader to the
surveys of the Tur\'an function by
F\"uredi~\cite{furedi:91}, Keevash~\cite{keevash:11},
and Sidorenko~\cite{sidorenko:95}.

As was observed by Katona, Nemetz, and
Simonovits~\cite{katona+nemetz+simonovits:64}, 
the limit
 $$
 \pi(\C F):=\lim_{n\to\infty} \frac{\ex(n,\C F)}{{n\choose k}}
 $$
 exists. It is called the \emph{Tur\'an density} of $\C F$. Let $\InfPi{r}$
consist of all possible Tur\'an densities of $r$-graph families and let
 $\FinPi{r}$ be the set of all possible Tur\'an densities when \textit{finitely many}
$r$-graphs are forbidden.  It is convenient to allow empty forbidden families, so that 
$1$ is also a Tur\'an density. Clearly, $\FinPi{r}\subseteq \InfPi{r}$. 
A result of Brown and Simonovits~\cite[Theorem~1]{brown+simonovits:84} implies that 
the topological closure $\cl{\FinPi{r}}$ of $\FinPi r$ contains $\InfPi r$ while the converse inclusion
was established in~\cite[Proposition~1]{pikhurko:14}; thus
 \begin{equation}\label{eq:cl}
 \InfPi r=\cl{\FinPi{r}},\quad \mbox{for every integer $r\ge 2$}.
 \end{equation}

For $r=2$, the celebrated Erd\H os-Stone-Simonovits 
Theorem~\cite{erdos+simonovits:66,erdos+stone:46} determines 
the Tur\'an density for every family $\C F$. In particular, we have
 \begin{equation}\label{eq:PI2}
 \FinPi{2}=\InfPi{2}=\left\{\frac{m-1}m\mid m=1,2,3,\dots,\infty\right\}.
 \end{equation}


Unfortunately, the Tur\'an function for
\emph{hypergraphs} (that is, $r$-graphs with 
$r\ge 3$) is much more difficult to analyse and many problems
(even rather basic ones) are wide open. 

Fix some $r\ge 2$. A \emph{gap}
is an open interval $(a,b)\subseteq (0,1)$ that is disjoint
from $\InfPi{r}$ (which, by~\eqref{eq:cl}, is equivalent to being
disjoint from $\FinPi{r}$). Here we consider $g_r$, the maximal possible length of a gap.
In other words, $g_r$ is
the maximal $g$ such that there is a real $a$ with $(a,a+g)\subseteq (0,1)\setminus
\InfPi{r}$.  For example, \eqref{eq:PI2} implies that $g_2=1/2$. Erd\H os~\cite{erdos:64} proved
that $(0,r!/r^r)$ is a gap; in particular, $g_r\ge r!/r^r$. Here we show that 
this is equality and every other gap has strictly smaller length.


\begin{theorem}\label{th:gap} For every $r\ge 3$, we have that $g_r=r!/r^r$ and, furthermore, $(0,r!/r^r)$ is the only gap of length $r!/r^r$ for $r$-graphs.
\end{theorem}

In particular we obtain the following result that was conjectured by Grosu~\cite[Conjecture 10]{grosu:densities}.

\begin{corollary}\label{cr:grosu} The union of $r$-graph Tur\'an densities over all
$r\ge 2$ is dense in $[0,1]$, that is, $\cl{\cup_{r=2}^\infty \InfPi r}=[0,1]$.\qed
 \end{corollary}

The question whether the set $\InfPi{r}$  is
a well-ordered subset of $([0,1],\le)$ for $r\ge 3$ was a famous \$1000 problem of Erd\H os that was answered in the negative by Frankl and R\"odl~\cite{frankl+rodl:84}. Despite a number of results
that followed~\cite{frankl+rodl:84}, very little is known about other gaps in $\InfPi{r}$ for $r\ge3$. For example, let $g_r'$
be the second largest gap length, that is, the maximum $g\ge 0$ such that $(a,a+g)\subseteq (r!/r^r,1)\setminus\InfPi r$
for some $a$. The computer-generated proof of 
Baber and Talbot~\cite{baber+talbot:11} implies that $g_3'\ge 0.0017$. Klas Markstr\"om and Fei Song~\cite{markstrom:15:talk}
conjectured that $(2/7,8/27)$ is the (unique) second largest gap for $3$-graphs (and, in particular, $g_3'=2/189$).
However, not for a single $r\ge 4$ is it known, for example, whether $g_r'$ is zero (i.e.\ whether
$\InfPi{r}$ is dense in $[r!/r^r,1]$).  

This paper is organised as follows. In Section~\ref{prelim} we give some definitions and auxiliary results. 
Theorem~\ref{th:gap} is proved in Section~\ref{first}. We give another proof of Corollary~\ref{cr:grosu} in Section~\ref{second}. Although the latter proof is not strong enough
to prove Theorem~\ref{th:gap}, its advantage is that it produces explicit elements of $\FinPi r$ (as opposed to 
the implicit values of certain maximisation problems returned by the proof in Section~\ref{first}). 
So we include both proofs here, even though the second one is longer. 

\section{Preliminaries}\label{prelim}

For $n\in \I N$, define $[n]:=\{1,\dots,n\}$. For reals $a\le b$, let $(a,b)$ and $[a,b]$ be respectively the open
and closed interval of reals with endpoints $a$ and $b$. The \emph{standard $(m-1)$-dimensional simplex}~is
 $$
 \IS_m:=\{\B x\in \I R^m\mid x_1+\dots+x_m=1,\ \forall\, i\in[m]\ x_i\ge 0\}.
 $$


An \emph{$r$-pattern} is a
collection $P$ of $r$-multisets on $[m]$, for some $m\in\I N$.
(By an \emph{$r$-multiset} we mean an unordered collection
of $r$ elements with repetitions allowed.) Let $V_1,\dots,V_m$ 
be disjoint sets and let $V=V_1\cup\dots\cup V_m$. The \emph{profile}
of an $r$-set $X\subseteq V$ (with respect to $V_1,\dots,V_m$) is
the $r$-multiset on $[m]$ that contains $i\in [m]$
with multiplicity $|X\cap V_i|$. For an $r$-multiset $Y$ on~$[m]$, let 
$\blow{Y}{V_1,\dots,V_m}$ consist of all $r$-subsets of $V$ whose profile is
$Y$. We call this $r$-graph the \emph{blow-up of $Y$} (with respect to $V_1,\dots,V_m$) and
the $r$-graph
 $$
 \blow{P}{V_1,\dots,V_m}:=\bigcup_{Y\in P} \blow{Y}{V_1,\dots,V_m}
 $$ 
 is called the \emph{blow-up of $P$}. 
Let the \emph{Lagrange polynomial} of $P$ be 
 $$
 \lambda_P(x_1,\dots,x_m):=r!\,\sum_{D\in P}\; \prod_{i=1}^m\;
\frac{x_i^{D(i)}}{D(i)!}\in\I R[x_1,\dots,x_m], 
 $$
 where $D(i)$ denotes the multiplicity of $i$ in $D$.
This definition is motivated by the fact that, 
for every partition $[n]=V_1\cup\dots\cup V_m$, we have that
 $$
|\blow{P}{V_1,\dots,V_m}|
= \lambda_P\left(\frac{|V_1|}n,\dots,\frac{|V_m|}n\right)\times {n\choose r}
+O(n^{r-1}),\qquad  \mbox{as $n\to\infty$}.
 $$

For example, if $r=3$, $m=3$, and $P$ consists of multisets $\{1,1,2\}$ and $\{1,2,3\}$,
then $\blow{P}{V_1,\dots,V_m}$ contains all triples that have two vertices in $V_1$ and one vertex in $V_2$ plus all triples with exactly one vertex in each part; here $\lambda_P(x_1,x_2,x_3)=3 x_1^2x_2+6x_1x_2x_3$.

 Let the \emph{Lagrangian of $P$} be $\Lambda_P:=\max\{\lambda_P(\B x)\mid \B x\in \IS_m\}$,  the maximum value of the polynomial 
$\lambda_P$ on the compact set~$\IS_m$. One obvious connection of this parameter to $r$-graph Tur\'an
densities is that, if each blow-up of $P$ is $\C F$-free, then $\pi(\C F)\ge \Lambda_P$.  Also, it is not hard
to show that $\Lambda_P=\pi(\C F)$, where $\C F$ consists
of all $r$-graphs $F$ such that every blow-up of $P$ is $F$-free; thus $\Lambda_P\in \InfPi r$.
As shown in~\cite[Theorem~3]{pikhurko:14}, we have in fact that
  \begin{equation}\label{eq:Lambda} 
  \Lambda_P\in \FinPi r,\quad\mbox{for every $r$-pattern $P$}.
  \end{equation}





We will use
the special case of Muirhead's inequality (see e.g.~\cite[Theorem 45]{hardy+littlewood+polya:i}) which states that, for any $0\le i<j\le k$, we have
 \begin{equation}\label{eq:Muirhead}
 x^{k+i}y^{k-i}+x^{k-i}y^{k+i}\le x^{k+j}y^{k-j}+x^{k-j}y^{k+j},\quad \mbox{for }x,y\ge 0.
 \end{equation}




\section{Proof of Theorem~\ref{th:gap}}\label{first}

Let $r\ge 3$. Fix a sufficiently large integer $m=m(r)$
so that $r!{m\choose r}/m^{r}> 1-r!/r^r$. Consider $r$-graphs $G_0,\dots,G_{{m\choose r}}$ on $[m]$ such that $G_0$ has no edges and, for $i=1,\dots,{m\choose r}$, the $r$-graph $G_i$ is obtained
from $G_{i-1}$ by adding a new edge. In other words, we enumerate all $r$-subsets of $[m]$ as $R_1,\dots,R_{{m\choose r}}$
and let $G_i:=\{R_1,\dots,R_i\}$. Let 
 $$
\lambda_i(\B x):=\lambda_{G_i}(\B x)=r!\sum_{D\in G_i} \prod_{j\in D} x_j,
 $$ 
 be the Lagrange polynomial of $G_i$ and $\Lambda_i:=\Lambda_{G_i}$ be its Lagrangian, where we view
$G_i$ as an $r$-pattern. Since $G_{i-1}\subseteq G_i$, we have that
$\Lambda_{i-1}\le \Lambda_i$. 

We claim that for every $i\in [\,{m\choose r}\,]$
 \begin{equation}\label{eq:aim3}
 \Lambda_i-\Lambda_{i-1}\le r!/r^r.
 \end{equation}
 Indeed, pick $\B x\in\IS_m$ with $\Lambda_i=\lambda_i(\B x)$. Let $R_i=\{u_1,\dots,u_r\}$. When we remove the term $r!\, x_{u_1}\ldots x_{u_r}$
from $\lambda_i(\B x)$, we get the evaluation of $\lambda_{i-1}$ on $\B x\in\IS_m$. By definition, $\Lambda_{i-1}\ge \lambda_{i-1}(\B x)$. 
Also, since $x_{u_1}+\cdots+x_{u_r}\le 1$, we have $x_{u_1}\ldots x_{u_r}\le r^{-r}$ by the Geometric-Arithmetic Mean Inequality. Thus we obtain the stated bound:
 $$
 \Lambda_i=\lambda_i(\B x)=\lambda_{i-1}(\B x)+r!\,x_{u_1}\ldots x_{u_r}\le \Lambda_{i-1}+r!/r^r.
 $$ 

Also, we have $\Lambda_{{m\choose r}}\ge \lambda_{{m\choose r}}(\frac1m,\dots,\frac1m)= r!{m\choose r}/m^{r}> 1-r!/r^r$. This and~\eqref{eq:Lambda} imply that $g_r\le r!/r^r$ (while
the above-mentioned result of Erd\H os~\cite{erdos:64} gives the converse inequality). Also, if we 
have equality in \eqref{eq:aim3}, then necessarily $x_{u_1}=\dots=x_{u_r}=1/r$, each other $x_j$ is zero, and $\Lambda_{i-1}=\lambda_{i-1}(\B x)=0$,
implying the uniqueness part of  Theorem~\ref{th:gap}.



\section{Alternative proof of Corollary~\ref{cr:grosu}}\label{second}

For integers $r,s\ge 2$, let $\C P_{r,s}$ consist of ordered $s$-tuples $(r_1,\dots,r_s)$ of non-negative integers such that $r_1\ge\dots\ge r_s$ and $r_1+\dots+r_s=r$. 
This set admits a partial order, where $\B x\succeq \B y$ if $\sum_{i=1}^k x_i\ge \sum_{i=1}^k y_i$ 
for every $k\in [s-1]$.
For example, the (unique) maximal element is $(r,0,\dots,0)$ and the (unique) minimal element is $(\ceil{r/s},\dots,\floor{r/s})$. 

Let $A\subseteq
\C P_{r,s}$. The set $A$ is called \emph{down-closed} if $\B y\in A$ whenever $\B x\in A$ and $\B x\succeq \B y$. 
Let $G_A$ consist of all $r$-multisets $X$ on $[s]$ such that the multiplicities of $X$ satisfy $\order{X(1),\dots,X(s)}\in A$,
where $\order{\B x}$ denotes the non-increasing ordering of a vector~$\B x$. 
%(In other words, $G_A$ is made of
%those $X$ for which there is a bijection $\sigma:[s]\to [s]$ such that $(X(\sigma(1)),\dots,X(\sigma(s)))\in A$.) 
Also, we use the shorthand $\lambda_{A}:=\lambda_{G_A}$ and $\Lambda_A:=\Lambda_{G_A}$.

\begin{lemma}\label{lm:opt} Let $r,s\ge 2$. If $A\subseteq \C P_{r,s}$ is down-closed, then
$\Lambda_A=\lambda_A(\frac 1s,\dots,\frac 1s)$.\end{lemma}

\begin{proof} We use induction on $s$. 

First, we prove the base case $s=2$. Let $k:=r/2$. For $h\ge 0$, let $I_h$ consist of all integer translates of $k$ whose absolute value is at most $h$, that is, 
$I_h:= (\I Z+k)\cap [-h,h]$. Also, let $I_h^+:=I_h\cap [0,h]$. (These definitions will allow us to deal with the cases of even and odd
$r$ uniformly.) For example, $\C P_{r,2}=\{(k+ i,k- i)\mid i\in I_k^+\}$. 

Take a down-closed set $A\subseteq \C P_{r,2}$. It consists of pairs $(k+i,k-i)$ with $i\in I_h^+$ for some~$h\le k$.
Then $G_A$ consists of all $2k$-multisets on $\{1,2\}$ that contain $1$ with multiplicity
$k+i$ for $i\in I_h$.
By the homogeneity of the polynomials involved, the required inequality can be rewritten as 
 \begin{equation}\label{eq:aim}
 \sum_{i\in I_h} {2k\choose k+i}\left(\frac{x+y}2\right)^{2k}-\sum_{i\in I_h} {2k\choose k+i}x^{k+i}y^{k-i}\ge 0,\quad \mbox{for }x,y\ge 0.
 \end{equation}

 We will apply the so-called \emph{bunching method} where we try to write the desired
inequality as a positive linear combination of Muirhead's inequalities~\eqref{eq:Muirhead}. If 
$j\in I_h$, then the coefficient in front of $x^{k+j}y^{k-j}$ in (\ref{eq:aim})
is
 $$
 2^{-2k}{2k\choose k+j}\sum_{i\in I_h} {2k\choose k+i}- {2k\choose k+j}\le 0.
 $$
 If $j\in I_k\setminus I_h$, then the coefficient is
 $
 2^{-2k}{2k\choose k+j}\sum_{i\in I_h} {2k\choose k+i}\ge 0.
 $
 Thus, if we group the left-hand side of (\ref{eq:aim}) into terms $x^{k+j}y^{k-j}+x^{k-j}y^{k+j}$, 
then we get non-positive coefficients for $0\le j\le h$ followed by non-negative
coefficients for $j>h$. Also, the total sum of coefficients is zero because
(\ref{eq:aim}) becomes equality for $x=y=1$. Thus we can ``bunch'' 
$I_h$-terms with $(I_k\setminus I_h)$-terms and use~\eqref{eq:Muirhead} to derive the desired inequality (\ref{eq:aim}).
This proves the case $s=2$.

Now, let $s\ge 3$ and suppose that we have proved the lemma for $s-1$ (and all $r$). The function
$\lambda_A$ is a continuous function on the compact set $\IS_s$. Let it attain its maximum
on some $\B x\in\IS_s$. If there is more than one choice, then choose $\B x$ so that
$\Delta:=\sum_{i\not=j} |x_i-x_j|$ is minimised.  Suppose that $\Delta\not=0$, say $x_1\not=x_2$.
Note that $\lambda_A$ is a homogeneous polynomial of degree $r$, 
and the coefficient at $x_1^{r_1}\ldots x_s^{r_s}$ is ${r\choose r_1,\dots,r_s}$ if the ordering $\order{\B r}$ of $\B r$ is in $A$ and 0 otherwise.

Fix $j\in \{0,\dots,r\}$. If we collect all terms in front of $x_s^j$, we get
 $$
 \sum_{\ins{r}{j}\in A\atop r_1+\dots+r_{s-1}=r-j} {r\choose r_1,\dots,r_{s-1},j} \prod_{i=1}^{s-1} x_i^{r_i}= 
{r\choose j}\, \lambda_{\minus{A}{j}}(x_1,\dots,x_{s-1}),
 $$
 where $\ins{y}{j}$ is 
obtained from $\B y$  by appending $j$ and ordering the obtained sequence, while $\minus{A}{j}$ consists of those $\B y\in \C P_{r-j,s-1}$ such that $\ins{y}{j}\in A$.

Let us show that $\minus{A}{j}\subseteq \C P_{r-j,s-1}$ is down-closed. Take arbitrary $\B z\in \minus{A}{j}$
and $\B y\preceq \B z$. We have to show that $\B y\in \minus{A}{j}$. 
Since $A\ni \ins{z}{j}$ is down-closed, it is enough to show that $\ins{z}{j}\succeq \ins{y}{j}$. We have to compare the sums of the first $i$ terms of $\ins{z}{j}$
and of $\ins{y}{j}$ for each $i\in [s-1]$. A problem could arise only if the new entry $j$ was included  into these terms for $\ins{y}{j}$, say as the term number $h\le i$, but not for $\ins{z}{j}$. Since $\B z\succeq \B y$, we have that $\sum_{f=1}^{h-1} z_f\ge \sum_{f=1}^{h-1} y_f$ (and these are also the initial sums for $\ins{z}{j}$ and $\ins{y}{j}$).
Furthermore, each of the subsequent $i-(h-1)$ entries is at least $j$ for $\ins{z}{j}$ and at most $j$ for $\ins{y}{j}$.
It follows that $\ins{z}{j}\succeq \ins{y}{j}$. Thus $\minus{A}{j}$ is down-closed, as claimed.

By the induction assumption (and since $\lambda_{\minus{A}{j}}$ is a homogeneous polynomial), we have that $\lambda_{\minus{A}{j}}(x_1,\dots,x_{s-1})\le \lambda_{\minus{A}{j}}(\frac{1-x_s}{s-1},\dots,\frac{1-x_s}{s-1})$. Thus
 $$
 \Lambda_A=\lambda_A(\B x)=\sum_{j=0}^r {r\choose j}\, \lambda_{\minus{A}{j}}(x_1,\dots,x_{s-1})\, x_s^j \le \lambda_{A}\left(\frac{1-x_s}{s-1},\dots,\frac{1-x_s}{s-1},x_s\right).
 $$
 Clearly, the sum $\sum_{i=1}^{s-1}|x_s-x_i|$ does not increase if we replace each of $x_1,\dots,x_{s-1}$ by their
arithmetic mean $(1-x_{s})/(s-1)$. Since $x_1\not=x_2$, we have found another optimal element of
$\IS_s$ with strictly smaller $\Delta$, a contradiction. The lemma is proved.\end{proof}



Fix some enumeration $\C P_{r,r}=\{R_1,\dots,R_t\}$ such that if $R_i\succeq R_j$ then $i\ge j$. For $j\in \{0,\dots,t\}$, let $A_j:=\{R_i\mid i\in [j]\}$.
Thus, for example, $A_0=\varnothing$ and $A_t=\C P_{r,r}$. By~\eqref{eq:Lambda}, $\FinPi{r}$ contains
all of the following numbers:
 $$
 0=\Lambda_{A_0}\le \Lambda_{A_1}\le \cdots\le \Lambda_{A_t}=1.
 $$


Let us
show that $\max\{\Lambda_{A_i}-\Lambda_{A_{i-1}}\mid i\in [t]\}=o(1)$ 
as $r\to\infty$. By definition, each $A_j\subseteq \C P_{r,r}$ is down-closed. Thus, by Lemma~\ref{lm:opt} the difference 
 $
 \Lambda_{A_i}-\Lambda_{A_{i-1}}
%=\lambda_{A_i}\left(\frac1r,\dots,\frac1r\right)- \lambda_{A_i}\left(\frac1r,\dots,\frac1r\right)
 $
is
the probability that, when $r$ balls are uniformly and independently distributed into $r$ cells, the
ordered ball distribution is given by $R_i$. 
Expose the first $r-m$ balls, where, for example, $m:=\lfloor \log r\rfloor$. 
Let $k$ be the number of empty cells. Its expected value is $r (1-1/r)^{r-m}=(\me^{-1}+o(1))\,r$.
By Azuma's inequality (see e.g.\ \cite[Theorem~7.2.1]{alon+spencer:pm}), we have
\emph{whp} (i.e.\ with probability $1-o(1)$ as $r\to\infty$) that $k$ is in $I:=[r/4,3r/4]$. Assume that $k\in I$ and expose the
remaining $m$ balls. Let $J$ be the number of balls that land inside the $k$  cells that were empty after the first round. The probability that $J=j$ for any particular integer
$j\in [m/8,7m/8]$ is
 \begin{eqnarray*}
  {m\choose j}\, \left(\frac{k}{r}\right)^{j}\, \left(\frac{r-k}{r}\right)^{m-{j}}
      &=& (1+o(1)) \, \sqrt{\frac{m}{2\pi {j}(m-{j})}}\, \left(\frac{mk}{{j}r}\right)^{j}\, \left(\frac{m(r-k)}{(m-{j})r}\right)^{m-{j}}\\
 &\le & (1+o(1)) \, \sqrt{\frac{m}{2\pi {j}(m-{j})}}\ =\ o(1),
   \end{eqnarray*}
 where we used Stirling's formula and the Arithmetic-Geometric Mean Inequality.
 On the other hand, we have whp that $m/8\le J\le 7m/8$ (by
Azuma's inequality and our assumption $k\in I$) and that the last $m$ balls
all go into different cells (since $m^2=o(r)$). 
Once the first $r-m$ balls are
exposed and we condition on the event that the last $m$ balls all land into
distinct cells, there is at most one value of $J$ for which the final
ball distribution is $R_i$. 
 %(Indeed, consider the number of zeros in $R_i$.)
Thus the probability of getting $R_i$
is $o(1)$ uniformly in $i$, as desired.
 This finishes the second proof of Corollary~\ref{cr:grosu}.

\section*{Acknowledgements}

The author would like to thank Codrut Grosu for helpful comments.

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{99}

\bibitem{alon+spencer:pm}
N.~Alon and J.~Spencer, \emph{The probabilistic method}, 3d ed., Wiley
  Interscience, 2008.

\bibitem{baber+talbot:11}
R.~Baber and J.~Talbot, \emph{Hypergraphs do jump}, Combin.\ Probab.\ Computing
  \textbf{20} (2011), 161--171.

\bibitem{brown+simonovits:84}
W.~G. Brown and M.~Simonovits, \emph{Digraph extremal problems, hypergraph
  extremal problems and the densities of graph structures}, Discrete Math.
  \textbf{48} (1984), 147--162.

\bibitem{erdos:64}
P.~Erd{\H{o}}s, \emph{On extremal problems of graphs and generalized graphs},
  Israel J.\ Math. \textbf{2} (1964), 183--190.

\bibitem{erdos+simonovits:66}
P.~Erd{\H{o}}s and M.~Simonovits, \emph{A limit theorem in graph theory},
  Stud.\ Sci.\ Math.\ Hungar. (1966), 51--57.

\bibitem{erdos+stone:46}
P.~Erd{\H o}s and A.~H. Stone, \emph{On the structure of linear graphs}, Bull.\
  Amer.\ Math.\ Soc. \textbf{52} (1946), 1087--1091.

\bibitem{frankl+rodl:84}
P.~Frankl and V.~R{\"o}dl, \emph{Hypergraphs do not jump}, Combinatorica
  \textbf{4} (1984), 149--159.

\bibitem{furedi:91}
Z.~F{\"u}redi, \emph{{Tur\'an} type problems}, Surveys in Combinatorics (A.~D.
  Keedwell, ed.), London Math.\ Soc.\ Lecture Notes Ser., vol. 166, Cambridge
  Univ.\ Press, 1991, pp.~253--300.

\bibitem{grosu:densities}
C.~Grosu, \emph{On the algebraic and topological structure of the set of
  {Tur\'an} densities}, \arxiv{1403.4653}, 2014.

\bibitem{hardy+littlewood+polya:i}
G.~H. Hardy, J.~E. Littlewood, and G.~P{\'o}lya, \emph{Inequalities}, Cambridge
  Univ.\ Press, 1952, 2d ed.

\bibitem{katona+nemetz+simonovits:64}
G.~O.~H. Katona, T.~Nemetz, and M.~Simonovits, \emph{On a graph problem of
  {Tur\'an} {(In Hungarian)}}, Mat.\ Fiz.\ Lapok \textbf{15} (1964), 228--238.

\bibitem{keevash:11}
P.~Keevash, \emph{Hypergraph {Tur\'an} problem}, Surveys in Combinatorics
  (R.~Chapman, ed.), London Math.\ Soc.\ Lecture Notes Ser., vol. 392,
  Cambridge Univ.\ Press, 2011, pp.~83--140.

\bibitem{markstrom:15:talk}
K.\ Markstr{\" o}m, \emph{Tur{\'a}n densities for 3-graphs}, Talk at the 25th
  British Combinatorial Conference, 6--10 July 2015.

\bibitem{pikhurko:14}
O.~Pikhurko, \emph{On possible {Tur\'an} densities}, Israel J.\ Math.
  \textbf{201} (2014), 415--454.

\bibitem{sidorenko:95}
A.~Sidorenko, \emph{What we know and what we do not know about {Tur\'an}
  numbers}, Graphs Combin. \textbf{11} (1995), 179--199.

\bibitem{turan:41}
P.~{Tur\'an}, \emph{On an extremal problem in graph theory (in {Hungarian})},
  Mat.\ Fiz.\ Lapok \textbf{48} (1941), 436--452.

\end{thebibliography}


\end{document}
