On a packing and covering problem

Let m(n,k,r) be the maximal cardinality of a family F of k-element subsets of n-element set with the property that \(| F\cap F'| <r\) for any distinct F,F'\(\in F\). Clearly m(n,k,r)\(\leq \left( \begin{matrix} n\\ r\end{matrix} \right)/_{\left( \begin{matrix} k\\ r\end{matrix} \right)}\) holds and the problem of characterizing triples (n,k,r) for which \[ m(n,k,r)=\left( \begin{matrix} n\\ r\end{matrix} \right)/_{\left( \begin{matrix} k\\ r\end{matrix} \right)} \] holds is one of the difficult classical open problems of combinatorics. In 1965 P. Erdős and H. Hanani proved that \[ (*)\quad m(n,k,r)=\left( \begin{matrix} n\\ r\end{matrix} \right)/\left( \begin{matrix} k\\ r\end{matrix} \right)(1- O(1)) \] holds for \(r=2\) and k arbitrary and \(r=3\) and k power of prime. (Here 0(1)\(\to 0\) as \(n\to \infty)\). They also conjectured that (*) holds for any \(r<k\). Here we prove this conjecture.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: On a packing and covering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058516)