 |
Discrete Mathematics & Theoretical Computer Science |
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 HypergraphsArticle
Authors: Alexandre Bazin 
1; Laurent Beaudou 2; Giacomo Kahn 3; Kaveh Khoshkhah 4
- 1 WEB Architecture x Semantic WEB x WEB of Data
- 2 Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
- 3 Décision et Information pour les Systèmes de Production [DISP]
- 4 Institute of Computer Science [University of Tartu, Estonie]
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.
Source: HAL:hal-01847459v7
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: Measure and conquer,Hypergraphs,Minimal transversal,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Consultation statistics
This page has been seen 374 times.
This article's PDF has been downloaded 275 times.