Cross-intersecting families of finite sets
The author continues the study of cross-intersecting families of finite sets initiated by Hilton and Milner. He describes the structure of the nontrivial extremal systems, namely he proves the theorem: If \({\mathcal A}\subset (\begin{smallmatrix} [n]\\ a\end{smallmatrix})\), \({\mathcal B}\subset (\begin{smallmatrix} [n]\\ b\end{smallmatrix})\), \(n\geq a+ b\), \(A\cap B\neq \varnothing\) for all \(A\in {\mathcal A}\) and \(B\in {\mathcal B}\); \[ |{\mathcal A}|> (\begin{smallmatrix} n- 1\\ a- 1\end{smallmatrix})- (\begin{smallmatrix} n- b- 1\\ a- 1\end{smallmatrix})\quad\text{and} \quad |{\mathcal B}|> (\begin{smallmatrix} n- 1\\ b- 1\end{smallmatrix})- (\begin{smallmatrix} n- a- 1\\ b- 1\end{smallmatrix}), \] then one of the following cases holds: (i) there exists \(x\in [n]\) such that \(x\in \bigcap {\mathcal A}\) and \(x\in \bigcap {\mathcal B}\); or \[ |{\mathcal A}|= (\begin{smallmatrix} n- 1\\ a- 1\end{smallmatrix})- (\begin{smallmatrix} n- b- 1\\ a- 1\end{smallmatrix})+ 1\quad\text{and} \quad |{\mathcal B}|= (\begin{smallmatrix} n- 1\\ b- 1\end{smallmatrix})- (\begin{smallmatrix} n- a- 1\\ b- 1\end{smallmatrix})+ 1.\tag{ii} \] The extremal cases in (ii) are described in full details.
scientific article; zbMATH DE number 823504
scientific article