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 条

[31] Anti-Ramsey number of expansions of paths and cycles in uniform hypergraphs
Tang, Yucong
Li, Tong
Yan, Guiying
JOURNAL OF GRAPH THEORY, 2022, 101 (04) : 668 - 685
[32] An upper bound for the k-power domination number in r-uniform hypergraphs
Alameda, Joseph S.
Kenter, Franklin
Meagher, Karen
Young, Michael
DISCRETE MATHEMATICS, 2022, 345 (11)
[33] Hypergraphs with Large Transversal Number and with Edge Sizes at Least 3
Henning, Michael A.
Yeo, Anders
JOURNAL OF GRAPH THEORY, 2008, 59 (04) : 326 - 348
[34] Spectrum of 3-uniform 6-and 9-cycle systems over Kv(3) - I
Keszler, Anita
Tuza, Zsolt
DISCRETE MATHEMATICS, 2024, 347 (03)
[35] The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform τ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau $$\end{document}-critical hypergraphs
André E. Kézdy
Jenő Lehel
European Journal of Mathematics, 2023, 9 (3)
[36] Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs
Henning, Michael A.
Yeo, Anders
DISCRETE MATHEMATICS, 2018, 341 (08) : 2285 - 2292
[37] Coloring d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d$$\end{document}-Embeddable k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-Uniform Hypergraphs
Carl Georg Heise
Konstantinos Panagiotou
Oleg Pikhurko
Anusch Taraz
Discrete & Computational Geometry, 2014, 52 (4) : 663 - 679

← 1 2 3 4 →