Upper bound for the size of a k-uniform s-wise t-intersecting set system - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:11:32Z http://mathoverflow.net/feeds/question/21520 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21520/upper-bound-for-the-size-of-a-k-uniform-s-wise-t-intersecting-set-system Upper bound for the size of a k-uniform s-wise t-intersecting set system Hung Q. Ngo 2010-04-16T00:17:18Z 2010-04-16T00:18:16Z <p>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$. </p> <p><strong>My question is</strong>: what is the best known upper bound on $m(n,k,s,t)$?</p> <p>Below are what I was able to dig out from the literature.</p> <p>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$.</p> <p>[Ahlswede and Khachatrian 1997] derived tight bounds for the $n &lt; n_0$ case, completely settling the pairwise $t$-intersecting sub-problem.</p> <p>[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$.</p> <p>[<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.77.2683&amp;rep=rep1&amp;type=pdf" rel="nofollow">Tokishige 2007</a>] 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$.</p> <p>There are also some other papers discussing bounds when $s$ and $t$ are small constants.</p> <p>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).</p>