1 Introduction

We denote the standard n-element set \(\{1,2,\ldots ,n\}\) by [n], the set of all subsets of [n] by \(2^{[n]}\), and for \(0 \le k \le n\) the collection of all k-element subsets of [n] by \(\left( {\begin{array}{c}[n]\\ k\end{array}}\right) \). We also use the standard notation |S| for the cardinality of a set S and \(\lfloor m \rfloor \) for the largest integer less than or equal to m.

A family \(\mathcal {F}\) of subsets of [n] is said to be a t-intersecting family for some positive integer t if \(|F\cap G| \ge t\) for any two members F, G of \(\mathcal {F}\). A 1-intersecting family is simply called an intersecting family. The infamous Erdős–Ko–Rado theorem [1] gives the tight upper bound on the size of t-intersecting families.

Theorem 1

(Erdős–Ko–Rado theorem for t-intersecting family) For given positive integers k, t with \(k \ge t\) there exists some \(n_0(k, t)\) such that if \(n \ge n_0(k, t)\) and \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) is t-intersecting, then

$$\begin{aligned} |\mathcal {F}| \le \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) . \end{aligned}$$

The above upper bound is tight for \(n_0(k, t)=(t+1)(k-t+1)\); this was proved by Frankl [2] for \(t\ge 15\) and all \(t \ge 1\) using a different technique by Wilson [6].

For a family \(\mathcal {F}\), let

$$\begin{aligned} \mathcal {D}(\mathcal {F}) = \{F\setminus G: F, G \in \mathcal {F}\} \end{aligned}$$

be the collection of all (setwise) differences of \(\mathcal {F}\). Here we allow the empty set \(\emptyset \) to be in \(\mathcal {F}\) when \(\mathcal {F} \ne \emptyset \). Marica and Schönheim [5] proved the following lower bound for \(|\mathcal {D}(\mathcal {F})|\).

Theorem 2

(Marica–Schönheim) For a nonempty family \(\mathcal {F} \subset 2^{[n]}\) one has

$$\begin{aligned} |\mathcal {D}(\mathcal {F})| \ge |\mathcal {F}|. \end{aligned}$$

Recently, Frankl [3] proved the following upper bound for \(|\mathcal {D}(\mathcal {F})|\) when \(\mathcal {F}\) is an intersecting family.

Theorem 3

(Frankl) Suppose that \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) is an intersecting family with \(n \ge k(k+3)\). Then

$$\begin{aligned} |\mathcal {D}(\mathcal {F})| \le \left( {\begin{array}{c}n-1\\ k-1\end{array}}\right) +\left( {\begin{array}{c}n-1\\ k-2\end{array}}\right) +\cdots +\left( {\begin{array}{c}n-1\\ 0\end{array}}\right) . \end{aligned}$$

In the same paper, Frankl [3] conjectured the following.

Conjucture 1

Suppose that \(n > 2k\). Then for an intersecting family \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) we have

$$\begin{aligned} |\mathcal {D}(\mathcal {F})| \le \left( {\begin{array}{c}n-1\\ k-1\end{array}}\right) +\left( {\begin{array}{c}n-1\\ k-2\end{array}}\right) +\cdots +\left( {\begin{array}{c}n-1\\ 0\end{array}}\right) . \end{aligned}$$

In [4], Frankl, Kiselev, and Kupavskii proved this conjecture for \(n \ge 50k\ln k\), with \(k \ge 50\). They also provided a counterexample for the conjecture when n is close to 2k.

In this note we extend Theorem 3 to the t-intersecting families \(\mathcal {F}\) of \(\left( {\begin{array}{c}[n]\\ k\end{array}}\right) \). Precisely, we prove the following theorem.

Theorem 4

Let \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) be a t-intersecting family with \(n \ge 2^t(k-t)(k+t+1)\). Then

$$\begin{aligned} |\mathcal {D}(\mathcal {F})| \le \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) +\left( {\begin{array}{c}n-t\\ k-t-1\end{array}}\right) +\cdots +\left( {\begin{array}{c}n-t\\ 0\end{array}}\right) . \end{aligned}$$

2 Preliminaries

To prove Theorem 4 we require the following notions.

For a family \(\mathcal {F} \subset 2^{[n]}\) and a non-negative integer \(\ell \) let

$$\begin{aligned} \mathcal {D}^{(\ell )}(\mathcal {F}) = \left\{ D \in \left( {\begin{array}{c}[n]\\ \ell \end{array}}\right) : \exists F, G \in \mathcal {F}, F\setminus G = D \right\} . \end{aligned}$$

Note that

$$\begin{aligned} |\mathcal {D}(\mathcal {F})| = \sum _{\ell \ge 0} |\mathcal {D}^{(\ell )}(\mathcal {F})|. \end{aligned}$$

