On the number of minimal transversals in 3-uniform hypergraphs
type: Item
instance of: scholarly article
title: On the number of minimal transversals in 3-uniform hypergraphs
zbMATH Open document ID: 1154.05046
author: Zbigniew Lonc
author: Mirosław Truszczyński
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
review text: In a hypergraph (without isolated vertex) a subset of vertices is \textit{independent} if it contains no edge. Erdős and Moser asked (around 1965): what is the possible maximum number \(f_{\mathcal G}(n)\) of maximal (for inclusion) independent sets in a \(n\)-vertex hypergraph (taken from a given class \(\mathcal G\) of hypergraphs), and which are the extremal ones. The original question was about the class of all 2-uniform hypergraphs, that is about all graphs, and was solved completely by Moon and Moser in 1965. Later the problem were studied and solved for several classes of graphs. The problem is easy for the class of all \(n\)-vertex hypergraph by application of the Sperner's Theorem. In 1981 for the classes of \(k\)-uniform hypergraphs (\(k>2\)) Tomescu constructed hypergraphs with \(d^n\) maximal independent sets (\(d\approx 1.5849\)) and conjectured that these are the extremal ones. The conjecture is still wide open. The nicely presented paper under review proves the upper bound \(c^n\) (\(c\approx 1.6702\)) for \(f_{\mathcal G}(n)\) in case of the class of all 3-uniform hypergraphs. The proofs are not easy and require lengthy case analysis.
reviewed by: Péter L. Erdős
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5300683
zbMATH Keywords: minimal transversal
zbMATH Keywords: maximal independent set
zbMATH Keywords: uniform hypergraph
MaRDI profile type: Publication
full work available at URL: j.disc.2007.07.024
OpenAlex ID: W2121301226
cites work: The number of maximal independent sets in connected graphs
cites work: The number of maximal independent sets in a connected graph
cites work: The Number of Maximal Independent Sets in Triangle-Free Graphs
cites work: New methods for 3-SAT decision and worst-case analysis
cites work: Circumscriptive theories: A logic-based framework for knowledge representation
cites work: Logic Programming
cites work: Circumscription - a form of non-monotonic reasoning
cites work: On cliques in graphs
cites work: A Note on Independent Sets in Trees
cites work: Le nombre maximum de cliques et de recouvrements par cliques des hypergraphes chromatiques complets
cites work: The Number of Maximal Independent Sets in a Tree
DOI: 10.1016/J.DISC.2007.07.024
description: scientific article; zbMATH DE number 5300683