2
$\begingroup$

Consider a family $\mathfrak{F}$ of $k$ element subsets of $\{1,2,..,n\}$, where $n\geq 2k$, such that any two members of $\mathfrak{F}$ have nonempty intersection. The Erdos-Ko-Rado theorem asserts that $|\mathfrak{F}|\leq {{n-1}\choose{k-1}}$.

One restriction we can put on our family of intersecting subsets is to say that any element $\{1,2,..,n\}$ may occur in at most $r$ subsets.

Let $f(n,k,r)$ be the cardinality of a maximal family of intersecting $k$-subsets on $\{1,2,..,n\}$, of which any element is in at most $r$ subsets.

Are there known sharp upper bounds for $f(n,k,r)$?

Improve this question
$\endgroup$
3
  • $\begingroup$ You now have n*r/k as an upper bound, which likely is strong for small r. Is there a region of r that interests you? Gerhard "Is In The Same Neighborhood?" Paseman, 2019.04.02. $\endgroup$
    – Gerhard Paseman
    Commented Apr 2, 2019 at 15:12
  • $\begingroup$ There is also the simple upper bound k*(r-1)+1. Is this the restriction that really interests you? Gerhard "The Neighborhood Seems Very Small" Paseman, 2019.04.02. $\endgroup$
    – Gerhard Paseman
    Commented Apr 2, 2019 at 15:16
  • 1
    $\begingroup$ Finally, I suspect the following will be optimal: take a projective plane where every point is on at most r lines, and then extend as needed to have each line contain k points. This gives something like O(r^2) for your f, and all that remains after proving the above optimal is to consider when k is smaller than r, and see how sharp the naive bounds are. Gerhard "Can't Get Out Of Suburb" Paseman, 2019.04.02. $\endgroup$
    – Gerhard Paseman
    Commented Apr 2, 2019 at 16:17

0

Reset to default

You must log in to answer this question.