# The maximum sum of sizes of non-empty pairwise cross-intersecting
families††thanks: This work is supported by NSFC (Grant No. 11931002). E-mail
addresses<EMAIL_ADDRESS>(Yang Huang<EMAIL_ADDRESS>(Yuejian Peng,
corresponding author).

Yang Huang, Yuejian Peng†
School of Mathematics, Hunan University
Changsha, Hunan, 410082, P.R. China

###### Abstract

Two families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting if $A\cap
B\neq\emptyset$ for any $A\in\mathcal{A}$ and $B\in\mathcal{B}$. We call $t$
families $\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{t}$ pairwise
cross-intersecting families if $\mathcal{A}_{i}$ and $\mathcal{A}_{j}$ are
cross-intersecting when $1\leq i<j\leq t$. Additionally, if
$\mathcal{A}_{j}\neq\emptyset$ for each $j\in[t]$, then we say that
$\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{t}$ are non-empty pairwise
cross-intersecting. Let $\mathcal{A}_{1}\subset{[n]\choose
k_{1}},\mathcal{A}_{2}\subset{[n]\choose
k_{2}},\dots,\mathcal{A}_{t}\subset{[n]\choose k_{t}}$ be non-empty pairwise
cross-intersecting families with $t\geq 2$, $k_{1}\geq k_{2}\geq\cdots\geq
k_{t}$, and $n\geq k_{1}+k_{2}$, we determine the maximum value of
$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}$ and characterize all extremal families.
This answers a question of Shi, Frankl and Qian [Combinatorica 42 (2022)] and
unifies results of Frankl and Tokushige [J. Combin. Theory Ser. A 61 (1992)]
and Shi, Frankl and Qian [Combinatorica 42 (2022)]. The key techniques in
previous works cannot be extended to our situation. A result of Kruskal-Katona
is applied to allow us to consider only families $\mathcal{A}_{i}$ whose
elements are the first $|\mathcal{A}_{i}|$ elements in lexicographic order. We
bound $\sum_{i=1}^{t}{|\mathcal{A}_{i}|}$ by a function $f(R)$ of the last
element $R$ (in the lexicographic order) of $\mathcal{A}_{1}$, introduce the
concepts ‘$c$-sequential’ and ‘down-up family’, and show that $f(R)$ has
several types of local convexities.

Key words: Cross-Intersecting families; Extremal finite sets

2010 Mathematics Subject Classification. 05D05, 05C65, 05D15.

##  1 Introduction

Let $[n]=\\{1,2,\dots,n\\}$. For $0\leq k\leq n$, let ${[n]\choose k}$ denote
the family of all $k$-subsets of $[n]$. A family $\mathcal{A}$ is $k$-uniform
if $\mathcal{A}\subset{[n]\choose k}$. A family $\mathcal{A}$ is intersecting
if $A\cap B\neq\emptyset$ for any $A$ and $B\in\mathcal{A}$. Many researches
in extremal set theory are inspired by the foundational result of
Erdős–Ko–Rado [6] showing that a maximum $k$-uniform intersecting family is a
full star. This theorem of Erdős–Ko–Rado has many interesting generalizations.
Two families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting if $A\cap
B\neq\emptyset$ for any $A\in\mathcal{A}$ and $B\in\mathcal{B}$. We call $t$
$(t\geq 2)$ families $\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{t}$
pairwise cross-intersecting families if $\mathcal{A}_{i}$ and
$\mathcal{A}_{j}$ are cross-intersecting when $1\leq i<j\leq t$. Additionally,
if $\mathcal{A}_{j}\neq\emptyset$ for each $j\in[t]$, then we say that
$\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{t}$ are non-empty pairwise
cross-intersecting. The following result was proved by Hilton.

######  Theorem 1.1 (Hilton, [16]).

Let $n,k$ and $t$ be positive integers with $n\geq 2k$ and $t\geq 2$. If
$\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{t}\subset{[n]\choose k}$
are pairwise cross-intersecting, then

$\displaystyle\sum_{i=1}^{t}|\mathcal{A}_{i}|\leq\begin{cases}{n\choose
k},&\text{if $t\leq\frac{n}{k}$};\\\ t{n-1\choose k-1},&\text{if
$t\geq\frac{n}{k}$},\end{cases}$

and the bound is tight. If
$|\mathcal{A}_{1}|\geq|\mathcal{A}_{2}|\geq\cdots\geq|\mathcal{A}_{t}|$,
$n\neq 2k$ when $t=2$, and the equality holds, then either
$\mathcal{A}_{1}={[n]\choose k}$,
$\mathcal{A}_{2}=\cdots=\mathcal{A}_{t}=\emptyset$ and $t\leq\frac{n}{k}$, or
$\mathcal{A}_{1}=\mathcal{A}_{2}=\cdots=\mathcal{A}_{t}=\\{F\in{[n]\choose
k}:x\in F,\ {\rm where}\ x\in[n]\\}$ and $t\geq\frac{n}{k}$.

For non-empty situation, Hilton and Milner gave the following result.

######  Theorem 1.2 (Hilton–Milner, [14]).

Let $n$ and $k$ be positive integers with $n\geq 2k$ and
$\mathcal{A},\mathcal{B}\subset{[n]\choose k}$. If $\mathcal{A}$ and
$\mathcal{B}$ are non-empty cross-intersecting, then

$|\mathcal{A}|+|\mathcal{B}|\leq{n\choose k}-{n-k\choose k}+1.$

The upper bound is achievable at $\mathcal{A}=\\{[k]\\}$ and
$\mathcal{B}=\\{F\in{[n]\choose k}:F\cap[k]\neq\emptyset\\}$. More generally,
Frankl and Tokushige showed that

######  Theorem 1.3 (Frankl-Tokushige, [11]).

Let $\mathcal{A}\subset{[n]\choose k}$ and $\mathcal{B}\subset{[n]\choose l}$
be non-empty cross-intersecting families with $n\geq k+l$ and $k\geq l$. Then

$|\mathcal{A}|+|\mathcal{B}|\leq{n\choose k}-{n-l\choose k}+1.$

The upper bound is achievable at $\mathcal{A}=\\{[l]\\}$ and
$\mathcal{B}=\\{F\in{[n]\choose k}:F\cap[l]\neq\emptyset\\}$. Borg and Feghali
[4] got the analogous maximum sum problem for the case when
$\mathcal{A}\subset{[n]\choose\leq r}$ and $\mathcal{B}\subset{[n]\choose\leq
s}$.

######  Theorem 1.4 (Borg–Feghali, [4]).

Let $n\geq 1,1\leq r\leq s,\mathcal{A}\subset{[n]\choose\leq r}$ and
$\mathcal{B}\subset{[n]\choose\leq s}$. If $\mathcal{A}$ and $\mathcal{B}$ are
non-empty cross-intersecting, then

$|\mathcal{A}|+|\mathcal{B}|\leq 1+\sum_{i=1}^{s}\left({n\choose
i}-{n-r\choose i}\right),$

and equality holds if $\mathcal{A}=\\{[r]\\}$ and
$\mathcal{B}=\\{B\in{[n]\choose\leq s}:B\cap[r]\neq\emptyset\\}.$

Recently, Shi, Frankl and Qian proved the following result.

######  Theorem 1.5 (Shi–Frankl–Qian, [21]).

Let $n,k,l,r$ be integers with $n\geq k+l,l\geq r\geq 1$, $c$ be a positive
constant and $\mathcal{A}\subset{[n]\choose k},\mathcal{B}\subset{[n]\choose
l}$. If $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting and
${n-r\choose l-r}\leq|\mathcal{B}|\leq{n-1\choose l-1}$, then

$|\mathcal{A}|+c|\mathcal{B}|\leq\textup{max}\left\\{{n\choose k}-{n-r\choose
k}+c{n-r\choose l-r},\,{n-1\choose k-1}+c{n-1\choose l-1}\right\\}$

and the upper bound is attained if and only if one of the following holds:
(i).

${n\choose k}-{n-r\choose k}+c{n-r\choose l-r}\geq{n-1\choose
k-1}+c{n-1\choose l-1},$ (1)

$n>k+l$, $\mathcal{A}=\\{A\in{[n]\choose k}:A\cap[r]\neq\emptyset\\}$ and
$\mathcal{B}=\\{B\in{[n]\choose l}:[r]\subset B\\}$;
(ii).

${n\choose k}-{n-r\choose k}+c{n-r\choose l-r}\leq{n-1\choose
k-1}+c{n-1\choose l-1},$ (2)

$n>k+l$, $\mathcal{A}=\\{A\in{[n]\choose k}:i\in A\\}$ and
$\mathcal{B}=\\{B\in{[n]\choose l}:i\in B\\}$ for some $i\in[n]$;
(iii). $n=k+l,c<1$, $\mathcal{B}\subset{[n]\choose l}$ with
$|\mathcal{B}|={n-r\choose l-r}$ and $\mathcal{A}={[n]\choose
k}\setminus\overline{\mathcal{B}}$;
(iv). $n=k+l,c=1$, $\mathcal{B}\subset{[n]\choose l}$ with ${n-r\choose
l-r}\leq|\mathcal{B}|\leq{n-1\choose l-1},\mathcal{A}={[n]\choose
k}\setminus\overline{\mathcal{B}}$;
(v). $n=k+l,c>1$, $\mathcal{B}\subset{[n]\choose l}$ with
$|\mathcal{B}|={n-1\choose l-1}$ and $\mathcal{A}={[n]\choose
k}\setminus\overline{\mathcal{B}}$;
where $\overline{\mathcal{B}}=\\{[n]\setminus B:B\in\mathcal{B}\\}$.

Setting $c=t-1$ in Theorem 1.5, they got the following interesting corollary
which is a generalization of Theorem 1.2.

######  Corollary 1.6 (Shi–Frankl–Qian, [21]).

Let $n$ and $k$ be positive integers with $n\geq 2k$ and $t\geq 2$. If
$\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{t}\subset{[n]\choose k}$
are non-empty pairwise cross-intersecting families, then

$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}\leq\textup{max}\left\\{{n\choose
k}-{n-k\choose k}+t-1,t{n-1\choose k-1}\right\\},$

and the upper bound is sharp.

Furthermore, Shi, Frankl and Qian [21] proposed the following problem.

######  Problem 1.7.

(Shi–Frankl–Qian, [21]) Let $\mathcal{A}_{1}\subset{[n]\choose
k_{1}},\mathcal{A}_{2}\subset{[n]\choose
k_{2}},\dots,\mathcal{A}_{t}\subset{[n]\choose k_{t}}$ be non-empty pairwise
cross-intersecting families with $t\geq 2$, $k_{1}\geq k_{2}\geq\cdots\geq
k_{t}$, and $n\geq k_{1}+k_{2}$. Is it true that

$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}\leq\max\left\\{{n\choose
k_{1}}-{n-k_{t}\choose k_{1}}+\sum_{i=2}^{t}{{n-k_{t}\choose
k_{i}-k_{t}}},\sum_{i=1}^{t}{n-1\choose k_{i}-1}\right\\}?$

As mentioned above that Shi, Frankl and Qian [21] obtained a positive answer
to the above problem for the special case that $k_{1}=k_{2}=\cdots=k_{t}$
(Corollary 1.6) by taking $c=t-1$ in the result of the maximum value of
$|\mathcal{A}|+c|\mathcal{B}|$ for two non-empty cross-intersecting families
$\mathcal{A}$ and $\mathcal{B}$ (Theorem 1.5). This will not work (will not
get a tight upper bound) if elements in different families have different
orders. In this paper, we get a positive answer to the above problem. The
following theorem is our main result.

######  Theorem 1.8.

Let $\mathcal{A}_{1}\subset{[n]\choose
k_{1}},\mathcal{A}_{2}\subset{[n]\choose
k_{2}},\dots,\mathcal{A}_{t}\subset{[n]\choose k_{t}}$ be non-empty pairwise
cross-intersecting families with $t\geq 2$, $k_{1}\geq k_{2}\geq\cdots\geq
k_{t}$, and $n\geq k_{1}+k_{2}$. Then

$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}\leq\textup{max}\left\\{{n\choose
k_{1}}-{n-k_{t}\choose k_{1}}+\sum_{i=2}^{t}{{n-k_{t}\choose
k_{i}-k_{t}}},\,\,\sum_{i=1}^{t}{n-1\choose k_{i}-1}\right\\}.$

The equality holds if and only if one of the following holds.
(i) ${n\choose k_{1}}-{n-k_{t}\choose k_{1}}+\sum_{i=2}^{t}{{n-k_{t}\choose
k_{i}-k_{t}}}>\sum_{i=1}^{t}{n-1\choose k_{i}-1}$, and there is some
$k_{t}$-element set $T\subset[n]$ such that
$\mathcal{A}_{1}=\\{F\in{[n]\choose k_{1}}:F\cap T\neq\emptyset\\}$ and
$\mathcal{A}_{j}=\\{F\in{[n]\choose k_{j}}:T\subset F\\}$ for each
$j\in[2,t]$;
(ii) ${n\choose k_{1}}-{n-k_{t}\choose k_{1}}+\sum_{i=2}^{t}{{n-k_{t}\choose
k_{i}-k_{t}}}\leq\sum_{i=1}^{t}{n-1\choose k_{i}-1}$, there are some $i\neq j$
such that $n>k_{i}+k_{j}$, and there is some $a\in[n]$ such that
$\mathcal{A}_{j}=\\{F\in{[n]\choose k_{j}}:a\in F\\}$ for each $j\in[t]$;
(iii) $t=2,n=k_{1}+k_{2}$, $\mathcal{A}_{1}\subset{[n]\choose k_{1}}$ and
$\mathcal{A}_{2}={[n]\choose k_{2}}\setminus\overline{\mathcal{A}_{1}}$;
(iv) $t\geq 3,k_{1}=k_{2}=\cdots=k_{t}=k,n=2k$ and
$\mathcal{A}_{1}=\mathcal{A}_{2}=\cdots=\mathcal{A}_{t}={[n]\choose
k}\setminus\overline{\mathcal{A}_{1}}$.

For $t=2$ in the above theorem, Theorem 1.3 and Theorem 1.5 already revealed
it. Our method works for $t=2$ as well, so we still include this case in the
proof. In both [21] and our paper, a result of Kruskal-Katona (Theorem 2.1) is
applied to allow us to consider only families $\mathcal{A}_{i}$ whose elements
are the first $|\mathcal{A}_{i}|$ elements in lexicographic order. The proof
technique in [21] (this kind of technique is also used by Wang and Zhang [22],
and Frankl and Kupavskii [10]) cannot be extended to more than two families of
subsets with different orders. We analyze the relationship between
$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}$ and the last element (in the lexicographic
order) of $\mathcal{A}_{1}$. Let $R$ be the last element of $\mathcal{A}_{1}$,
we will bound $\sum_{i=1}^{t}{|\mathcal{A}_{i}|}$ by a function $f(R)$. In
order to do this, we will prove a strong version of a result of Frankl-
Kupavskii [10] (Proposition 2.7). Namely, we prove Proposition 2.8 which gets
rid of some restrictions of Proposition 2.7. The main challenge left is to
estimate $f(R)$. In order to do this, we introduce new concepts
‘$c$-sequential’ and ‘down-up family’, and show four types of ‘local
convexity’ of $f(R)$ in Lemmas 2.11, 2.12, 2.13 and 2.14.

There are also studies regarding the problem of maximizing the product of
sizes of pairwise cross-intersecting families. This problem was first
addressed by Pyber [20] who proved that if $\mathcal{A}\subset{[n]\choose k}$
and $\mathcal{B}\subset{[n]\choose l}$ are cross-intersecting and either
$k=l\leq n/2$ or $k<l$ and $n\geq 2l+k-2$, then
$|\mathcal{A}||\mathcal{B}|\leq{n-1\choose k-1}{n-1\choose l-1}$.
Subsequently, Matsumoto and Tokushige [19] proved this for any $k\leq l\leq
n/2$, and they also determined the optimal structures. There are also related
product-version results in [2, 3, 9, 12, 13] (Due to the limitation of our
knowledge, we might have missed some references). Note that
$|\mathcal{A}||\mathcal{B}|\leq{n-1\choose k-1}{n-1\choose l-1}$ for two
cross-intersecting families implies that
$\prod_{i=1}^{t}|\mathcal{A}_{i}|\leq\prod_{i=1}^{t}{n-1\choose k_{i}-1}$ for
pairwise cross-intersecting families $\mathcal{A}_{1}\subset{[n]\choose
k_{1}},\mathcal{A}_{2}\subset{[n]\choose
k_{2}},\dots,\mathcal{A}_{t}\subset{[n]\choose k_{t}}$ and this bound is tight
by taking each $\mathcal{A}_{i}$ to be a full star. For the sum-version, tight
bound for the sum of sizes of two cross-intersecting families will not imply
the tight bound of the sum of sizes of more pairwise cross-intersecting
families of subsets of different orders.

Families $\mathcal{F}_{1},\dots,\mathcal{F}_{t}\subset{[n]\choose k}$ are said
to be cross-intersecting if $F_{1}\cap\cdots\cap F_{t}\neq\emptyset$ for all
$F_{i}\in\mathcal{F}_{i},i\in[t]$. If $F_{1}\cup\cdots\cup F_{t}\neq[n]$ for
all $F_{i}\in\mathcal{F}_{i},i\in[t]$, then we say
$\mathcal{F}_{1},\dots,\mathcal{F}_{t}\subset{[n]\choose k}$ are cross-union.
Cross-union can be viewed as the dual notation of cross-intersecting. It’s
easy to see that $\mathcal{F}_{1},\cdots,\mathcal{F}_{t}$ are cross-
intersecting if and only if
$\overline{\mathcal{F}_{1}},\cdots,\overline{\mathcal{F}_{t}}$ are cross-
union, where $\overline{\mathcal{F}_{i}}=\\{[n]-F:F\in\mathcal{F}_{i}\\}$.
Recently, Cambie–Kim–Liu–Tran [5] proved a conjecture of Frankl [7] about the
maximum sum of the sizes of cross union families. Formulated in terms of
cross-intersecting families, their result is

######  Theorem 1.9.

