Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs

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.

Bibliografski detalji

Glavni autori:	Alexandre Bazin, Laurent Beaudou, Giacomo Kahn, Kaveh Khoshkhah
Format:	Artigo
Jezik:	Inglês
Izdano:	Discrete Mathematics & Theoretical Computer Science 2023-04-01
Serija:	Discrete Mathematics & Theoretical Computer Science
Teme:	measure and conquer hypergraphs minimal transversal [math.math-co]mathematics [math]/combinatorics [math.co] [info.info-dm]computer science [cs]/discrete mathematics [cs.dm]
Online pristup:	https://dmtcs.episciences.org/7129/pdf
Oznake:	Dodaj oznaku Bez oznaka, Budi prvi tko označuje ovaj zapis!