On the number of minimal transversals in 3-uniform hypergraphs

DOI10.1016/J.DISC.2007.07.024MaRDI QIDQ932689zbMATH OpenOpenAlexFDO

Authors Zbigniew Lonc, Mirosław Truszczyński

Publication date 11 July 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.07.024

zbMATH Keywords

maximal independent setminimal transversaluniform hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

• On upper transversals in 3-uniform hypergraphs
• Transversal numbers of uniform hypergraphs
• Transversals in 4-uniform hypergraphs
• Upper transversals in hypergraphs
• Bounds on upper transversals in hypergraphs

Cites work

• A Note on Independent Sets in Trees
• Circumscription - a form of non-monotonic reasoning
• Circumscriptive theories: A logic-based framework for knowledge representation
• Le nombre maximum de cliques et de recouvrements par cliques des hypergraphes chromatiques complets
• Logic Programming
• New methods for 3-SAT decision and worst-case analysis
• On cliques in graphs
• The number of maximal independent sets in a connected graph
• The Number of Maximal Independent Sets in a Tree
• The number of maximal independent sets in connected graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs

Cited in

(13)

• On upper transversals in 3-uniform hypergraphs
• Counting minimal transversals of -acyclic hypergraphs
• Maximizing \(2\)-independents sets in \(3\)-uniform hypergraphs
• Small cores in 3-uniform hypergraphs
• Hypergraphs with large transversal number and with edge sizes at least 3
• Minimum size transversals in uniform hypergraphs
• Extremal problems related to Betti numbers of flag complexes
• scientific article; zbMATH DE number 165088 (Why is no real title available?)
• On the number of minimal dominating sets on some graph classes
• On Triple Systems with Independent Neighbourhoods
• Combination of bases and an evaluation of the set of extremal 3-uniform hypergraphs
• On the number of \(A\)-transversals in hypergraphs
• Identification of a monotone Boolean function with \(k\) ``reasons as a combinatorial search problem

This page was built for publication: On the number of minimal transversals in 3-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q932689)