# Diversity

Peter Frankl  Rényi Institute, Budapest, Hungary; Email:
<EMAIL_ADDRESS>and  Andrey Kupavskii  University of Birmingham and
Moscow Institute of Physics and Technology; Email<EMAIL_ADDRESS>
###### Abstract.

Given a family ${\mathcal{F}}\subset 2^{[n]}$, its diversity is the number of
sets not containing an element with the highest degree. The concept of
diversity has proven to be very useful in the context of $k$-uniform
intersecting families. In this paper, we study (different notions of)
diversity in the context of other extremal set theory problems. One of the
main results of the paper is a sharp stability result for cross-intersecting
families in terms of diversity and, slightly more generally, sharp stability
for the Kruskal–Katona theorem.

The research of the second author was supported by the Advanced
Postdoc.Mobility grant no. P300P2_177839 of the Swiss National Science
Foundation.

##  1\. Introduction and main results

Given a family ${\mathcal{F}}\subset 2^{[n]}$, we define its diversity
$\gamma({\mathcal{F}})$ to be
$\gamma({\mathcal{F}}):=\min_{i\in[n]}|\\{F\in{\mathcal{F}}:i\notin F\\}|$.
The maximum degree $\Delta({\mathcal{F}})$ of ${\mathcal{F}}$ is
$\Delta({\mathcal{F}}):=\max_{i\in[n]}|\\{F\in{\mathcal{F}}:i\in F\\}|$. That
is, $\gamma({\mathcal{F}})+\Delta({\mathcal{F}})=|{\mathcal{F}}|$. We say that
a family ${\mathcal{F}}$ is intersecting if $F_{1}\cap F_{2}\neq\emptyset$ for
any $F_{1},F_{2}\in{\mathcal{F}}$. To the best of our knowledge, the problem
of maximizing diversity first appeared explicitly in the following question of
Katona: what is the maximum possible diversity of an intersecting family
${\mathcal{F}}\subset{[n]\choose k}$? Lemons and Palmer [35] showed that
$\gamma({\mathcal{F}})\leq{n-3\choose k-2}$ for $n\geq 6k^{3}$ (they used the
term “unbalance” instead of diversity). Later, this bound on $n$ was improved
to $n\geq 6k^{2}$ by the first author [15] and to $n\geq Ck$ with some
absolute constant $C$ by the second author [33].

Diversity is also closely related to the concept of influence of a Boolean
function, which we discuss later in the paper. Katona’s question was motivated
by the work of Dinur and Friedgut [5], who studied approximations of
intersecting families by juntas using the tools coming from the Analysis of
Boolean functions. In particular, using these tools, they showed that
$\gamma({\mathcal{F}})=O({n-2\choose k-2})$ for $n>Ck$. We note that this
result in itself was not new: the first author showed
$\gamma({\mathcal{F}})\leq 3{n-2\choose k-2}$ for any $n>2k>0$ in [12].
However, the more general approximation by juntas result of [5] was an
important tool in the proof in [33].

Diversity proved to be a very useful concept in the study of intersecting
families. It was recently applied to different problems in [9, 17, 24, 34].
One of the tools that was particularly fruitful is a recent theorem that
allows us to bound the size of $k$-uniform intersecting families based on
their diversity, proven by the second author and Zakharov in [32]. This
theorem is a stronger version of an old result due the first author [12]. Both
results provide strong and in many cases sharp stability versions of the
Erdős-Ko-Rado [6] theorem, which states that any intersecting family
${\mathcal{F}}\subset{[n]\choose k}$ has size at most ${n-1\choose k-1}$,
provided $n\geq 2k$. An even stronger version of these theorems, which is
sharp in all cases, was proven in [34].

For a real $x\geq k$, let us put ${x\choose
k}:=\frac{x(x-1)\ldots(x-k+1)}{k!}$, and put ${x\choose k}:=0$ for $x<k$.

######  Theorem 1 ([32]).

Let $n>2k>0$ and ${\mathcal{F}}\subset{[n]\choose k}$ be an intersecting
family. Then, if $\gamma({\mathcal{F}})\geq{n-u-1\choose n-k-1}$ for some real
$3\leq u\leq k$, then

(1) $|{\mathcal{F}}|\leq{n-1\choose k-1}+{n-u-1\choose n-k-1}-{n-u-1\choose
k-1}.$

The bound from Theorem 1 is sharp for integer $u$, as witnessed by the family
$\mathcal{L}_{u,u}(n,k)$, defined after Theorem 3.

In this paper, we conduct a more systematic study of diversity in the context
of some classic extremal set theory problems. For an integer $t\geq 1$, we say
that the families ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{l}\subset 2^{[n]}$
are cross $t$-intersecting if $|F_{1}\cap\ldots\cap F_{l}|\geq t$ for any
$F_{1}\in{\mathcal{F}}_{1},\ldots,F_{l}\in{\mathcal{F}}_{l}$. If $t=1$ then we
use the term cross-intersecting. The following theorem is a generalization of
the Erdős–Ko–Rado theorem.

######  Theorem 2 ([2]).

Let $a,b$ be positive integers and $n\geq a+b$. Suppose that
${\mathcal{A}}\subset{[n]\choose a}$ and ${\mathcal{B}}\subset{[n]\choose b}$
are cross-intersecting and $|{\mathcal{A}}|\geq{n-1\choose a-1}$. Then
$|{\mathcal{B}}|\leq{n-1\choose b-1}$.

If one puts $a=b=k$ and ${\mathcal{A}}={\mathcal{B}}$, then one retrieves the
EKR theorem. Again, the bound in Theorem 2 is sharp: take ${\mathcal{A}}$ and
${\mathcal{B}}$ to be the families of all sets containing $1$ of sizes $a$ and
$b$, respectively.

The key result of this paper is the following stability for Theorem 2 in terms
of diversity.

######  Theorem 3.

Let $a,b$ be positive integers and $n\geq a+b$. Suppose that
${\mathcal{A}}\subset{[n]\choose a}$ and ${\mathcal{B}}\subset{[n]\choose b}$
are cross-intersecting. Suppose that

$\displaystyle|{\mathcal{A}}|\ \geq$ $\displaystyle\ {n-1\choose
a-1}-{n-v-1\choose a-1}+{n-u-1\choose n-a-1}\ \ \ {\text{a}nd}$
$\displaystyle|{\mathcal{B}}|\ \geq$ $\displaystyle\ {n-1\choose
b-1}-{n-u-1\choose b-1}+{n-v-1\choose n-b-1}$

for some real $3\leq u\leq a$, $3\leq v\leq b$ and, moreover, that at least
one of the displayed inequalities is strict. Then

$\gamma({\mathcal{A}})<{n-u-1\choose n-a-1}\ \ \ \text{and}\ \ \
\gamma({\mathcal{B}})<{n-v-1\choose n-b-1},$

moreover, both families have the same (unique) element of the largest degree.

The theorem above is sharp for each integer $u\in[3,a],v\in[3,b]$ for
$\mathcal{A}=\mathcal{L}_{u,v}(n,a)$, $\mathcal{B}=\mathcal{L}_{v,u}(n,b)$,
where

$\mathcal{L}_{u,v}(n,k):=\Big{\\{}L\in{[n]\choose k}:1\in
L,L\cap[2,v+1]\neq\emptyset\Big{\\}}\cup\Big{\\{}L\in{[n]\choose
k}:[2,u+1]\subset L\Big{\\}}.$

Putting $a=b,u=v,{\mathcal{A}}={\mathcal{B}}$, one retrieves Theorem 1. The
proof of Theorem 3 is given in Section 4. Note also that the statement does
not hold for $u=v=3$ with non-strict inequality on both sizes of
${\mathcal{A}}$ and ${\mathcal{B}}$: the families
${\mathcal{A}}=\mathcal{L}_{2,2}(n,a)$,
${\mathcal{B}}=\mathcal{L}_{2,2}(n,b)$, satisfy the inequality on the size
(note that $|\mathcal{L}_{2,2}(n,k)|=|\mathcal{L}_{3,3}(n,k)|$), but have much
larger diversity.

Let us deduce the following numerical corollary of the theorem above. For
simplicity, we only deal with $u=v=x$ case and with $n\geq 2\max\\{a,b\\}$.

######  Corollary 4.

Fix $a,b>0$ and $n\geq 2\max\\{a,b\\}$. If ${\mathcal{A}}\subset{[n]\choose
a}$ and ${\mathcal{B}}\subset{[n]\choose b}$ are cross-intersecting and, for
some $n-\min\\{a,b\\}-1\leq x\leq n-4$, $|{\mathcal{A}}|>{n-1\choose
a-1}-(1-\frac{a^{2}}{(n-a)^{2}}){x\choose a-1}$, $|{\mathcal{B}}|>{n-1\choose
b-1}-(1-\frac{b^{2}}{(n-b)^{2}}){x\choose b-1}$, then
$\gamma({\mathcal{A}})<{x\choose n-a-1}$ and $\gamma({\mathcal{B}})<{x\choose
n-b-1}$.

###### Proof.

For $n\geq 2k$ and $n-k-1\leq x\leq n-4$, the polynomial $p(x):={x\choose
n-k-1}/{x\choose k-1}$ is increasing (and for smaller $x\geq k-1$, the ratio
is $0$), and thus $p(x)\leq p(n-4)={n-4\choose k-3}/{n-4\choose
k-1}=\frac{(k-1)(k-2)}{(n-k-1)(n-k-2)}\leq\frac{k^{2}}{(n-k)^{2}}.$ Thus,
because of our assumption on $|{\mathcal{A}}|,\ |{\mathcal{B}}|$, we have
$|{\mathcal{A}}|\geq{n-1\choose a-1}-{x\choose a-1}+{x\choose n-a-1}$ and
similar inequality for ${\mathcal{B}}$. Theorem 3 then implies that the
diversities satisfy the desired inequalities. ∎

Statements concerning sizes of cross-intersecting families are often directly
related to the famous Kruskal–Katona theorem [31, 28], which is one of the
cornerstones of extremal set theory. Let us give the following definition.

######  Definition 1.

For a family ${\mathcal{F}}$, denote by $\partial^{l}{\mathcal{F}}$ the
collection of $l$-element sets that are contained in at least one set from
${\mathcal{F}}$. We call $\partial^{l}{\mathcal{F}}$ the $l$-shadow of
${\mathcal{F}}$. If ${\mathcal{F}}\subset{[n]\choose k}$ then we denote by
$\partial{\mathcal{F}}$ the immediate shadow $\partial^{k-1}{\mathcal{F}}$.

We state the Kruskal-Katona Theorem in the form proposed by Lovász.

######  Theorem 5.

If ${\mathcal{F}}$ is a family of $k$-element sets, such that for some real
$x\geq k$ we have $|{\mathcal{F}}|={x\choose k}$, then
$|\partial{\mathcal{F}}|\geq{x\choose k-1}$.

The other main result of this paper is a strengthening of Theorem 3 in the
Kruskal–Katona-type form. For a family ${\mathcal{F}}$ and integer $n$, define
the Kruskal-Katona diversity
$\gamma_{KK}({\mathcal{F}},n):=\min_{X,|X|=n}\big{|}{\mathcal{F}}\setminus{X\choose
k}\big{|}$. In Section 5, we will prove the following theorem.

######  Theorem 6.

Let $n>k>0$ and assume that ${\mathcal{F}}$ is a family of $k$-element sets,
such that $|{\mathcal{F}}|\geq{n\choose k}-{y\choose n-k}+{x\choose k-1}$ and
$\gamma_{KK}({\mathcal{F}},n)\geq{x\choose k-1}$ for some real numbers
$k-1\leq x\leq n-3$, $n-k\leq y\leq n-3$. Then
$\partial({\mathcal{F}})\geq{n\choose k-1}-{y\choose n-k+1}+{x\choose k-2}$.

Again, the theorem is sharp for integer $y,x$, as is witnessed by the example

$\mathcal{KK}_{x,y}:={[n]\choose
k}\setminus\big{\\{}S\subset[n]:[y+1,n]\subset
S\big{\\}}\cup\Big{\\{}S\cup\\{n+1\\}:S\in{[x]\choose k-1}\Big{\\}}.$

Moreover, one sees that $|\mathcal{KK}_{3,3}|=|\mathcal{KK}_{2,2}|$, and
$\mathcal{KK}_{2,2}$ has the same “distance” from three different subsets of
$[n+1]:$ $[n+1]\setminus\\{i\\}$, where $i\in[n-1,n+1]$. This means that the
range of $x$, $y$ in the theorem is in some sense best possible. From this
theorem, we can derive the following numerical corollary.

######  Corollary 7.

If $|{\mathcal{F}}|={n\choose k}$ and $\gamma_{KK}({\mathcal{F}},n)\geq
t:={x\choose k-1}$ for some $t\leq\\{{n-3\choose k-3},{n-3\choose k-1}\\},$
then $|\partial{\mathcal{F}}|\geq{n\choose
k-1}+\max\\{\frac{1}{n-k+1},\frac{1}{k-1}\\}{x\choose k-2}$.

###### Proof.

Find $y\leq n-3$ such that $|{\mathcal{F}}|={n\choose k}-{y\choose
n-k}+{x\choose k-1}$. It is easy to see that $n-k\leq y\leq n-2$ and $k-1\leq
x\leq n-2$. Then, by Theorem 6, $|\partial{\mathcal{F}}|\geq{n\choose
k-1}-{y\choose n-k+1}+{x\choose
k-2}\geq\min\\{\frac{1}{n-k+1},\frac{1}{k-1}\\}{x\choose k-2}$ since
${y\choose n-k+1}=\frac{y-n+k}{n-k+1}{y\choose
n-k}=\frac{y-n+k}{n-k+1}{x\choose
k-1}=\frac{(y-n+k)(x-(k-2))}{(n-k+1)(k-1)}{x\choose
k-2}\leq\frac{(k-2)(n-k)}{(n-k+1)(k-1)}{x\choose k-2}$. ∎

