3

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$.

[Tokishige 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).

flag
I've removed the LaTeX in the title because it does not render properly on the front page or the questions page. – Harry Gindi Apr 16 2010 at 0:19
Harry, many thanks! – Hung Q. Ngo Apr 16 2010 at 0:22
It might help to mention an obvious lower bound: (n-t) choose (k-t). Gerhard "Ask Me About System Design" Paseman, 2010.04.15 – Gerhard Paseman Apr 16 2010 at 0:40
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. – Gerhard Paseman Apr 16 2010 at 0:59
1 
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. – Tony Huynh Apr 16 2010 at 4:32
show 1 more comment

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.