(Cambie–Kim–Liu–Tran, [5]) Let $n=((t-1)k-l)/(t-2)$ where $1\leq l\leq n-k$
and $t\geq 4l+1$. If $\mathcal{F}_{1},\dots,\mathcal{F}_{t}\subset{[n]\choose
k}$ are non-empty cross-intersecting, then

$|\mathcal{F}_{1}|+\cdots+|\mathcal{F}_{t}|\leq t{n-1\choose k-1}.$

The condition $l\leq n-k$ (i. e. , $n\geq{t\over t-1}k$ ) in the above theorem
is natural since $n<{t\over t-1}k$ implies that all families
$\mathcal{F}_{1},\dots,\mathcal{F}_{t}\subset{[n]\choose k}$ are cross-
intersecting automatically. However, the condition $l\geq 1$ (i.e.
$n\leq{(t-1)k-1\over t-2}$) is because that an upper bound of the sum of the
sizes of $(t-1)$ cross-intersecting families will give an upper bound of the
sum of the sizes of $t$ cross-intersecting families, in other words, results
on small $t$ build a sort of foundation for large $t$. Indeed, due to the
requirement of large $t$ in the above theorem, the authors in [5] also pointed
out a natural question what happens if $t$ is smaller. Our result is a basis
for a more general question not requiring that all $t$ families are
$k$-uniform and generalizing to that any $s$ families from these $t$ families
are cross-intersecting. Precisely, let $2\leq s\leq t$, we say that
$\mathcal{F}_{1}\subset{[n]\choose
k_{1}},\dots,\mathcal{F}_{t}\subset{[n]\choose k_{t}}$ are $s$-wise-cross-
intersecting families if $\mathcal{F}_{i_{1}},\ldots,\mathcal{F}_{i_{s}}$ are
cross-intersecting for any $1\leq i_{1}<i_{2}<\cdots<i_{s}\leq t$.

######  Question 1.10.

Let $\mathcal{F}_{1}\subset{[n]\choose
k_{1}},\dots,\mathcal{F}_{t}\subset{[n]\choose k_{t}}$ be $s$-wise-cross-
intersecting with $k_{1}\geq k_{2}\geq\dots\geq k_{t}$, $2\leq s\leq t$ and
$n\geq(k_{1}+\cdots+k_{s})/(s-1)$. What is
$\max\sum_{i=1}^{t}|\mathcal{F}_{i}|$?

There is the condition $n\geq(k_{1}+\cdots+k_{s})/(s-1)$ since all
$\mathcal{F}_{1}\subset{[n]\choose
k_{1}},\dots,\mathcal{F}_{s}\subset{[n]\choose k_{s}}$ are automatically
cross-intersecting if $n<(k_{1}+\cdots+k_{s})/(s-1)$. Clearly, if
$\mathcal{F}_{1}\subset{[n]\choose
k_{1}},\dots,\mathcal{F}_{t}\subset{[n]\choose k_{t}}$ are $s$-wise-cross-
intersecting, then $\mathcal{F}_{1},\dots,\mathcal{F}_{t}$ are $(s-1)$-wise
cross-intersecting, hence a result for $s_{0}$-wise cross-intersecting
families yields a result for all $s$-wise cross-intersecting families for
$s\geq s_{0}$ and the same range of $n$. Theorem 1.8 answers the question
above for $s\in[2,t]$ and $n\geq k_{1}+k_{2}$. It’s interesting to study
further for $s\geq 3$ and $(k_{1}+\cdots+k_{s})/(s-1)\leq n<k_{1}+k_{2}$.

The condition that $n\geq k_{1}+k_{2}$ in Theorem 1.8 is to guarantee that no
two families are automatically cross-intersecting. If $n<k_{1}+k_{t}$, then
$\mathcal{A}_{1}$ and $\mathcal{A}_{i}$ are automatically cross-intersecting
for each $i\in[2,t]$ and we can remove $\mathcal{A}_{1}$. Hence $n\geq
k_{1}+k_{t}$ is a natural condition when we consider extremal problems for
non-empty pairwise cross-intersecting families
$\mathcal{A}_{1}\subset{[n]\choose k_{1}},\mathcal{A}_{2}\subset{[n]\choose
k_{2}},\dots,\mathcal{A}_{t}\subset{[n]\choose k_{t}}$ with $t\geq 2$,
$k_{1}\geq k_{2}\geq\cdots\geq k_{t}$. On the other hand, it is interesting to
consider the same question under the condition $k_{1}+k_{t}\leq
n<k_{1}+k_{2}$. For example, if $k_{1}+k_{3}\leq n<k_{1}+k_{2}$, then all
$k_{1}$-uniform families and all $k_{2}$-uniform families are automatically
cross-intersecting, on the other hand, $k_{i}$-uniform families and
$k_{j}$-uniform families are not automatically cross-intersecting for
$\\{i,j\\}\neq\\{1,2\\}$. Our method can go further by relaxing the
requirement to $n\geq k_{1}+k_{t}$. Indeed, our method is a basis, there are
more ingredients in the proof, we will reveal this in another manuscript.

##  2  Proof for Theorem 1.8

When we write a set $A=\\{a_{1},a_{2},\ldots,a_{s}\\}\subset[n]$, we always
assume that $a_{1}<a_{2}<\ldots<a_{s}$ throughout the paper. Let us introduce
the lexicographic (lex for short) order of subsets of positive integers. Let
$A$ and $B$ be finite subsets of the set of positive integers
$\mathbb{Z}_{>0}$. We say that $A\prec B$ if either $A\supset B$ or
$\min(A\setminus B)<\min(B\setminus A)$. In particular, $A\prec A$. Let
$\mathcal{L}([n],r,k)$ denote the first $r$ subsets in ${[n]\choose k}$ in the
lex order. Given a set $R$, we denote
$\mathcal{L}([n],R,k):=\\{F\in{[n]\choose k}:F\prec R\\}$. Let
$\mathcal{F}\subset{[n]\choose k}$ be a family, we say $\mathcal{F}$ is
L-initial if $\mathcal{F}=\mathcal{L}([n],|\mathcal{F}|,k)$.

The well-known Kruskal-Katona theorem [17, 18] will play an important role in
our discussion, an equivalent formulation of which was given in [8, 15] as
follows.

######  Theorem 2.1 (Kruskal-Katona, [17, 18]).

For $\mathcal{A}\subset{[n]\choose k}$ and $\mathcal{B}\subset{[n]\choose l}$,
if $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then
$\mathcal{L}([n],|\mathcal{A}|,k)$ and $\mathcal{L}([n],|\mathcal{B}|,l)$ are
cross-intersecting as well.

By Theorem 2.1, to prove the quantitative part of Theorem 1.8 we may assume
that $\mathcal{A}_{i}$ is L-initial, that is,
$\mathcal{A}_{i}=\mathcal{L}([n],|\mathcal{A}_{i}|,k_{i})$ for each $i\in[t]$.
From now on, we assume that $\mathcal{A}_{1}\subset{[n]\choose
k_{1}},\mathcal{A}_{2}\subset{[n]\choose
k_{2}},\dots,\mathcal{A}_{t}\subset{[n]\choose k_{t}}$ are non-empty pairwise
cross-intersecting families with $k_{1}\geq k_{2}\geq\cdots\geq k_{t},n\geq
k_{1}+k_{2}$, and $\mathcal{A}_{j}$ is L-initial for each $j\in[t]$.

######  Remark 2.2.

If $|\mathcal{A}_{i}|\leq{n-1\choose k_{i}-1}$ for each $i\in[t]$, then
$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}\leq\sum_{i=1}^{t}{{n-1\choose k_{i}-1}}$,
as desired.

From now on, we may assume that $|\mathcal{A}_{i}|\geq{n-1\choose k_{i}-1}$
for some $i\in[t]$, and we fix such an $i$.

###  2.1 Sketch of the proof of Theorem 1.8

In this section, we give an outline of the proof and leave the proofs of some
propositions and lemmas to Subsection 2.2 and Section 3.

We will first show that $|\mathcal{A}_{i}|$ cannot be too large ( See
Proposition2.3 whose proof will be given in Subsection 2.2). Let

$m=\min_{j\neq i}k_{j}.$ (3)

######  Proposition 2.3.

$|\mathcal{A}_{i}|\leq{n-1\choose k_{i}-1}+\cdots+{n-m\choose k_{i}-1}$.

One important ingredient of the proof is to bound
$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}$ by a function of the last element of
$\mathcal{A}_{i}$. Let us list the set of the last elements of all possible
$\mathcal{A}_{i}$.

Let $Z={n-2\choose k_{i}-1}+\cdots+{n-m\choose
k_{i}-1},R_{0}=\\{1,n-k_{i}+2,n-k_{i}+3,\dots,n\\},R_{1}=\\{2,3,\cdots,k_{i}+1\\}$,
$R_{Z}=\\{m,n-k_{i}+2,n-k_{i}+3,\dots,n\\}$ and $R_{0}\precneqq
R_{1}\precneqq\cdots\precneqq R_{Z}$ in lex order with each $|R_{j}|=k_{i}$
for $j\in[Z]$. We denote

$\mathcal{R}:=\\{R_{0},R_{1},\dots,R_{Z}\\}.$ (4)

By Proposition 2.3, we have ${n-1\choose
k_{i}-1}\leq|\mathcal{A}_{i}|\leq{n-1\choose k_{i}-1}+Z$. Since
$\mathcal{A}_{i}$ is L-initial, we have the following remark.

######  Remark 2.4.

Let $0\leq r\leq Z$. If $|\mathcal{A}_{i}|={n-1\choose k_{i}-1}+r$, then
$\mathcal{A}_{i}=\mathcal{L}([n],R_{r},k_{i})$.

Let $R$ be the last element of $\mathcal{A}_{i}$ (we call $R$ the ID of
$\mathcal{A}_{i}$), clearly $R\in\mathcal{R}$. We will bound
$\sum_{i=1}^{t}{|\mathcal{A}_{i}|}$ by a function of $R$. In order to do this,
we will extend a result of Frankl-Kupavskii (Proposition 2.7).

######  Definition 2.5.

We say that $A$ and $B$ strongly intersect at their last element $q$ if $A\cap
B=\\{q\\}$ and $A\cup B=[q]$. We also say $A$ is $B$’s partner.

######  Definition 2.6.

Let $t\geq 2$. We say that $\mathcal{F}_{1}\subset{[n]\choose
l_{1}},\mathcal{F}_{2}\subset{[n]\choose
l_{2}},\dots,\mathcal{F}_{t}\subset{[n]\choose l_{t}}$ are maximal pairwise
cross-intersecting if whenever $\mathcal{F}^{\prime}_{1}\subset{[n]\choose
l_{1}},\mathcal{F}^{\prime}_{2}\subset{[n]\choose
l_{2}},\dots,\mathcal{F}^{\prime}_{t}\subset{[n]\choose l_{t}}$ are pairwise
cross-intersecting with
$\mathcal{F}^{\prime}_{1}\supset\mathcal{F}_{1},\dots,\mathcal{F}^{\prime}_{t}\supset\mathcal{F}_{t}$,
then
$\mathcal{F}_{1}=\mathcal{F}^{\prime}_{1},\dots,\mathcal{F}_{t}=\mathcal{F}^{\prime}_{t}$.

######  Proposition 2.7 (Frankl-Kupavskii [10]).

Let $a,b\in\mathbb{Z}_{>0},a+b\leq n$. Let $P$ and $Q$ be non-empty subsets of
$[n]$ with $|P|\leq a$ and $|Q|\leq b$. If $Q$ is the partner of $P$, then
$\mathcal{L}([n],P,a)$ and $\mathcal{L}([n],Q,b)$ are maximal cross-
intersecting families.

This result cannot be applied to our situation directly. We will get rid of
the condition $|Q|\leq b$ in Proposition 2.7 and show the following result in
Subsection 2.2.

######  Proposition 2.8.

Let $a,b,n\in\mathbb{Z}_{>0}$ and $a+b\leq n$. For $P\subset[n]$ with $|P|\leq
a$, let $Q$ be the partner of $P$. Then $\mathcal{L}([n],Q,b)$ is the maximum
L-initial $b$-uniform family that is cross-intersecting to
$\mathcal{L}([n],P,a)$. Moreover, $\mathcal{L}([n],Q,b)\neq\emptyset$ if and
only if $\min P\leq b$.

We will give a formula to calculate the size of an $L-$initial family as
follows. The proof will be given in Subsection 2.2.

######  Proposition 2.9.

Let $k,l,n$ be positive integers. Let
$A=\\{a_{1},a_{2},\dots,a_{s_{a}}\\}\subset[n]$ and
$B=\\{b_{1},b_{2},\dots,b_{s_{b}}\\}$ be $A$’s partner. Then

$\displaystyle|\mathcal{L}([n],A,k)|={n-b_{1}\choose k-b_{1}}+{n-b_{2}\choose
k-b_{2}+1}+\cdots+{n-b_{s_{b}}\choose k-b_{s_{b}}+s_{b}-1},$ (5)
$\displaystyle|\mathcal{L}([n],B,l)|={n-a_{1}\choose l-a_{1}}+{n-a_{2}\choose
l-a_{2}+1}+\cdots+{n-a_{s_{a}}\choose l-a_{s_{a}}+s_{a}-1}.$ (6)

Combining Proposition 2.8 and Proposition 2.9, we can bound
$\sum_{j=1}^{t}|\mathcal{A}_{j}|$ based on the ID of $\mathcal{A}_{i}$ as
follows.

######  Corollary 2.10.

Let $R=\\{a_{1},a_{2},\dots,a_{k_{i}}\\}$ be the ID of $\mathcal{A}_{i}$ and
$T=\\{b_{1},b_{2},\dots,b_{s_{b}}\\}$ be the partner of $R$. Then

$\displaystyle\sum_{j=1}^{t}|\mathcal{A}_{j}|$
$\displaystyle\leq{n-b_{1}\choose k_{i}-b_{1}}+{n-b_{2}\choose
k_{i}-b_{2}+1}+\cdots+{n-b_{s_{b}}\choose k_{i}-b_{s_{b}}+s_{b}-1}$ (7)
$\displaystyle\quad+\sum_{j\neq i}\left[{n-a_{1}\choose
k_{j}-a_{1}}+{n-a_{2}\choose k_{j}-a_{2}+1}+\cdots+{n-a_{k_{i}}\choose
k_{j}-a_{k_{i}}+k_{i}-1}\right]$
$\displaystyle\overset{\triangle}{=}f_{i}(R).$

Thus, to show Theorem 1.8, it is sufficient to show that

$f_{i}(R)\leq\textup{max}\left\\{{n\choose k_{1}}-{n-k_{t}\choose
k_{1}}+\sum_{i=2}^{t}{{n-k_{t}\choose
k_{i}-k_{t}}},\,\,\sum_{i=1}^{t}{n-1\choose k_{i}-1}\right\\}.$

Note that

$\displaystyle
f_{1}(\\{1,n-k_{1}+2,n-k_{1}+3,\ldots,n\\})=\sum_{i=1}^{t}{n-1\choose
k_{i}-1},{\rm\ and\ correspondingly,}$
$\displaystyle|\mathcal{A}_{j}|={n-1\choose k_{j}-1}{\rm\ for\ each\ }j\in[t]$
(8)

in view of (7). And

$\displaystyle f_{1}(\\{m\\}\cup[n-k_{1}+2,n])$ $\displaystyle=$
$\displaystyle f_{1}(\\{k_{t}\\}\cup[n-k_{1}+2,n])(\rm\ in\ view\ of\
(\ref{m}))$ $\displaystyle=$ $\displaystyle{n\choose k_{1}}-{n-k_{t}\choose
k_{1}}+\sum_{i=2}^{t}{{n-k_{t}\choose k_{i}-k_{t}}}{\rm\ and\
correspondingly,}$ $\displaystyle|\mathcal{A}_{1}|$ $\displaystyle=$
$\displaystyle{n\choose k_{1}}-{n-k_{t}\choose k_{1}},{\rm\ and\
}|\mathcal{A}_{j}|={n-k_{t}\choose k_{j}-k_{t}}{\rm\ if\ }j\in[t]$ (9)

in view of (7).

