Great intersecting families of edges in hereditary hypergraphs
type: Item
instance of: scholarly article
title: Great intersecting families of edges in hereditary hypergraphs
zbMATH Open document ID: 0533.05047
DOI: 10.1016/0012-365X(84)90135-3
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3845625
zbMATH Keywords: hereditary hypergraph
zbMATH Keywords: intersecting subhypergraph
author: Dezsö Miklós
reviewed by: Leszek S. Zaremba
MaRDI profile type: Publication
cites work: Q4087226
cites work: Q4060998
cites work: Pairings from down-sets and up-sets in distributive lattices
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: On the number of latent subsets of intersecting collections
cites work: Q4182515
cites work: Q4046052
cites work: Q4060997
description: scientific article; zbMATH DE number 3845625