Cycle decompositions in k-uniform hypergraphs

Allan Lo; Simon Piga; Nicolas Sanhueza Matamala

doi:10.1016/j.jctb.2024.02.003

Cycle decompositions in k-uniform hypergraphs

Allan Lo, Simon Piga, Nicolas Sanhueza Matamala

Mathematics

Research output: Contribution to journal › Article › peer-review

13 Downloads (Pure)

Abstract

We show that k-uniform hypergraphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles, subject to the trivial divisibility conditions. As a corollary, we show those graphs contain tight Euler tours as well. In passing, we also investigate decompositions into tight paths.

In addition, we also prove an alternative condition for building absorbers for edge-decompositions of arbitrary k-uniform hypergraphs, which should be of independent interest.

Original language	English
Pages (from-to)	55-103
Number of pages	49
Journal	Journal of Combinatorial Theory. Series B
Volume	167
Early online date	5 Mar 2024
DOIs	https://doi.org/10.1016/j.jctb.2024.02.003
Publication status	E-pub ahead of print - 5 Mar 2024

Bibliographical note

Funding:
The research leading to these results was supported by ANID-Chile through the FONDECYT Iniciación Nº11220269 grant (N. Sanhueza-Matamala) and EPSRC, grant no. EP/V002279/1 (A. Lo and S. Piga) and EP/V048287/1 (A. Lo). There are no additional data beyond that contained within the main manuscript.

Keywords

Hypergraphs
Euler tours
Cycles

Access to Document

10.1016/j.jctb.2024.02.003Licence: Creative Commons: Attribution (CC BY)

LoA2024CycleFinal published version, 826 KBLicence: Creative Commons: Attribution (CC BY)

1 Finished
1 Active

Ramsey theory: an extremal perspective
Treglown, A. & Lo, A.
Engineering & Physical Science Research Council
1/01/22 → 31/12/24
Project: Research Councils
Matchings and tilings in graphs
Lo, A. & Treglown, A.
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils

Cite this

@article{795ac32a9b9645499ec0a66e2b1ad8df,

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

abstract = "We show that k-uniform hypergraphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles, subject to the trivial divisibility conditions. As a corollary, we show those graphs contain tight Euler tours as well. In passing, we also investigate decompositions into tight paths.In addition, we also prove an alternative condition for building absorbers for edge-decompositions of arbitrary k-uniform hypergraphs, which should be of independent interest. ",

keywords = "Hypergraphs, Euler tours, Cycles",

author = "Allan Lo and Simon Piga and {Sanhueza Matamala}, Nicolas",

note = "Funding: The research leading to these results was supported by ANID-Chile through the FONDECYT Iniciaci{\'o}n Nº11220269 grant (N. Sanhueza-Matamala) and EPSRC, grant no. EP/V002279/1 (A. Lo and S. Piga) and EP/V048287/1 (A. Lo). There are no additional data beyond that contained within the main manuscript.",

year = "2024",

month = mar,

day = "5",

doi = "10.1016/j.jctb.2024.02.003",

language = "English",

volume = "167",

pages = "55--103",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Cycle decompositions in k-uniform hypergraphs

AU - Lo, Allan

AU - Piga, Simon

AU - Sanhueza Matamala, Nicolas

N1 - Funding: The research leading to these results was supported by ANID-Chile through the FONDECYT Iniciación Nº11220269 grant (N. Sanhueza-Matamala) and EPSRC, grant no. EP/V002279/1 (A. Lo and S. Piga) and EP/V048287/1 (A. Lo). There are no additional data beyond that contained within the main manuscript.

PY - 2024/3/5

Y1 - 2024/3/5

N2 - We show that k-uniform hypergraphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles, subject to the trivial divisibility conditions. As a corollary, we show those graphs contain tight Euler tours as well. In passing, we also investigate decompositions into tight paths.In addition, we also prove an alternative condition for building absorbers for edge-decompositions of arbitrary k-uniform hypergraphs, which should be of independent interest.

AB - We show that k-uniform hypergraphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles, subject to the trivial divisibility conditions. As a corollary, we show those graphs contain tight Euler tours as well. In passing, we also investigate decompositions into tight paths.In addition, we also prove an alternative condition for building absorbers for edge-decompositions of arbitrary k-uniform hypergraphs, which should be of independent interest.

KW - Hypergraphs

KW - Euler tours

KW - Cycles

U2 - 10.1016/j.jctb.2024.02.003

DO - 10.1016/j.jctb.2024.02.003

M3 - Article

SN - 0095-8956

VL - 167

SP - 55

EP - 103

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Cycle decompositions in k-uniform hypergraphs

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Projects

Ramsey theory: an extremal perspective

Matchings and tilings in graphs

Cite this