1
$\begingroup$

Fix $c\in (0,1]$ and $r\in\mathbb{N}$. For $n\geq 2r$, define $$f_{r,c}(n):=\max{|\Omega_{n,c,r}|}$$ where $\Omega_{n,c,r}$ is a family of subsets of size $r$ of $(1,2,\ldots ,n)$, such that for every $A\in\Omega_{n,c,r}$, at least $c|\Omega_{n,c,r}|$ elements of $\Omega_{n,c,r}$ intersect $A$.

The Erdos-Ko-Rado theorem settles the case $c=1$: $$f_{r,1}(n)=\binom{n-1}{r-1}$$

For a generic $c$, can we find an explicit formula or an asymptotic for $f_{r,c}(n)$?

$\endgroup$
1
  • $\begingroup$ There is the generic situation: if Omega is all r-sets of an n-set $\binom{n-r}{r}$ do not intersect a given r-set $A$, giving a ratio of $(a-b)/a$ where $a=n(n-1)...(n-r+1)$ and $b=(n-r)(n-r-1)...(n-2r+1)$. In general $f_{r,c}(n)$ won't have much range for large $n$ and small $r$. Gerhard "How Tight Do You Need?" Paseman, 2015.09.22 $\endgroup$ Commented Sep 22, 2015 at 19:12

0

You must log in to answer this question.

Browse other questions tagged .