Given integers $n \geq k \geq t \geq 1$ and an integer $s$, let $m(n,k,s,t)$ denote the maximum size of a family $\mathcal F$ of $k$-subsets of $[n]$, i.e. $\mathcal F \subseteq \binom{[n]}{k}$, such that the intersection of any $s$ members of $\mathcal F$ is at least $t$.

My question is: what is the best known upper bound on $m(n,k,s,t)$?

Below are what I was able to dig out from the literature.

The classic Erdos-Ko-Rado theorem ([EKR 61] plus a result by [Wilson 1984]) states that $m(n,k,2,t) \leq \binom{n-t}{k-t}$ for $n \geq n_0(k,t) = (k-t+1)(t+1)$. This bound is tight for $n \geq n_0$.

[Ahlswede and Khachatrian 1997] derived tight bounds for the $n < n_0$ case, completely settling the pairwise $t$-intersecting sub-problem.

[Frankl 1974] showed that $m(n,k,s,1) \leq \binom{n-1}{k-1}$, provided that $ks \leq n(s-1)$. This bound is tight. (When $ks > n(s-1)$, the intersection of any $s$ members of $\mathcal F$ is not empty.) Several other papers of Frankl gave some bounds for the non-uniform case, i.e. when members of $\mathcal F$ do not need to be of the same size $k$.

[Tokushige 2007] gave a bound for $m(n,k,3,t)$. Conjecture 1 in that paper specifies a formula for $m(n,k,s,t)$ but not much evidence was given other than that the conjecture holds for $s=2$. I'd be interested to know whether the conjecture holds if we replace $=$ by $\leq$.

There are also some other papers discussing bounds when $s$ and $t$ are small constants.

In summary, I was not able to find any generic upper bound for $m(n,k,s,t)$ (except for the obvious fact that $s$-wise $t$-intersecting systems are also $(s-1)$-wise $t$-intersecting systems, and thus the EKR bound applies).

  • $\begingroup$ I've removed the LaTeX in the title because it does not render properly on the front page or the questions page. $\endgroup$ Apr 16 '10 at 0:19
  • $\begingroup$ It might help to mention an obvious lower bound: (n-t) choose (k-t). Gerhard "Ask Me About System Design" Paseman, 2010.04.15 $\endgroup$ Apr 16 '10 at 0:40
  • $\begingroup$ Now that the math has rendered correctly, it seems the lower bound (n-t) choose (k-t) figures often, and is applicable when s <= (n-t) choose (k-t), and may not apply otherwise. $\endgroup$ Apr 16 '10 at 0:59
  • 1
    $\begingroup$ Somewhat related is Fisher's inquality. That is, if we insist that every two sets have intersection exactly $t$, then there can be at most $n$ such sets (where $n$ is the size of the underlying set). Indeed, this holds even in the non-uniform case. $\endgroup$
    – Tony Huynh
    Apr 16 '10 at 4:32
  • $\begingroup$ Thanks Gerhard & Tony for the comments. @Gerhard, I did implicitly mention the $\binom{n-t}{k-t}$ bound in the last paragraph. @Tony, I'm aware of the Fisher's inequality. It's perhaps a little too far from what I'm seeking. $\endgroup$ Apr 16 '10 at 13:39

This is not as general as what is asked, but in N. Tokushige, The random walk method for intersecting families, in Horizons of Combinatorics, Bolyai Society Mathematical Studies, 17 (2008) 215-224, it is stated that

For any fixed $p = \frac{k}{n}$ such that $p < \frac{s-1}{s+1}$ and $n$ large enough,

$$m(n,k,s,t) \leq \alpha_{s, p}^t{{n}\choose{k}},$$

where $\alpha_{s,p} \in (p, 1)$ is the unique root of the equation $(1-p)x^s-x+p$.

The proof can be found in N. Tokushige, The maximum size of 4-wise 2-intersecting and 4-wise 2-union families, European J. Combin., 27 (2006) 814-825, where this is used as a tool to prove a strong theorem for specific $t$ and $s$. Upper bounds of the same kind seem to be proved in other places as well to give strong theorems for different fixed $t$ and $s$.

The first paper I linked to also proves that

There exist positive constants $n_1$, $\epsilon$ such that for all $t$ such that $1 \leq t \leq \frac{3^s-2s-1}{2}$ and all $n > n_1$ and $k$ such that $\frac{k}{n} < \frac{1}{3}+\epsilon$,

$$m(n,k,s,t) = \max\left\{{{n-t}\choose{k-t}}, (t+s){{n-t-s}\choose{k-t-s+1}}+{{n-t-s}\choose{k-t-s}}\right\}.$$

Note that ${n-t}\choose{k-t}$ and $(t+s){{n-t-s}\choose{k-t-s+1}}+{{n-t-s}\choose{k-t-s}}$ are exactly the sizes of $\mathcal{F}_0$ and $\mathcal{F}_1$ respectively in $\text{Conjecture}\ 1$ in question. So, this proves the conjecture for a restricted case. Results in the same spirit by the same author can also be found in

N. Tokushige, Multiply-intersecting families revisited, J. Combin. Theory B, 97 (2007) 929-948


N. Tokushige, A multiply intersecting Erdos-Ko-Rado theorem - The principal case, Discrete Math. 310 (2010) 453-460.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.