Codegree conditions for cycle decompositions and Euler tours in 3-uniform hypergraphs

被引：0

作者：

Piga, Simon ^{[1
]}

Sanhueza-Matamala, Nicolas ^{[2
]}

机构：

[1] Univ Hamburg, Fachbereich Math, Hamburg, Germany

[2] Czech Acad Sci, Inst Comp Sci, Pod Vodarenskou Vezi 2, Prague 18207, Czech Republic

来源：

PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM | 2021年 / 195卷

关键词：

Hypergraphs; Euler tours; Cycles; Decompositions;

D O I：

10.1016/j.procs.2021.11.043

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that 3-graphs whose codegree is at least (2/3 + o(1))n can be decomposed into tight cycles and admit Euler tours, subject to the trivial necessary divisibility conditions. We also provide a construction showing that our bounds are best possible up to the o(1) term. All together, our results answer in the negative some recent questions of Glock, Joos, Kiihn and Osthus. (C) 2021 The Authors. Published by Elsevier B.V.

引用

页码：350 / 358

页数：9

共 34 条

[21] 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)
[22] Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
Bazin A.
Beaudou L.
Kahn G.
Khoshkhah K.
Discrete Mathematics and Theoretical Computer Science, 2023, 23 (02)
[23] PERFECT MATCHINGS IN 3-UNIFORM HYPERGRAPHS WITH LARGE VERTEX DEGREE
Khan, Imdadullah
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) : 1021 - 1039
[24] Tiling 3-Uniform Hypergraphs With K43-2e
Czygrinow, Andrzej
DeBiasio, Louis
Nagle, Brendan
JOURNAL OF GRAPH THEORY, 2014, 75 (02) : 124 - 136
[25] 3-Uniform hypergraphs of bounded degree have linear Ramsey numbers
Cooley, Oliver
Fountoulakis, Nikolaos
Kuehn, Daniela
Osthus, Deryk
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (03) : 484 - 505
[26] Saturation for the 3-uniform loose 3-cycle
English, Sean
Kostochka, Alexandr
Zirlin, Dara
DISCRETE MATHEMATICS, 2023, 346 (11)
[27] 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
[28] On 2- and 3-factorizations of complete 3-uniform hypergraphs of order up to 9
Adams, Peter
El-Zanati, Saad, I
Florido, Peter
Turner, William
AUSTRALASIAN JOURNAL OF COMBINATORICS, 2020, 78 : 100 - 113
[29] 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
[30] On maximum packings of λ-fold complete 3-uniform hypergraphs with triple-hyperstars of size 4
Armstrong, Amber
Bunge, Ryan C.
Duncan, William
El-Zanati, Saad, I
Koe, Kristin
Stutzman, Rachel
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2021, 9 (02) : 451 - 468

← 1 2 3 4 →