Upper bound for the size of a k-uniform s-wise t-intersecting set system

2010-04-16T00:17:18Z

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

Upper bound for the size of a k-uniform s-wise t-intersecting set system - MathOverflow

Upper bound for the size of a k-uniform s-wise t-intersecting set system