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 条

[21] Turan density of cliques of order five in 3-uniform hypergraphs with quasirandom links
Berger, Soeren
Piga, Simon
Reiher, Christian
Rodl, Vojtech
Schacht, Mathias
PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, 2021, 195 : 412 - 418
[22] Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs
Buss, Enno
Han, Hiep
Schacht, Mathias
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (06) : 658 - 678
[23] A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
Elbassioni, Khaled
Rauf, Imran
Ray, Saurabh
THEORETICAL COMPUTER SCIENCE, 2019, 767 : 26 - 33
[24] A DEGREE SEQUENCE STRENGTHENING OF THE VERTEX DEGREE THRESHOLD FOR A PERFECT MATCHING IN 3-UNIFORM HYPERGRAPHS*
Bowtell, Candida
Hyde, Joseph
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (02) : 1038 - 1063
[25] Turan and Ramsey numbers for 3-uniform minimal paths of length 4
Han, Jie
Polcyn, Joanna
Rucinski, Andrzej
JOURNAL OF GRAPH THEORY, 2021, 98 (03) : 460 - 498
[26] Embedding factorizations for 3-uniform hypergraphs II: r-factorizations into s-factorizations
Bahmanian, Amin
Newman, Mike
ELECTRONIC JOURNAL OF COMBINATORICS, 2016, 23 (02)
[27] The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform T-critical hypergraphs
Kezdy, Andre E.
Lehel, Jeno
EUROPEAN JOURNAL OF MATHEMATICS, 2023, 9 (03)
[28] Saturation for the 3-uniform loose 3-cycle
English, Sean
Kostochka, Alexandr
Zirlin, Dara
DISCRETE MATHEMATICS, 2023, 346 (11)
[29] On Ramsey numbers of 3-uniform Berge cycles
Maherani, Leila
Shahsiah, Maryam
DISCRETE MATHEMATICS, 2024, 347 (04)
[30] The Lagrangian density of the disjoint union of a 3-uniform tight path and a matching and the Turin number of its extension
Chen, Pingge
Liang, Jinhua
Peng, Yuejian
PURE AND APPLIED MATHEMATICS QUARTERLY, 2022, 18 (06) : 2379 - 2411

← 1 2 3 4 →