Polynomial Bounds for Monochromatic Tight Cycle Partition in $r$-Edge-Coloured $K_n^{(k)}$

Let $K_n^{(k)}$ be the complete $k$-graph on $n$ vertices. A $k$-uniform tight cycle is a $k$-graph with its vertices cyclically ordered so that every $k$ consecutive vertices form an edge and any two consecutive edges share exactly $k-1$ vertices. A result of Bustamante, Corsten, Frankl, Pokrovskiy and Skokan shows that all $r$-edge coloured $K_{n}^{(k)}$ can be partitioned into $c_{r, k}$ vertex disjoint monochromatic tight cycles. However, the constant $c_{r, k}$ is of tower-type. In this work, we show that $c_{r, k}$ is a polynomial in $r$.

Authors

Institutions

Publication Details

Journal
The Electronic Journal of Combinatorics
Published
2025-03-27
DOI
https://doi.org/10.37236/13343
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Polynomial Bounds for Monochromatic Tight Cycle Partition in $r$-Edge-Coloured $K_n^{(k)}$

Allan Lo, Debmalya Bandyopadhyay
The Electronic Journal of Combinatorics
Limits and Structures in Graph Theory
article

Polynomial Bounds for Monochromatic Tight Cycle Partition in $r$-Edge-Coloured $K_n^{(k)}$

Allan Lo, Debmalya Bandyopadhyay
article en

Abstract

Let $K_n^{(k)}$ be the complete $k$-graph on $n$ vertices. A $k$-uniform tight cycle is a $k$-graph with its vertices cyclically ordered so that every $k$ consecutive vertices form an edge and any two consecutive edges share exactly $k-1$ vertices. A result of Bustamante, Corsten, Frankl, Pokrovskiy and Skokan shows that all $r$-edge coloured $K_{n}^{(k)}$ can be partitioned into $c_{r, k}$ vertex disjoint monochromatic tight cycles. However, the constant $c_{r, k}$ is of tower-type. In this work, we show that $c_{r, k}$ is a polynomial in $r$.

The Electronic Journal of CombinatoricsVol. 32(1)
University of Birmingham (GB)
Openalex Percentile: Top 90%
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.