Hence, to show Theorem 1.8, it is sufficient to show that
$f_{i}(R)\leq\max\\{f_{1}(\\{1,n-k_{i}+2,n-k_{i}+3,\ldots,n\\}),f_{1}(\\{m,n-k_{i}+2,n-k_{i}+3,\ldots,n\\})\\}$.
In order to do this, we will show that
$f_{i}(R)\leq\max\\{f_{i}(\\{1,n-k_{i}+2,n-k_{i}+3,\ldots,n\\}),f_{i}(\\{m,n-k_{i}+2,n-k_{i}+3,\ldots,n\\})\\}$
and
$\max\\{f_{i}(\\{1,n-k_{i}+2,n-k_{i}+3,\ldots,n\\})=f_{1}(\\{1,n-k_{1}+2,n-k_{1}+3,\ldots,n\\})$,
$\max\\{f_{i}(\\{m,n-k_{i}+2,n-k_{i}+3,\ldots,n\\})=f_{1}(\\{m,n-k_{1}+2,n-k_{1}+3,\ldots,n\\})$.
For this purpose, we will introduce the concept ‘$c$-sequential’ and show some
‘local convexity’ of $f_{i}(R)$.

Let $\mathcal{A}\subset{[n]\choose k}$ be a family and $c\in[k]$. We say that
$\mathcal{A}$ is $c$-sequential if there are $A\subset[n]$ with $|A|=k-c$ and
$a\geq\max A$ (For a set $A\subset[n]$, denote $\max A=\max\\{a:a\in A\\}$ and
$\min A=\min\\{a:a\in A\\}$) such that
$\mathcal{A}=\\{A\sqcup\\{a+1,\dots,a+c\\},A\sqcup\\{a+2,\dots,a+c+1\\},\dots,A\sqcup\\{b-c+1,\dots,b\\}\\}$,
and we say $A$ is the head of $\mathcal{A}$ and $\mathcal{A}$ is
$c$-sequential from $a+c$ to $b$, write
$A_{1}\overset{c}{\prec}A_{2}\overset{c}{\prec}\cdots\overset{c}{\prec}A_{b-a-c+1}$,
where
$A_{1}=A\sqcup\\{a+1,\dots,a+c\\},A_{b-a-c+1}=A\sqcup\\{b-c+1,\dots,b\\}$. In
particular, if $l_{2}=l_{1}+1$, we write
$A_{l_{1}}\overset{c}{\prec}A_{l_{2}}$; if $\max A_{l_{2}}=n$, write
$A_{l_{1}}\overset{c}{\longrightarrow}A_{l_{2}}$. Note that if
$|\mathcal{A}|=1$, then $\mathcal{A}$ is $c$-sequential for any $c\in[k]$. Let
$\mathcal{F}$ be a family and $F_{1},F_{2}\in\mathcal{F}$. If $F_{1}\precneqq
F_{2}$ and there is no $F^{\prime}\in\mathcal{F}$ such that $F_{1}\precneqq
F^{\prime}\precneqq F_{2}$, then we say $F_{1}<F_{2}$ in $\mathcal{F}$, or
$F_{1}<F_{2}$ simply if there is no confusion.

Let $R$ and $R^{\prime}$ satisfy $R\prec R^{\prime}$ with the corresponding
partners $T$ and $T^{\prime}$ respectively. In order to measure
$f_{i}(R^{\prime})-f_{i}(R)$, we define

$\displaystyle\alpha(R,R^{\prime}):=|\mathcal{L}([n],R^{\prime},k_{i})|-|\mathcal{L}([n],R,k_{i})|,$
(10) $\displaystyle\beta(R,R^{\prime}):=\sum_{j\neq
i}(|\mathcal{L}([n],T,k_{j})|-|\mathcal{L}([n],T^{\prime},k_{j})|).$ (11)

Consequently,

$\displaystyle
f_{i}(R^{\prime})-f_{i}(R)=\alpha(R,R^{\prime})-\beta(R,R^{\prime}).$

We will prove the following four crucial lemmas showing some ‘local convexity’
of $f_{i}(R)$ in Section 3.

######  Lemma 2.11.

Let $c\in[k_{i}]$ and $F,G,H\in\mathcal{R}$ with
$F\overset{c}{\prec}G\overset{c}{\prec}H$. Assume that $n>k_{1}+k_{2}$ or
$t>2$. If $\alpha(F,G)\geq\beta(F,G)$, then $\alpha(G,H)>\beta(G,H)$. This
means that $f_{i}(G)\geq f_{i}(F)$ implies $f_{i}(H)>f_{i}(G)$.

Denote $\mathcal{R}_{k}:=\\{R\in\mathcal{R}:[n-k+1,n]\subset R\\}$, and
$\mathcal{R}(k):=\\{R\setminus[n-k+1,n]:R\in\mathcal{R}_{k}\\}$ for
$k\in[k_{i}-1]$. In addition, we will write $\mathcal{R}(0)=\mathcal{R}$. When
we consider $f_{i}(R),\alpha(R,T)$ and $\beta(R,T)$ for
$R,T\in\mathcal{R}_{k}$, we simply write $f_{i}(R\setminus[n-k+1,n])$ etc. In
particular, $f_{i}(\\{1\\})$ is indeed
$f_{i}(\\{1,n-k_{i}+1,n-k_{i}+2,\dots,n\\})$, and $f_{i}(\\{m\\})$ is indeed
$f_{i}(\\{m,n-k_{i}+1,n-k_{i}+2,\dots,n\\})$.

######  Lemma 2.12.

For any $j\in[0,k_{i}-1]$, let $1\leq c\leq k_{i}-j$ and
$F,G,H\in\mathcal{R}(j)$ with $F\overset{c}{\prec}G\overset{c}{\prec}H$.
Assume that $n>k_{1}+k_{2}$ or $t>2$. If $\alpha(F,G)\geq\beta(F,G)$, then
$\alpha(G,H)>\beta(G,H)$. This means that $f_{i}(G)\geq f_{i}(F)$ implies
$f_{i}(H)>f_{i}(G)$.

######  Lemma 2.13.

Suppose $k_{i}\geq 2$. Let $3\leq j\leq k_{i}+1$. Assume that $n>k_{1}+k_{2}$
or $t>2$. If $f(\\{2,3,\dots,j\\})\leq f(\\{2,3,\dots,j-1\\})$, then
$f(\\{2,3,\dots,j-1\\})<f(\\{2,3,\dots,j-2\\})$.

######  Lemma 2.14.

Let $m+1\leq j\leq m+k_{i}-1$. Assume that $n>k_{1}+k_{2}$ or $t>2$. If
$f(\\{m,m+1,\dots,j\\})\leq f(\\{m,m+1,\dots,j-1\\})$, then
$f(\\{m,m+1,\dots,j-1\\})<f(\\{m,m+1,\dots,j-2\\})$.

Combining these four lemmas, we will be able to show that
$f_{i}(R)\leq\max\\{f_{i}(\\{1\\}),f_{i}(\\{m\\})\\}$. Let us be precise
below.

First, if $n=k_{1}+k_{2}$ and $t=2$, then note that a set
$A\in{k_{1}+k_{2}\choose k_{1}}$ intersects with any set
$B\in{k_{1}+k_{2}\choose k_{2}}$ except $B=\overline{A}$. So the maximum value
of $|\mathcal{A}_{1}|+|\mathcal{A}_{2}|$ is reached when
$\mathcal{A}_{1}\subset{[n]\choose k_{1}}$ and $\mathcal{A}_{2}={[n]\choose
k_{2}}\setminus\overline{\mathcal{A}_{1}}$.

Next, we may assume that $n>k_{1}+k_{2}$ or $t>2$.

For a family $\mathcal{F}$, denote
$f(\mathcal{F})=\max\\{f(F):F\in\mathcal{F}\\}$. Applying Lemma 2.11
repeatedly, we have

$f_{i}(\mathcal{R})=\max\\{f_{i}(\\{2,3,\dots,k_{i}+1\\}),f_{i}(\\{m,m+1,\dots,m+k_{i}-1\\}),f_{i}(\mathcal{R}(1))\\}.$
(12)

(Let us explain the above observation. For example, suppose that
$k_{i}=3,a<b<c\in[n]$ and $\\{a,b,c\\}\in\mathcal{R}$. Applying Lemma 2.11, we
have

$\displaystyle f_{i}(\\{a,b,c\\})$
$\displaystyle\leq\max\\{f_{i}(\\{a,b,b+1\\},f(_{i}\\{a,b,n\\})\\}$
$\displaystyle\leq\max\\{f_{i}(\\{a,b,b+1\\},f_{i}(\mathcal{R}(1))\\}$
$\displaystyle\leq\max\\{f_{i}(\\{a,a+1,a+2\\}),f_{i}(\mathcal{R}(1))\\}$
$\displaystyle\leq\max\\{f_{i}(\\{2,3,4\\}),f_{i}(\\{m,m+1,m+2\\}),f_{i}(\mathcal{R}(1))\\}.)$

Similarly, applying Lemma 2.12 repeatedly, we have

$\displaystyle
f_{i}(\mathcal{R}(1))=\max\\{f_{i}(\\{2,3,\dots,k_{i}\\}),f_{i}(\\{m,m+1,\dots,m+k_{i}-2\\}),f_{i}(\mathcal{R}(2))\\},$
$\displaystyle
f_{i}(\mathcal{R}(2))=\max\\{f_{i}(\\{2,3,\dots,k_{i}-1\\}),f_{i}(\\{m,m+1,\dots,m+k_{i}-3\\}),f_{i}(\mathcal{R}(3))\\},$
$\displaystyle\quad\vdots$ $\displaystyle
f_{i}(\mathcal{R}(k_{i}-1))=\max\\{f_{i}(\\{1\\}),f_{i}(\\{m\\})\\}.$ (13)

By Lemma 2.13, we have

$\displaystyle\max\\{f_{i}(\\{2,3,\dots,k_{i}+1\\}),f_{i}(\\{2,3,\dots,k_{i}\\}),\dots,f_{i}(\\{2,3\\})\\}$
$\displaystyle\leq\max\\{f_{i}(\\{2,3,\dots,k_{i}+1\\}),f_{i}(\\{2\\})\\}$
$\displaystyle\leq\max\\{f_{i}(\\{2,3,\dots,k_{i}+1\\}),\max\\{f_{i}(\\{1\\}),f_{i}(\\{m\\})\\}\\}$
(14)

By Lemma 2.14 , we have

$\displaystyle\max\\{f_{i}(\\{m,m+1,\dots,m+k_{i}-1\\}),f_{i}(\\{m,m+1,\dots,m+k_{i}-2\\}),\dots,f_{i}(\\{m\\})\\}$
$\displaystyle=\max\\{f_{i}(\\{m,m+1,\dots,m+k_{i}-1\\}),f_{i}(\\{m\\})\\}.$
(15)

Note that $\\{m-1,n-k_{i}+2,\dots,n\\}<\\{m,m+1,\dots,m+k_{i}-1\\}$ in
$\mathcal{R}$. By Proposition 2.19,

$\beta(\\{m-1,n-k_{i}+2,\dots,n\\},\\{m,m+1,\dots,m+k_{i}-1\\})=\sum_{j\neq
i}{n-(m+k_{i}-1)\choose k_{j}-m+1}\geq 1,$

so

$f_{i}(\\{m,m+1,\dots,m+k_{i}-1\\})\leq
f_{i}(\\{m-1,n-k_{i}+2,\dots,n\\})=f_{i}(\\{m-1\\})\leq\max\\{f_{i}(\\{1\\}),f_{i}(\\{m\\})\\}.$
(16)

Combining (12), (13), (2.1), (2.1) and (16), we have

$f_{i}(\mathcal{R})=\max\\{f_{i}(\\{2,3,\dots,k_{i}+1\\}),f_{i}(\\{1\\}),f_{i}(\\{m\\})\\}.$
(17)

Recall that $\\{1,n-k_{i}+2,\dots,n\\}<\\{2,3,\dots,k_{i}+1\\}$ in
$\mathcal{R}$. So we have

$\alpha(\\{1\\},\\{2,3,\dots,k_{i}+1\\})=1.$

By Proposition 2.19, we get

$\beta((\\{1\\},\\{2,3,\dots,k_{i}+1\\}))=\sum_{j\neq i}{n-(k_{i}+1)\choose
k_{j}-1}\geq 1.$

So $f_{i}(\\{1\\})\geq f_{i}(\\{2,3,\dots,k_{i}+1\\})$. Combining with (17),
we have

$f_{i}(\mathcal{R})=\max\\{f_{i}(\\{1\\}),f_{i}(\\{m\\})\\}.$ (18)

The quantitative part of Theorem 1.8 will be complete by showing the following
result in Subsection 2.2.

######  Proposition 2.15.

Suppose that $n\geq k_{1}+k_{2}$ and $k_{1}\geq k_{2}\geq\dots\geq k_{t}$. Let
$i\in[t]$ and $m$ be defined in (3), then for $1\leq s\leq m$, we have

$f_{1}(\\{s\\})=\max\\{f_{j}(\\{s\\}):j\in[t]\\}.$

In particular,

$\displaystyle f_{1}(\\{1\\})=\max\\{f_{j}(\\{1\\}):j\in[t]\\},$
$\displaystyle f_{1}(\\{m\\})=\max\\{f_{j}(\\{m\\}):j\in[t]\\}.$

What left is to discuss when the equality holds in the above inequality.

Firstly, we assume that $\sum_{j=1}^{t}{n-1\choose k_{j}-1}<{n\choose
k_{1}}-{n-k_{t}\choose k_{1}}+\sum_{i=2}^{t}{n-k_{t}\choose k_{i}-k_{t}}$ and

$\sum_{i=1}^{t}|\mathcal{A}_{i}|={n\choose k_{1}}-{n-k_{t}\choose
k_{1}}+\sum_{i=2}^{t}{n-k_{t}\choose k_{i}-k_{t}}.$

Combining Lemma 2.12 and Lemma 2.14, we have
$\sum_{i=1}^{t}|\mathcal{A}_{i}|=f(\\{m\\})$. In view of (2.1), we have
$|\mathcal{A}_{1}|={n\choose k_{1}}-{n-k_{t}\choose k_{1}}$ and
$|\mathcal{A}_{j}|={n-k_{t}\choose k_{i}-k_{t}}$ for $j\in[2,t]$, in
particular, $|\mathcal{A}_{t}|=1$. Let $\mathcal{A}_{t}=\\{T\\}$ for some
$T\in{[n]\choose k_{t}}$. Since $\mathcal{A}_{1}$ and $\mathcal{A}_{t}$ are
cross-intersecting and $|\mathcal{A}_{1}|={n\choose k_{1}}-{n-k_{t}\choose
k_{1}}$, we have $\mathcal{A}_{1}=\\{F\in{[n]\choose k_{1}}:F\cap
T\neq\emptyset\\}$. Since $\mathcal{A}_{j}$ and $\mathcal{A}_{t}$ are cross-
intersecting and $|\mathcal{A}_{j}|={n-k_{t}\choose k_{i}-k_{t}}$, we get
$\mathcal{A}_{j}=\\{F\in{[n]\choose k_{j}}:T\subset F\\}$ for $j\in[2,t]$. As
desired.

Next, we assume that $\sum_{j=1}^{t}{n-1\choose k_{j}-1}>{n\choose
k_{1}}-{n-k_{t}\choose k_{1}}+\sum_{i=2}^{t}{n-k_{t}\choose k_{i}-k_{t}}$ and

$\sum_{i=1}^{t}|\mathcal{A}_{i}|=\sum_{j=1}^{t}{n-1\choose k_{j}-1}.$

Combining Lemma 2.12 and Lemma 2.14, we have
$\sum_{i=1}^{t}|\mathcal{A}_{i}|=f(\\{1\\})$ and
$|\mathcal{A}_{j}|={n-1\choose k_{j}-1}$ for each $j\in[t]$ and
$|\mathcal{A}_{i}|+|\mathcal{A}_{j}|={n-1\choose k_{i}-1}+{n-1\choose
k_{j}-1}$ for any $i,j\in[t]$. If there are some $i\neq j\in[t]$ such that
$n>k_{i}+k_{j}$, then by taking $c=1$ in Theorem 1.5 (ii), there is $a\in[n]$
such that $\mathcal{A}_{i}=\\{F\in{[n]\choose k_{i}}:a\in F\\}$ and
$\mathcal{A}_{j}=\\{F\in{[n]\choose k_{j}}:a\in F\\}$. Thus,
$\mathcal{A}_{j}=\\{F\in{[n]\choose k_{j}}:a\in F\\}$ for $j\in[t]$, as
desired. Otherwise, we will meet the following case: $t\geq 3$,
$k:=k_{1}=k_{2}=\cdots=k_{t}$ and $n=2k$. since
$|\mathcal{A}_{1}|+|\mathcal{A}_{j}|=2{n-1\choose k-1}$ for each $j\in[2,t]$,
then by theorem 1.5 (iv), we can see that
$\mathcal{A}_{2}=\cdots=\mathcal{A}_{t}={[n]\choose
k}\setminus\overline{\mathcal{A}_{1}}$, similarly, we have
$\mathcal{A}_{1}=\mathcal{A}_{3}=\cdots=\mathcal{A}_{t}$, therefore,
$\mathcal{A}_{1}=\mathcal{A}_{2}=\cdots=\mathcal{A}_{t}={[n]\choose
k}\setminus\overline{\mathcal{A}_{1}}$.

We owe the proofs of Proposition 2.3, 2.8, 2.9, 2.15 and 2.19, and Lemmas
2.11, 2.12, 2.13 and 2.14. The proofs of Propositions 2.8, 2.9, 2.15 and 2.19
will be given in Section 2.2, and the proofs of Lemmas 2.11, 2.12, 2.13 and
2.14 will be given in Section 3.

###  2.2 Proofs of Propositions 2.3, 2.8, 2.9 2.15 and 2.19

######  Claim 2.16.

Let $s\geq 1$ be integer and $j\in[t]\setminus\\{i\\}$. If
$|\mathcal{A}_{i}|\geq{n-1\choose k_{i}-1}+{n-2\choose
k_{i}-1}+\cdots+{n-s\choose k_{i}-1}$, then $[s]\subset F$ for any
$F\in\mathcal{A}_{j}$.

###### Proof.

Suppose that there is $j\in[t]\setminus\\{i\\},a\in[s]$ and
$F\in\mathcal{A}_{j}$ such that $a\not\in F$. Since $n\geq k_{1}+k_{2}\geq
k_{i}+k_{j}$, there exists $F^{\prime}\subset[n]\setminus F$ with $a\in
F^{\prime}$ and $|F^{\prime}|=k_{i}$. Since $\mathcal{A}_{i}$ is L-initial and
$|\mathcal{A}_{i}|\geq{n-1\choose k_{i}-1}+{n-2\choose
k_{i}-1}+\cdots+{n-s\choose k_{i}-1}$, $F^{\prime}\in\mathcal{A}_{i}$.
However, $F\cap F^{\prime}=\emptyset$, a contradiction to that
$\mathcal{A}_{i}$ and $\mathcal{A}_{j}$ are cross-intersecting. ∎

Now we apply the above fact to show Proposition 2.3. For convenience, let us
restate Proposition 2.3.

Proposition 2.3. $|\mathcal{A}_{i}|\leq{n-1\choose k_{i}-1}+\cdots+{n-m\choose
k_{i}-1}$.

###### Proof.

Let $j\in[t]\setminus\\{i\\}$ and $F\in\mathcal{A}_{j}$. If
$|\mathcal{A}_{i}|>{n-1\choose k_{i}-1}+\cdots+{n-m\choose k_{i}-1}$, then, by
Claim 2.16, $[m]\subset F$. Let
$\mathcal{A^{\prime}}\in\\{\mathcal{A}_{1},\dots,\mathcal{A}_{t}\\}\setminus\\{\mathcal{A}_{i}\\}$
be $m$-uniform. Then $\mathcal{A^{\prime}}=\\{[m]\\}$. Since $\mathcal{A}_{i}$
is L-initial and $|\mathcal{A}_{i}|>{n-1\choose k_{i}-1}+\cdots+{n-m\choose
k_{i}-1}$, there exists $G\in\mathcal{A}_{i}$ such that $G\cap[m]=\emptyset$,
so $\mathcal{A^{\prime}}$ and $\mathcal{A}_{i}$ are not cross-intersecting, a
contradiction. ∎

Now we give the proof of Proposition 2.9.

Proposition 2.9. Let $k,l,n$ be positive integers. Let
$A=\\{a_{1},a_{2},\dots,a_{s_{a}}\\}\subset[n]$ and
$B=\\{b_{1},b_{2},\dots,b_{s_{b}}\\}$ be $A$’s partner. Then

$\displaystyle|\mathcal{L}([n],A,k)|={n-b_{1}\choose k-b_{1}}+{n-b_{2}\choose
k-b_{2}+1}+\cdots+{n-b_{s_{b}}\choose k-b_{s_{b}}+s_{b}-1},$ (19)
$\displaystyle|\mathcal{L}([n],B,l)|={n-a_{1}\choose l-a_{1}}+{n-a_{2}\choose
l-a_{2}+1}+\cdots+{n-a_{s_{a}}\choose l-a_{s_{a}}+s_{a}-1}.$ (20)

###### Proof.

We give the proof of (19) only, since the proof of (20) is similar to (19).
W.l.o.g., assume $b_{1}=1$. Let
$D_{1}:=\\{1,\dots,a_{1}-1\\},D_{j}:=\\{a_{j-1}+1,\dots,a_{j}-1\\}$ for
$j\in[2,s_{a}-1]$, and $D_{s_{a}}:=\\{a_{s_{a-1}}+1,\dots,a_{s_{a}}\\}$. Let
$B:=\sqcup_{j=1}^{s_{a}}D_{j}$. If $k<s_{a}$, then

$\displaystyle\mathcal{L}([n],A,k)$ $\displaystyle=\\{F\in{[n]\choose
k}:F\prec A\\}$ $\displaystyle=\\{F\in{[n]\choose k}:F\cap
D_{1}\neq\emptyset\\}\sqcup\\{F\in{[n]\choose k}:F\cap
D_{1}=\emptyset,a_{1}\in F,F\cap D_{2}\neq\emptyset\\}$
$\displaystyle\quad\sqcup\cdots\sqcup\\{F\in{[n]\choose k}:F\cap
D_{j}=\emptyset,a_{j}\in F\,\,\text{for}\,\,j\in[k-1],F\cap
D_{k}\neq\emptyset\\}.$

If $k\geq s_{a}$, then

$\displaystyle\mathcal{L}([n],A,k)$ $\displaystyle=\\{F\in{[n]\choose k}:F\cap
D_{1}\neq\emptyset\\}\sqcup\\{F\in{[n]\choose k}:F\cap
D_{1}=\emptyset,a_{1}\in F,F\cap D_{2}\neq\emptyset\\}$
$\displaystyle\quad\sqcup\cdots\sqcup\\{F\in{[n]\choose k}:F\cap
D_{j}=\emptyset,a_{j}\in F\,\,\text{for}\,\,j\in[{s_{a}}-1],F\cap
D_{s_{a}}\neq\emptyset\\}$ $\displaystyle\quad\sqcup\\{F\in{[n]\choose
k}:F\cap[a_{s_{a}}]=A\\}.$

Thus,

$\displaystyle|\mathcal{L}([n],A,k)|$
$\displaystyle=\sum_{d=1}^{s_{a}}\sum_{j\in D_{d}}{n-j\choose k-d}$ (21)
$\displaystyle={n-b_{1}\choose k-b_{1}}+{n-b_{2}\choose
k-b_{2}+1}+\cdots+{n-b_{s_{b}}\choose k-b_{s_{b}}+s_{b}-1},$ (22)

as desired. ∎

We have the following observations.

######  Remark 2.17.

Let $k,n\in\mathbb{Z}_{>0}$ and $A=\\{a_{1},a_{2},\dots,a_{|A|}\\}\subset[n]$
with $|A|>k$. Let $j=\max\\{q:q\in[a_{k}]\setminus A\\}$ and
$A^{\prime}=(A\cap[j])\cup\\{j\\}$. Then
$\mathcal{L}([n],A,k)=\mathcal{L}([n],A^{\prime},k)$.

######  Remark 2.18.

Let $k,l,n\in\mathbb{Z}_{>0},n\geq k+l,R\subset[n],|R|=k$ and $\max R=n$. Let
$p$ be the last element of $R$ not continuing to $n$ and
$R^{\prime}=R\cap[p]$. Let $T$ and $T^{\prime}$ be the partners of $R$ and
$R^{\prime}$ respectively. Then
$\mathcal{L}([n],R,k)=\mathcal{L}([n],R^{\prime},k)$ and
$\mathcal{L}([n],T,l)=\mathcal{L}([n],T^{\prime},l)$.

Proposition 2.8. Let $a,b,n$ be positive integers satisfying $a+b\leq n$. For
$P\subset[n]$ with $|P|\leq a$, let $Q$ be the partner of $P$. Then
$\mathcal{L}([n],Q,b)$ is the maximum L-initial $b$-uniform family that is
cross-intersecting to $\mathcal{L}([n],P,a)$. Moreover,
$\mathcal{L}([n],Q,b)\neq\emptyset$ if and only if $\min P\leq b$.

###### Proof of Proposition 2.8.

Let $P_{0}$ be the last element of $\mathcal{L}([n],P,a)$. If $|P|=a$, then
$P_{0}=P$ and if $|P|<a$, then $P_{0}=P\cup[n-a+|P|+1,n]$. So $\min P_{0}=\min
P$. Then $[b]\cap P_{0}=\emptyset$ if and only if $\min P>b$, this implies
that $\mathcal{L}([n],Q,b)\neq\emptyset$ if and only if $\min P\leq b$. As
desired. So we may assume $\min P\leq b$.

By Proposition 2.7, we only need to consider the case that $|Q|>b$. We first
show that $\mathcal{L}([n],Q,b)$ and $\mathcal{L}([n],P,a)$ are cross-
intersecting. For any $F\in\mathcal{L}([n],Q,b)$, we have $\min F\setminus
Q<\min Q\setminus F$. Let $z_{1}=\min F\setminus Q$. Then $z_{1}\in P$ since
$P$ is $Q$’s partner and $z_{1}<\min Q\setminus F\leq\max Q=\max P$. This
implies that $F\cap P_{0}\neq\emptyset$. Let $P^{\prime}\precneqq P_{0}$ with
$|P^{\prime}|=a$. If $P\subseteq P^{\prime}$, then $F\cap
P^{\prime}\neq\emptyset$ since $z_{1}\in F\cap P^{\prime}$. So we may assume
$P\not\subseteq P^{\prime}$. This implies $\min P^{\prime}\setminus P<\min
P\setminus P^{\prime}$. Let $z_{2}=\min P^{\prime}\setminus P$, then $z_{2}\in
Q$ since $Q$ is $P$’s partner and $z_{2}<\min P\setminus P^{\prime}\leq\max
P=\max Q$. If $z_{2}\in F$, then $F\cap P^{\prime}\neq\emptyset$. Suppose
$z_{2}\not\in F$. If $z_{1}\in P^{\prime}$, then $F\cap
P^{\prime}\neq\emptyset$. So assume that $z_{1}\not\in P^{\prime}$. Since
$z_{1}\in P$, we get $z_{2}=\min P^{\prime}\setminus P<\min P\setminus
P^{\prime}\leq z_{1}$. However, $z_{2}\in Q,z_{2}\not\in F$, so $z_{2}\geq\min
Q\setminus F>\min F\setminus Q=z_{1}$, a contradiction. We have proved that
$\mathcal{L}([n],P,a)$ and $\mathcal{L}([n],Q,b)$ are cross-intersecting.

Next we show that $\mathcal{L}([n],Q,b)$ is the maximal L-initial $b$-uniform
family that is cross-intersecting to $\mathcal{L}([n],P,a)$. Let $Q_{b}$ be
the $b$-th element of $Q$. Since $\min P\leq b$, then $Q_{b}>b$ and
$[Q_{b}]\setminus Q\neq\emptyset$. Let $y=\max\\{q:q\in[Q_{b}]\setminus Q\\}$
and $Q^{\prime}=(Q\cap[y])\cup\\{y\\}$. Then $|Q^{\prime}|\leq b$. By Remark
2.17, $\mathcal{L}([n],Q^{\prime},b)=\mathcal{L}([n],Q,b)$. Suppose that
$\mathcal{G}$ is another $b$-uniform L-initial family cross-intersecting with
$\mathcal{L}([n],P,a)$ and $|\mathcal{G}|>|\mathcal{L}([n],Q^{\prime},b)|$.
Then $\mathcal{G}\supsetneqq\mathcal{L}([n],Q^{\prime},b)$. Let $H$ be the
last set in $\mathcal{L}([n],Q^{\prime},b)$ and $G$ be the first set in
$\mathcal{G}\setminus\mathcal{L}([n],Q^{\prime},b)$. Clearly $y=\max
Q^{\prime}<n$. Let $|Q^{\prime}|=p$. We have the following two cases.

Case (i) $|Q^{\prime}|=b$. In this case $H=Q^{\prime}$. Then
$G=(Q^{\prime}\setminus\\{y\\})\cup\\{y+1\\}$. Since $y\not\in Q$ and $y<\max
Q=\max P$, $y\in P$. By our definition of $y$, $y+1\in Q$. And $y+1\not\in P$,
otherwise $|Q|=b$, also a contradiction. However, by the definition of
$Q^{\prime}$, we have $Q^{\prime}\cap P=\\{y\\}$, so $G\cap P=\emptyset$,
therefore, $G\cap P_{0}=\emptyset$, a contradiction again.

Case (ii) $|Q^{\prime}|<b$. In this case
$H=Q^{\prime}\cup\\{n-b+p+1,\dots,n\\}$ and
$G=(Q^{\prime}\setminus\\{y\\})\cup\\{y+1,y+2,\dots,y+b-p+1\\}.$ Moreover, by
the definitions of $Q_{b}$ and $y$, we can see that $y+b-p+1=Q_{b}$ and
$\\{y+1,y+2,\dots,y+b-p+1\\}\subset Q$. Since $Q$ is the partner of $P$ and
$Q_{b}<\max Q=\max P$, $\\{y+1,y+2,\dots,y+b-p+1\\}\cap P=\emptyset$. Recall
that $Q^{\prime}\cap P=\\{y\\}$, so $G\cap P=\emptyset$, therefore, $G\cap
P_{0}=\emptyset$, a contradiction. So we have shown that
$\mathcal{L}([n],Q^{\prime},b)$, the same as $\mathcal{L}([n],Q,b)$ (see
Remark 2.17) is the maximum $b$-uniform L-initial family that is cross-
intersecting to $\mathcal{L}([n],P,a)$, as desired. ∎

######  Proposition 2.19.

Let $F<G\in\mathcal{R}$ and $\max G=q$. Then $\beta(F,G)=\sum_{j\neq
i}{n-q\choose k_{j}-(q-k_{i})}$.

###### Proof.

Let $F^{\prime},G^{\prime}$ be the partners of $F,G$ respectively. We have the
following two cases.

Case (i) $\max F<n$. In this case, $\max F=q-1$ and
$F\setminus\\{q-1\\}=G\setminus\\{q\\}$. By (11) and Proposition 2.9, we have

$\displaystyle\beta(F,G)$ $\displaystyle=\sum_{j\neq
i}(|\mathcal{L}([n],F^{\prime},k_{j})|-|\mathcal{L}([n],G^{\prime},k_{j})|)$
$\displaystyle=\sum_{j\neq i}\left[{n-(q-1)\choose
k_{j}-(q-k_{i})}-{n-q\choose k_{j}-(q-k_{i}+1)}\right]$
$\displaystyle=\sum_{j\neq i}{n-q\choose k_{j}-(q-k_{i})},$

as desired.

Case (ii) $\max F=n$. Let $p$ be the last element of $F$ not continuing to
$n$. Then $G=(F\cap[p-1])\cup\\{p+1,p+2,\dots,q\\}$. Let
$\widetilde{F}=F\cap[p]$ and $\widetilde{F^{\prime}}$ be the partner of
$\widetilde{F}$. It follows from Remark 2.18 that

$\sum_{j\neq i}|\mathcal{L}([n],F^{\prime},k_{j})|=\sum_{j\neq
i}|\mathcal{L}([n],\widetilde{F^{\prime}},k_{j})|.$

Therefore,

$\displaystyle\beta(F,G)$ $\displaystyle=\sum_{j\neq
i}(|\mathcal{L}([n],F^{\prime},k_{j})|-|\mathcal{L}([n],G^{\prime},k_{j})|)$
$\displaystyle=\sum_{j\neq
i}(|\mathcal{L}([n],\widetilde{F^{\prime}},k_{j})|-|\mathcal{L}([n],G^{\prime},k_{j})|)$
$\displaystyle=\sum_{j\neq i}\left\\{{n-p\choose
k_{j}-p+(k_{i}-q+p)}\right.-\left[{n-(p+1)\choose
k_{j}-(p+1)+(k_{i}-q+p)}\right.$
$\displaystyle\quad\left.\left.+{n-(p+2)\choose
k_{j}-(p+1)+(k_{i}-q+p)}+\cdots+{n-q\choose
k_{j}-(p+1)+(k_{i}-q+p)}\right]\right\\}$ $\displaystyle=\sum_{j\neq
i}\left\\{{n-p\choose k_{j}-(q-k_{i})}-\left[{n-p\choose
k_{j}-(q-k_{i})}-{n-q\choose k_{j}-(q-k_{i})}\right]\right\\}$
$\displaystyle=\sum_{j\neq i}{n-q\choose k_{j}-(q-k_{i})},$

as desired. ∎

Now we show Proposition 2.15.

Proposition 2.15. Suppose that $n\geq k_{1}+k_{2}$ and $k_{1}\geq
k_{2}\geq\dots\geq k_{t}$. Let $i\in[t]$ and $m$ be defined in (3), then for
$1\leq s\leq m$, we have

$f_{1}(\\{s\\})=\max\\{f_{j}(\\{s\\}):j\in[t]\\}.$

In particular,

$\displaystyle f_{1}(\\{1\\})=\max\\{f_{j}(\\{1\\}):j\in[t]\\},$
$\displaystyle f_{1}(\\{m\\})=\max\\{f_{j}(\\{m\\}):j\in[t]\\}.$

Proof of Proposition 2.15. Note that for each $j\in[t]$, we have

$f_{j}(\\{1\\})=\sum_{q=1}^{t}{n-1\choose k_{q}-1},$ (23)

since $\mathcal{A}_{j}$ is the family of all sets having lex order smaller
than or equal to $\\{1\\}$, this means that $\mathcal{A}_{j}$ is the full star
containing $1$. Consequently, all sets in other $\mathcal{A}_{l}$ are also the
full star containing $1$ since they are pairwise cross-intersecting. So
$f_{1}(\\{1\\})=\max\\{f_{j}(\\{1\\}):j\in[t]\\}$.

We next prove that for $2\leq s\leq m$,
$f_{1}(\\{s\\})=\max\\{f_{j}(\\{s\\}):j\in[t]\\}.$

Since $n\geq k_{1}+k_{2}$ and $k_{1}\geq k_{2}\geq\cdots\geq k_{t}$, we only
need to prove that

$f_{1}(\\{s\\})\geq f_{2}(\\{s\\}).$ (24)

By the definition of $f_{j}(R)$, we have

$\displaystyle f_{1}(\\{s\\})={n-1\choose k_{1}-1}+\cdots+{n-s\choose
k_{1}-1}+\sum_{j=2}^{t}{n-s\choose k_{j}-s},$

and

$\displaystyle f_{2}(\\{s\\})={n-1\choose k_{2}-1}+\cdots+{n-s\choose
k_{2}-1}+\sum_{j\neq 2,j=1}^{t}{n-s\choose k_{j}-s}.$

It is easy to see that if $n=k_{1}+k_{2}$, then we have
$f_{1}(\\{s\\})=f_{2}(\\{s\\})$. Let us denote
$g(n)=f_{1}(\\{s\\})-f_{2}(\\{s\\})$, then $g(k_{1}+k_{2})=0$. Inequality (24)
immediately follows from the forthcoming claim.

######  Claim 2.20.

For any integer $q$ with $q\geq k_{1}+k_{2}$ and $k_{1}\geq k_{2}$, we have

$g(q+1)-g(q)\geq 0.$ (25)

Proof of Claim 2.20. Indeed,

$\displaystyle g(q)$ $\displaystyle={q-1\choose k_{1}-1}+\cdots+{q-s\choose
k_{1}-1}+{q-s\choose k_{2}-s}$ $\displaystyle\quad-\left\\{{q-1\choose
k_{2}-1}+\cdots+{q-s\choose k_{2}-1}+{q-s\choose k_{1}-s}\right\\}$
$\displaystyle={q-2\choose k_{1}-1}+\cdots+{q-s\choose
k_{1}-1}+\sum_{j=2}^{s}{q-j\choose k_{1}-j+1}$
$\displaystyle\quad-\left\\{{q-2\choose k_{2}-1}+\cdots+{q-s\choose
k_{2}-1}+\sum_{j=2}^{s}{q-j\choose k_{2}-j+1}\right\\},$

and

$\displaystyle g(q+1)$ $\displaystyle={q-1\choose
k_{1}-1}+\cdots+{q+1-s\choose k_{1}-1}+\sum_{j=2}^{s}{q+1-j\choose k_{1}-j+1}$
$\displaystyle\quad-\left\\{{q-1\choose k_{2}-1}+\cdots+{q+1-s\choose
k_{2}-1}+\sum_{j=2}^{s}{q+1-j\choose k_{2}-j+1}\right\\}.$

Since $q\geq k_{1}+k_{2}$ and $k_{1}\geq k_{2}$, then for all $j\geq 0$, we
have

${q-j\choose k_{1}-j}\geq{q-j\choose k_{2}-j}.$ (26)

This gives

$\displaystyle\sum_{j=2}^{s}{q+1-j\choose
k_{1}-j+1}-\sum_{j=2}^{s}{q+1-j\choose k_{2}-j+1}-\sum_{j=2}^{s}{q-j\choose
k_{1}-j+1}+\sum_{j=2}^{s}{q-j\choose k_{2}-j+1}$
$\displaystyle=\sum_{j=2}^{s}\left\\{{q-j\choose k_{1}-j}-{q-j\choose
k_{2}-j}\right\\}$ $\displaystyle\geq 0.$

Hence, to get (25), it is sufficient to show the following claim.

######  Claim 2.21.

For any integer $q$ with $q\geq k_{1}+k_{2}$ and $k_{1}\geq k_{2}$, we have

${q-1\choose k_{1}-1}-{q-s\choose k_{1}-1}\geq{q-1\choose k_{2}-1}-{q-s\choose
k_{2}-1}.$ (27)

###### Proof of Claim 2.21.

If ${q-s\choose k_{1}-1}\leq{q-s\choose k_{2}-1}$, then applying (26) for
$j=1$, we have ${q-1\choose k_{1}-1}\geq{q-1\choose k_{2}-1}$, so the desired
inequality (27) holds. Suppose that ${q-s\choose k_{1}-1}>{q-s\choose
k_{2}-1}$. Since $k_{1}\geq k_{2}$ and $q\geq k_{1}+k_{2}$, we have

$\frac{{q-s\choose k_{1}-2}}{{q-s\choose k_{1}-1}}\geq\frac{{q-s\choose
k_{2}-2}}{{q-s\choose k_{2}-1}},$

this implies that ${q-s\choose k_{1}-2}>{q-s\choose k_{2}-2}$. Similarly, for
all $j\geq 0$,

$\frac{{q-s+j\choose k_{1}-2}}{{q-s\choose k_{1}-2}}\geq\frac{{q-s+j\choose
k_{2}-2}}{{q-s\choose k_{2}-2}}.$

So ${q-s+j\choose k_{1}-2}\geq{q-s+j\choose k_{2}-2}$ holds for any $j\geq 0$,
yielding

$\displaystyle{q-1\choose k_{1}-1}-{q-s\choose k_{1}-1}-\left\\{{q-1\choose
k_{2}-1}-{q-s\choose k_{2}-1}\right\\}$
$\displaystyle=\sum_{j=2}^{s}\left\\{{q-j\choose k_{1}-2}-{q-j\choose
k_{2}-2}\right\\}$ $\displaystyle\geq 0,$

as desired. ∎

##  3 Proofs of Lemmas 2.11, 2.12, 2.13 and 2.14

We show some preliminary properties. We need the following preparation.

######  Claim 3.1.

Let
$F_{1},F_{2},F^{\prime}_{1},F^{\prime}_{2}\in\mathcal{R},c\in[k_{i}],F_{1}\overset{c}{\prec}F_{2}$
and $F^{\prime}_{1}\overset{c}{\prec}F^{\prime}_{2}$. If $\max F_{1}=\max
F^{\prime}_{1}$, then
$\alpha(F_{1},F_{2})=\alpha(F^{\prime}_{1},F^{\prime}_{2})$ and
$\beta(F_{1},F_{2})=\beta(F^{\prime}_{1},F^{\prime}_{2})$.

###### Proof.

Let $A$ be the head of $F_{1}$ and $F_{2}$, $A^{\prime}$ be the head of
$F^{\prime}_{1}$ and $F^{\prime}_{2}$ and let $\max F_{1}=\max F_{2}=q$. Then
$\max F_{2}=\max F^{\prime}_{2}=q+1.$ It is easy to see that $F_{1}\setminus
A=F^{\prime}_{1}\setminus A^{\prime}$ and $F_{2}\setminus
A=F^{\prime}_{2}\setminus A^{\prime}$, by Proposition 2.9, we conclude that
$\beta(F_{1},F_{2})=\beta(F^{\prime}_{1},F^{\prime}_{2})$. Let
$G_{1},G_{2},G^{\prime}_{1},G^{\prime}_{2}$ be the partners of
$F_{1},F_{2},F^{\prime}_{1},F^{\prime}_{2}$ respectively. Then $G_{1}\setminus
G_{2}=G^{\prime}_{1}\setminus G^{\prime}_{2}$ and $G_{2}\setminus
G_{1}=G^{\prime}_{2}\setminus G^{\prime}_{1}$, by Proposition 2.9, we have
$\alpha(F_{1},F_{2})=\alpha(F^{\prime}_{1},F^{\prime}_{2})$, as promised. ∎

######  Claim 3.2.

Let $F,H,G\in\mathcal{R}$ with $F\prec H\prec G$. Then
$\alpha(F,G)=\alpha(F,H)+\alpha(H,G)$ and $\beta(F,G)=\beta(F,H)+\beta(H,G)$.

###### Proof.

By (10), we have

$\displaystyle\alpha(F,H)+\alpha(H,G)$
$\displaystyle=|\mathcal{L}([n],H,k_{i})|-|\mathcal{L}([n],F,k_{i})|+|\mathcal{L}([n],G,k_{i})|-|\mathcal{L}([n],H,k_{i})|$
$\displaystyle=|\mathcal{L}([n],G,k_{i})|-|\mathcal{L}([n],F,k_{i})|$
$\displaystyle=\alpha(F,G),$

as desired. Let $F^{\prime},H^{\prime},G^{\prime}$ be the partners of $F,H,G$
respectively. Then by (11), we have

$\displaystyle\beta(F,H)+\beta(H,G)$ $\displaystyle=\sum_{j\neq
i}(|\mathcal{L}([n],F^{\prime},k_{j})|-|\mathcal{L}([n],H^{\prime},k_{j})|+|\mathcal{L}([n],H^{\prime},k_{j})|-|\mathcal{L}([n],G^{\prime},k_{j})|)$
$\displaystyle=\sum_{j\neq
i}(|\mathcal{L}([n],F^{\prime},k_{j})|-|\mathcal{L}([n],G^{\prime},k_{j})|)$
$\displaystyle=\beta(F,G),$

as desired. ∎

By Claims 3.1 and 3.2, the following corollary is obvious.

######  Corollary 3.3.

Let $c\in[k_{i}]$ and $F,G,F^{\prime},G^{\prime}\in\mathcal{R}$. If $F,G$ are
$c$-sequential, $F^{\prime},G^{\prime}$ are $c$-sequential and $\max F=\max
F^{\prime},\max G=\max G^{\prime}$, then
$\alpha(F,G)=\alpha(F^{\prime},G^{\prime})$ and
$\beta(F,G)=\beta(F^{\prime},G^{\prime})$.

######  Claim 3.4.

Let $2\leq c\leq k_{i}$ and $F,G,H,F_{1}\in\mathcal{R}$ with
$F\overset{c}{\prec}G\overset{c}{\prec}H,F\overset{c-1}{\prec}F_{1}$ and $\max
F=q$. Then

$\displaystyle\alpha(F,G)=\alpha(F,F_{1})+\alpha(G,H),$
$\displaystyle\beta(F,G)=\beta(F,F_{1})+\beta(G,H)+\sum_{j\neq
i}{n-(q+2)\choose k_{j}-(q-k_{i}+1)}.$

###### Proof.

Let $A$ be the head of $F,G,H$. Then by the definition,
$F=A\sqcup\\{q-c+1,\dots,q\\},G=A\sqcup\\{q-c+2,\dots,q+1\\},H=A\sqcup\\{q-c+3,\dots,q+2\\}$
and $F_{1}=A\sqcup\\{q-c+1\\}\sqcup\\{q-c+3,\dots,q+1\\}$. Define $F_{2}$ as
$F_{2}<G$ in $\mathcal{R}$. Since $G\setminus A$ continues and $q-c+1\not\in
G$, then $q-c+1\in F_{2}$. Hence,
$F_{2}=A\cup\\{q-c+1,n-c+2,n-c+3,\dots,n\\}$. Similarly, define $F_{3}$ as
$F_{3}<H$ in $\mathcal{R}$. Then
$F_{3}=A\sqcup\\{q-c+2,n-c+2,n-c+3,\dots,n\\}$. Moreover, $F_{1}$ and $F_{2}$
are $(c-1)$-sequential, and $G$ and $F_{3}$ are $(c-1)$-sequential. Clearly,
$\max F_{1}=\max G=q+1$ and $\max F_{2}=\max F_{3}=n$. By Corollary 3.3, we
have $\alpha(F_{1},F_{2})=\alpha(G,F_{3})$ and
$\beta(F_{1},F_{2})=\beta(G,F_{3})$. By the definition, we get
$\alpha(F_{2},G)=\alpha(F_{3},H)=1$. Combining with Claim 3.2, we have

$\displaystyle\alpha(F,G)$ $\displaystyle=\alpha(F,F_{1})+\alpha(F_{1},G)$
$\displaystyle=\alpha(F,F_{1})+\alpha(F_{1},F_{2})+\alpha(F_{2},G)$
$\displaystyle=\alpha(F,F_{1})+\alpha(G,F_{3})+\alpha(F_{3},H)$
$\displaystyle=\alpha(F,F_{1})+\alpha(G,H),$

and

$\displaystyle\beta(F,G)$ $\displaystyle=\beta(F,F_{1})+\beta(F_{1},G)$
$\displaystyle=\beta(F,F_{1})+\beta(F_{1},F_{2})+\beta(F_{2},G)$
$\displaystyle=\beta(F,F_{1})+\beta(G,F_{3})+\beta(F_{3},H)+\beta(F_{2},G)-\beta(F_{3},H)$
$\displaystyle=\beta(F,F_{1})+\beta(G,H)+\sum_{j\neq i}{n-(q+2)\choose
k_{j}-(q-k_{i}+1)},$

where the last equality follows from Proposition 2.19. More specifically, we
can see that

$\displaystyle\beta(F_{2},G)=\sum_{j\neq i}{n-(q+1)\choose
k_{j}-(q+1-k_{i})},$ $\displaystyle\beta(F_{3},H)=\sum_{j\neq
i}{n-(q+2)\choose k_{j}-(q+2-k_{i})}.$

∎

######  Definition 3.5.

Let $M\geq 2$ and
$\mathcal{G}=\\{G_{1},G_{2},\dots,G_{M}\\}\subset\mathcal{R}$ with $G_{1}\prec
G_{2}\prec\dots\prec G_{M}$. If there is $g\in[0,M-1]$ satisfying the
following two conditions:
(i) $f(G_{j+1})<f(G_{j})$ for $1\leq j\leq g$,
(ii) $f(G_{j+1})\geq f(G_{j})$ for $g+1\leq j\leq M-1$,
then we say that $\mathcal{G}$ is a down-up family and $g$ is the down degree
of $\mathcal{G}$, write $d_{\mathcal{G}}^{\downarrow}$.

Recall that $i\in[t]$ is the fixed index satisfying
$|\mathcal{A}_{i}|\geq{n-1\choose k_{i}-1}$. Let

$l=\max_{j\neq i}k_{j}.$

###  3.1 Proof of Lemma 2.11

To show Lemma 2.11, we need the following preparations. All arguments below
are under the assumption of Lemma 2.11, i.e., assume that $c\in[k_{i}]$ and
$F,G,H\in\mathcal{R}$ with $F\overset{c}{\prec}G\overset{c}{\prec}H$
satisfying $\alpha(F,G)\geq\beta(F,G)$. We need to show that
$\alpha(G,H)>\beta(G,H)$.

######  Claim 3.6.

Let $c^{\prime}\in[k_{i}]$ and $R,R^{\prime},T\in\mathcal{R}$ with $R\precneqq
T\precneqq R^{\prime}$. If $R,R^{\prime}$ are $c^{\prime}$-sequential, then
$\max T\geq\max R+1$.

###### Proof.

Let $A$ be the head of $R$ and $R^{\prime}$. Since $R\precneqq T\precneqq
R^{\prime}$, we have $A\subset T$. Since $\min R\setminus T<\min T\setminus R$
and $R\setminus A$ continues to $\max R$, we have $\max T>\max R$. ∎

Let $A$ be the head of $F,G,H$ and $\max F=q$. Then
$F=A\sqcup\\{q-c+1,\dots,q\\},G=A\sqcup\\{q-c+2,\dots,q+1\\}$ and
$H=A\sqcup\\{q-c+3,\dots,q+2\\}$.

######  Claim 3.7.

If $q\geq k_{i}+l-1$, then $\alpha(G,H)>\beta(G,H)$.

###### Proof.

Since $q\geq k_{i}+l-1$, we have $\max G\geq k_{i}+l$ and $\max H\geq
k_{i}+l+1$. Let $G<T_{1}<T_{2}<\cdots<T_{\lambda}<H$ in $\mathcal{R}$. By
Claim 3.6, $\max T_{j}\geq k_{i}+l+1$ for all $j\in[\lambda]$. By Proposition
2.19, $\beta(G,T_{1})=\beta(T_{1},T_{2})=\cdots=\beta(T_{\lambda},H)=0$.
Consequently,

$\alpha(G,H)=\alpha(G,T_{1})+\alpha(T_{1},T_{2})+\cdots+\alpha(T_{\lambda},H)>0,$

and

$\beta(G,H)=\beta(G,T_{1})+\beta(T_{1},T_{2})+\cdots+\beta(T_{\lambda},H)=0.$

So we conclude that $\alpha(G,H)>\beta(G,H)$. ∎

By Claim 3.7, we may assume that $k_{i}+1\leq q\leq k_{i}+l-2$. We will show
Lemma 2.11 by induction on $c$.

Let $c=1$. Then $\alpha(F,G)=1$. Since $q\leq k_{i}+l-2,then\max G\leq
k_{i}+l-1<n$. By Proposition 2.19, $\beta(F,G)\geq\sum_{j\neq
i}{n-(k_{i}+l-1)\choose k_{j}-(l-1)}>1$, then $\alpha(F,G)<\beta(F,G)$. So
Lemma 2.11 holds for $c=1$. Let $c\geq 2$. Assume it holds for all
$c^{\prime}\leq c-1$, we will prove that it holds for $c$. We will define
$c_{1},c_{2},\dots,c_{h}$ and $t_{1},t_{2},\dots,t_{h}$, one by one, until
$t_{1}+t_{2}+\cdots+t_{h}=k_{i}+l-q$, where $h$ is to be determined later.

Let $t_{0}=0,F_{0}^{+}=F$ and $c_{0}=c$. We determine $c_{1}$ first.

######  Claim 3.8.

There exists a unique integer $c_{1}\in[1,c_{0}-1]$satisfying the following
two conditions.
(i) If $F_{1}$ satisfies $F_{0}^{+}\overset{c_{1}}{\prec}F_{1}$, then
$\alpha(F_{0}^{+},F_{1})<\beta(F_{0}^{+},F_{1})$;
(ii) For any $1\leq j\leq c_{0}-c_{1}$ and $F^{\prime}$ satisfying
$F_{0}^{+}\overset{c_{1}+j}{\prec}F^{\prime}$, we have
$\alpha(F_{0}^{+},F^{\prime})\geq\beta(F_{0}^{+},F^{\prime})$.

###### Proof.

Let $F^{\prime}$ be the set such that $F_{0}^{+}\overset{1}{\prec}F^{\prime}$,
i.e., $F_{0}^{+}<F^{\prime}$. Since $q\leq k_{i}+l-2$, $\max F^{\prime}\leq
k_{i}+l-1$. By Proposition 2.19,

$\displaystyle\beta(F_{0}^{+},F^{\prime})=\sum_{j\neq i}{n-(q+1)\choose
k_{j}-(q+1-k_{i})}>1=\alpha(F_{0}^{+},F^{\prime}).$

Note that $F\overset{c}{\prec}G$ and $\alpha(F,G)\geq\beta(F,G)$. Let $c_{1}$
be the largest integer in $[1,c_{0}-1]$ satisfying
$\alpha(F_{0}^{+},F^{\prime})<\beta(F_{0}^{+},F^{\prime})$ for $F^{\prime}$
satisfying $F_{0}^{+}\overset{c_{1}}{\prec}F^{\prime}$. Then $c_{1}$ satisfies
both (i) and (ii). ∎

Define $\mathcal{F}_{0}^{+}$ to be the $c_{1}$-sequential family that range
from $q$ to $n$ with $F_{0}^{+}$ as it’s first member. Since $c_{1}<c$, by
induction hypothesis and the definition of down-up family, we can see that
$\mathcal{F}_{0}^{+}$ is a down-up family. Let
$t_{1}:=d_{\mathcal{F}_{0}^{+}}^{\downarrow}$. Clearly, $1\leq t_{1}\leq
k_{i}+l-q$ (in view of Claim 3.7). If $t_{1}=k_{i}+l-q$, then we stop and
$h=1$. Otherwise, if $t_{1}\leq k_{i}+l-q-1$, then we continue to find $c_{2}$
and $t_{2}$. Before performing the next step, we give the following
definitions.

Let
$\mathcal{F}_{0}^{+}:=\\{F_{0}^{+},F_{1},M_{2}^{(1)},M_{3}^{(1)},\dots,M_{t_{1}}^{(1)},M_{t_{2}}^{(1)},\dots,G_{1}\\}$,
where

$F_{0}^{+}\overset{c_{1}}{\prec}F_{1}\overset{c_{1}}{\prec}M_{2}^{(1)}\overset{c_{1}}{\prec}M_{3}^{(1)}\overset{c_{1}}{\prec}\cdots\overset{c_{1}}{\prec}M_{t_{1}}^{(1)}\overset{c_{1}}{\prec}M_{t_{2}}^{(1)}\overset{c_{1}}{\prec}\cdots\overset{c_{1}}{\prec}G_{1}.$

Let $M_{1}^{(1)}:=F_{1}$ and $\max G_{1}=n$. Actually, $\max
M_{t_{1}}^{(1)}=q+t_{1}$.

Since $d_{\mathcal{F}_{0}^{+}}^{\downarrow}=t_{1}$ and
$f(M_{t_{1}+1}^{(1)})>f(M_{t_{1}}^{(1)})$, that is,
$\alpha(M_{t_{1}}^{(1)},M_{t_{1}+1}^{(1)})>\beta(M_{t_{1}}^{(1)},M_{t_{1}+1}^{(1)})$,
then we can define
$F_{1}^{+},F_{2}^{+},\dots,F_{t_{1}}^{+},F_{2},F_{3},\dots,F_{t_{1}}$ as
follows:

$F_{0}^{+}\overset{c_{1}+1}{\prec}F_{1}^{+}\overset{c_{1}+1}{\prec}F_{2}^{+}\overset{c_{1}+1}{\prec}\cdots\overset{c_{1}+1}{\prec}F_{t_{1}}^{+},$

and

$F_{1}^{+}\overset{c_{1}}{\prec}F_{2},\,\,F_{2}^{+}\overset{c_{1}}{\prec}F_{3},\,\,\dots,\,\,F_{t_{1}-1}^{+}\overset{c_{1}}{\prec}F_{t_{1}}.$

Let $2\leq p\leq h$. Assume that $c_{1},c_{2},\dots,c_{p-1}$ and
$t_{1},t_{2},\dots,t_{p-1}$ have been determined and the condition to
terminate is not reached (i.e., $t_{p-1}<k_{i}+l-q$). We next determine
$c_{p}$.

For $0\leq k\leq h$, let $a_{k}:=\sum_{j=0}^{k}t_{j}$.

######  Claim 3.9.

There exists a unique integer $c_{p}$, $1\leq c_{p}\leq c_{p-1}-1$, satisfying
the following two conditions.
(i) If $F_{a_{p-1}}^{+}\overset{c_{p}}{\prec}F_{a_{p-1}+1}$, then
$\alpha(F_{a_{p-1}}^{+},F_{a_{p-1}+1})<\beta(F_{a_{p-1}}^{+},F_{a_{p-1}+1})$;
(ii) For any $1\leq j\leq c_{p-1}-c_{p}$ and $F^{\prime}$ satisfying
$F_{a_{p-1}}^{+}\overset{c_{p}+j}{\prec}F^{\prime}$, we have

$\alpha(F_{a_{p-1}}^{+},F^{\prime})\geq\beta(F_{a_{p-1}}^{+},F^{\prime}).$

As Claim 3.8, after the $(p-1)$-th step, we have defined the following family:

$\mathcal{F}_{a_{p-2}}^{+}=\\{F_{a_{p-2}}^{+},F_{a_{p-2}+1},M_{a_{p-2}+2}^{(p-1)},\dots,M_{a_{p-1}}^{(p-1)},M_{a_{p-1}+1}^{(p-1)},\dots,G_{a_{p-2}+1}\\},$

where the sets of $\mathcal{F}_{a_{p-2}}^{+}$ satisfy

$F_{a_{p-2}}^{+}\overset{c_{p-1}}{\prec}F_{a_{p-2}+1}\overset{c_{p-1}}{\prec}M_{a_{p-2}+2}^{(p-1)}\overset{c_{p-1}}{\prec}\cdots\overset{c_{p-1}}{\prec}M_{a_{p-1}}^{(p-1)}\overset{c_{p-1}}{\prec}M_{a_{p-1}+1}^{(p-1)}\overset{c_{p-1}}{\prec}\cdots\overset{c_{p-1}}{\prec}G_{a_{p-2}+1}.$

Define
$F_{a_{p-2}+1}^{+},\,F_{a_{p-2}+2}^{+},\,\dots,\,F_{a_{p-1}}^{+},\,F_{a_{p-2}+1},\,F_{a_{p-2}+2},\,\dots,\,F_{a_{p-1}}$
as follows:

$F_{a_{p-2}}^{+}\overset{c_{p-1}+1}{\prec}F_{a_{p-2}+1}^{+}\overset{c_{p-1}+1}{\prec}F_{a_{p-2}+2}^{+}\overset{c_{p-1}+1}{\prec}\cdots\overset{c_{p-1}+1}{\prec}F_{a_{p-1}}^{+},$

and

$F_{a_{p-2}}^{+}\overset{c_{p-1}}{\prec}F_{a_{p-2}+1},\,\,F_{a_{p-2}+1}^{+}\overset{c_{p-1}}{\prec}F_{a_{p-2}+2},\,\,\dots,\,\,F_{a_{p-1}-1}^{+}\overset{c_{p-1}}{\prec}F_{a_{p-1}}.$

###### Proof of Claim 3.9.

First, we can see that $c_{p-1}\geq 2$. Since if not, that is, $c_{p-1}=1$,
then $t_{p-1}=d_{\mathcal{F}_{a_{p-2}}}^{\downarrow}=k_{i}+l-q-a_{p-2}$. On
the other hand, since $p-1<h$, we have $t_{p-1}<k_{i}+l-q-a_{p-2}$, a
contradiction. Let $F^{\prime}$ be the set satisfying
$F_{a_{p-1}}^{+}\overset{1}{\prec}F^{\prime}$. Then
$\alpha(F_{a_{p-1}}^{+},F^{\prime})=1<\beta(F_{a_{p-1}}^{+},F^{\prime})$ by
Proposition 2.19. Let $F^{\prime}$ be the set satisfying
$F_{a_{p-1}}^{+}\overset{c_{p-1}}{\prec}F^{\prime}$. Since
$M_{a_{p-1}}^{(p-1)}\overset{c_{p-1}}{\prec}M_{a_{p-1}+1}^{(p-1)}$ and $\max
F_{a_{p-1}}^{+}=\max M_{a_{p-1}}^{(p-1)}=q+a_{p-1}$, by Claim 3.1,

$\displaystyle\alpha(F_{a_{p-1}}^{+},F^{\prime})=\alpha(M_{a_{p-1}}^{(p-1)},M_{a_{p-1}+1}^{(p-1)})\geq\beta(M_{a_{p-1}}^{(p-1)},M_{a_{p-1}+1}^{(p-1)})=\beta(F_{a_{p-1}}^{+},F^{\prime}).$

Let $c_{p}$ be the maximum integer in $[1,c_{p-1}-1]$ such that if
$F_{a_{p-1}}^{+}\overset{c_{p}}{\prec}F_{a_{p-1}+1}$, then

$\alpha(F_{a_{p-1}}^{+},F_{a_{p-1}+1})<\beta(F_{a_{p-1}}^{+},F_{a_{p-1}+1}).$

Then $c_{p}$ satisfies both $(i)$ and $(ii)$. ∎

After $h$ steps, we can get $k_{i}+l-q$ sets, namely, $F_{j}$ for $1\leq j\leq
k_{i}+l-q$. We also defined
$G_{1},G_{a_{1}+1},G_{a_{2}+1},\dots,G_{a_{h-1}+1}$ as
$F_{1}\overset{c_{1}}{\longrightarrow}G_{1},F_{a_{1}+1}\overset{c_{2}}{\longrightarrow}G_{a_{1}+1},\dots,F_{a_{h-1}+1}\overset{c_{h}}{\longrightarrow}G_{a_{h-1}+1}$.
For each $1\leq j\leq h$ and $a_{j-1}+1\leq p\leq a_{j}$, we now define
$G_{p}$ as $F_{p}\overset{c_{j}}{\longrightarrow}G_{p}$.

######  Claim 3.10.

If $c_{1}+1=c$, then $\alpha(G,H)>\beta(G,H)$.

###### Proof.

If $c_{1}+1=c$, then $F_{1}^{+}=G$. Since
$F_{1}\overset{c_{1}}{\longrightarrow}G_{1}$, we have $G_{1}<G$. Then

$\alpha(F,G)=\alpha(F,F_{1})+\alpha(F_{1},G_{1})+\alpha(G_{1},G)$

and

$\beta(F,G)=\beta(F,F_{1})+\beta(F_{1},G_{1})+\beta(G_{1},G).$

By the choice of $c_{1}$ and $t_{1}\geq 1$, we have
$\alpha(F,F_{1})\leq\beta(F,F_{1})$. Due to $\max G=q+1$, applying Proposition
2.19, we have

$\beta(G_{1},G)=\sum_{j\neq i}{n-(q+1)\choose k_{j}-(q+1-k_{i})}.$

Since $\alpha(F,G)>\beta(F,G)$, we get
$\alpha(F_{1},G_{1})+1>\beta(F_{1},G_{1})+\beta(G_{1},G)$. Let $\widetilde{G}$
be the set satisfying $\widetilde{G}<H$. Then
$G\overset{c_{1}}{\longrightarrow}\widetilde{G}$. Since $\max G=\max F_{1}$
and $\max G_{1}=\max\widetilde{G}$, by Corollary 3.3, we obtain
$\alpha(F_{1},G_{1})=\alpha(G,\widetilde{G})$ and
$\beta(F_{1},G_{1})=\beta(G,\widetilde{G})$. Due to $\max H=q+2$, applying
Proposition 2.19, we have

$\beta(\widetilde{G},H)=\sum_{j\neq i}{n-(q+2)\choose
k_{j}-(q+2-k_{i})}<\beta(G_{1},G).$

So

$\displaystyle\alpha(G,H)$
$\displaystyle=\alpha(G,\widetilde{G})+\alpha(\widetilde{G},H)$
$\displaystyle=\alpha(F_{1},G_{1})+1$
$\displaystyle>\beta(F_{1},G_{1})+\beta(G_{1},G)$
$\displaystyle>\beta(G,\widetilde{G})+\beta(\widetilde{G},H)$
$\displaystyle=\beta(G,H).\qed$

By Claim 3.10, we may assume that $c_{1}<c-1$.

######  Claim 3.11.

Let $0\leq p\leq k_{i}+l-q-1$. Then
$\alpha(F_{p}^{+},F_{p+1}^{+})\geq\beta(F_{p}^{+},F_{p+1}^{+})$ and
$\alpha(F_{p}^{+},F_{p+1})<\beta(F_{p}^{+},F_{p+1}).$

###### Proof.

Without loss of generality, assume that $a_{j}\leq p\leq a_{j+1}-1$ for some
$0\leq j\leq h-1$. We next consider the family $\mathcal{F}_{a_{j}}^{+}$.
Recall that
$\mathcal{F}_{a_{j}}^{+}=\\{F_{a_{j}}^{+},F_{a_{j}+1},M_{a_{j}+2}^{(j+1)},\dots,M_{a_{j+1}}^{(j+1)},M_{a_{j+1}+1}^{(j+1)},\dots,G_{a_{j}+1}\\}$,
where

$F_{a_{j}}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+1}\overset{c_{j+1}}{\prec}M_{a_{j}+2}^{(j+1)}\overset{c_{j+1}}{\prec}\cdots\overset{c_{j+1}}{\prec}M_{a_{j+1}}^{(j+1)}\overset{c_{j+1}}{\prec}M_{a_{j+1}+1}^{(j+1)}\overset{c_{j+1}}{\prec}\dots\overset{c_{j+1}}{\prec}G_{a_{j}+1},$

and $\max G_{a_{j}+1}=n.$ We also have the following relations

$F_{a_{j}}^{+}\overset{c_{j+1}+1}{\prec}F_{a_{j}+1}^{+}\overset{c_{j+1}+1}{\prec}F_{a_{j}+2}^{+}\overset{c_{j+1}+1}{\prec}\cdots\overset{c_{j+1}+1}{\prec}F_{a_{j+1}}^{+},$
$F_{a_{j}}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+1},\,F_{a_{j}+1}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+2},\,\dots,\,F_{a_{j+1}-1}^{+}\overset{c_{j+1}}{\prec}F_{a_{j+1}}.$

By the choice of $c_{j+1}$, we have
$\alpha(F_{a_{j}}^{+},F_{a_{j}+1}^{+})\geq\beta(F_{a_{j}}^{+},F_{a_{j}+1}^{+})$.
Since $F_{a_{j}}^{+}\overset{c_{j+1}+1}{\prec}F_{a_{j}+1}^{+}$ and
$c_{j+1}+1\leq c_{1}+1<c$, by induction hypothesis, we have

$\alpha(F_{p}^{+},F_{p+1}^{+})\geq\beta(F_{p}^{+},F_{p+1}^{+}).$ (28)

By the definition of $t_{j+1}$, since
$F_{a_{j}}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+1}$, for each $a_{j}\leq p\leq
a_{j+1}-1$, we get