For two sets $A,B$, let $A\oplus B$ stand for the symmetric difference of $A$
and $B$. While we were preparing this paper, Keevash and Long [30] published
the following theorem.

######  Theorem 8 ([30]).

If $\delta_{0}\in(0,1)$ and ${\mathcal{A}}\subset{[n]\choose k}$ with
$|{\mathcal{A}}|={x\choose k}$ and $\partial A\leq(1+\frac{c}{x}){x\choose
k-1}$, with $c:=10^{-9}\delta_{0}$, then $|{\mathcal{A}}\oplus{S\choose
k}|\leq\delta_{0}{|S|-1\choose k-1}$ for some $S\subset[n]$.

Theorems 6 and Theorem 8 deal with stability in similar scenarios, as one sees
in Corollary 7, however, none implies the other. Where applicable, Theorem 6
gives better (sharp) bounds, and its range is at least big for $k$ comparable
to $n$ and especially for $k$ that are close to $n$. However, for $n$ large
w.r.t. $k$, it works for the families that are closer to ${S\choose k}$ for
some set $S$ than Theorem 8.

One advantage of Theorem 6 is that it has a much less technical proof
(especially in terms of computations) than that of Theorem 8. We could have
made our conclusions work in a wider range, but then it would have made the
statements and the proofs uglier, which, in view of Theorem 8, we decided to
avoid. The two proofs share one important ingredient: to deal with families
with very large diversity, we continuously transform the family into one that
has smaller, but not too small, diversity, using combinatorial operations, in
particular, the so-called Daykin shifts (cf. Section 3). A similar approach
appeared earlier in the paper by Zakharov and the second author [32] to obtain
Theorem 1, and our analysis resembles that of [32]. However, in [32], (normal)
shifts were used, together with some other exchange operation. For other
stability results on Kruskal–Katona theorem, cf. [29, 37].

Let $r\geq 2,t\geq 1$ be integers. We say that a family ${\mathcal{F}}\subset
2^{[n]}$ is $r$-wise $t$-intersecting if $|F_{1}\cap\ldots F_{r}|\geq t$ for
any $F_{1},\ldots,F_{r}\in{\mathcal{F}}$. If $r=2$, then we sometimes omit
“$2$-wise” for brevity. Similarly, we shorten “$r$-wise $1$-intersecting” to
“$r$-wise intersecting”.

######  Theorem 9.

Fix integers $r\geq 3$ and $t\geq 1$. Then for $n>\max\\{15,2(r+t)\\}k$ and an
$r$-wise $t$-intersecting family ${\mathcal{F}}\subset{[n]\choose k}$ we have

(2) $\gamma({\mathcal{F}})\leq{n-r-t\choose k-r-t+1}.$

The theorem is tight, as witnessed by the example $\\{F\in{[n]\choose
k}:F\cap[r+t]\geq r+t-1\\}$. We give the proof of Theorem 9 in Section 6. We
note the case $r=2$ seems to be the hardest. For $r=2,t=1$, this corresponds
to the “diversity of intersecting families” question of Katona, discussed in
the beginning of the introduction, and thus the same statement is true for
$n>Ck$ with some absolute constant $C$. For $r=2$ and $t\geq 2$, it seems that
it is possible to resolve by generalizing techniques of the second author from
[33]. The case of shifted families is easy, see Corollary 14.

For a family ${\mathcal{F}}\subset 2^{[n]}$, let the matching number
$\nu({\mathcal{F}})$ stand for the largest $s$, such that there are
$F_{1},\ldots,F_{s}\in{\mathcal{F}}$, satisfying $F_{i}\cap F_{j}=\emptyset$
for $1\leq i<j\leq s$. In particular, $\nu({\mathcal{F}})=1$ if and only if
${\mathcal{F}}$ is intersecting. The $s$-diversity $\gamma_{s}({\mathcal{F}})$
of ${\mathcal{F}}\subset 2^{[n]}$ is defined as

