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