$\displaystyle\alpha(F_{a_{j}}^{+},F_{a_{j}+1})<\beta(F_{a_{j}}^{+},F_{a_{j}+1}),$
(29)
$\displaystyle\alpha(F_{a_{j}+1},M_{a_{j}+2}^{(j+1)})<\beta(F_{a_{j}+1},M_{a_{j}+2}^{(j+1)}).$

Moreover, for each $a_{j}+2\leq u\leq a_{j+1}-1$, we get

$\alpha(M_{u}^{(j+1)},M_{u+1}^{(j+1)})<\beta(M_{u}^{(j+1)},M_{u+1}^{(j+1)}).$
(30)

Thus Claim 3.11 holds for $p=a_{j}$.

Next we consider $a_{j}+1\leq p\leq a_{j+1}-1$. Note that
$F_{a_{j}+1}\overset{c_{j+1}}{\prec}M_{a_{j}+2}^{(j+1)},\,F_{a_{j}+1}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+2}$
and $\max F_{a_{j}+1}=\max F_{a_{j}+1}^{+}$. Additionally, for $a_{j}+2\leq
p\leq a_{j+1}-1$, we have
$M_{p}^{(j+1)}\overset{c_{j+1}}{\prec}M_{p+1}^{(j+1)},F_{p}^{+}\overset{c_{j+1}}{\prec}F_{p+1}$
and $\max M_{p}^{(j+1)}=\max F_{p}^{+}$. So Claim 3.1 yields