$\gamma_{s}({\mathcal{F}}):=\min\Big{\\{}\big{|}\\{F\in{\mathcal{F}}:F\cap
R=\emptyset\big{|}\ :\ R\in{[n]\choose s}\Big{\\}}.$

This notion seems to be the correct generalization of the notion of diversity
to families ${\mathcal{F}}$ with $\nu({\mathcal{F}})=s$. For $s=1$, we get
back the usual notion of diversity. In Section 7, we determine the maximum
value of $\gamma_{s}({\mathcal{F}})$ for ${\mathcal{F}}\subset{[n]\choose k}$
for all $n>n_{0}(s,k)$ (and completely resolve the $k=2$ case).

In the next section, we recall the definition of shifting and discuss some of
its properties. Lemma 16 (“shifted families are positively correlated”),
although simple, appears to be a new and useful tool in the study of shifted
families. In Section 3, we discuss the Kruskal–Katona theorem and some other,
more advanced, tools.

Most of the results that we present are for uniform families. However, we
prove some results in the non-uniform case as well. For diversity of $r$-wise
$t$-intersecting families in $2^{[n]}$, see Corollary 15 (shifted case) and
Section 8 (general case).

##  2\. Shifting and initial families

For a set $F\subset[n]$, a family ${\mathcal{F}}\subset 2^{[n]}$ and $1\leq
i<j\leq n$, one defines the $i\leftarrow j$ shift $S_{ij}$ by

$\displaystyle S_{ij}(F):=$
$\displaystyle\begin{cases}(F-\\{j\\})\cup\\{i\\}&\mbox{if
}F\cap\\{i,j\\}=j,\\\ F&\mbox{otherwise};\end{cases}$ $\displaystyle
S_{ij}({\mathcal{F}}):=$ $\displaystyle\ \big{\\{}S_{ij}(F)\ :\
F\in{\mathcal{F}}\big{\\}}\cup\big{\\{}F\ :\
F,S_{ij}(F)\in{\mathcal{F}}\big{\\}}.$

It is easy to see that $|S_{ij}({\mathcal{F}})|=|{\mathcal{F}}|$. Since
$|S_{ij}(F)|=|F|$, should ${\mathcal{F}}$ be $k$-uniform, then so is
$S_{ij}({\mathcal{F}})$.

######  Proposition 10 ([6, 13]).

  * (i)

If ${\mathcal{F}}$ is $r$-wise $t$-intersecting then so is
$S_{ij}({\mathcal{F}})$;

  * (ii)

$\nu\big{(}S_{ij}({\mathcal{F}})\big{)}\leq\nu({\mathcal{F}})$.

Given ${\mathcal{F}}\subset 2^{[n]}$ and two disjoint sets $X,Y\subset[n]$, we
define

${\mathcal{F}}(X\bar{Y}):=\big{\\{}F\setminus X:F\in{\mathcal{F}},F\cap(X\cup
Y)=X\big{\\}}.$

For $X=\\{i\\}$, $Y=\\{j\\}$ we write ${\mathcal{F}}(i\bar{j})$ instead of
${\mathcal{F}}\big{(}\\{i\\}\overline{\\{j\\}}\big{)}$. We define
${\mathcal{F}}(X)$, ${\mathcal{F}}(\bar{Y})$ similarly.

The following proposition is obvious from the definitions of the $i\leftarrow
j$ shift and diversity.

######  Proposition 11.

The following properties hold.

  * (i)

For $x\in[n]\setminus\\{i,j\\}$,
$d_{S_{ij}({\mathcal{F}})}(x)=d_{{\mathcal{F}}}(x)$;

  * (ii)

$d_{S_{ij}({\mathcal{F}})}(j)\leq
d_{S_{ij}({\mathcal{F}})}(i)=d_{{\mathcal{F}}}(i)+\big{|}{\mathcal{F}}(\bar{i}j)\setminus{\mathcal{F}}(i\bar{j})\big{|}=d_{{\mathcal{F}}}(j)+\big{|}{\mathcal{F}}(i\bar{j})\setminus{\mathcal{F}}(\bar{i}j)\big{|}$;

  * (iii)

$\gamma(S_{ij}({\mathcal{F}}))\geq\gamma({\mathcal{F}})-\min\big{\\{}\big{|}{\mathcal{F}}(\bar{i}j)\setminus{\mathcal{F}}(i\bar{j})\big{|},\big{|}{\mathcal{F}}(i\bar{j})\setminus{\mathcal{F}}(\bar{i}j)\big{|}\big{\\}}\geq\gamma({\mathcal{F}})-\big{|}{\mathcal{F}}(i\bar{j})\oplus{\mathcal{F}}(\bar{i}j)\big{|}/2$.

If $\\{x_{1},\ldots,x_{k}\\}\subset[n]$ and $x_{1}<\ldots<x_{k}$ then we also
denote it by $(x_{1},\ldots,x_{k})$. One defines the shifting partial order
$\prec_{s}$ by

$(x_{1},\ldots,x_{k})\prec_{s}(y_{1},\ldots,y_{k})\text{ iff }x_{i}\leq
y_{i}\text{ for all }1\leq i\leq k.$

This can be naturally extended to $F,G\in{[n]\choose k}$ by arranging the
elements of $F$ and $G$ in increasing order.

######  Definition 2.

A family ${\mathcal{F}}\subset 2^{[n]}$ is called shifted if
$G\prec_{s}F\in{\mathcal{F}}$ implies $G\in{\mathcal{F}}$.

Note that repeated applications of the $i\leftarrow j$ shifts, $1\leq i<j\leq
n$ eventually produces a shifted family. The following statement should be
obvious.

######  Proposition 12.

Suppose that ${\mathcal{F}}\subset 2^{[n]}$ is shifted. Then (i) and (ii)
hold.

  * (i)

$d_{{\mathcal{F}}}(1)\geq\ldots\geq d_{{\mathcal{F}}}(n)$,

  * (ii)

$\gamma({\mathcal{F}})=|{\mathcal{F}}(\bar{1})|=|{\mathcal{F}}|-d_{{\mathcal{F}}}(1)$.

In many cases, the following easy result reduces the maximum diversity problem
for shifted families to well-known extremal results.

######  Lemma 13 ([13]).

Suppose that ${\mathcal{F}}\subset 2^{[n]}$ is $r$-wise $t$-intersecting and
shifted. Then ${\mathcal{F}}(\bar{1})$ is $r$-wise $(t+r-1)$-intersecting.

###### Proof.

Assume for contradiction that there exist
$G_{1},\ldots,G_{r}\in{\mathcal{F}}(\bar{1})$ satisfying $G_{1}\cap\ldots\cap
G_{r}=\\{x_{1},\ldots,x_{r+t-2}\\}$. Set
$F_{i}:=(G_{i}\setminus\\{x_{i}\\})\cup\\{1\\}$ for $i=1,\ldots,r-1$ and
$F_{r}:=G_{r}$. Then $F_{i}\in{\mathcal{F}}$ by shiftedness and

$F_{1}\cap\ldots\cap F_{r}=\\{x_{r},\ldots,x_{r+t-2}\\},$

contradicting the $r$-wise $t$-intersecting property. ∎

######  Corollary 14.

Suppose that $n\geq 1+(k-t)(t+2)$ and ${\mathcal{F}}\subset{[n]\choose k}$ is
$2$-wise $t$-intersecting and shifted. Then

(3) $\gamma({\mathcal{F}})\leq{n-t-2\choose k-t-1}.$

###### Proof.

Since $\gamma({\mathcal{F}})=|{\mathcal{F}}(\bar{1})|$ by Proposition 12 (ii),
we need to show $|{\mathcal{F}}(\bar{1})|\leq{n-t-2\choose k-t-1}$. By Lemma
13, the family ${\mathcal{F}}(\bar{1})\subset{[2,n]\choose k}$ is $2$-wise
$(t+1)$-intersecting. Now (3) follows from the Complete Erdős-Ko-Rado Theorem
[11, 38]. ∎

######  Corollary 15.

Suppose that $r\geq 3$, $t\leq 2^{r}-2r$ and ${\mathcal{F}}\subset 2^{[n]}$ is
$r$-wise $t$-intersecting and shifted. Then

(4) $\gamma({\mathcal{F}})\leq 2^{n-r-t}.$

The family

${\mathcal{A}}:=\big{\\{}A\subset[n]\ :\ |A\cap[r+t]|\geq r+t-1\big{\\}}$

shows that (4) is best possible for $n\geq r+t$.

###### Proof.

Note that ${\mathcal{F}}(\bar{1})$ is $r$-wise $(r+t-1)$-intersecting and
$r+t-1\leq 2^{r}-r-1$ by our assumption. Thus (4) follows from the bound on
the size of $r$-wise $(r+t-1)$-intersecting families, proved in [14]. ∎

Let us also remark that for $n<r+t$ one has $\gamma({\mathcal{F}})=0$ whenever
${\mathcal{F}}$ is $r$-wise $t$-intersecting. For the results on diversity of
$r$-wise $t$-intersecting families ${\mathcal{F}}\subset 2^{[n]}$ that are not
necessarily shifted, see Section 8.

In the next lemma we show that any two shifted families are positively
correlated. (And thus behave similarly to up-sets in this respect.) It proved
to be very useful in our proof. We believe that it will have more applications
to other problems involving shifted families.

######  Lemma 16 (“Shifted families are positively correlated”).

Let ${\mathcal{F}}_{1},{\mathcal{F}}_{2}\subset{[n]\choose k}$ be shifted.
Then

(5)
$|{\mathcal{F}}_{1}\cap{\mathcal{F}}_{2}|\geq|{\mathcal{F}}_{1}||{\mathcal{F}}_{2}|/{n\choose
k}.$

###### Proof.

Let us apply induction on $k$, and for fixed $k$ induction on $n$. The case
$n=k$ is trivial, as well as the case $k=1$. Suppose that $n>k>1$ and that (5)
holds for $n-1,k-1$ and $n-1,k$.

Note that ${\mathcal{F}}_{i}(1)\subset{[2,n]\choose k-1}$ and
${\mathcal{F}}_{i}(\bar{1})\subset{[2,n]\choose k}$, $i=1,2$. These families
are shifted. Therefore, by induction we have

(6)
$|{\mathcal{F}}_{1}(1)\cap{\mathcal{F}}_{2}(1)|\geq\frac{|{\mathcal{F}}_{1}(1)||{\mathcal{F}}_{2}(1)|}{{n-1\choose
k-1}},\ \ \ \ \ \ \ \
|{\mathcal{F}}_{1}(\bar{1})\cap{\mathcal{F}}_{2}(\bar{1})|\geq\frac{|{\mathcal{F}}_{1}(\bar{1})||{\mathcal{F}}_{2}(\bar{1})|}{{n-1\choose
k}}.$

Due to shiftedness, $\Delta({\mathcal{F}}_{i})=|{\mathcal{F}}_{i}(1)|$ for
$i=1,2,$ and so

(7) $\frac{|{\mathcal{F}}_{i}(1)|}{{n-1\choose
k-1}}\geq\frac{|{\mathcal{F}}_{i}(\bar{1})|}{{n-1\choose k}}.$

We have

$\displaystyle|{\mathcal{F}}_{1}\cap{\mathcal{F}}_{2}|=$
$\displaystyle|{\mathcal{F}}_{1}(1)\cap{\mathcal{F}}_{2}(1)|+|{\mathcal{F}}_{1}(\bar{1})\cap{\mathcal{F}}_{2}(\bar{1})|\overset{\eqref{eqshift1}}{\geq}\frac{|{\mathcal{F}}_{1}(1)||{\mathcal{F}}_{2}(1)|}{{n-1\choose
k-1}}+\frac{|{\mathcal{F}}_{1}(\bar{1})||{\mathcal{F}}_{2}(\bar{1})|}{{n-1\choose
k}}$ $\displaystyle=$
$\displaystyle\frac{|{\mathcal{F}}_{1}||{\mathcal{F}}_{2}|}{{n\choose
k}}+\frac{\big{(}{n-1\choose k}|{\mathcal{F}}_{1}(1)|-{n-1\choose
k-1}|{\mathcal{F}}_{1}(\bar{1})|\big{)}\cdot\big{(}{n-1\choose
k}|{\mathcal{F}}_{2}(1)|-{n-1\choose
k-1}|{\mathcal{F}}_{2}(\bar{1})|\big{)}}{{n\choose k}{n-1\choose k}{n-1\choose
k-1}}$ $\displaystyle\overset{\eqref{eqshift3}}{\geq}$
$\displaystyle\frac{|{\mathcal{F}}_{1}||{\mathcal{F}}_{2}|}{{n\choose k}},$

where the equality between the first and second lines is easy to verify by
direct computation (multiplying out the brackets in the latter expression). ∎

##  3\. Advanced tools

It was first observed by Daykin [2] that Theorem 5 implies Theorem 2. Let us
show this relationship and restate Theorem 5 in terms of cross-intersecting
families.

######  Corollary 17.

Let $n\geq a+b$. If ${\mathcal{A}}\subset{[n]\choose a}$ and
${\mathcal{B}}\subset{[n]\choose b}$ are cross-intersecting and
$|{\mathcal{A}}|\geq{x\choose n-a}$ for some $n-a\leq x\leq n$, then
$|{\mathcal{B}}|\leq{n\choose b}-{x\choose b}$.

Although it is rather standard, we give the proof for completeness.

###### Proof.

Consider the family ${\mathcal{A}}^{c}:=\\{[n]\setminus
A:A\in{\mathcal{A}}\\}$. We have
$|{\mathcal{A}}^{c}|=|{\mathcal{A}}|\geq{x\choose n-a}$, and, using Theorem 5,
we get $|\partial^{b}{\mathcal{A}}^{c}|\geq{x\choose b}$ (note that, in case
$n=a+b$, $\partial^{b}{\mathcal{A}}^{c}={\mathcal{A}}^{c}$ and thus we do not
even need Theorem 5). It should be clear that ${\mathcal{B}}$ and
$\partial^{b}{\mathcal{A}}^{c}$ are disjoint, which implies the bound in the
corollary. ∎

Recall that “$\oplus$” stands for symmetric difference. Let us next state the
Kruskal–Katona theorem in terms of (co)lexicographic order. For two sets
$A,B\subset{[n]\choose k}$ we say that $A\prec_{lex}B$ or that $A$ precedes
$B$ in the lexicographic order, if the smallest element in $A\oplus B$ belongs
to $A$. Similarly, $A\prec_{colex}B$ if the largest element in $A\oplus B$
belongs to $B$. We note that if $A\prec_{s}B$, then both $A\prec_{lex}B$ and
$A\prec_{colex}B$. If for some $t$ ${\mathcal{F}}\subset{[n]\choose k}$
consists of the $t$ first sets in the lexicographic order, then we call
${\mathcal{F}}$ an initial segment (in the lexicographic order), and similarly
for the colexicographic order. For a set $X$ and integers $t,k$, let us denote
$\mathcal{L}(X,t,k)$ the family of the first $t$ $k$-element subsets of $X$ in
the lexicographic order (the initial segment of size $t$ in ${X\choose k}$),
and define $\mathcal{C}(X,t,k)$ similarly for colexicographic order.

The following is the classic form of the Kruskal-Katona theorem.

######  Theorem 18 ([31, 28]).

If ${\mathcal{F}}\subset{[n]\choose k}$, then
$|\partial{\mathcal{F}}|\geq\partial\mathcal{C}([n],|{\mathcal{F}}|,k)$.

Similarly, one can derive a slightly weaker version of Theorem 18 in terms of
cross-intersecting families. This was observed by Hilton [22].

######  Corollary 19.

Let $n\geq a+b$ and assume that ${\mathcal{A}}\subset{[n]\choose a}$,
${\mathcal{B}}\subset{[n]\choose b}$ are cross-intersecting. Then
$\mathcal{L}([n],|{\mathcal{A}}|,a)$ and $\mathcal{L}([n],|{\mathcal{B}}|,b)$
are cross-intersecting.

Fix any two disjoint sets $U,V$ of the same size. The following operation,
which generalizes shifting, was introduced by Daykin [1]. For a set $F$, the
$U\leftarrow V$ shift $S_{U,V}(F)$ is $S_{U,V}(F):=(F\setminus V)\cup U$ if
$F\cap(V\cup U)=V$, and $S_{U,V}(F):=F$ otherwise. For a family
${\mathcal{F}}\subset 2^{[n]}$, define

$S_{U,V}({\mathcal{F}}):=\big{\\{}S_{U,V}(F):F\in{\mathcal{F}}\big{\\}}\cup\big{\\{}F:F,S_{U,V}(F)\in{\mathcal{F}}\big{\\}}.$

Daykin used it in the following setting. Take integers $n>k>0$ and consider a
family ${\mathcal{F}}\subset{[n]\choose k}$. If ${\mathcal{F}}$ is not an
initial segment in the colex order, then there exists a pair $(U,V)$ of
disjoint sets, such that $|U|=|V|$, $U\prec_{colex}V$ and a set
$F\in{\mathcal{F}}$ satisfying $F\cap(U\cup V)=V$, such that $(F\setminus
V)\cup U$ is not in ${\mathcal{F}}$. Take such pair $(U,V)$ that is inclusion-
minimal and apply $S_{U,V}$ to ${\mathcal{F}}$. To underline the choice of $U$
and $V$, we denote any such $S_{U,V}$-shift by $S_{U,V}^{colex}$.

The next lemma is the essence of Daykin’s short and elegant proof of the
Kruskal–Katona Theorem.

######  Lemma 20.

We have $\big{|}\partial
S_{U,V}^{colex}({\mathcal{F}})\big{|}\leq|\partial{\mathcal{F}}|$.

We can define a similar operation in the cross-intersecting setting. Take
integers $a,b,n$, where $n\geq a+b$, and cross-intersecting families
${\mathcal{A}}\subset{[n]\choose a}$, ${\mathcal{B}}\subset{[n]\choose b}$.
Assume that ${\mathcal{A}}$ and ${\mathcal{B}}$ are not initial segments in
the lexicographic order. Then we can find members $A\in{\mathcal{A}}$,
$B\in{\mathcal{B}}$ and pairwise disjoint sets $(U,V)$ and
$(U^{\prime},V^{\prime})$ such that $|U|=|V|,$ $|U^{\prime}|=|V^{\prime}|$,
$U\prec_{lex}V$, $U^{\prime}\prec_{lex}V^{\prime}$, $A\cap(U\cup V)=V$,
$B\cap(U^{\prime}\cup V^{\prime})=V^{\prime}$ and the sets $(A\setminus V)\cup
U$, $(B\setminus V^{\prime})\cup U^{\prime}$ are not in ${\mathcal{A}}$ and
${\mathcal{B}}$, respectively. Let us choose the sets that are inclusion-
minimal and assume by symmetry that $|U|\leq|U^{\prime}|$. Then the operation
$S_{U,V}$ for any such pair $U,V$ is denoted by $S_{U,V}^{lex}$.

The next lemma is essentially Lemma 20 restated in cross-intersecting terms.

######  Lemma 21.

If ${\mathcal{A}}$ and ${\mathcal{B}}$ are cross-intersecting and $U,V$ are as
above, then the families $S_{U,V}^{lex}({\mathcal{A}})$ and
$S_{U,V}^{lex}({\mathcal{B}})$ are cross-intersecting as well.

Since Daykin did not state this statement in the above form, we provide the
proof. Note the role of $U,V$ being inclusion-minimal. We also note that in
the symmetric cross-intersecting setting, the proof becomes slightly easier.

###### Proof.

Arguing for contradiction, we may assume by symmetry that there is $A\in
S_{U,V}^{lex}({\mathcal{A}})\setminus{\mathcal{A}}$ and $B\in
S_{U,V}^{lex}({\mathcal{B}})$ that are disjoint. Now $A\cap(U\cup V)=U$
implies $B\cap U=\emptyset$, in particular $B\in{\mathcal{B}}$. Note also that
$A\in S_{U,V}^{lex}({\mathcal{A}})\setminus{\mathcal{A}}$ implies that
$\tilde{A}:=(A\setminus U)\cup V$ is in ${\mathcal{A}}\setminus
S_{U,V}^{lex}({\mathcal{A}})$.

We distinguish two cases.

(i) $V\subset B$. By definition, $S_{U,V}(B)=(B\setminus V)\cup
U\in{\mathcal{B}}$ follows. However,
$S_{U,V}^{lex}(B)\cap\tilde{A}=\emptyset$, contradicting the cross-
intersection property of ${\mathcal{A}}$ and ${\mathcal{B}}$.

(ii) $V\not\subset B$. Define $\tilde{V}:=B\cap V$, a proper subset of $V$.
Let $\tilde{U}\subset U$ be the subset of $U$ that consists of $|\tilde{V}|$
smallest elements of $U$. Then $\tilde{U}\prec_{lex}\tilde{V}$.111Note that
this would not necessarily hold for colex.

By the choice of $U$ being inclusion-minimal,
$\tilde{B}:=(B\setminus\tilde{V})\cup\tilde{U}\in{\mathcal{B}}$. However,
$\tilde{B}\cap V=\emptyset$, $\tilde{A}\cap U=\emptyset$ and on
$[n]\setminus(U\cup V)$ $\tilde{A}$ and $\tilde{B}$ coincide with $A$ and $B$.
Consequently, $\tilde{A}\cap\tilde{B}=\emptyset$, the final contradiction. ∎

In the proof of Theorem 3, we shall need the following lemma, resemblant of
[20, Lemma 2].

######  Lemma 22.

Fix integers $s\geq 2,t\geq 2$ and $m\geq s+t-1$.

  * (i)

The function $f(x,m,t,s):={x\choose t-1}\cdot\frac{{m-3\choose
s-2}}{{m-3\choose t-2}}-{x\choose m-s}$ is monotone increasing for $m-s\leq
x\leq m-3$, and is strictly monotone increasing if additionally $m\geq s+t$.

  * (ii)

Moreover, if $s\geq 3$ and $f(x,m,t,s)\geq f(m-3,m,t,s)$ for some $x>m-3$,
then $f(y,m,t,s)\geq f(m-3,m,t,s)$ for any $m-3\leq y\leq x$.

  * (iii)

In particular, $f(y,m,t,s)\geq f(m-3,m,t,s)$ for any $m-3\leq y\leq m-2$ and
$s\geq 2$.

###### Proof.

For $m=s+t-1$ $f$ is constant as a function of $x$. Thus, (i)–(iii) are
obvious in this case. In what follows, we assume that $m\geq s+t$.

(i) For $s=2$ there is nothing to prove. Assume that $x\geq m-s$ and $s\geq
3$. We have

$f^{\prime}(x,m,t,s)={x\choose t-1}\cdot\frac{{m-3\choose s-2}}{{m-3\choose
t-2}}\cdot\sum_{i=0}^{t-2}\frac{1}{x-i}-{x\choose
m-s}\cdot\sum_{i=0}^{m-s-1}\frac{1}{x-i}.$

Thus, proving $f^{\prime}(x,m,t,s)>0$ is equivalent to proving

(8) $\frac{{x\choose t-1}{m-3\choose s-2}}{{x\choose m-s}{m-3\choose
t-2}}>1+\frac{\sum_{i=t-1}^{m-s-1}\frac{1}{x-i}}{\sum_{i=0}^{t-2}\frac{1}{x-i}}.$

The right hand side of (8) is strictly smaller than

$g(x,m,t,s):=1+\frac{(m-s-t+1)/(x-(m-s-1))}{(t-1)/x}=1+\frac{(m-s-t+1)x}{(x-m+s+1)(t-1)}.$

It is clear that $g(x,m,t,s)\cdot(x-m+s+1)$ is monotone increasing as $x$
increases. On the other hand,

$\frac{{x\choose t-1}{m-3\choose s-2}}{{x\choose m-s}{m-3\choose
t-2}}\cdot(x-m+s+1)=\frac{{m-3\choose s-2}}{{m-3\choose
t-2}}\cdot\frac{(m-s)(m-s-1)\ldots t}{(x-t+2)(x-t+1)\ldots(x-m+s+2)},$

and thus the right hand side of (8) times $(x-m+s+1)$ is monotone decreasing
as $x$ grows. Thus, in order to verify (8) for any $m-s\leq x\leq m-3$, it is
sufficient to show that

$\frac{{x\choose t-1}{m-3\choose s-2}}{{x\choose m-s}{m-3\choose t-2}}\geq
1+\frac{(m-s-t+1)x}{(x-m+s+1)(t-1)}$

for $x=m-3$. Substituting the value of $x$ and rewriting, we obtain the
inequality

$\displaystyle\frac{{m-3\choose t-1}{m-3\choose s-2}}{{m-3\choose
s-3}{m-3\choose t-2}}-\frac{(m-s-t+1)(m-3)}{(s-2)(t-1)}\geq 1$
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{(m-t-1)(m-s)}{(s-2)(t-1)}-\frac{((m-s)-(t-1))((m-t-1)+(t-2))}{(s-2)(t-1)}\geq
1$ $\displaystyle\Leftrightarrow$
$\displaystyle\frac{(t-1)((m-t-1)+(t-2))-(m-s)(t-2)}{(s-2)(t-1)}\geq 1$
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{(t-1)(s-3)+(m-s)}{(s-2)(t-1)}\geq 1.$

The last inequality clearly holds, since $m-s\geq t-1$.

(ii) Assume that this is not the case. Then there are $p,q$ such that
$m-3<p<q\leq y$, $f(q,m,t,s)<f(m-3,m,t,s)<f(p,m,t,s)$ and
$f^{\prime}(q,m,t,s)=f^{\prime}(p,m,t,s)=0$. Whenever $f^{\prime}(z,m,t,s)=0$,
we have

${z\choose t-1}\cdot\frac{{m-3\choose s-2}}{{m-3\choose t-2}}={z\choose
m-s}\cdot\frac{\sum_{i=0}^{m-s-1}\frac{1}{z-i}}{\sum_{i=0}^{t-2}\frac{1}{z-i}},$

and thus $f(z,m,t,s)=h(z,m,t,s)$, where

$h(z,m,t,s)={z\choose
m-s}\cdot\frac{\sum_{i=t-1}^{m-s-1}\frac{1}{z-i}}{\sum_{i=0}^{t-2}\frac{1}{z-i}}.$

It is easy to see that $h(z,m,t,s)$ is a monotone increasing function of
$z$,222in fact, even $h(z,m,t,s)\cdot\sum_{i=0}^{t-2}\frac{1}{z-i}$ is
monotone increasing and thus $f(m-3,m,t,s)<f(p,m,t,s)=h(p,m,t,s)\leq
h(q,m,t,s)=f(q,m,t,s)$, contradicting our assumption.

(iii) In view of (ii), for $s\geq 3$ it is sufficient to verify that
$f(m-3,m,t,s)\leq f(m-2,m,t,s)$. We have

$f(m-2,m,t,s)-f(m-3,m,t,s)={m-3\choose t-2}\cdot\frac{{m-3\choose
s-2}}{{m-3\choose t-2}}-{m-3\choose m-s-1}=0.$

For $s=2$ and $y<m-2$ this is obvious. The case $s=2,y=m-2$ is a
straightforward computation. ∎

The following theorem was proven by Frankl, Lee, Siggers and Tokushige [18].

######  Theorem 23 ([18]).

For every $k\geq t\geq 14$ and $n\geq(t+1)k$ we have the following. If
${\mathcal{A}},{\mathcal{B}}\subset{[n]\choose k}$ are cross $t$-intersecting,
then $|{\mathcal{A}}||{\mathcal{B}}|\leq{n-t\choose k-t}^{2}$.

We can derive the following corollary for $t<14$.

######  Corollary 24.

Fix some $k\geq t>0$ and an integer $\alpha$. If the statement of Theorem 23
is valid for $k+\alpha,t+\alpha$ and $n+\alpha\geq n_{0}+\alpha$ playing the
roles of $k,t,n$, then it is valid for $k,t$ and $n\geq n_{0}$. In particular,
Theorem 23 is valid for any $k\geq t\geq 1$ and $n\geq\max\\{15k,(t+1)k\\}$.

###### Proof.

Given cross $t$-intersecting families
${\mathcal{A}},{\mathcal{B}}\subset{[n]\choose k}$, we obtain families
${\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}\subset{[n+\alpha]\choose
k+\alpha}$, where
${\mathcal{A}}^{\prime}:=\\{A\cup[n+1,n+\alpha]:A\in{\mathcal{A}}\\}$ and
${\mathcal{B}}^{\prime}$ is defined similarly. Then, clearly,
${\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}$ are cross
$(t+\alpha)$-intersecting, and thus
$|{\mathcal{A}}^{\prime}||{\mathcal{B}}^{\prime}|\leq{(n+\alpha)-(t+\alpha)\choose(k+\alpha)-(t+\alpha)}^{2}={n-t\choose
k-t}^{2}$ since the conditions of Theorem 23 hold for
${\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}$. Since
$|{\mathcal{A}}|=|{\mathcal{A}}^{\prime}|$ and
$|{\mathcal{B}}|=|{\mathcal{B}}^{\prime}|$, the conclusion of the theorem is
valid for ${\mathcal{A}},{\mathcal{B}}$ as well. The second part of the
statement follows directly from the first one and Theorem 23. ∎

##  4\. Cross-intersecting families. Proof of Theorem 3

Take $u,v$ and ${\mathcal{A}},\ {\mathcal{B}}$ as in the statement. The proof
of the theorem consists of the following two lemmas. The first one handles the
case when the diversities of the families ${\mathcal{A}},{\mathcal{B}}$ are
not too large.

######  Lemma 25.

Theorem 3 is valid, provided that additionally
$\gamma({\mathcal{A}})={n-u^{\prime}-1\choose n-a-1}$ and
$\gamma({\mathcal{B}})={n-v^{\prime}-1\choose n-b-1}$ for some
$u^{\prime},v^{\prime}\geq 2$.

###### Proof.

Recall that we put ${x\choose k}:=0$ for $x<k$. Arguing indirectly, assume
that $u^{\prime}\leq u.$ W.l.o.g., suppose that element $1$ has the largest
degree in ${\mathcal{A}}$. Clearly, ${\mathcal{A}}(1)$ and
${\mathcal{B}}(\bar{1})$, as well as ${\mathcal{B}}(1)$ and
${\mathcal{A}}(\bar{1})$, are cross-intersecting.

By Corollary 17 we conclude that $|{\mathcal{B}}(1)|\leq{n-1\choose
b-1}-{n-u^{\prime}-1\choose b-1}$. Since $|{\mathcal{B}}|\geq{n-1\choose
b-1}-{n-u-1\choose b-1}+{n-v-1\choose n-b-1}$, we have $v^{\prime}\leq v$.
Thus, diversity of ${\mathcal{B}}$ is non-zero and we similarly have
$|{\mathcal{A}}(1)|\leq{n-1\choose a-1}-{n-v^{\prime}-1\choose a-1}$.

Let us consider the following expression:

$E:=\Big{(}{n-1\choose a-1}-|{\mathcal{A}}|\Big{)}+\frac{{n-4\choose
a-2}}{{n-4\choose b-2}}\Big{(}{n-1\choose b-1}-|{\mathcal{B}}|\Big{)}.$

On the one hand, by our assumptions on $|{\mathcal{A}}|$ and
$|{\mathcal{B}}|$,

(9) $E<\Big{(}{n-v-1\choose a-1}-{n-u-1\choose n-a-1}\Big{)}+\frac{{n-4\choose
a-2}}{{n-4\choose b-2}}\Big{(}{n-u-1\choose b-1}-{n-v-1\choose n-b-1}\Big{)}.$

On the other hand, due to the bounds on $|{\mathcal{A}}(1)|$ and
$|{\mathcal{B}}(1)|$ above, we have

$\displaystyle E\ \geq$ $\displaystyle\ \Big{(}{n-v^{\prime}-1\choose
a-1}-\frac{{n-4\choose a-2}}{{n-4\choose b-2}}{n-v^{\prime}-1\choose
n-b-1}\Big{)}+\Big{(}\frac{{n-4\choose a-2}}{{n-4\choose
b-2}}{n-u^{\prime}-1\choose b-1}-{n-u^{\prime}-1\choose n-a-1}\Big{)}$
$\displaystyle=$ $\displaystyle\ \frac{{n-4\choose a-2}}{{n-4\choose
b-2}}f(n-v^{\prime}-1,n-1,a,b)+f(n-u^{\prime}-1,n-1,b,a),$

where the function $f$ is as in Lemma 22. We have shown in Lemma 22 that
$f(x,m,t,s)$ increases as $x$ increases, as long as $m-s\leq x\leq m-3$, and
that $f(x,m,t,s)\geq f(m-3,m,t,s)$ for $m-3\leq x\leq m-2$. This, combined
with the assumption $2\leq v^{\prime}\leq v$, and $2\leq u^{\prime}\leq u$,
allows us to conclude

$\displaystyle E\ \geq\ $ $\displaystyle\frac{{n-4\choose a-2}}{{n-4\choose
b-2}}f(n-v-1,n-1,a,b)+f(n-u-1,n-1,b,a)$ (10) $\displaystyle=\ $
$\displaystyle\Big{(}{n-v-1\choose a-1}-{n-u-1\choose
n-a-1}\Big{)}+\frac{{n-4\choose a-2}}{{n-4\choose b-2}}\Big{(}{n-u-1\choose
b-1}-{n-v-1\choose n-b-1}\Big{)}.$

Inequalities (9) and (10) contradict each other, which implies that our
assumption on $u^{\prime}$ was wrong, and thus
$\gamma({\mathcal{A}})<{n-u-1\choose n-a-1}$. The same holds for
${\mathcal{B}}$. Finally, note that we have actually shown that
$|{\mathcal{A}}(\bar{1})|<{n-u-1\choose a-1}$, and thus
$|{\mathcal{B}}(\bar{1})|<{n-v-1\choose b-1}$, which implies that $1$ has the
largest degree in both families. ∎

The second lemma allows us to reduce the case of (at least) one of the
families having large diversity to the case handled in Lemma 25.

######  Lemma 26.

Given ${\mathcal{A}}$, ${\mathcal{B}}$ satisfying the conditions of Theorem 3,
there exist cross-intersecting families ${\mathcal{A}}^{\prime},$
${\mathcal{B}}^{\prime}$ with $\gamma({\mathcal{A}}^{\prime})\leq{n-3\choose
a-2}$, $\gamma({\mathcal{B}})\leq{n-3\choose b-2}$ and such that
$|{\mathcal{A}}^{\prime}|\geq|{\mathcal{A}}|$,
$|{\mathcal{B}}^{\prime}|\geq|{\mathcal{B}}|$. Moreover, either
$\gamma({\mathcal{A}}^{\prime})\geq\min\\{{n-u-1\choose
n-a-1},\gamma({\mathcal{A}})\\}$ or
$\gamma({\mathcal{B}}^{\prime})\geq\min\\{{n-v-1\choose
n-b-1},\gamma({\mathcal{B}})\\}$.

It should be clear that Lemmas 26 and 25 imply Theorem 3. We prove Lemma 26
using a series of transformations that would maintain the necessary properties
of ${\mathcal{A}}$, ${\mathcal{B}}$. The transformations would include shifts
and Daykin’s shifts, as well as some others. The main difficulty here would be
to show that the diversities of ${\mathcal{A}},{\mathcal{B}}$ are not
decreasing by too much after each transformation (i.e., to maintain the
moreover condition from Lemma 26). Another aspect that we will have to keep
track of is that the transformation process will eventually converge to the
desired situation. This is done by, roughly speaking, showing that each
transformation makes our families closer to initial segments in lex order.
Since the proof of Lemma 26 is rather involved and consists of several
reduction steps, we present it in a separate subsection.

###  4.1. Proof of Lemma 26

Arguing indirectly, among all the pairs ${\mathcal{A}},{\mathcal{B}}$ that do
not satisfy the statement of Lemma 26, let us take the pair that is minimal in
the following sense: there is no pair ${\mathcal{A}}_{1},{\mathcal{B}}_{1}$
other than ${\mathcal{A}},{\mathcal{B}}$ violating the statement of Lemma 26
and such that ${\mathcal{A}}_{1}\prec^{\prime}{\mathcal{A}}$,
${\mathcal{B}}_{1}\prec^{\prime}{\mathcal{B}}$, where
${\mathcal{F}}^{\prime}\prec^{\prime}{\mathcal{F}}$ if the sum of order
numbers of sets in ${\mathcal{F}}^{\prime}$ in lex order is smaller than that
of ${\mathcal{F}}$.

Case 1.  Assume that $\Delta({\mathcal{A}})\leq{n-2\choose a-2}+{n-u-1\choose
n-a-1},$ $\Delta({\mathcal{B}})\leq{n-2\choose b-2}+{n-v-1\choose n-b-1}$. In
particular, this implies that

$\gamma({\mathcal{A}})\geq{n-3\choose a-2}+{n-4\choose a-2},\ \ \
\gamma({\mathcal{B}})\geq{n-3\choose b-2}+{n-4\choose b-2}.$

Indeed,

$\gamma({\mathcal{A}})=|{\mathcal{A}}|-\Delta({\mathcal{A}})\geq{n-1\choose
a-1}-{n-4\choose a-1}+{n-u-1\choose n-a-1}-{n-2\choose a-2}-{n-u-1\choose
n-a-1}={n-3\choose a-2}+{n-4\choose a-2}.$

In what follows, we obtain a contradiction with the minimality of
${\mathcal{A}},{\mathcal{B}}$, given that the inequalities defining Case 1
hold. Then we proceed to the next case. We first “test” the families
${\mathcal{A}},{\mathcal{B}}$ using shifting.

W.l.o.g., assume that $a\leq b$ (and thus $n\geq 2a$).

For any $i<j$, if $\gamma(S_{ij}({\mathcal{A}}))\geq{n-4\choose a-3}$ or
$\gamma(S_{ij}({\mathcal{B}}))\geq{n-4\choose b-3}$ then we call a shift
successful. After a successful shift, we obtain cross-intersecting families
$S_{ij}({\mathcal{A}}),S_{ij}({\mathcal{B}})$. Moreover, if Lemma 26 fails for
${\mathcal{A}},{\mathcal{B}}$, then it fails for
$S_{ij}({\mathcal{A}}),S_{ij}({\mathcal{B}})$. Indeed, if not, then the
families ${\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}$ that we found will
also fit for ${\mathcal{A}}$ and ${\mathcal{B}}$. (The only nontrivial
condition to check is the “moreover” condition. If, say,
$\gamma(S_{ij}({\mathcal{A}}))\geq{n-4\choose k-3}$, then
$\gamma({\mathcal{A}}^{\prime})\geq\min\\{{n-u-1\choose n-a-1},{n-4\choose
k-3}\\}\geq{n-u-1\choose n-a-1}$, where the last inequality is due to $u>3$.)

If all the shifts are successful (and we always stay in Case 1), then, by
minimality, ${\mathcal{A}},{\mathcal{B}}$ are shifted.

Now, assume that an $i\leftarrow j$ shift is unsuccessful. If this is the case
then $\gamma({\mathcal{A}})-\gamma(S_{ij}({\mathcal{A}}))>2{n-4\choose a-2}$
and the same for ${\mathcal{B}}$. Then, using Proposition 11 (iii), we get
that the following properties hold for both
$({\mathcal{F}},k)\in\\{({\mathcal{A}},a),({\mathcal{B}},b)\\}$.

  * (i)

$|{\mathcal{F}}(\bar{i}\bar{j})|<{n-4\choose k-3}$;

  * (ii)

$|{\mathcal{F}}(i\bar{j})|,|{\mathcal{F}}(j\bar{i})|>2{n-4\choose k-2}$.

  * (iii)

$|{\mathcal{F}}(i\bar{j})\oplus{\mathcal{F}}(\bar{i}j)|>4{n-4\choose k-2}$;

  * (iv)

$|{\mathcal{F}}(i\bar{j})\cap{\mathcal{F}}(\bar{i}j)|<{n-4\choose k-3}$.

Here (iv) follows from the fact that the sets in
${\mathcal{F}}(i\bar{j})\oplus{\mathcal{F}}(\bar{i}j)$ stay intact after the
shift and thus provide a lower bound on the diversity for
$S_{ij}({\mathcal{F}})$. The following lemma is crucial for the understanding
of the structure of the family of all unsuccessful shifts.

######  Lemma 27.

If $i\leftarrow j$ shift is unsuccessful, then any $k\leftarrow l$ shift must
be successful for $\\{i,j\\}\cap\\{k,l\\}=\emptyset$.

###### Proof.

Using (iii), we have

$|{\mathcal{A}}(i\bar{j})\oplus{\mathcal{A}}(\bar{i}j)|>4{n-4\choose k-2}.$

Recall that $n\geq 2a$. Then

$\big{|}{\mathcal{A}}(i\overline{jk})\oplus{\mathcal{A}}(j\overline{ik})\big{|}\geq\Big{|}\big{(}{\mathcal{A}}(i\bar{j})\oplus{\mathcal{A}}(j\bar{i})\big{)}\setminus{[n]\setminus\\{i,j,k\\}\choose
a-2}\Big{|}>4{n-4\choose a-2}-{n-3\choose a-2}\geq 2{n-4\choose a-2},$

since ${n-4\choose a-2}\geq{n-4\choose a-3}$ for $n\geq 2a$. Similarly,

$\big{|}{\mathcal{A}}(i\overline{jkl})\oplus{\mathcal{A}}(j\overline{ikl})\big{|}\geq\big{|}\big{(}{\mathcal{A}}(i\overline{jk})\oplus{\mathcal{A}}(j\overline{ik})\big{)}\big{|}-{n-4\choose
k-2}>{n-4\choose a-3},$

and so (i) is not satisfied for the $k\leftarrow l$ shift. Thus, it must be
successful. ∎

Lemma 27 implies that either the families ${\mathcal{A}},{\mathcal{B}}$ are
shifted or there is an unsuccessful shift, say $1\leftarrow 2$, and in that
case both ${\mathcal{A}}(1\bar{2})$ and ${\mathcal{A}}(\bar{1}2)$ are shifted.
Let us show that the second situation is not possible. Indeed, apply (5) to
${\mathcal{A}}(1\bar{2})$, ${\mathcal{A}}(\bar{1}2)$. We get that

$\big{|}{\mathcal{A}}(1\bar{2})\cap{\mathcal{A}}(\bar{1}2)\big{|}\cdot{n-2\choose
a-1}\overset{\eqref{eqcorrshift}}{\geq}|{\mathcal{A}}(1\bar{2})|\cdot|{\mathcal{A}}(2\bar{1})|\overset{(ii)}{>}4{n-4\choose
a-2}^{2}\geq{n-3\choose a-2}^{2}.$

Note that for the last inequality we used $2a\leq n$. But ${n-4\choose
a-3}{n-2\choose a-1}=\frac{(a-2)(n-2)}{(n-3)(a-1)}\cdot{n-3\choose
a-2}^{2}\leq{n-3\choose a-2}$,333We have $\frac{a-2}{a-1}\leq\frac{n-3}{n-2}$
since $a\leq n-1$. and thus
$|{\mathcal{A}}(1\bar{2})\cap{\mathcal{A}}(\bar{1}2)|>{n-4\choose k-3},$ a
contradiction with property (iii) of an unsuccessful shift.

Recall the definition of a $S_{U,V}^{lex}$-shift from Section 3. Find
$U,V\subset[n]$ as in the definition and consider
$S_{U,V}^{lex}({\mathcal{A}})$, $S_{U,V}^{lex}({\mathcal{B}})$. Put $m:=|U|$.
Clearly, $m>0$ since ${\mathcal{A}},{\mathcal{B}}$ do not form initial
segments in the lexicographical order due to small maximal degree. Moreover,
$m\neq 1$ since the families ${\mathcal{A}},{\mathcal{B}}$ are shifted.
Therefore, $m\geq 2$. First,
$|{\mathcal{A}}|=|S_{U,V}^{lex}({\mathcal{A}})|,|{\mathcal{B}}|=|S_{U,V}^{lex}({\mathcal{B}})|.$
Next, we move at most ${n-|U|-|V|\choose a-|U|}\leq{n-4\choose k-2}$ sets to
obtain $S_{U,V}^{lex}({\mathcal{A}})$ from ${\mathcal{A}}$. Therefore, we have
$\gamma(S_{U,V}^{lex}({\mathcal{A}}))\geq{n-4\choose k-3}$. Finally, Lemma 21
implies that $S_{U,V}^{lex}({\mathcal{A}})$ and $S_{U,V}^{lex}({\mathcal{B}})$
are cross-intersecting. Thus, we get a contradiction with the minimality of
${\mathcal{A}},{\mathcal{B}}$.

Case 2.  Either $\Delta({\mathcal{A}})>{n-2\choose a-2}+{n-u-1\choose n-a-1}$
or $\Delta({\mathcal{B}})>{n-2\choose b-2}+{n-v-1\choose n-b-1}$. Without loss
of generality, let the first inequality hold and assume that
$\Delta({\mathcal{A}})=|{\mathcal{A}}(1)|$. Define
${\mathcal{A}}_{1},{\mathcal{B}}_{1}$ such that
${\mathcal{A}}_{1}(1)=\mathcal{L}([2,n],|{\mathcal{A}}(1)|,k-1)$,
${\mathcal{A}}_{1}(\bar{1})=\mathcal{L}([2,n],|{\mathcal{A}}(\bar{1})|,k)$,
and similarly for ${\mathcal{B}}_{1}$. (That is,
${\mathcal{A}}_{1}(1),{\mathcal{A}}(\bar{1}),{\mathcal{B}}(1),{\mathcal{B}}(\bar{1})$
all form lex segments on $[2,n]$.)

We may assume that
${\mathcal{A}}={\mathcal{A}}_{1},{\mathcal{B}}={\mathcal{B}}_{1}$. Indeed,
$|{\mathcal{A}}|=|{\mathcal{A}}_{1}|,$ $|{\mathcal{B}}|=|{\mathcal{B}}_{1}|$
and, due to Corollary 19, the pairs
$({\mathcal{A}}_{1}(1),{\mathcal{B}}_{1}(\bar{1}))$,
$({\mathcal{A}}_{1}(\bar{1}),{\mathcal{B}}_{1}(1))$ and
$({\mathcal{A}}_{1}(\bar{1}),{\mathcal{B}}_{1}(\bar{1}))$ are cross-
intersecting, implying that ${\mathcal{A}}_{1},{\mathcal{B}}_{1}$ are cross-
intersecting. Moreover,
$\gamma({\mathcal{A}}_{1})\geq\min\\{|{\mathcal{A}}(\bar{1})|,|{\mathcal{A}}(1\bar{2})|\\}=\min\\{\gamma({\mathcal{A}}),\lfloor{n-u-1\choose
n-a-1}\rfloor+1\big{\\}}.$ Therefore, either
${\mathcal{A}}_{1},{\mathcal{B}}_{1}$ may be taken as
${\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}$ from the statement of Lemma
26, or we get a contradiction with the minimality of
${\mathcal{A}},{\mathcal{B}}$ unless ${\mathcal{A}}_{1}={\mathcal{A}},$
${\mathcal{B}}_{1}={\mathcal{B}}$.

Finally, assume that ${\mathcal{A}},{\mathcal{B}}$ have the structure as
above, but still, say, $\gamma({\mathcal{A}})>{n-3\choose a-2}$. This implies
that ${\mathcal{A}}\supset\big{\\{}A\in{[n]\choose k}:|A\cap[3]|\geq
2\big{\\}}$, in particular, $1\leftarrow j$ shift is successful for any $j\geq
2$ and thus, by minimality, ${\mathcal{A}}$ is shifted.444Note that
$S_{ij}({\mathcal{A}})={\mathcal{A}}$ for any $2\leq i<j\leq n$, because
${\mathcal{A}}(1)$ and ${\mathcal{A}}(\bar{1})$ are lex segments. Since,
clearly, ${\mathcal{A}}$ does not form an initial segment in the lex order,
there is a Daykin shift that is possible to apply to
${\mathcal{A}},{\mathcal{B}}$, getting “smaller” (in the lex sense) families.
Arguing as before, the diversity of ${\mathcal{A}}$ will be at least
${n-4\choose a-3}$ after the application of this shift, and thus either we get
a contradiction with the minimality of ${\mathcal{A}},{\mathcal{B}}$, or
obtain families ${\mathcal{A}}^{\prime}$, ${\mathcal{B}}^{\prime}$ satisfying
the requirements of Lemma 26 for ${\mathcal{A}},{\mathcal{B}}$.

##  5\. Stability for Kruskal–Katona: proof of Theorem 6

Let us first show that the statement is true, provided
${\mathcal{F}}\subset{Y\choose k}$ for some $Y$, $|Y|=n+1$. W.l.o.g., assume
that $Y=[n+1]$. Consider the families

$\displaystyle{\mathcal{A}}:=$ $\displaystyle\ \big{\\{}[n+1]\setminus
F:F\in{\mathcal{F}}\big{\\}},$ $\displaystyle{\mathcal{B}}:=$ $\displaystyle\
\Big{\\{}F\in{[n+1]\choose k-1}:F\notin\partial({\mathcal{F}})\Big{\\}}.$

It is easy to see that $|{\mathcal{A}}|=|{\mathcal{F}}|$ and
$|{\mathcal{B}}|={n+1\choose k-1}-|\partial({\mathcal{F}})|.$ Moreover, the
families ${\mathcal{A}}$ and ${\mathcal{B}}$ are cross-intersecting (cf. the
proof of Corollary 17). Putting $m:=n+1,\ a:=n+1-k,\ b:=k-1$, we get that
${\mathcal{A}}\subset{[m]\choose a}$ and $|{\mathcal{A}}|\geq{m-1\choose
a-1}-{y\choose a-1}+{x\choose m-a-1}$. Next,
$\gamma({\mathcal{A}})=\gamma_{KK}({\mathcal{F}},n)\geq{x\choose
k-1}={x\choose m-a-1}$. Therefore, applying Theorem 3 (with $m:=n,$
$u:=m-x-1$, $v:=m-y-1$), we conclude that $|{\mathcal{B}}|\leq{m-1\choose
b-1}-{x\choose b-1}+{y\choose m-b-1}$ (indeed, having “$>$” here would
contradict Theorem 3). Consequently,

$|\partial{\mathcal{F}}|={m\choose b}-|{\mathcal{B}}|\geq{m-1\choose
b}-{y\choose m-b-1}+{x\choose b-1}={n\choose k-1}-{y\choose n-k+1}+{x\choose
k-2}.$

Therefore, it is sufficient to show that we can actually assume that
${\mathcal{F}}\subset{Y\choose k}$ for some $Y$, $|Y|=n+1$.

The proof here resembles the proof of Lemma 26, however, a direct reduction
seems to be impossible. Arguing indirectly, assume that the theorem does not
hold for some ${\mathcal{F}}$ satisfying the conditions. Among such
${\mathcal{F}}$, take the one that is minimal w.r.t. colex order.555More
precisely, the sum of order numbers of sets from ${\mathcal{F}}$ in colex is
the smallest.

Case 1 Assume that $\gamma_{KK}({\mathcal{F}})>{n-2\choose k-1}+{n-3\choose
k-2}$. Our first step is to show that ${\mathcal{F}}$ is shifted. Borrowing
terminology from the proof of Theorem 3, we say that the $(U,V)$-shift is
unsuccessful if $\gamma_{KK}(S_{U,V}({\mathcal{F}}))<{x\choose k-1}$.

Assume that the $i\leftarrow j$ shift is unsuccessful. This implies that there
is a subset $X$, $X=n-1$, $i,j\notin X$, such that

(11) $\Big{|}S_{ij}({\mathcal{F}})\cap{X\cup\\{i\\}\choose k}\Big{|}>{n\choose
k}-{y\choose n-k-1}\geq{n\choose k}-{n-3\choose k-3},$

where the first inequality comes from the assumption on the size of
${\mathcal{F}}$ and the second is due to $y\leq n-3$. We may then assume that
the family is shifted on $X$. Indeed, assume that one of the
$i^{\prime}\leftarrow j^{\prime}$ shifts is unsuccessful for
$i^{\prime},j^{\prime}\in X$. Then
$\big{|}S_{i^{\prime}j^{\prime}}({\mathcal{F}})(j^{\prime})\big{|}<{n-3\choose
k-1}$ and thus
$\big{|}S_{ij}(S_{i^{\prime}j^{\prime}}({\mathcal{F}}))(j^{\prime})\big{|}<{n-3\choose
k-1}<{n-1\choose k-1}-{n-3\choose k-3}$. This implies that

(12)
$\Big{|}S_{ij}\big{(}S_{i^{\prime}j^{\prime}}({\mathcal{F}})\big{)}\cap{X\cup\\{i\\}\choose
k}\Big{|}<{n\choose k}-{n-3\choose k-3}.$

However,

(13)
$\Big{|}S_{ij}\big{(}S_{i^{\prime}j^{\prime}}({\mathcal{F}})\big{)}\cap{X\cup\\{i\\}\choose
k}\Big{|}=\Big{|}S_{ij}\big{(}{\mathcal{F}}\big{)}\cap{X\cup\\{i\\}\choose
k}\Big{|}$

due to the fact that $i^{\prime},j^{\prime}\in X$, and shifts inside
$X\cup\\{i\\}$ do not alter the size of the family inside $X\cup\\{i\\}$. Then
(12) and (13) contradict (11).

Next, if $i\leftarrow j$ shift was unsuccessful then
$\gamma_{KK}({\mathcal{F}})-\gamma_{KK}(S_{ij}({\mathcal{F}}))>{n-2\choose
k-1}+{n-3\choose k-2}-{x\choose k-1}\geq 2{n-3\choose k-2}$. An obvious
analogue of Proposition 11 (iii) in our situation states that

(14)
$\min\big{\\{}|{\mathcal{F}}_{i}\setminus{\mathcal{F}}_{j}|,|{\mathcal{F}}_{j}\setminus{\mathcal{F}}_{i}|\big{\\}}>2{n-3\choose
k-2}>{n-3\choose k-2},$

where ${\mathcal{F}}_{l}:=\\{F\subset{X\choose
k-1}:F\cup\\{l\\}\in{\mathcal{F}}\\}$ for $l\in\\{i,j\\}.$ At the same time,
due to (11), we have $|{\mathcal{F}}_{i}\cup{\mathcal{F}}_{j}|>{n-1\choose
k-1}-{n-3\choose k-3}={n-2\choose k-1}+{n-3\choose k-2}$. Thus, putting
$t:=|{\mathcal{F}}_{i}\cap{\mathcal{F}}_{j}|$ we get
$|{\mathcal{F}}_{i}|+|{\mathcal{F}}_{j}|\geq{n-2\choose k-1}+{n-3\choose
k-2}+t$. The combination of the last inequality and (14) gives
$|{\mathcal{F}}_{i}||{\mathcal{F}}_{j}|\geq{n-2\choose k-1}({n-3\choose
k-2}+t)$. At the same time, as we have seen above, the families
${\mathcal{F}}_{i},{\mathcal{F}}_{j}$ are shifted. Using (5), we get

(15) $t{n-1\choose
k-1}\geq|{\mathcal{F}}_{i}||{\mathcal{F}}_{j}|\geq{n-2\choose
k-1}\Big{(}{n-3\choose k-2}+t\Big{)}.$

Clearly, $g(t):=t{n-1\choose k-1}-{n-2\choose k-1}({n-3\choose k-2}+t)$ is a
monotone increasing function of $t$. We claim that for $t\leq{n-3\choose k-1}$
we have $g(t)<0$. It is sufficient to show for $t={n-3\choose k-1}$. In that
case, we have $g(t)={n-3\choose k-1}{n-1\choose k-1}-{n-2\choose
k-1}^{2}=\big{(}\frac{(n-1)(n-k-2)}{(n-3)(n-k)}-1\big{)}{n-2\choose
k-1}^{2}<0$. Therefore, if there is $t$ satisfying the displayed inequality,
it must satisfy $t>{n-3\choose k-1}$, and thus we have
$\gamma_{KK}(S_{ij}({\mathcal{F}}))\geq t>{n-3\choose k-1}$, a contradiction
with the fact that $i\leftarrow j$ shift is unsuccessful.

From now we suppose that ${\mathcal{F}}$ is shifted. Since ${\mathcal{F}}$
clearly does not form an initial segment in the colex order, there is a Daykin
$U\leftarrow V$-shift $S_{U,V}^{colex}$ that will alter ${\mathcal{F}}$.
Moreover, we have $s:=|U|=|V|\geq 2$ due to shiftedness of ${\mathcal{F}}$.
Therefore, by minimality of ${\mathcal{F}}$, the $U\leftarrow V$ shift must be
unsuccessful, and thus there exists $X$, $|X|=n-s$ and $X\cap(U\cup
V)=\emptyset$, such that

(16)
$\min\big{\\{}|{\mathcal{F}}_{U}\setminus{\mathcal{F}}_{V}|,|{\mathcal{F}}_{V}\setminus{\mathcal{F}}_{U}|\big{\\}}>2{n-3\choose
k-2},$

where ${\mathcal{F}}_{W}:=\\{F\subset{X\choose
k-s}:F\cup\\{W\\}\in{\mathcal{F}}\\}$ for $W\in\\{U,V\\}.$ Putting
$t:=|{\mathcal{F}}_{U}\cap{\mathcal{F}}_{V}|$ and using shiftedness, we get
the following analogue of (15).

(17) $t{n-2\choose k-2}\geq t{n-s\choose
k-s}=|{\mathcal{F}}_{U}\cap{\mathcal{F}}_{V}|{X\choose
k-s}\geq|{\mathcal{F}}_{U}||{\mathcal{F}}_{V}|\geq\Big{(}2{n-3\choose
k-2}+t\Big{)}^{2}.$

On the one hand, if $2k\geq n$, then we have ${n-3\choose k-1}{n-2\choose
k-2}=\frac{(n-k-2)(n-2)}{(k-1)(n-k)}{n-3\choose k-2}^{2}<2{n-3\choose
k-2}^{2}$, and thus (17) can be only satisfied for $t>{n-3\choose k-1}$. On
the other hand, if $2k<n$ then ${n-2\choose k-2}={n-3\choose k-2}+{n-3\choose
k-3}<2{n-3\choose k-2}$, and thus (17) (or even (16)) is never satisfied.
Therefore, either (17) cannot be true, or
$\gamma_{KK}(S_{U,V}({\mathcal{F}}))>t\geq{n-3\choose k-1}$, which contradicts
the assumption that $(U,V)$-shift was unsuccessful. We conclude that the
assumption of Case 1 contradicts minimality of ${\mathcal{F}}$.

Case 2. Assume that ${x\choose
k-1}\leq\gamma_{KK}({\mathcal{F}})\leq{n-2\choose k-1}+{n-3\choose k-2}$.
Therefore, there exists $X$, $|X|=n$, such that
$\big{|}{\mathcal{F}}\cap{X\choose k}\big{|}\geq{n\choose k}-{y\choose
k-1}+{x\choose k-1}-{n-2\choose k-1}-{n-3\choose k-2}={n-1\choose
k}+{n-3\choose k-3}-{y\choose k-1}+{x\choose k-1}\geq{n-1\choose k}+{x\choose
k-1}$. W.l.o.g., assume that $X=[n]$. In this case, we may assume that
${\mathcal{F}}$ is $(U,V)$-shifted for all $U\prec_{colex}V\subset[n]$:
indeed, for any of these shifts we have

$\gamma_{KK}(S_{U,V}({\mathcal{F}}))\geq\min\big{\\{}\gamma_{KK}({\mathcal{F}}),\min_{i\in[n]}d_{i}(S_{U,V}({\mathcal{F}}))\big{\\}}\geq\min\Big{\\{}\gamma_{KK}({\mathcal{F}}),{x\choose
k-1}\Big{\\}}$

since
$\min_{i\in[n]}d_{i}(S_{U,V}({\mathcal{F}}))\geq|{\mathcal{F}}\cap{[n]\choose
k}|-{n-1\choose k}\geq{x\choose k-1}$. In particular, ${[n-1]\choose
k}\subset{\mathcal{F}}$. Replace
${\mathcal{F}}_{\gamma}:={\mathcal{F}}\setminus{[n]\choose k}$ with
$\\{F\cup\\{n+1\\}:F\in\mathcal{C}([n],|{\mathcal{F}}_{\gamma}|,k-1)\\}$,
obtaining a new family ${\mathcal{F}}^{\prime}$. Again, one easily sees that
$\gamma_{KK}({\mathcal{F}}^{\prime})\geq{x\choose k-1}$. Next,
$|\partial{\mathcal{F}}^{\prime}|\leq|\partial{\mathcal{F}}|$. Indeed, the new
shadows ${\mathcal{F}}^{\prime}$ add to the shadows of
${\mathcal{F}}\cap{[n]\choose k}$ have form $\big{\\{}F:n+1\in
F,F\in\partial\mathcal{C}([n],|{\mathcal{F}}_{\gamma}|,k-1)\big{\\}}$.
However, $|\partial\mathcal{C}([n],|{\mathcal{F}}_{\gamma}|,k-1)|$ is smaller
than $\sum_{i\geq n+1}|\partial\\{F\setminus\\{i\\}:F\in{\mathcal{F}},i\in
F\\}|$ due to subadditivity of the shadow of $\mathcal{C}([n],t,k-1)$ as a
function of $t$. It follows from the Kruskal–Katona theorem (Theorem 18)
itself: we may realize families $\\{F\setminus\\{i\\}:F\in{\mathcal{F}},i\in
F\\}$ on disjoint ground sets, and then their union has shadow larger than
that of $\mathcal{C}([n],|{\mathcal{F}}^{\prime}|,k-1)$.

Thus, due to minimality, ${\mathcal{F}}={\mathcal{F}}^{\prime}$, so
${\mathcal{F}}\subset{[n+1]\choose k}$ and we arrive at a contradiction.

Remark.  What we used here in essentially [30, Lemma 3.2], and the elegant way
of seeing subadditivity is borrowed from [30, Lemma 3.1(iii)].

##  6\. Uniform $r$-wise $t$-intersecting families. Proof of Theorem 9

Recall that the families ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{r}$ are
cross $t$-intersecting if for any
$F_{1}\in{\mathcal{F}}_{1},\ldots,F_{r}\in{\mathcal{F}}_{r}$ we have
$|F_{1}\cap\ldots\cap F_{r}|\geq t$.

Take any family ${\mathcal{F}}$ satisfying the conditions of the theorem.

Suppose that $\gamma({\mathcal{F}})>0$. This implies that ${\mathcal{F}}$ is
$2$-wise $(r+t-2)$-intersecting. Indeed, if $F_{1}\cap
F_{2}=\\{i_{1},\ldots,i_{l}\\}$ for $l\leq r+t-3$, then, given that
$\gamma({\mathcal{F}})>0$, for each $j\in[\min\\{r-2,l\\}]$ we can find
$F_{i_{j}}\in{\mathcal{F}}$ such that $i_{j}\notin F_{i_{j}}$, and thus
$|F_{1}\cap F_{2}\cap F_{i_{1}}\cap\ldots\cap F_{i_{l}}|\leq t-1$.

Assume that ${\mathcal{F}}$ is $2$-wise $(r+t-1)$-intersecting. Then
${\mathcal{F}}(\bar{x})$ is $2$-wise $(r+t-1)$-intersecting for any $x\in[n]$,
and, by a theorem of Frankl [11],
$\gamma({\mathcal{F}})\leq|{\mathcal{F}}(\bar{x})|\leq{n-r-t\choose k-r-t+1}$
for $n>2(r+t)k$.

Assume now that there exist $F_{1},F_{2}\in{\mathcal{F}}$ that intersect in
$r+t-2$ elements. W.l.o.g., suppose that $F_{1}\cap F_{2}=[r+t-2]$. The
$r$-wise $t$-intersecting property implies

(18) $|F\cap[r+t-2]|\geq r+t-3\ \ \ \ \ \text{for all }F\in{\mathcal{F}}.$

For each $i\in[r+t-2]$, define

${\mathcal{F}}_{i}:=\big{\\{}F\in{\mathcal{F}}:F\cap[r+t-2]=[r+t-2]\setminus\\{i\\}\big{\\}}.$

The families ${\mathcal{F}}_{1}\ldots,{\mathcal{F}}_{r+t-2}$ are cross
2-intersecting subfamilies of ${[r+t-1,n]\choose k-r-t+3}$. By (18),

(19) $\gamma({\mathcal{F}})\leq\min_{i}|{\mathcal{F}}_{i}|.$

Applying Corollary 24 to ${\mathcal{F}}_{1},{\mathcal{F}}_{2}$, we get that
one of them has size at most ${n-r-t\choose k-r-t+1}$, since $n\geq
15k>r+t-2+15(k-r-t+3)$.

##  7\. Families with $\nu({\mathcal{F}})\leq s$

For $X\subset[n]$, we use the standard notations
${\mathcal{F}}(X):=\\{F-X:F\in{\mathcal{F}}\\}$ and
${\mathcal{F}}(\bar{X}):=\\{F:F\cap X=\emptyset,F\in{\mathcal{F}}\\}$. Let
$n>k(s+1)$ and let ${\mathcal{F}}\subset{[n]\choose k}$,
$\nu({\mathcal{F}})=s$. The $s$-diversity $\gamma_{s}({\mathcal{F}})$ of
${\mathcal{F}}$ is defined as

$\gamma_{s}({\mathcal{F}}):=\min\Big{\\{}|{\mathcal{F}}(\bar{R}):R\in{[n]\choose
s}\Big{\\}}.$

For $s=1$ we get back to the usual notion of diversity. Recall also the
construction

${\mathcal{A}}_{2}:={\mathcal{A}}_{2}(n,k,s):=\Big{\\{}A\in{[n]\choose
k}:|A\cap[2s+1]|\geq 2\Big{\\}}.$

######  Theorem 28.

If ${\mathcal{F}}\subset{[n]\choose k},\ \nu({\mathcal{F}})=s$ and
$n>n_{0}(k,s)$, then

(20)
$\gamma_{s}({\mathcal{F}})\leq\gamma_{s}({\mathcal{A}}_{2})=|{\mathcal{A}}_{2}\big{(}\bar{[s]}\big{)}|.$

Note that $|{\mathcal{A}}_{2}\big{(}\bar{[s]}\big{)}|=(1+o(1)){s+1\choose
2}{n-s-2\choose k-2}$.

We also note that the motivation for this theorem is the famous Erdős Matching
Conjecture. If one would have an analogous result in the range of the
parameters where the EMC is still open, it would most likely lead to some
major progress in the conjecture.

###### Proof.

For a family ${\mathcal{F}}$ satisfying the requirements of the theorem, let
$\tilde{\mathcal{F}}\supseteq{\mathcal{F}}$ be an extended family satisfying
the following conditions:

  * (i)

For any $\tilde{F}\in\tilde{\mathcal{F}}$ there exists $F\in{\mathcal{F}}$,
such that $\tilde{F}\subseteq F$;

  * (ii)

$\nu(\tilde{\mathcal{F}})=s$;

  * (iii)

$\tilde{\mathcal{F}}$ is maximal with respect to (i), (ii).

We prove (20) by induction on $s$. The case $s=1$ is implied by the result of
[33] on the diversity of intersecting $k$-uniform families.

Case 0. $\exists x\in[n]:\\{x\\}\in\tilde{\mathcal{F}}$.  Then
$\nu(\tilde{\mathcal{F}}(\bar{x}))=s-1$ and by induction

$\gamma_{s}({\mathcal{F}})\leq\gamma_{s-1}({\mathcal{F}}(\bar{x}))\leq\gamma_{s-1}({\mathcal{A}}_{2}(n-1,k,s-1))<\gamma_{s}({\mathcal{A}}_{2}(n,k,s)).$

Case 1.  For every $\tilde{F}\in\tilde{\mathcal{F}}$ we have $|\tilde{F}|\geq
2$.

Define the (edge set of the) graph ${\mathcal{G}}$ by
${\mathcal{G}}:=\\{\tilde{F}\in\tilde{\mathcal{F}}:|\tilde{F}|=2\\}$. Then

(21) $|{\mathcal{F}}|\leq\big{(}|{\mathcal{G}}|+o(1)\big{)}{n-2\choose k-2}.$

by the argumentation from [10].666 Namely, the minimal sets with respect to
containment cannot form any sunflowers of size more than $ks$. Therefore,
their number is less than $(ks)^{k}\cdot k!$ by a classic result of Erdős and
Rado [8].  Combined with the following lemma, this concludes the proof of the
theorem (which we check below).

######  Lemma 29.

Let ${\mathcal{G}}$ be (the edge set of) a graph on $n$ vertices with
$\nu({\mathcal{G}})=s$, $s\geq 1$ and with no isolated vertices. Then there
exists an $s$-element set $R$, such that

(22) $|{\mathcal{G}}(\bar{R})|\leq{s+1\choose 2},$

with equality if and only if ${\mathcal{G}}$ forms a complete graph on $2s+1$
vertices. Moreover, if ${\mathcal{G}}$ is not a subgraph of a complete graph
on $2s+1$ vertices, then

(23) $|{\mathcal{G}}(\bar{R})|\leq{s\choose 2}+1$

We remark that Lemma 29 completely solves the question of maximizing the
$s$-diversity for graphs, and even provides us with a Hilton-Milner-type
result.

###### Proof.

Let $(x_{i},y_{i})$, $i\in[s]$, be a maximal matching in ${\mathcal{G}}$. Let
$Z:=[n]\setminus\cup_{i=1}^{s}\\{x_{i},y_{i}\\}$ be the remaining vertices.
Note that $Z$ is an independent set. Note also that $\nu({\mathcal{G}})=s$
implies that there are no $z,z^{\prime}\in Z$ and $i\in[s]$ such that
$(z,x_{i}),(z^{\prime},y_{i})\in{\mathcal{G}}$. That is, for $i\in[s]$,
either:

  * (a)

there is a unique $z_{i}\in Z$ with
$(z_{i},x_{i}),(z_{i},y_{i})\in{\mathcal{G}}$ and none of
$(z,x_{i}),(z,y_{i})$ are in ${\mathcal{G}}$ for $z\in Z\setminus\\{z_{i}\\}$,
or

  * (b)

we can suppose by symmetry that $(z,y_{i})\notin{\mathcal{G}}$ holds for all
$z\in Z$.

Let us delete the set $X:=\\{x_{1},\ldots,x_{s}\\}$. The only possible edges
that remain in ${\mathcal{G}}(\bar{X})$ are edges $(y_{i},y_{j})$, which
account for at most ${t\choose 2}$ edges, and for each $1\leq i\leq t$ at most
one edge of the form $(y_{i},z_{i})$ (note that $z_{i}=z_{i^{\prime}}$ is
possible for $i\neq i^{\prime}$!). Thus, there are at most ${s\choose
2}+s={s+1\choose 2}$ edges.

If $z_{i}$ is the same for all $i$ for which it is defined, then
${\mathcal{G}}$ is a subgraph of a complete graph on $2s+1$ vertices. If for
some $i\neq j\in[s]$ $z_{i},z_{j}$ are different then there is no edge between
$y_{i}$ and $y_{j}$. Indeed, otherwise we can replace $x_{i}y_{i}$ and
$x_{j}y_{j}$ with $z_{i}x_{i},$ $y_{i}y_{j}$ and $x_{j}z_{j}$, thus obtaining
a matching of size $s+1$. Moreover, if not all $z_{i}$ are the same, and
$z_{i}$’s are defined for $t$ indices $i\in[s]$, then there are at least $t-1$
pairs $\\{i,j\\}$ for which $z_{i}\neq z_{j}$. In this case, the total number
of edges is at most ${s\choose 2}+t-(t-1)={s\choose 2}+1$. ∎

Lemma 29 and (21) imply that $\gamma_{s}({\mathcal{F}})\leq\big{(}{s+1\choose
2}+o(1)\big{)}{n-2\choose k-2}$, moreover, ${s+1\choose 2}$ can be replaced by
${s+1\choose 2}-1$ provided $\mathcal{G}$ is not a complete graph on $2s+1$
vertices. Since $|\mathcal{A}_{2}(\bar{[}s])|=(1+o(1)){s+1\choose
2}{n-2\choose k-2}$, we conclude that the family $\mathcal{G}(\bar{R})$ from
21 must have size ${s+1\choose 2}$, and thus $\mathcal{G}$ must be a complete
graph on $2s+1$ vertices, say $[2s+1]$. This clearly forces all the sets from
${\mathcal{F}}$ to intersect $[2s+1]$ in at least $2$ elements. This concludes
the proof of Theorem 28.∎

##  8\. Non-uniform families

We say that ${\mathcal{F}}\subset 2^{[n]}$ is $r$-wise $t$-union if for any
$F_{1},\ldots,F_{r}\in{\mathcal{F}}$ we have $|F_{1}\cup\ldots\cup F_{r}|\leq
n-t$. Daykin [3] proposed the following problem: given an $r$-wise $t$-union
family ${\mathcal{F}}\subset 2^{[n]}$, what is the maximum possible minimum
degree of ${\mathcal{F}}$?

######  Observation 30.

${\mathcal{F}}\subset 2^{[n]}$ is an $r$-wise $t$-intersecting family with
diversity $\gamma({\mathcal{F}})=d$ if and only if the family of the
complements ${\mathcal{F}}^{c}:=\\{[n]\setminus F:F\in{\mathcal{F}}\\}$ is an
$r$-wise $t$-union family of minimum degree $d$.

Daykin [3] proposed the following conjecture.

######  Conjecture 1 ([3]).

If $r\geq 3$ and ${\mathcal{F}}\subset 2^{[n]}$ is $r$-wise union then its
minimum degree is at most $2^{n-r-1}$.

This was proved in [4] for $r\geq 25$ and in [14] for $r\geq 5$. For the
corresponding values, we have

(24) $\gamma({\mathcal{F}})\leq 2^{n-r-1}\ \ \ \text{ for all $r$-wise
intersecting families }\ \ {\mathcal{F}}\subset 2^{[n]},\text{ where }\ r\geq
5.$

In [14], it was even shown that

(25) $\gamma({\mathcal{F}})\leq 2^{n-r-t}\ \ \ \text{for all $r$-wise
$t$-intersecting families}\ \ {\mathcal{F}}\subset 2^{[n]},\ \text{ where }\
r\geq 5\ \text{ and }\ t\leq 2^{r}-2r.$

The construction showing that (24) and (25) are optimal is

$\big{\\{}A\subset[n]:|A\cap[r+t]|\geq r+t-1\big{\\}}.$

Note that removing from the family above some or all of the members containing
$[r+t]$ will not alter the diversity. Therefore, the optimal families are not
unique.

Next, let us consider the case of ($2$-wise) $t$-intersecting families for
$t\geq 2$. The following classic result was proved by Katona [27].

######  Theorem 31 ([27]).

If ${\mathcal{F}}\subset 2^{[n]}$ is $t$-intersecting then

$|{\mathcal{F}}|\leq\begin{cases}\sum_{i=(n+t)/2}^{n}{n\choose i}&\mbox{if
}n+t\text{ is even},\\\ 2\sum_{i=(n+t-1)/2}^{n-1}{n-1\choose i}&\mbox{if
}n+t\text{ is odd}.\end{cases}$

Both functions on the right hand side are asymptotically
$\big{(}1-\Theta(n^{-0.5})\big{)}2^{n-1}$ for fixed $t$. The theorem is sharp
due to the following examples:

$\displaystyle n+t\text{ is even: }$ $\displaystyle\
\big{\\{}X\subset[n]:|X|\geq(n+t)/2\big{\\}},$ $\displaystyle n+t\text{ is
odd: }$ $\displaystyle\
\big{\\{}X\subset[n]:|X\cap[2,n]|\geq(n+t-1)/2\big{\\}}.$

These two families have diversity $(1-O_{t}(n^{-0.5}))2^{n-2}$. On the other
hand, for any $t$-intersecting ${\mathcal{F}}\subset 2^{[n]}$ and $x\in[n]$,
${\mathcal{F}}(\bar{x})$ is $t$-intersecting on $[n]\setminus\\{x\\}$. Thus,
we may apply Theorem 31 and conclude that
$\gamma({\mathcal{F}})\leq\big{(}1-\Omega_{t}(n^{-0.5})\big{)}2^{n-2}$ for any
$t$-intersecting family ${\mathcal{F}}\subset 2^{[n]}$. We formulate these
findings in a proposition.

######  Proposition 32.

For integer $t\geq 2$, the largest diversity $\gamma$ of a $t$-intersecting
family ${\mathcal{F}}\subset 2^{[n]}$ satisfies

$\gamma=\Big{(}1-\Theta\big{(}n^{-0.5}\big{)}\Big{)}2^{n-2}.$

The case $k=2$, $t=1$ is special. In [5], the authors managed to prove
$\gamma({\mathcal{F}})\leq\big{(}1-n^{-1}\big{)}2^{n-2}$ for any intersecting
family ${\mathcal{F}}\subset 2^{[n]}$ and constructed an example with of an
intersecting family
$\gamma({\mathcal{F}})\geq\big{(}1-n^{-0.651})\big{)}2^{n-2}$. The authors of
[5] conjectured that the construction attaining the lower bound is in fact
optimal. Unaware of [5], Huang [23] asked, what is the largest diversity of an
intersecting family in $2^{[n]}$. He conjectured that it is at most
$\big{(}1-\Omega(n^{-0.5}))\big{)}2^{n-2}$. In what follows, we solve the
problem asymptotically using the tools coming from the Analysis of Boolean
Functions. Both conjectures have negative answer.

