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.7129
Bounding the Number of Minimal Transversals in Tripartite 3-Uniform HypergraphsArticle

Authors: Alexandre Bazin ORCID1; Laurent Beaudou 2; Giacomo Kahn ORCID3; Kaveh Khoshkhah 4

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.4977n and at most like 1.5012n.


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 412 times.
This article's PDF has been downloaded 326 times.