$\alpha(F_{p}^{+},F_{p+1})=\alpha(M_{p}^{(j+1)},M_{p+1}^{(j+1)})~{}~{}\text{and}~{}~{}\beta(F_{p}^{+},F_{p+1})=\beta(M_{p}^{(j+1)},M_{p+1}^{(j+1)}).$

Hence, for each $a_{j}+1\leq p\leq a_{j+1}-1$, by (30), we conclude that

$\alpha(F_{p}^{+},F_{p+1})<\beta(F_{p}^{+},F_{p+1}).$ (31)

The proof of Claim 3.11 is complete. ∎

######  Claim 3.12.

$\max F_{p}=\max F_{p}^{+}=q+p$ for all $1\leq p\leq k_{i}+l-q$.

###### Proof.

Let $a_{j}+1\leq p\leq a_{j+1}$ for some $0\leq j\leq h-1$. Then
$F_{p-1}^{+}\overset{c_{j+1}}{\prec}F_{p}$ and
$F_{p-1}^{+}\overset{c_{j+1}+1}{\prec}F_{p}$, so

$\max F_{p}=\max F_{p}^{+}.$ (32)

We next prove that $\max F_{p}=q+p$. For $j=0$, then $1\leq p\leq t_{1}$.
Recall that
$f_{0}^{+}\overset{c_{1}}{\prec}F_{1},f_{1}^{+}\overset{c_{1}}{\prec}F_{2},\dots,f_{t_{1}-1}^{+}\overset{c_{1}}{\prec}F_{t_{1}}$.
By (32), $\max F_{0}^{+}=q$ implies $\max F_{p}=q+p,$ as desired. Assume it
holds for all $j^{\prime}\leq j-1$, we want to prove it holds for $j$. Recall
that
$F_{a_{j}}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+1},\,F_{a_{j}+1}^{+}\overset{c_{j+1}}{\prec}F_{a_{j}+2},\,\dots,\,F_{a_{j+1}-1}^{+}\overset{c_{j+1}}{\prec}F_{a_{j+1}}$.
By induction hypothesis, $\max F_{a_{j}}^{+}=q+a_{j}$, then $\max
F_{a_{j}+1}=q+a_{j}+1,\dots,\max F_{a_{j+1}}=q+a_{j+1}$, as desired. ∎