######  Proposition 33.

The largest diversity $\gamma$ of an intersecting family ${\mathcal{F}}\subset
2^{[n]}$ satisfies

$\gamma=\Big{(}1-\Theta\big{(}\frac{\log n}{n}\big{)}\Big{)}2^{n-2}.$

###### Proof.

Consider the uniform measure $\mu$ on all subsets of $2^{[n]}$. The influence
$I_{i}({\mathcal{F}})$ of coordinate $i$ in ${\mathcal{F}}$ is

$I_{i}({\mathcal{F}}):=2\mu\big{(}\\{F\subset[n]:i\notin
F,|\\{F,F\cup\\{i\\}|\cap{\mathcal{F}}=1\\}\big{)},$

where here and below $\mu$ stands for the uniform measure on $2^{[n]}$. The
total influence is $I({\mathcal{F}}):=\sum_{i}I_{i}({\mathcal{F}})$. In case
if ${\mathcal{F}}$ is closed upwards, we have

(26) $I_{i}({\mathcal{F}})=2\mu\big{(}\\{F\in{\mathcal{F}}:i\in
F\\}\big{)}-2\mu\big{(}\\{F\in{\mathcal{F}}:i\notin F\\}\big{)}.$

By the definition of diversity, it is easy to see that

(27)
$\frac{1}{2}\max_{i\in[n]}I_{i}({\mathcal{F}})+2\gamma({\mathcal{F}})=\mu({\mathcal{F}}).$

Since increasing the size of the family cannot reduce the diversity, we may
restrict ourselves to the families having measure $1/2$. Therefore, to
maximize diversity, one has to minimize maximal influence of one coordinate in
a family. By the famous KKL theorem [25], we have
$\max_{i\in[n]}I_{i}({\mathcal{F}})=\Omega(\frac{\log n}{n})$, and thus
$\gamma({\mathcal{F}})=\big{(}\frac{1}{4}-\Omega(\frac{\log
n}{n})\big{)}2^{n}$.

For the lower bound, consider the following example. Arrange the elements of
$[n]$ on the circle, and for each set $S\subset 2^{[n]}$ form a sequence
$\mathbf{u}:=(u_{1},u_{2},\ldots)$, where $u_{i}$ is the length of the $i$-th
longest run of consecutive $1$’s; similarly,
$\mathbf{z}:=(z_{1},z_{2},\ldots)$ is the sequence, in which $z_{i}$ is the
$i$-th longest run of consecutive $0$’s. Form an intersecting family by
including all sets, for which its sequence $\mathbf{u}$ is lexicographically
bigger than $\mathbf{z}$. If $n$ is even, then there may be sets which have
$\mathbf{u}=\mathbf{z}$, and we take a half of them, one out of each pair of
two opposite sets, arbitrarily (note that such sets must have exactly $n/2$
ones). This example was proposed by Gil Kalai [26], where the properties of
this family were briefly described. In [33], the first author gave a detailed
proof of the fact that each coordinate has influence $O(\log n/n)$ in such a
family for odd $n$. We note that the analysis for the even case can be done
along the same lines, just taking into account that there are very few sets
for which the sequences $\mathbf{u}$ and $\mathbf{z}$ coincide. Therefore, we
conclude that the minimum of the largest individual influence in an
intersecting monotone family is $\Theta(\log n/n)$, and, substituting into
(27), we get that the diversity of this family is
$\big{(}\frac{1}{4}-O(\frac{\log n}{n})\big{)}2^{n}$. ∎

##  9\. Open problems

There are many interesting open problems that involve diversity-related
quantities. We have already mentioned some of them, in particular, Conjecture
1.

The next problem was discussed in Section 7.

######  Problem 1.

Extend Theorem 28 to the range $n\geq Cks$ for some absolute $C>0$.

In Theorem 6 we defined the diversity of families in terms of their distance
from the family of all subsets of an $n$-element set. One may generalize this
notion and, for a family ${\mathcal{F}}\subset{[n]\choose k}$, define its
diversity with respect to a initial segment in the colex order:
$\gamma_{colex}({\mathcal{F}},t):=\min|{\mathcal{F}}\setminus\mathcal{C}(n,k,t)|$,
where the minimum is taken over all possible orderings of the ground set. It
seems plausible that the following extension of our stability result for the
Kruskal–Katona is possible. We note that it generalizes the results of Füredi
and Griggs [21], who characterized the cases in which equality holds in the
Kruskal–Katona theorem.

######  Problem 2.

Let $s>0$ and $n_{s}>n_{s-1}>\ldots>n_{1}>n>k>0$ be integers, and assume that
${\mathcal{F}}$ is a family of $k+s$-element sets, such that
$|{\mathcal{F}}|\geq t:={n_{s}\choose k+s}+\ldots+{n_{1}\choose k+1}+{n\choose
k}-{y\choose n-k}+{x\choose k-1}$ and
$\gamma_{colex}({\mathcal{F}},t)\geq{x\choose k-1}$ for some real numbers
$k-1\leq x\leq n-3$, $n-k\leq y\leq n-3$. Then
$\partial({\mathcal{F}})\geq{n_{s}\choose k+s-1}+\ldots+{n_{1}\choose
k}+{n\choose k-1}-{y\choose n-k+1}+{x\choose k-2}$.

Fix integers $0\leq a<b\leq k$. Find $\max\min|{\mathcal{F}}(\bar{B})|$, where
the maximum is over all ${\mathcal{F}}\subset{[n]\choose k}$, such that
${\mathcal{F}}$ is intersecting, $\tau({\mathcal{F}})=b$ and the minimum is
over all $B\in{[n]\choose a}$.

Probably, the most interesting case is $b=k$, that is, of intersecting
$k$-graphs ${\mathcal{F}}$ that cannot be covered by $k-1$ vertices. A
classical result of Erdős and Lovász [7] shows that $|{\mathcal{F}}|\leq
k^{k}$, independent of $n$ (cf. [16] for the current best bound).

In [19] constructions with $|{\mathcal{F}}|>\Big{(}\frac{k}{2}\Big{)}^{k}$
were given. However, almost all edges contain one specific vertex. Slightly
more precisely, the number of edges not containing that vertex is polynomial
in $k$.

Let $m(k,a)$ be the maximum above over all $n$ for $b=k$. That is, the value
of $m(k,0)$ is the answer to the Erdős–Lovász problem.

######  Conjecture 2.

$m(k,1)/m(k,0)\to 0$ as $k\to\infty$.

######  Conjecture 3.

There is an absolute constant $c>1$ such that $m(k,k-1)>c^{k}$ for all $k\geq
3$.

It is easy to show that $m(3,2)=2$. Using product-type constructions, we
managed to show that there is no such $\epsilon>0$ such that
$m(k,k-1)<2^{k^{1-\epsilon}}$ holds for all $k$.

## References

  * [1] D. E. Daykin, A Simple Proof of the Kruskal–Katona Theorem, J. Combin. Theory Ser. A 17 (1974), 252–253.
  * [2] D.E. Daykin, Erdős-Ko-Rado from Kruskal-Katona, Journal of Combinatorial Theory Ser. A 17 (1974), N2, 254–255.
  * [3] D.E. Daykin, Minimum subcover of a finite set Amer. Math. Monthly, 85 (1978), 766.
  * [4] D.E. Daykin and P. Frankl, Sets of finite sets satisfying union conditions, Mathematika 29 (1982), N1, 128–134.
  * [5] I. Dinur, E. Friedgut, Intersecting families are essentially contained in juntas, Combinatorics, Probability and Computing 18 (2009), 107–122.
  * [6] P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics, 12 (1961) N1, 313–320.
  * [7] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infnite and Finite Sets, Proc. Colloq. Math. Soc. János Bolyai, Keszthely, Hungary (1973), North-Holland, Amsterdam (1974), 609–627.
  * [8] P. Erdős and R. Rado Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90.
  * [9] C. Feghali, Multiply Erdő s-Ko-Rado Theorem. arXiv:1712.09942.
  * [10] P. Frankl, On intersecting families of finite sets, Journal of Combinatorial Theory Ser. A 24 (1978), N2, 146–161.
  * [11] P. Frankl, The Erdos-Ko-Rado theorem is true for $n=ckt$, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976). Vol. 1, 1978.
  * [12] P. Frankl, Erdos-Ko-Rado theorem with conditions on the maximal degree, Journal of Combinatorial Theory, Series A 46 (1987), N2, 252–263.
  * [13] P. Frankl, The shifting technique in extremal set theory, Surveys in combinatorics 123 (1987), 81–110.
  * [14] P. Frankl, Multiply-intersecting families, Journal of Combinatorial Theory, Series B 53 (1991), N2, 195–234.
  * [15] P. Frankl, Antichains of fixed diameter, Moscow Journal of Combinatorics and Number Theory 7 (2017), N3
  * [16] P. Frankl, A near exponential improvement on a bound of Erdős and Lovász, preprint, https://users.renyi.hu/~pfrankl/2017-4.pdf
  * [17] P. Frankl, A. Kupavskii, Counting intersecting and pairs of cross-intersecting families, Comb. Probab. Comput. 27 (2018), N1, 60–68.
  * [18] P. Frankl, S.J. Lee, M. Siggers, and N. Tokushige, An Erdős-Ko-Rado theorem for cross $t$-intersecting families, Journal of Combinatorial Theory, Series A 128 (2014), 207–249.
  * [19] P. Frankl, K. Ota and N. Tokushige, Covers in uniform intersecting families and a counterexample to a conjecture of Lovász, J. Comb. Theory Ser. A 74 (1996), 33–42.
  * [20] P. Frankl and N. Tokushige, Some best possible inequalities concerning cross-intersecting families, Journal of Combinatorial Theory, Series A 61 (1992), N1, 87-97.
  * [21] Z. Füredi and J. R. Griggs, Families of finite sets with minimum shadows, Combinatorica 6 (1986), N4, 355–363.
  * [22] A.J.W. Hilton, The Erdős-Ko-Rado theorem with valency conditions (1976), unpublished manuscript.
  * [23] H. Huang, Two extremal problems on intersecting families, Eur. J. Comb. 76 (2019), 1-9.
  * [24] F. Ihringer, A. Kupavskii, Regular intersecting families, arXiv:1709.10462
  * [25] J. Kahn, G. Kalai, N. Linial, The influence of variables on Boolean functions, Proc. 29th Annual Symposium on Foundations of Computer Science (1988), 68–80.
  * [26] G. Kalai, A post on MathOverflow, https://mathoverflow.net/questions/105086/kahn-kalai-linial-for-intersecting-upsets
  * [27] G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329–337.
  * [28] G.O.H. Katona, A theorem of finite sets, Theory of Graphs, Proc. Coll. Tihany 1966, Akad, Kiado, Budapest, 1968; Classic Papers in Combinatorics (1987), 381–401.
  * [29] P. Keevash, Shadows and intersections: Stability and new proofs, Advances in Mathematics 218 (2008), N5, 1685–1703.
  * [30] P. Keevash and E. Long, Stability for vertex isoperimetry in the cube (2018) arXiv:1807.09618
  * [31] J.B. Kruskal, The Number of Simplices in a Complex, Mathematical optimization techniques 251 (1963), 251–278.
  * [32] A. Kupavskii, D. Zakharov, Regular bipartite graphs and intersecting families, J. Comb. Theory Ser. A 155 (2018), 180-189.
  * [33] A. Kupavskii, Diversity of intersecting families, Eur. J. Comb. 74 (2018), 39-47.
  * [34] A. Kupavskii, Structure and properties of large intersecting families, arXiv:1710.02440
  * [35] N. Lemons, C. Palmer, Unbalance of set systems, Graphs and Combinatorics 24 (2008), N4, 361–365.
  * [36] M. Matsumoto and N. Tokushige, The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families, Journal of Combinatorial Theory, Series A 52 (1989), N1, 90-97.
  * [37] R. O’Donnell and K. Wimmer, KKL, Kruskal–Katona and monotone nets, SIAM Journal on Computing 42 (2013), N6, 2375–2399.
  * [38] R.M. Wilson, The exact bound in the Erdős-Ko-Rado theorem, Combinatorica 4 (1984), N2, 247–257.