Great intersecting families of edges in hereditary hypergraphs (Q789409): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Great intersecting families of edges in hereditary hypergraphs |
scientific article |
Statements
Great intersecting families of edges in hereditary hypergraphs (English)
0 references
1984
0 references
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).
0 references
hereditary hypergraph
0 references
intersecting subhypergraph
0 references