Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 '10 at 0:19
    
Harry, many thanks! –  Hung Q. Ngo Apr 16 '10 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 '10 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 '10 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 '10 at 4:32

1 Answer 1

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

and

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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