We call a family \(\mathcal {F}\) to be a t-star if there is some t-subset contained in every member of \(\mathcal {F}\). Similarly, we call \(\mathcal {F}\) to be the full t-star, if all elements of \(\left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) containing a fixed t-subset are the only elements of the family \(\mathcal {F}\).

Lemma 1

Let \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) be a t-intersecting family such that \(\mathcal {D}^{(k-t)}(\mathcal {F})\) has \(k+t+2\) members that are pairwise disjoint. Then \(\mathcal {F}\) is a t-star.

Proof

We can assume that \(k\ge t+1\), as the conclusion of the lemma is trivial for \(k = t\). Let \(D_0, D_1, \ldots , D_{k+t+1}\) be \(k+t+2\) pairwise disjoint members of \(\mathcal {D}^{(k-t)}(\mathcal {F})\). As \(D_i=F_i\setminus F_i^\prime \) for some \(F_i, F_i^\prime \in \mathcal {F}\) and \(\mathcal {F}\) is t-intersecting, for each \(D_i\) there exist some subset \(X_i\) of \(2^{[n]}\) with \(|X_i|=t\) and \(D_i\cup X_i \in \mathcal {F}\). Since \(D_i\) are pairwise disjoint, the set \(X_0\) intersects at most t distinct \(D_i\), and so without loss of generality we may assume \(D_{k+2}, D_{k+3}, \ldots , D_{k+t+1}\) are such \(D_i\) which may have non-empty intersection with \(X_0\). Therefore, \((D_0 \cup X_0) \cap D_i = \emptyset \) for all \(i=1,2,\ldots ,k+1\).

However, as \(D_i \cup X_i \in \mathcal {F}\) and \(\mathcal {F}\) is a t-intersecting family, we have in particular that \(|(D_0 \cup X_0) \cap (D_i \cup X_i)| \ge t\). But \(D_i\) are pairwise disjoint and \(X_0\cap D_i = \emptyset \) for \(1 \le i \le k+1\), the only possibility that we have is \(X_i \subset (D_0\cup X_0)\) for \(1 \le i \le k+1\).

Further, as \(|(D_1 \cup X_1) \cap (D_i \cup X_i)| \ge t\) for \(2 \le i \le k+1\), we have \(X_1 \cap D_i = \emptyset \), otherwise we would have \(D_1 \cap D_i \ne \emptyset \) or \((D_0 \cup X_0) \cap D_1 \ne \emptyset \) giving contradictions. By a similar argument, we have \(X_i \cap D_1 = \emptyset \). Thus, \(X_1=X_i\) for \(2 \le i \le k+1\).

We claim that \(X_1 \in F\) for all \(F \in \mathcal {F}\). Suppose that \(X_1 \nsubseteq F\) for some \(F \in \mathcal {F}\). Then \(|(D_i \cup X_i) \cap F| \ge t\) implies \(|D_i \cap F| \ne \emptyset \) for all \(1 \le i \le k+1\), which further implies \(|F| \ge k+1\), a contradiction to the fact that \(\mathcal {F}\) is a family of k-subsets of [n]. This completes the proof. \(\square \)

We note that, if \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) is a t-star with \(X \subset F\) for all \(F \in \mathcal {F}\) and \(|X|=t\), then \(\mathcal {D}^{(\ell )}(\mathcal {F}) \subset \left( {\begin{array}{c}[n]{\setminus } X\\ \ell \end{array}}\right) \) for all \(0 \le \ell \le k-t\). Thus, for t-stars \(|\mathcal {D}(\mathcal {F})| \le \sum _{\ell =0}^{k-t} |\mathcal {D}^{(\ell )}(\mathcal {F})|\). The equality holds when \(\mathcal {F}\) is the full t-star. Hence, for a t-star \(\mathcal {F}\), Theorem 4 is true. By Lemma 1, it is sufficient to prove Theorem 4 for t-intersecting families \(\mathcal {F}\) with \(\mathcal {D}^{(k-t)}(\mathcal {F})\) not containing \(k+t+2\) pairwise disjoint members.

Corollary 1

It is sufficient to prove Theorem 4 for families \(\mathcal {F}\) with \(\mathcal {D}^{(k-t)}(\mathcal {F})\) not containing \(k+t+2\) pairwise disjoint members.

3 The Proof of Theorem 4

Proof of Theorem 4

Choose uniformly at random a family \(\mathcal {D} \subset \left( {\begin{array}{c}[n]\\ k-t\end{array}}\right) \) such that it has \(2^t(k+t+1)\) members that are pairwise disjoint. Then the expected value

$$\begin{aligned} \mathbb {E}(|\mathcal {D} \cap \mathcal {D}^{(k-t)}(\mathcal {F})|) = \frac{2^t(k+t+1)}{\left( {\begin{array}{c}n\\ k-t\end{array}}\right) } |\mathcal {D}^{(k-t)}(\mathcal {F})|. \end{aligned}$$