######  Claim 3.13.

Let $1\leq p\leq k_{i}+l-q$. Then
$\alpha(F_{p},F_{p}^{+})-\beta(F_{p},G_{p})>\sum_{j\neq i}{n-(q+p)\choose
k_{j}-(q+p-k_{i})}$.

###### Proof.

By Claim 3.12, $\max F_{p}^{+}=q+p$. By our definition of $G_{p}$,
$G_{p}<F_{p}^{+}$. Applying Proposition 2.19, we get

$\beta(G_{p},F_{p}^{+})=\sum_{j\neq i}{n-(q+p)\choose k_{j}-(q+p-k_{i})}.$

By Claim 3.11, $\alpha(F_{p-1}^{+},F_{p}^{+})\geq\beta(F_{p-1}^{+},F_{p}^{+})$
and $\alpha(F_{p-1}^{+},F_{p})<\beta(F_{p-1}^{+},F_{p})$. On the other hand,
we have

$\alpha(F_{p-1}^{+},F_{p}^{+})=\alpha(F_{p-1}^{+},F_{p})+\alpha(F_{p},F_{p}^{+}),$

and

$\displaystyle\beta(F_{p-1}^{+},F_{p}^{+})$
$\displaystyle=\beta(F_{p-1}^{+},F_{p})+\beta(F_{p},G_{p})+\beta(G_{p},F_{p}^{+})$
$\displaystyle=\beta(F_{p-1}^{+},F_{p})+\beta(F_{p},G_{p})+\sum_{j\neq
i}{n-(q+p)\choose k_{j}-(q+p-k_{i})}.$

Thus $\alpha(F_{p},F_{p}^{+})-\beta(F_{p},G_{p})>\sum_{j\neq i}{n-(q+p)\choose
k_{j}-(q+p-k_{i})}$. ∎

Define $H_{p}$ and $J_{p}$ for each $1\leq p\leq k_{i}+l-q+1$ (i.e.,
$a_{0}\leq p\leq a_{h}+1$) as follows.

$J_{1}=G\overset{c_{1}+1}{\prec}J_{2}\overset{c_{1}+1}{\prec}\cdots\overset{c_{1}+1}{\prec}J_{a_{1}}\overset{c_{2}+1}{\prec}J_{a_{1}+1}\overset{c_{2}+1}{\prec}\cdots\overset{c_{2}+1}{\prec}J_{a_{2}}\overset{c_{3}+1}{\prec}\cdots\overset{c_{h}+1}{\prec}J_{a_{h}}\overset{c_{h}+1}{\prec}J_{a_{h}+1},$

where the last set $J_{a_{h}+1}$ exists since Claim 3.12 implies that $\max
J_{a_{h}+1}=q+k_{i}+l-q+1\leq n$. Let $H_{p}$ be the set such that
$H_{p}<J_{p+1}$ in $\mathcal{R}$.

By the definition of $J_{p},1\leq p\leq k_{i}+l-q+1$, we get $\max J_{p}=q+p$.
Proposition 2.19 gives

$\beta(H_{p},J_{p+1})=\sum_{j\neq i}{n-(q+p+1)\choose k_{j}-(q+p+1-k_{i})}.$
(33)

######  Claim 3.14.

Let $1\leq p\leq k_{i}+l-q+1$. Then $\alpha(J_{p},H_{p})=\alpha(F_{p},G_{p})$
and $\beta(J_{p},H_{p})=\beta(F_{p},G_{p})$.

