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 Hypergraphs

Authors: 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.

    https://doi.org/10.46298/dmtcs.7129
    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]
    Licence: https://creativecommons.org/licenses/by

    Share and export

    Consultation statistics

    This page has been seen 48 times.
    This article's PDF has been downloaded 25 times.