Cross-intersecting families of finite sets
type: Item
instance of: scholarly article
title: Cross-intersecting families of finite sets
zbMATH Open document ID: 0839.05092
DOI: 10.1016/0097-3165(95)90072-1
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-06-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 823504
zbMATH Keywords: Hilton-Milner theorem
zbMATH Keywords: shifting technique
zbMATH Keywords: cross-intersecting families
zbMATH Keywords: finite sets
zbMATH Keywords: extremal systems
author: Zoltán Füredi
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: 0097-3165(95)90072-1
OpenAlex ID: W2076669108
cites work: Q3726125
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Q3770569
cites work: Extremal problems concerning Kneser-graphs
cites work: Non-trivial intersecting families
cites work: Some best possible inequalities concerning cross-intersecting families
cites work: Q3676174
cites work: SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Extremal problems for finite sets and convex hulls---a survey
cites work: Q5726070
cites work: The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
cites work: A new generalization of the Erdős-Ko-Rado theorem
cites work: A bipartite Erdős-Ko-Rado theorem
description: scientific article; zbMATH DE number 823504