8
$\begingroup$

Is there any result known about the following generalization of the Erdős-Ko-Rado theorem?

Let $n, k, r, s$ be positive integers. We call a family $\mathcal{F}$ of $k$-element subsets of $\{1,\ldots, n\}$, an $(r, s)$-intersection family if among every $r$ elements of $\mathcal{F}$ at least two have an $s$-element intersection. What is the maximum size of such a family?

$\endgroup$

1 Answer 1

6
$\begingroup$

The case $s=1$ is Erdős hypergraph mathcing conjecture from

Paul Erdős (1965). A problem on independent $r$-tuples. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95. users.renyi.hu/~p_erdos/1965-01.pdf

A recent paper about it is

Peter Frankl (2017) Proof of the Erdős matching conjecture in a new range, Israel Journal of Mathematics 222(1), pp 421-430 doi:10.1007/s11856-017-1595-7

The generalization you are asking about is studied in

Christos Pelekis, Israel Rocha (2017), A generalization of Erdős' matching conjecture. arxiv:1710.04633

In the notation of this paper you are asking for the maximum number of edges in a $k$-uniform hypergraph, such that its $s$-matching number is strictly less than $r$. Their abstract says that they identify a collection of candidate solutions, and show that it contains the optimum when $n\geqslant 4k\binom{k}{s}r$.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your time. I truly appreciate your help. $\endgroup$
    – 123...
    Commented Apr 7, 2018 at 8:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .