← All problems

Gyárfás's monochromatic tight-cycle partition conjecture

7 years old · traced to

Let kk and rr be positive integers. A kk-uniform hypergraph is a hypergraph whose edges are kk-element subsets of its vertex set, and a tight cycle is a cyclically ordered sequence of vertices in which every kk consecutive vertices form an edge; single vertices are also regarded as tight cycles. Gyárfás's conjecture. There is a constant c=c(k,r)c=c(k,r) such that the vertices of every rr-edge-coloured complete kk-uniform hypergraph can be partitioned into at most cc monochromatic tight cycles. The paper confirms this conjecture, so the asserted bounded partition exists for all positive integers kk and rr.

References

2 papers in this index state this conjecture (2017–2019). The statement above is taken from the most recent of them; the others are arXiv:1705.09370.

Source: https://arxiv.org/abs/1903.04471 Gyárfás (2016), external paper cited in the source

Status

  • Solved: Sebastián Bustamante, Jan Corsten, Nóra Frankl, Alexey Pokrovskiy and Jozef Skokan. Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles (SIAM Journal on Discrete Mathematics, 2020) https://epubs.siam.org/doi/10.1137/19M1269786

Source: Sebastián Bustamante, Jan Corsten, Nóra Frankl, Alexey Pokrovskiy and Jozef Skokan, “Partitioning edge-coloured hypergraphs into few monochromatic tight cycles”, arXiv:1903.04471 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.