Great intersecting families of edges in hereditary hypergraphs (Q789409): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Dezsö Miklós / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Leszek S. Zaremba / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4087226 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4060998 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pairings from down-sets and up-sets in distributive lattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of latent subsets of intersecting collections / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4182515 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4046052 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4060997 / rank | |||
Normal rank |
Latest revision as of 10:58, 14 June 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