Great intersecting families of edges in hereditary hypergraphs (Q789409): Difference between revisions

Let \({\mathcal H}\) be a hereditary hypergraph on a set S and \({\mathcal M}\subset {\mathcal H}\) be an intersecting subgraph, i.e., \(A\cap B\neq \emptyset\) holds for any pair A,\(B\in {\mathcal M}\). Chvátal conjectured in 1972 that then there exists an \(x\in S\) such that \(| \{A\in {\mathcal H}:\quad x\in A\}| =| {\mathcal M}|,\) whenever \({\mathcal M}\) is an intersecting subhypergraph of maximum cardinality. It is also known (\textit{C. Berge} [Proc. 5th Br. Comb. Conf., Aberdeen 1975, 35-40 (1976; Zbl 0324.05121)], \textit{J. Schönheim} [ibid., 537-539 (1976; Zbl 0399.05002)]) that \(| {\mathcal M}| \leq frac{1}{2}| {\mathcal H}|\) for every \({\mathcal M}\) and \({\mathcal H}\). The present paper is strictly related to the above mentioned conjecture and theorem. Namely, it is proved (Theorem 2) that if there exists an \({\mathcal M}\subset {\mathcal H}\) such that \(| {\mathcal M}| =\lfloor frac{1}{2}| {\mathcal H}| \rfloor\) then Chvátal's conjecture is true for these \({\mathcal M}\) and \({\mathcal H}\). This result follows from a stronger result (Theorem 3).