###### Proof.

By Claim 3.12 and $\max J_{p}=q+p$, we have $\max J_{p}=\max F_{p}$.
Trivially, $\max H_{p}=\max G_{p}=n$. By our definition, $J_{p}$ and $H_{p}$
are $c_{x}$-sequential for some $x$, and $F_{p}$ and $G_{p}$ are
$c_{x}$-sequential as well. It follows from Corollary 3.3 that
$\alpha(J_{p},H_{p})=\alpha(F_{p},G_{p})$ and
$\beta(J_{p},H_{p})=\beta(F_{p},G_{p})$. ∎

Accordingly,

$\displaystyle\alpha(J_{p},J_{p+1})-\beta(J_{p},H_{p})$
$\displaystyle=\alpha(J_{p},H_{p})+1-\beta(F_{p},G_{p})$
$\displaystyle=\alpha(F_{p},G_{p})+1-\beta(F_{p},G_{p})$
$\displaystyle=\alpha(F_{p},F_{p}^{+})-\beta(F_{p},G_{p})$
$\displaystyle>\sum_{j\neq i}{n-(q+p)\choose k_{j}-(q+p-k_{i})},$ (34)

where the first and second equalities hold by Claim 3.14 and the last
inequality holds by Claim 3.13. Furthermore,

$\displaystyle\alpha(J_{p},J_{p+1})-\beta(J_{p},J_{p+1})$
$\displaystyle=\alpha(J_{p},J_{p+1})-\beta(J_{p},H_{p})-\beta(H_{p},J_{p+1})$
$\displaystyle=\alpha(J_{p},J_{p+1})-\beta(J_{p},H_{p})-\sum_{j\neq
i}{n-(q+p+1)\choose k_{j}-(q+p+1-k_{i})}$ $\displaystyle>\sum_{j\neq
i}\left[{n-(q+p)\choose k_{j}-(q+p-k_{i})}-{n-(q+p+1)\choose
k_{j}-(q+p+1-k_{i})}\right],$ (35)

where the second equality holds by (33) and the last inequality holds by
(3.1).

Let $J_{n-q}$ be the set such that
$J_{a_{h}+1}\overset{c_{h}+1}{\longrightarrow}J_{n-q}$. In particular, if
$n=k_{i}+l+1$, then $J_{n-q}=J_{a_{h}+1}$.

######  Claim 3.15.

Let $1\leq p\leq k_{i}+l-q$. Then

$\alpha(J_{p},J_{n-q})-\beta(J_{p},J_{n-q})>\sum_{j\neq i}{n-(q+p)\choose
k_{j}-(q+p-k_{i})}.$

###### Proof.

Without loss of generality, let $a_{j-1}+1\leq p\leq a_{j}$ for some $1\leq
j\leq h$. By our definition,

$J_{p}\overset{c_{j}+1}{\prec}J_{p+1}\overset{c_{j}+1}{\prec}\cdots\overset{c_{j}+1}{\prec}J_{a_{j}}\overset{c_{j+1}+1}{\prec}J_{a_{j}+1}\overset{c_{j+1}+1}{\prec}\cdots\overset{c_{h}+1}{\prec}J_{a_{h}}\overset{c_{h}+1}{\prec}J_{a_{h}+1}\overset{c_{h}+1}{\prec}\cdots\overset{c_{h}+1}{\prec}J_{n-q}.$
(36)

Let $T_{1},T_{2},\dots,T_{Y}\in\mathcal{R}$ be the sets such that
$J_{a_{h}}<T_{1}<T_{2}<\dots<T_{Y}<J_{n-q}.$ By Claim 3.6, $\max T_{j}\geq\max
J_{a_{h}}+1=k_{i}+l-q+1$ holds for all $j\in[Y]$. By Proposition 2.19,

$\beta(J_{a_{h}},J_{n-q})=\beta(J_{a_{h}},T_{1})+\beta(T_{1},T_{2})+\cdots+\beta(T_{Y},J_{n-q})=0.$

Then (3.1) and (36) give

$\displaystyle\alpha(J_{p},J_{n-q})-\beta(J_{p},J_{n-q})$
$\displaystyle=\alpha(J_{p},J_{p+1})+\cdots+\alpha(J_{a_{h}-1},J_{a_{h}})+\alpha(J_{a_{h}},J_{n-q})$
$\displaystyle\quad-\beta(J_{p},J_{p+1})-\cdots-\beta(J_{a_{h}-1},J_{a_{h}})-\beta(J_{a_{h}},J_{n-q})$
$\displaystyle>\sum_{j\neq i}{n-(q+p)\choose k_{j}-(q+p-k_{i})}.$

∎

It is easy to see that $1\leq c_{1}+1-c_{h}<c-c_{h}$. If $c-c_{h}=2$, then
$h=1$ and $c_{1}+1=c-1$. By (36),
$J_{1}\overset{c_{1}+1}{\longrightarrow}J_{n-q}$ and $J_{n-q}<H$. By
Proposition 2.19 and $\max H=q+2$,

$\beta(J_{n-q},H)=\sum_{j\neq i}{n-(q+2)\choose k_{j}-(q+2-k_{i})}.$ (37)

Then by Claim 3.15,

$\displaystyle\alpha(G,H)-\beta(G,H)$
$\displaystyle=\alpha(J_{1},H)-\beta(J_{1},H)$
$\displaystyle=\alpha(J_{1},J_{n-q})+\alpha(J_{n-q},H)-\beta(J_{1},J_{n-q})-\beta(J_{n-q},H)$
$\displaystyle>\sum_{j\neq i}\left[{n-(q+1)\choose
k_{j}-(q+1-k_{i})}-{n-(q+2)\choose k_{j}-(q+2-k_{i})}\right]+1$
$\displaystyle>0,$

where the first inequality holds by Claim 3.15 and equation (37). As desired.

Next we assume that $c-c_{h}>2$.

Since $c_{h}<c_{h-1}<\cdots<c_{1}<c$ and $c-c_{h}>2$, we may define sequential
families $\mathcal{F}_{p}$, $1\leq p\leq c-c_{h}-2$, as follows. Let
$c_{d}-c_{h}+1\leq p\leq c_{d-1}-c_{h}$ for some $d=2,\dots,h$ or
$c_{1}-c_{h}+1\leq p\leq c-c_{h}-2$. We define

$\mathcal{F}_{p}:J_{a_{d-1}+1}\overset{c_{h}+1+p}{\prec}J_{a_{d-1}+2}^{(p)}\overset{c_{h}+1+p}{\prec}\cdots\overset{c_{h}+1+p}{\prec}J_{a_{d}}^{(p)}\overset{c_{h}+1+p}{\prec}J_{a_{d}+1}^{(p)}\overset{c_{h}+1+p}{\prec}\cdots\overset{c_{h}+1+p}{\prec}J_{n-q}^{(p)}.$

By our definition, for any $J_{j}^{(p)}\in\mathcal{F}_{p}$, we get

$\max J_{j}^{(p)}=q+j.$ (38)

Knowing that
$J_{a_{h-1}+1}\overset{c_{h}+1}{\prec}\cdots\overset{c_{h}+1}{\prec}J_{a_{h}}\overset{c_{h}+1}{\prec}J_{a_{h}+1}\overset{c_{h}+1}{\longrightarrow}J_{n-q}$,
$J_{a_{h-1}+1}\overset{c_{h}+2}{\prec}J_{a_{h-1}+2}^{(1)}$ and
$\alpha(J_{n-q},J_{a_{h-1}+2}^{(1)})=1$, we also denote
$J_{n-q,1}^{(1)},J_{n-q,2}^{(1)},\dots,J_{{n-q},t_{h}}^{(1)}$ as follows

$\displaystyle
J_{a_{h-1}+2}^{(1)}\overset{c_{h}+1}{\longrightarrow}J_{n-q,1}^{(1)},\,\,i.e.,\,\,J_{{n-q},1}^{(1)}<J_{a_{h-1}+3}^{(1)};$
$\displaystyle
J_{a_{h-1}+3}^{(1)}\overset{c_{h}+1}{\longrightarrow}J_{n-q,2}^{(1)},\,\,i.e.,\,\,J_{{n-q},2}^{(1)}<J_{a_{h-1}+4}^{(1)};$
$\displaystyle\quad\vdots$ $\displaystyle
J_{a_{h}+1}^{(1)}\overset{c_{h}+1}{\longrightarrow}J_{n-q,t_{h}}^{(1)},\,\,i.e.,\,\,J_{{n-q},t_{h}}^{(1)}<J_{a_{h}+2}^{(1)}.$

Consequently,

$\displaystyle\alpha(J_{a_{h-1}+1},J_{n-q}^{(1)})-\beta(J_{a_{h-1}+1},J_{n-q}^{(1)})$
$\displaystyle=\alpha(J_{a_{h-1}+1},J_{n-q})+\alpha(J_{n-q},J_{a_{h-1}+2}^{(1)})+\alpha(J_{a_{h-1}+2}^{(1)},J_{{n-q},1}^{(1)})+\cdots$
$\displaystyle\quad+\alpha(J_{{n-q},t_{h}-1}^{(1)},J_{a_{h}+1}^{(1)})+\alpha(J_{a_{h}+1}^{(1)},J_{n-q}^{(1)})-\beta(J_{a_{h-1}+1},J_{n-q})$
$\displaystyle\quad-\beta(J_{n-q},J_{a_{h-1}+2}^{(1)})-\beta(J_{a_{h-1}+2}^{(1)},J_{{n-q},1}^{(1)})-\cdots$
$\displaystyle\quad-\beta(J_{{n-q},t_{h}-1}^{(1)},J_{a_{h}+1}^{(1)})-\beta(J_{a_{h}+1}^{(1)},J_{n-q}^{(1)}).$

Applying Corollary 3.3, we get

$\displaystyle\alpha(J_{a_{h-1}+2}^{(1)},J_{{n-q},1}^{(1)})=\alpha(J_{a_{h-1}+2},J_{n-q}),\,\beta(J_{a_{h-1}+2}^{(1)},J_{{n-q},1}^{(1)})=\beta(J_{a_{h-1}+2},J_{n-q}),$
$\displaystyle\alpha(J_{a_{h-1}+3}^{(1)},J_{{n-q},2}^{(1)})=\alpha(J_{a_{h-1}+3},J_{n-q}),\,\beta(J_{a_{h-1}+3}^{(1)},J_{{n-q},2}^{(1)})=\beta(J_{a_{h-1}+3},J_{n-q}),$
$\displaystyle\quad\vdots$
$\displaystyle\alpha(J_{a_{h}+1}^{(1)},J_{{n-q},t_{h}}^{(1)})=\alpha(J_{a_{h}+1},J_{n-q}),\,\beta(J_{a_{h}+1}^{(1)},J_{{n-q},t_{h}}^{(1)})=\beta(J_{a_{h}+1},J_{n-q}).$

By Proposition 2.19 and (38),

$\displaystyle\beta(J_{n-q},J_{a_{h-1}+2}^{(1)})=\sum_{j\neq
i}{n-(a_{h-1}+2+q)\choose k_{j}-(a_{h-1}+2+q-k_{i})},$
$\displaystyle\beta(J_{{n-q},1}^{(1)},J_{a_{h-1}+3}^{(1)})=\sum_{j\neq
i}{n-(a_{h-1}+3+q)\choose k_{j}-(a_{h-1}+3+q-k_{i})},$
$\displaystyle\quad\vdots$
$\displaystyle\beta(J_{{n-q},t_{h}-1}^{(1)},J_{a_{h}+1}^{(1)})=\beta(J_{a_{h}+1}^{(1)},J_{n-q}^{(1)})=0.$

Then by Claim 3.15, we have

$\displaystyle\alpha(J_{a_{h-1}+1},J_{n-q})-\beta(J_{a_{h-1}+1},J_{n-q})$ (39)
$\displaystyle>\sum_{j\neq i}\left[{n-(a_{h-1}+1+q)\choose
k_{j}-(a_{h-1}+1+q-k_{i})}-{n-(a_{h-1}+2+q)\choose
k_{j}-(a_{h-1}+2+q-k_{i})}\right.$
$\displaystyle\quad\left.+{n-(a_{h-1}+2+q)\choose
k_{j}-(a_{h-1}+2+q-k_{i})}-\cdots+{n-(a_{h}+1+q)\choose
k_{j}-(a_{h}+1+q-k_{i})}\right]$ $\displaystyle=\sum_{j\neq
i}{n-(a_{h-1}+1+q)\choose k_{j}-(a_{h-1}+1+q-k_{i})}.$ (40)

Using the same argument, we get

$\displaystyle\alpha(J_{a_{h-1}+2}^{(1)},J_{n-q}^{(1)})-\beta(J_{a_{h-1}+2}^{(1)},J_{n-q}^{(1)})>\sum_{j\neq
i}{n-(a_{h-1}+2+q)\choose k_{j}-(a_{h-1}+2+q-k_{i})},$ (41)
$\displaystyle\quad\vdots$
$\displaystyle\alpha(J_{a_{h}}^{(1)},J_{n-q}^{(1)})-\beta(J_{a_{h}}^{(1)},J_{n-q}^{(1)})>\sum_{j\neq
i}{n-(a_{h}+q)\choose k_{j}-(a_{h}+q-k_{i})},$ (42)
$\displaystyle\alpha(J_{a_{h}+1}^{(1)},J_{n-q}^{(1)})-\beta(J_{a_{h}+1}^{(1)},J_{n-q}^{(1)})>0.$
(43)

######  Claim 3.16.

Let $1\leq k\leq c-c_{h}-2$ and $D\in\mathcal{F}_{k}$ with $\max D=p+q$. Then

$\alpha(D,J_{n-q}^{(k)})-\beta(D,J_{n-q}^{(k)})>\sum_{j\neq i}{n-(p+q)\choose
k_{j}-(p+q-k_{i})}.$

###### Proof.

By induction on $k$. For $k=1$, following from (39)– (43), we are done. Assume
that it holds for $\mathcal{F}_{j},j\in[1,c-c_{h}-3]$, we want to prove it
holds for $\mathcal{F}_{j+1}$. Define
$\widetilde{J}_{2}^{(j)},\dots,\widetilde{J}_{t_{1}}^{(j)},\\\
\widetilde{J}_{t_{1}+1}^{(j)},\dots,\widetilde{J}_{n-q}^{(j)}$ as follows:
$\widetilde{J}_{p}^{(j)}<J_{p}^{(j)},p=2,\dots,n$. Note that
$\widetilde{J}_{2}^{(j)}=J_{n-q}^{(j-1)}$. By induction hypothesis, and $\max
J_{1}=q+1$, we have

$\displaystyle\alpha(J_{1},\widetilde{J}_{2}^{(j)})-\beta(J_{1},\widetilde{J}_{2}^{(j)})$
$\displaystyle=\alpha(J_{1},J_{n-q}^{(j-1)})-\beta(J_{1},J_{n-q}^{(j-1)})$
$\displaystyle>\sum_{j\neq i}{n-(q+1)\choose k_{j}-(q+1-k_{i})}.$ (44)

And for $2\leq p\leq n-q$, we have

$\alpha(J_{p}^{(j-1)},\widetilde{J}_{p}^{(j)})-\beta(J_{p}^{(j-1)},\widetilde{J}_{p}^{(j)})>\sum_{j\neq
i}{n-(q+p)\choose k_{j}-(q+p-k_{i})}.$ (45)

Recall that for $2\leq p\leq n-q-1$, we have

$J_{p}^{(j)}\overset{c_{h}+j}{\longrightarrow}\widetilde{J}_{p+1}^{(j)},\,\,J_{p}^{(j-1)}\overset{c_{h}+j}{\longrightarrow}J_{n-q}^{(j-1)}$

and

$\max J_{p}^{(j)}=\max
J_{p}^{(j-1)}=q+p,\,\,\max\widetilde{J}_{p+1}^{(j)}=\max J_{n-q}^{(j-1)}=n.$

Applying Corollary 3.3, we get

$\alpha(J_{p}^{(j)},{J}_{p+1}^{(j)})=\alpha(J_{p}^{(j-1)},J_{n-q}^{(j-1)})$

and

$\beta(J_{p}^{(j)},{J}_{p+1}^{(j)})=\beta(J_{p}^{(j-1)},J_{n-q}^{(j-1)}).$

By Proposition 2.19 and inequalities (44), (45), if $2\leq p\leq n-q-1$, then

$\displaystyle\alpha(J_{p}^{(c_{h}+j-1)},J_{n-q}^{(c_{h}+j-1)})-\beta(J_{p}^{(c_{h}+j-1)},J_{n-q}^{(c_{h}+j-1)})$
$\displaystyle=\alpha(J_{p}^{(c_{h}+j-1)},\widetilde{J}_{p+1}^{(c_{h}+j-1)})+\alpha(\widetilde{J}_{p+1}^{(c_{h}+j-1)},J_{p+1}^{(c_{h}+j-1)})+\alpha(J_{p+1}^{(c_{h}+j-1)},\widetilde{J}_{p+2}^{(c_{h}+j-1)})+\cdots$
$\displaystyle\quad+\alpha(\widetilde{J}_{n-q}^{(c_{h}+j-1)},J_{n-q}^{(c_{h}+j-1)})-\beta(J_{p}^{(c_{h}+j-1)},\widetilde{J}_{p+1}^{(c_{h}+j-1)})-\beta(\widetilde{J}_{p+1}^{(c_{h}+j-1)},J_{p+1}^{(c_{h}+j-1)})$
$\displaystyle\quad-\beta(J_{p+1}^{(c_{h}+j-1)},\widetilde{J}_{p+2}^{(c_{h}+j-1)})-\cdots-\beta(\widetilde{J}_{n-q}^{(c_{h}+j-1)},J_{n-q}^{(c_{h}+j-1)})$
$\displaystyle>\sum_{j\neq i}\left[{n-(q+p)\choose
k_{j}-(q+p-k_{i})}-{n-(q+p+1)\choose k_{j}-(q+p+1-k_{i})}+{n-(q+p+1)\choose
k_{j}-(q+p+1-k_{i})}\right.$
$\displaystyle\quad\left.-\cdots+{n-(k_{i}+l)\choose
k_{j}-(k_{i}+l-k_{i})}-{n-(k_{i}+l+1)\choose k_{j}-(k_{i}+l+1-k_{i})}\right]$
$\displaystyle=\sum_{j\neq i}{n-(q+p)\choose k_{j}-(q+p-k_{i})},$

