Alexandre Bazin ; Laurent Beaudou ; Giacomo Kahn ; Kaveh Khoshkhah
-
Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
dmtcs:7129 -
Discrete Mathematics & Theoretical Computer Science,
April 20, 2023,
vol. 23 no. 2, special issue in honour of Maurice Pouzet
-
https://doi.org/10.46298/dmtcs.7129Bounding the Number of Minimal Transversals in Tripartite 3-Uniform HypergraphsArticleAuthors: Alexandre Bazin
1; Laurent Beaudou
2; Giacomo Kahn
3; Kaveh Khoshkhah
4
0000-0002-4268-8961##0000-0003-1959-6855##0000-0002-2889-4435##NULL
Alexandre Bazin;Laurent Beaudou;Giacomo Kahn;Kaveh Khoshkhah
We focus on the maximum number of minimal transversals in 3-partite 3-uniform hypergraphs on n vertices. Those hypergraphs (and their minimal transversals) are commonly found in database applications. In this paper we prove that this number grows at least like $1.4977^n$ and at most like $1.5012^n$.
Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
Section: Special issues
Published on: April 20, 2023
Accepted on: February 23, 2023
Submitted on: January 25, 2021
Keywords: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] Measure and conquer, Hypergraphs, Minimal transversal