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 ORCID-iD1; Laurent Beaudou 2; Giacomo Kahn ORCID-iD3; 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
  • 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.

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: Attribution 4.0 International (CC BY 4.0)

Share and export

Consultation statistics

This page has been seen 99 times.
This article's PDF has been downloaded 56 times.