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 条

[1] Cycle Decompositions in 3-Uniform Hypergraphs
Simón Piga
Nicolás Sanhueza-Matamala
Combinatorica, 2023, 43 : 1 - 36
[2] Cycle Decompositions in 3-Uniform Hypergraphs
Piga, Simon
Sanhueza-Matamala, Nicolas
COMBINATORICA, 2023, 43 (01) : 1 - 36
[3] LOCALIZED CODEGREE CONDITIONS FOR TIGHT HAMILTON CYCLES IN 3-UNIFORM HYPERGRAPHS
Araujo, Pedro
Piga, Simon
Schacht, Mathias
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (01) : 147 - 169
[4] Cycle decompositions in k-uniform hypergraphs
Lo, Allan
Piga, Simon
Sanhueza-Matamala, Nicolas
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 167 : 55 - 103
[5] On Decompositions of Complete 3-Uniform Hypergraphs into a Linear Forest with 4 Edges
Bunge, Ryan C.
Dawson, Erin
Donovan, Mary
Hatzer, Cody
Maass, Jacquelyn
COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2021, 2024, 448 : 333 - 354
[6] On 3-uniform hypergraphs without a cycle of a given length
Furedi, Zoltan
Ozkahya, Lale
DISCRETE APPLIED MATHEMATICS, 2017, 216 : 582 - 588
[7] Book free 3-uniform hypergraphs
Ghosh, Debarun
Gyori, Ervin
Nagy-Gyorgy, Judit
Paulos, Addisu
Xiao, Chuanqi
Zamora, Oscar
DISCRETE MATHEMATICS, 2024, 347 (03)
[8] Stability on Matchings in 3-Uniform Hypergraphs
Guo, Mingyang
Lu, Hongliang
GRAPHS AND COMBINATORICS, 2022, 38 (03)
[9] Stability on Matchings in 3-Uniform Hypergraphs
Mingyang Guo
Hongliang Lu
Graphs and Combinatorics, 2022, 38
[10] 3-UNIFORM HYPERGRAPHS AND LINEAR CYCLES
Ergemlidze, Beka
Gyori, Ervin
Methuku, Abhishek
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 933 - 950

← 1 2 3 4 →