On Helly families of maximal size (Q793730): Difference between revisions

The authors present some generalizations of their previous results [J. Comb. Theory, Ser. A 26, 197-200 (1979; Zbl 0411.05002)]. A family of sets is said to be an \(H_ k\)-family if in every subfamily with empty intersection there exists a set consisting of at most k sets whose intersection is empty. For a set X and \(x\in X\) put \(X^{(r)}=\{A;\quad A\subseteq X,\quad | A| =r\},\quad X_ x^{(r)}=\{A\in X^{(r)};\quad x\in A\}.\) Theorem 1: Let X be a set with \(n\geq 5\) elements and r an integer \(>2\). Let \({\mathcal F}\) be a Sperner \(H_ 2\)- family of subsets of X. If the members of \({\mathcal F}\) have at most r elements, then \[ | {\mathcal F}| \leq \begin{cases} \binom{ni1}{r-1} \quad&\text{if } r\leq n/2, \\ \binom{n-1}{[n/2]} \quad&\text{if } r>n/2. \end{cases} \] Moreover, equality holds for \(r\leq n/2\) iff \({\mathcal F}=X_ x^{(r)}\) for some \(x\in X\). For \(r>n/2\) equality occurs iff: (i) n is even and \({\mathcal F}=X_ x^{(n/2)}\) or \({\mathcal F}=X_ x^{(n/2+1)}\) for some \(x\in X\), (ii) n is od\(d\geq 7\) and \({\mathcal F}=X_ x^{((n+1)/2)}\) for some \(x\in X\), (iii) \(n=5\) and \({\mathcal F}=X_ x^{(3)}\) for some \(x\in X\) or \({\mathcal F}\simeq K_{2,3}\) (where \(K_{2,3}\) denotes the complete bipartite graph on 2, 3 vertices). Theorem 2: Let X be a set of n elements and let \({\mathcal F}\subset \cup^{r}_{s=0}X^{(s)}\) be an \(H_ k\)-family, where \(k<r\). Then \[ | {\mathcal F}| \leq \sum^{k- 1}_{s=1}\left( \begin{matrix} n\\ s\end{matrix} \right)+\sum^{r}_{s=k}\left( \begin{matrix} n-1\\ s-1\end{matrix} \right) \] with equality iff \[ {\mathcal F}=\cup^{k-1}_{s=1}X^{(s)}\cup \cup^{r}_{s=k}X_ x^{(s)}\quad for\quad some\quad x\in X. \]