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$
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$
  • $\begingroup$ Thank you very much for your time. I truly appreciate your help. $\endgroup$ – 123... Apr 7 '18 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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