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

被引：0

作者：

Bazin A. ^{[1
]}

Beaudou L. ^{[2
]}

Kahn G. ^{[3
]}

Khoshkhah K. ^{[4
]}

机构：

[1] Université de Montpellier, CNRS, LIRMM, Montpellier

[2] Université Clermont Auvergne, Clermont Auvergne INP, CNRS, Mines Saint-Etienne, LIMOS, Clermont-Ferrand

[3] Univ Lyon, Univ Lumière Lyon 2, INSA Lyon, Université Claude Bernard Lyon 1, DISP, EA4570, Bron

[4] Institute of Computer Science, University of Tartu, Tartu

来源：

Discrete Mathematics and Theoretical Computer Science | 2023年 / 23卷 / 02期

关键词：

conquer; hypergraphs; measure; Minimal transversals;

D O I：

10.46298/DMTCS.7129

中图分类号：

学科分类号：

摘要：

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 © 2023 by the author(s).

引用

共 37 条

[1] Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
Bazin, Alexandre
Beaudou, Laurent
Kahn, Giacomo
Khoshkhah, Kaveh
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2021, 23 (02)
[2] Book free 3-uniform hypergraphs
Ghosh, Debarun
Gyori, Ervin
Nagy-Gyorgy, Judit
Paulos, Addisu
Xiao, Chuanqi
Zamora, Oscar
DISCRETE MATHEMATICS, 2024, 347 (03)
[3] Cycle Decompositions in 3-Uniform Hypergraphs
Simón Piga
Nicolás Sanhueza-Matamala
Combinatorica, 2023, 43 : 1 - 36
[4] Stability on Matchings in 3-Uniform Hypergraphs
Guo, Mingyang
Lu, Hongliang
GRAPHS AND COMBINATORICS, 2022, 38 (03)
[5] Stability on Matchings in 3-Uniform Hypergraphs
Mingyang Guo
Hongliang Lu
Graphs and Combinatorics, 2022, 38
[6] Cycle Decompositions in 3-Uniform Hypergraphs
Piga, Simon
Sanhueza-Matamala, Nicolas
COMBINATORICA, 2023, 43 (01) : 1 - 36
[7] 3-UNIFORM HYPERGRAPHS AND LINEAR CYCLES
Ergemlidze, Beka
Gyori, Ervin
Methuku, Abhishek
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 933 - 950
[8] On Generalized Ramsey Numbers for 3-Uniform Hypergraphs
Dudek, Andrzej
Mubayi, Dhruv
JOURNAL OF GRAPH THEORY, 2014, 76 (03) : 217 - 223
[9] Squares of Hamiltonian cycles in 3-uniform hypergraphs
Bedenknecht, Wiebke
Reiher, Christian
RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (02) : 339 - 372
[10] 3-Uniform hypergraphs from vector spaces
Meulewaeter, Jeroen
Van Maldeghem, Hendrik
LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 690 : 91 - 111

← 1 2 3 4 →