where the second inequality follows from (45) and Proposition 2.19.

For $p=1$, by (44) and using the same argument as above, we get

$\alpha(J_{1},J_{n-q}^{(c_{h}+j-1)})-\beta(J_{1},J_{n-q}^{(c_{h}+j-1)})>\sum_{j\neq
i}{n-(q+1)\choose k_{j}-(q+1-k_{i})}.$ (46)

∎

Next, we are going to complete the proof of Lemma 2.11.

Recall that $J_{n-q}^{(c-3)}<H$ and $\max H=q+2,G=J_{1}$, so

$\displaystyle\alpha(G,H)-\beta(G,H)$
$\displaystyle=\alpha(G,J_{n-q}^{(c-3)})+\alpha(J_{n-q}^{(c-3)},H)-\beta(G,J_{n-q}^{(c-3)})-\beta(J_{n-q}^{(c-3)},H)$
$\displaystyle>\sum_{j\neq i}\left[{n-(q+1)\choose
k_{j}-(q+1-k_{i})}-{n-(q+2)\choose k_{j}-(q+2-k_{i})}\right]+1$
$\displaystyle>0,$

where the second inequality follows from (46) and Proposition 2.19. The proof
of Lemma 2.11 is complete.

###  3.2 Proof of Lemma 2.12

Recall that $\mathcal{R}_{k}:=\\{R\in\mathcal{R}:[n-k+1,n]\subset
R\\},\mathcal{R}(k):=\\{R\setminus[n-k+1,n]:R\in\mathcal{R}_{k}\\}$ for
$k\in[k_{i}-1]$. By Remark 2.17 and using the same argument as Claim 3.1, we
have the following claim.

######  Claim 3.17.

Let $1\leq j\leq k_{i}-1$ and $1\leq c\leq k_{i}-j$. Let
$F,H,F^{\prime},H^{\prime}\in\mathcal{R}(j)$ and
$F\overset{c}{\prec}H,F^{\prime}\overset{c}{\prec}H^{\prime}$. If $\max F=\max
F^{\prime}$, then $\alpha(F,H)=\alpha(F^{\prime},H^{\prime})$ and
$\beta(F,H)=\beta(F^{\prime},H^{\prime})$.

######  Claim 3.18.

Let $F_{1}<G_{1},F_{2}<G_{2}$ in $\mathcal{R}(j),j\in[0,k_{i}-1]$ with $\max
G_{1}=\max G_{2}$. Then $\alpha(F_{1},G_{1})=\alpha(F_{2},G_{2})$ and
$\beta(F_{1},G_{1})=\beta(F_{2},G_{2})$.

###### Proof.

For $j=0$, we can see that $\alpha(F_{1},G_{1})=\alpha(F_{2},G_{2})=1$, then
Claim 3.18 follows from Proposition 2.19. Now assume that $j\geq 1$. Let
$F^{\prime}_{1}=F_{1}\sqcup\\{n-j+1,\dots,n\\},F^{\prime}_{2}=F_{2}\sqcup\\{n-j+1,\dots,n\\},G^{\prime}_{1}=G_{1}\sqcup\\{n-j+1,\dots,n\\},G^{\prime}_{2}=G_{2}\sqcup\\{n-j+1,\dots,n\\},$
then
$F^{\prime}_{1},F^{\prime}_{2},G^{\prime}_{1},G^{\prime}_{2}\in\mathcal{R}$.
Let $H_{1}$ and $H_{2}$ be the sets such that $F^{\prime}_{1}<H_{1}$ and
$F^{\prime}_{2}<H_{2}$ in $\mathcal{R}$. We get
$H_{1}\overset{j}{\longrightarrow}G^{\prime}_{1}$ and
$H_{2}\overset{j}{\longrightarrow}G^{\prime}_{2}$. By the definitions of
$F_{1},G_{1},F_{2}$ and $G_{2}$, we have $\max H_{1}=\max H_{2}$ and $\max
G^{\prime}_{1}=\max G^{\prime}_{2}$. So Corollary 3.3 gives
$\alpha(F^{\prime}_{1},G^{\prime}_{1})=\alpha(F^{\prime}_{2},G^{\prime}_{2})$
and
$\beta(F^{\prime}_{1},G^{\prime}_{1})=\beta(F^{\prime}_{2},G^{\prime}_{2})$,
that is $\alpha(F_{1},G_{1})=\alpha(F_{2},G_{2})$ and
$\beta(F_{1},G_{1})=\beta(F_{2},G_{2})$. ∎

It’s easy to check the following corollary by using a similar argument of
Corollary3.3.

######  Corollary 3.19.

Let $c\in[k_{i}-j]$ and $F,G,F^{\prime},G^{\prime}\in\mathcal{R}(j)$. If $F,G$
are $c$-sequential, $F^{\prime},G^{\prime}$ are $c$-sequential satisfying
$\max F=\max F^{\prime}$ and $\max G=\max G^{\prime}$, then
$\alpha(F,G)=\alpha(F^{\prime},G^{\prime})$ and
$\beta(F,G)=\beta(F^{\prime},G^{\prime})$.

###### Proof.

We prove Lemma 2.12 by induction on $j$. It holds for $j=0$ by Lemma 2.11.
Suppose it holds for $j\in[0,k_{i}-2]$, we are going to prove it holds for
$j+1$. Let $F,G,H\in\mathcal{R}(j+1)$ with
$F\overset{c}{\prec}G\overset{c}{\prec}H$ and $\alpha(F,G)>\beta(F,G)$. We are
going to apply induction assumption to show $\alpha(G,H)>\beta(G,H)$. Let
$F^{\prime}=F\sqcup\\{\max F+1\\},G^{\prime}=G\sqcup\\{\max G+1\\}$ and
$H^{\prime}=H\sqcup\\{\max H+1\\}$. Then
$F^{\prime},G^{\prime},H^{\prime}\in\mathcal{R}(j)$. Moreover,
$F^{\prime}\overset{c+1}{\prec}G^{\prime}\overset{c+1}{\prec}H^{\prime}$ in
$\mathcal{R}(j)$.

Let $G_{1},G_{2},H_{1},F_{1},F_{2}$ be sets satisfying
$G_{1}<G^{\prime}<G_{2},H_{1}<H^{\prime},F^{\prime}\overset{c}{\prec}F_{1}$
and $F^{\prime}<F_{2}$. Let
$\widetilde{F}=F\sqcup\\{n-j\\},\widetilde{G}=G\sqcup\\{n-j\\}$,
$\widetilde{H}=H\sqcup\\{n-j\\}$. Then
$\widetilde{F},\widetilde{G},\widetilde{H}\in\mathcal{R}(j)$. We get

$F^{\prime}<F_{2}\overset{1}{\longrightarrow}\widetilde{F}<F_{1}\overset{c}{\longrightarrow}G_{1}<G^{\prime}<G_{2}\overset{1}{\longrightarrow}\widetilde{G}\,\,\text{and}\,\,G^{\prime}\overset{c}{\longrightarrow}H_{1}<H^{\prime}.$
(47)

######  Claim 3.20.

$\alpha(F_{1},G_{1})>\beta(F_{1},G_{1}).$

###### Proof.

Suppose on the contrary that $\alpha(F_{1},G_{1})\leq\beta(F_{1},G_{1}).$ By
(47),

$\displaystyle\alpha(\widetilde{F},\widetilde{G})=\alpha(\widetilde{F},F_{1})+\alpha(F_{1},G_{1})+\alpha(G_{1},G^{\prime})+\alpha(G^{\prime},\widetilde{G}),$
$\displaystyle\beta(\widetilde{F},\widetilde{G})=\beta(\widetilde{F},F_{1})+\beta(F_{1},G_{1})+\beta(G_{1},G^{\prime})+\beta(G^{\prime},\widetilde{G}).$

Note that $\alpha(F,G)\geq\beta(F,G)$ means
$\alpha(\widetilde{F},\widetilde{G})\geq\beta(\widetilde{F},\widetilde{G})$.
Since $\alpha(F_{1},G_{1})\leq\beta(F_{1},G_{1})$, then

$\alpha(\widetilde{F},F_{1})+\alpha(G_{1},G^{\prime})+\alpha(G^{\prime},\widetilde{G})\geq\beta(\widetilde{F},F_{1})+\beta(G_{1},G^{\prime})+\beta(G^{\prime},\widetilde{G}).$
(48)

Note that $\max F_{2}=\max G^{\prime}.$ By Claim 3.18, we have
$\beta(F^{\prime},F_{2})=\beta(G_{1},G^{\prime})$ and
$\alpha(F^{\prime},F_{2})=\alpha(G_{1},G^{\prime})$. Note that
$F_{2}\overset{1}{\longrightarrow}\widetilde{F},G^{\prime}\overset{1}{\longrightarrow}\widetilde{G}$,
$\max F_{2}=\max G^{\prime}$ and $\max\widetilde{F}=\max\widetilde{G}$, it
follows from Corollary 3.19 that
$\alpha(F_{2},\widetilde{F})=\alpha(G^{\prime},\widetilde{G})$ and
$\beta(F_{2},\widetilde{F})=\beta(G^{\prime},\widetilde{G}).$ Then

$\displaystyle\alpha(\widetilde{F},F_{1})+\alpha(G_{1},G^{\prime})+\alpha(G^{\prime},\widetilde{G})$
$\displaystyle=\alpha(\widetilde{F},F_{1})+\alpha(F^{\prime},F_{2})+\alpha(F_{2},\widetilde{F})=\alpha(F^{\prime},F_{1}).$

Similarly, we have

$\beta(\widetilde{F},F_{1})+\beta(G_{1},G^{\prime})+\beta(G^{\prime},\widetilde{G})=\beta(F^{\prime},F_{1}).$

So inequality (48) gives
$\alpha(F^{\prime},F_{1})\geq\beta(F^{\prime},F_{1})$.

Note that
$F^{\prime}\overset{c}{\prec}F_{1},F_{1}\overset{c}{\longrightarrow}G_{1}\in\mathcal{R}(j),c\in[k_{i}-j]$,
by induction hypothesis, $\alpha(F_{1},G_{1})>\beta(F_{1},G_{1})$. A
contradiction to our assumption. ∎

By (47), we have
$G^{\prime}\overset{c}{\longrightarrow}H_{1},F_{1}\overset{c}{\longrightarrow}G_{1},\max
G^{\prime}=\max F_{1},\max H_{1}=\max G_{1}$, by Corollary 3.19 and Claim
3.20, we get

$\alpha(G^{\prime},H_{1})>\beta(G^{\prime},H_{1}).$ (49)

Since $G^{\prime}<G_{2}$ and $H_{1}<H^{\prime}$ in $\mathcal{R}(j)$, by Claim
3.18, $\alpha(G^{\prime},G_{2})=\alpha(H_{1},H^{\prime})$ and
$\beta(G^{\prime},G_{2})=\beta(H_{1},H^{\prime})$. Then
$f(G_{2})<f(H^{\prime})$ following from (49). Recall that
$G_{2}\overset{1}{\longrightarrow}\widetilde{G}$ and
$H^{\prime}\overset{1}{\longrightarrow}\widetilde{H}$. Hence,
$f(\widetilde{G})<f(\widetilde{H})$ by applying Corollary 3.19. This implies
$\alpha(G,H)>\beta(G,H)$, as desired. The proof of Lemma 2.12 is complete.

∎

###  3.3 Proofs of Lemma 2.13 and Lemma 2.14

We only give the proof of Lemma 2.13, Lemma 2.14 can be proved by the same
argument.

###### Proof of Lemma 2.13.

Since $f(\\{2,3,\dots,j\\})\leq f(\\{2,3,\dots,j-1\\})$, we have

$\alpha(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})\geq\beta(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\}).$
(50)

We need the following claim.

######  Claim 3.21.

$\displaystyle\alpha(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})=\alpha(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\}),$
$\displaystyle\beta(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})=\beta(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\}).$

###### Proof of Claim 3.21.

Note that the sets in
$\mathcal{L}([n],\\{2,3,\dots,j-1\\},k_{i})\setminus\mathcal{L}([n],\\{2,3,\dots,j\\},k_{i})$
are the $k_{i}$-sets containing $\\{2,3,\dots,j-1,j\\}$ but containing neither
$\\{1\\}$ nor $\\{j-1\\}$. Then we can see that

$\displaystyle\alpha(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})$
$\displaystyle=|\mathcal{L}([n],\\{2,3,\dots,j-1\\},k_{i})|-|\mathcal{L}([n],\\{2,3,\dots,j\\},k_{i})|$
$\displaystyle={n-j\choose k_{i}-j+2}.$

Since the sets in
$\mathcal{L}([n],\\{2,3,\dots,j-2,j\\},k_{i})\setminus\mathcal{L}([n],\\{2,3,\dots,j-2,j-1\\},k_{i})$
are the $k_{i}$-sets containing $\\{2,3,\dots,j-2\\}$ but containing neither
$\\{1\\}$ nor $\\{j-1\\}$, we also get

$\alpha(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\})={n-j\choose k_{i}-j+2}.$

So we have

$\alpha(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})=\alpha(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\}),$
$\displaystyle\beta(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})$
$\displaystyle=\sum_{p\neq i}\left[{n-2\choose k_{p}-2}+\cdots+{n-j\choose
k_{p}-2}-{n-2\choose k_{p}-2}-\right.$
$\displaystyle\quad\left.\cdots-{n-(j-1)\choose k_{p}-2}\right]$
$\displaystyle=\sum_{p\neq i}{n-j\choose k_{p}-2},$

and

$\displaystyle\beta(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\})$
$\displaystyle=\sum_{p\neq i}\left[{n-2\choose k_{p}-2}+\cdots+{n-(j-1)\choose
k_{p}-2}\right.$ $\displaystyle\quad\left.-{n-2\choose
k_{p}-2}-\cdots-{n-(j-2)\choose k_{p}-2}-{n-j\choose k_{p}-3}\right]$
$\displaystyle=\sum_{p\neq i}{n-j\choose k_{p}-2}.$

Thus, we get

$\beta(\\{2,3,\dots,j\\},\\{2,3,\dots,j-1\\})=\beta(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\}).$

This completes the proof. ∎

By (50) and Claim 3.21, we have

$\alpha(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\})\geq\beta(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,j\\}).$

By Lemma 2.12, we have

$\displaystyle\alpha(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,n-k_{i}+j-4\\})$
$\displaystyle>\beta(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2,n-k_{i}+j-4\\}),$

that is,

$\alpha(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2\\})>\beta(\\{2,3,\dots,j-1\\},\\{2,3,\dots,j-2),$

or equivalently,

$f(\\{2,3,\dots,j-1\\})<f(\\{2,3,\dots,j-2\\}),$

as desired. ∎

##  4 Acknowledgements

We are thankful to two reviewers for giving us insightful comments to help
improve the presentation. This research is supported by National natural
science foundation of China (Grant No. 11931002).

## References

  * [1] P. Borg, The maximum product of sizes of cross-t-intersecting uniform families, Australas. J. Combin. 60 (2014) 69–78.
  * [2] P. Borg, A cross-intersection theorem for subsets of a set, Bull. Lond. Math. Soc. 47 (2015) 248–256.
  * [3] P. Borg, The maximum product of sizes of cross-intersecting families, Discrete Math. 340 (2017) 2307–2317.
  * [4] P. Borg, C. Feghali, The maximum sum of sizes of cross-intersecting families of subsets of a set, Discrete Math. 345 (2022) 112981.
  * [5] S. Cambie, J. Kim, H. Liu, T. Tran, A proof of Frankl’s conjecture on cross-union families, 9 pages, 2022 https://arxiv.org/pdf/2202.10365v1.pdf.
  * [6] P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxf. 2(12) (1961) 313–320.
  * [7] P. Frankl. On the arithmetic mean of the size of cross-union families, Acta Math. Hungar., 164(1):312–325, 2021.
  * [8] P. Frankl, A. Kupavskii, Sharp results concerning disjoint cross-intersecting families, Europ J. Combin 86 (2020) 103089.
  * [9] P. Frankl, A. Kupavskii, A size-sensitive inequality for cross-intersecting families, European J. Combin. 62 (2017) 263–271.
  * [10] P. Frankl, A. Kupavskii, Erdős-Ko-Rado theorem for {0, ±1}-vectors, J. Comb. Theory Ser. A 155 (2018), 157–179.
  * [11] P. Frankl, N. Tokushige, Some best possible inequalities concerning crossing-intersecting families, J. Combin. Theory Ser. A 61 (1992) 87-97.
  * [12] P. Frankl, Jian Wang, A product version of the Hilton-Milner theorem, 24 pages, 2022, https://arxiv.org/pdf/2206.07218.pdf
  * [13] P. Frankl, Jian Wang, A product version of the Hilton-Milner-Frankl theorem, 22 pages, 2022, https://arxiv.org/pdf/2206.07217.pdf
  * [14] A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxf. 2 (18) (1967) 369-384.
  * [15] A.J.W. Hilton, The Erdős-Ko-Rado theorem with valency conditions, Unpublished Manuscript, 1976.
  * [16] A.J.W. Hilton, An intersection theorem for a collection of families of subsets of a finite set, J. London Math. Soc. 2 (1977) 369-376.
  * [17] G.O.H. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq. Tihany, Akadémai Kiadó, (1968) 187–207.
  * [18] J.B. Kruskal, The number of simplices in a complex, in: Math. Opt. Techniques, Univ. of Calif. Press, (1963) 251-278.
  * [19] M. Matsumoto, N. Tokushige, The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families, J. Combin. Theory Ser. A 52 (1989), 90–97.
  * [20] L. Pyber, A new generalization of the Erdős-Ko-Rado, J. Combin. Theory Ser. A 43 (1986) 85–90.
  * [21] C. Shi, P. Frankl, J. Qian, On non-empty cross-intersecting families, Combinatorica 42 (2022) 1513–1525
  * [22] J. Wang, H. Zhang, Nontrivial independent sets of bipartite graphs and cross-intersecting families, J. Combin. Theory, Ser. A 120 (2013) 129–141.