On the representing number of intersecting families (Q1093635): Difference between revisions

The paper presents a generalization of well-known results: Theorems of Erdős-Ko-Rado (1961) and Hilton-Milner (1967). Let \({\mathcal M}\) be a family of sets, and \(R\) a single set. \(R\) is said to represent \({\mathcal M}\) or be a representing set for \({\mathcal M}\) if \(R\cap X\neq 0\) for all \(X\in {\mathcal M}\) has representing number \(r\) if \(r\) is the cardinality of a smallest set representing. Let \(\begin{pmatrix} M \\ k\end{pmatrix}\) denote the collection of all \(k\)-subsets of a finite set. A family is intersecting if any two members of it have a non-trivial intersection. Theorem. Denote by \(g(n;r,k)\) the maximal cardinality of an intersecting family \({\mathcal M}\subseteq \begin{pmatrix} M \\ k\end{pmatrix}\) of an n-set with representing number \(r\), \(1\leq r\leq k\leq n\). Then there are constants \(c_{r,k}\), \(C_{r,k}\) only depending on \(r\) and \(k\), such that \(c_{r,k}n^{k-r}\leq g(n;r,k)\leq C_{r,k}n^{k-r}\). The precise value of \(g(n;i,k)=\binom{n-1}{k-1}\) and \(g(n;2,k)=\binom{n-1}{k-1}-\binom{n-k-1}{k-1}\) are given by Theorems Erdős-Ko-Rado and Hilton-Milner, correspondingly. Some estimations of \(g(k)=g(n;k,k)\), which for \(n\geq n_0(k)\) is independent of \(n\), are obtained. The authors put the following questions: first, improve the bounds on \(g(k)\), second, estimate the value of \(n_0(k)\). See also: \textit{I. Anderson} and \textit{A. J. W. Hilton}, The Erdős-Ko-Rado theorem with valency conditions, Q. J. Math., Oxf. II. Ser. 37, 385-390 (1986; Zbl 0619.05037).