On the number of minimal transversals in 3-uniform hypergraphs
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.
scientific article; zbMATH DE number 5300683