But then Corollary 1 implies

$$\begin{aligned} \frac{2^t(k+t+1)}{\left( {\begin{array}{c}n\\ k-t\end{array}}\right) } |\mathcal {D}^{(k-t)}(\mathcal {F})| \le k+t+1. \end{aligned}$$

Thus,

$$\begin{aligned} |\mathcal {D}^{(k-t)}(\mathcal {F})|&\le \frac{1}{2^t}\left( {\begin{array}{c}n\\ k-t\end{array}}\right) \\&= \frac{1}{2^t} \cdot \frac{n(n-1)\cdots (n-t+1)}{(n-k+t)(n-k+t-1)\cdots (n-k+1)} \cdot \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) \\&\le \frac{1}{2^t} \cdot \left( \frac{n}{n-k+1}\right) ^t \cdot \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) . \end{aligned}$$

Note that

$$\begin{aligned}{} & {} \frac{n}{n-k+1} \le \frac{2(k+t+2)}{k+t+3} \\\Longleftrightarrow & {} n(k+t+3) \le 2(n-k+1)(k+t+2) \\\Longleftrightarrow & {} n(k+t+1) \ge 2(k-1)(k+t+2) \\\Longleftrightarrow & {} n \ge \frac{2(k-1)(k+t+2)}{k+t+1}, \end{aligned}$$

which is true, as \(n \ge 2^t(k-t)(k+t+1) \ge 4(k-1) \ge \frac{2(k-1)(k+t+2)}{k+t+1}\). So,

$$\begin{aligned} \frac{1}{2^t} \cdot \left( \frac{n}{n-k+1}\right) ^t \le \left( \frac{k+t+2}{k+t+3}\right) ^t, \end{aligned}$$

and hence

$$\begin{aligned} |\mathcal {D}^{(k-t)}(\mathcal {F})|&\le \left( \frac{k+t+2}{k+t+3}\right) ^t \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) \nonumber \\&< \frac{k+t+2}{k+t+3} \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) \nonumber \\&= \left( 1- \frac{1}{k+t+3}\right) \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) . \end{aligned}$$
(1)

For all other values of \(\ell =0,1,\ldots ,k-t-1\), as \(\mathcal {F} \subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) is t-intersecting, we have

$$\begin{aligned} |\mathcal {D}^{(0)}(\mathcal {F})| \le 1 = \left( {\begin{array}{c}n-t\\ 0\end{array}}\right) , \end{aligned}$$
(2)

and

$$\begin{aligned} |\mathcal {D}^{(\ell )}(\mathcal {F})| \le \left( {\begin{array}{c}n-t+1\\ \ell \end{array}}\right) = \left( {\begin{array}{c}n-t\\ \ell \end{array}}\right) +\left( {\begin{array}{c}n-t\\ \ell -1\end{array}}\right) \end{aligned}$$
(3)

for \(\ell =1,\ldots ,k-t-1\). Note that

$$\begin{aligned} \sum _{\ell =0}^{k-t-2} \left( {\begin{array}{c}n-t\\ \ell \end{array}}\right) \le (k-t-1)\left( {\begin{array}{c}n-t\\ k-t-2\end{array}}\right) < \frac{1}{k+t+3} \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) , \end{aligned}$$
(4)

where the last inequality can be easily verified by just expanding the binomial coefficients. Hence, combining the Eqs. (1), (2), (3), and (4) we obtain

$$\begin{aligned} |\mathcal {D}(\mathcal {F})|&= \sum _{\ell =0}^{k-t} |\mathcal {D}^{(\ell )}(\mathcal {F})|\\&< \sum _{\ell =0}^{k-t-1} |\mathcal {D}^{(\ell )}(\mathcal {F})| + \left( 1- \frac{1}{k+t+3}\right) \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) \\&= \sum _{\ell =0}^{k-t-1} \left( {\begin{array}{c}n-t\\ \ell \end{array}}\right) + \sum _{\ell =0}^{k-t-2} \left( {\begin{array}{c}n-t\\ \ell \end{array}}\right) + \left( 1-\frac{1}{k+t+3}\right) \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) \\&< \sum _{\ell =0}^{k-t-1} \left( {\begin{array}{c}n-t\\ \ell \end{array}}\right) + \frac{1}{k+t+3}\left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) + \left( 1- \frac{1}{k+t+3}\right) \left( {\begin{array}{c}n-t\\ k-t\end{array}}\right) \\&= \sum _{\ell =0}^{k-t} \left( {\begin{array}{c}n-t\\ \ell \end{array}}\right) . \end{aligned}$$

This completes the proof of the theorem. \(\square \)