Cycle decompositions in 3-uniform hypergraphs

Simón Piga; Nicolás Sanhueza-Matamala

doi:10.48550/arXiv.2101.12205

Cycle decompositions in 3-uniform hypergraphs

Simón Piga
, Nicolás Sanhueza-Matamala

Mathematics

Research output: Working paper/Preprint › Preprint

184 Downloads (Pure)

Abstract

We show that 3-graphs on n vertices 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, Kühn, and Osthus.

Original language	English
Publisher	arXiv
Pages	1-29
Number of pages	29
DOIs	https://doi.org/10.48550/arXiv.2101.12205
Publication status	Published - 31 Jan 2021

Bibliographical note

28 pages, fixed small errors in references and compilation

Keywords

math.CO
05C65, 05C45, 05C70

Access to Document

10.48550/arXiv.2101.12205Licence: Other (please provide link to licence statement

PigaS2021CycleOther version, 730 KBLicence: Other (please provide link to licence statement

Cite this

@techreport{070db888b8104a70ab3fbeaa8f12927c,

title = "Cycle decompositions in 3-uniform hypergraphs",

abstract = "We show that 3-graphs on n vertices 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, K{\"u}hn, and Osthus.",

keywords = "math.CO, 05C65, 05C45, 05C70",

author = "Sim{\'o}n Piga and Nicol{\'a}s Sanhueza-Matamala",

note = "28 pages, fixed small errors in references and compilation",

year = "2021",

month = jan,

day = "31",

doi = "10.48550/arXiv.2101.12205",

language = "English",

pages = "1--29",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Cycle decompositions in 3-uniform hypergraphs

AU - Piga, Simón

AU - Sanhueza-Matamala, Nicolás

N1 - 28 pages, fixed small errors in references and compilation

PY - 2021/1/31

Y1 - 2021/1/31

N2 - We show that 3-graphs on n vertices 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, Kühn, and Osthus.

AB - We show that 3-graphs on n vertices 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, Kühn, and Osthus.

KW - math.CO

KW - 05C65, 05C45, 05C70

UR - https://www.scopus.com/pages/publications/85101811770

U2 - 10.48550/arXiv.2101.12205

DO - 10.48550/arXiv.2101.12205

M3 - Preprint

SP - 1

EP - 29

BT - Cycle decompositions in 3-uniform hypergraphs

PB - arXiv

ER -

Cycle decompositions in 3-uniform hypergraphs

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this