Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles
Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles
复制标题
将边缘彩色超图划分为几个单色紧循环
DOI：
--
复制
发表时间：
2019
影响因子：
0.8
通讯作者：
J. Skokan
中科院分区：
文献类型：
--
作者：
Sebastián Bustamante;Jan Corsten;Nóra Frankl;A. Pokrovskiy;J. Skokan
证实了Gya fas的一个猜想，证明了对于所有自然数k和r，每个r边色的完全k一致超图的顶点都可以分成一个有界数(与超图的大小无关)的单色紧圈.进一步证明了对于所有的自然数p和r，每个r边色完全图的顶点都可以分成有限数目的p次圈，从而解决了Elekes，Soukup，Soukup和Szentmiklossy问题。事实上，我们证明了这两个定理的共同推广，从而进一步将这些结果推广到所有有界独立数的宿主超图。
Confirming a conjecture of Gyarfas, we prove that, for all natural numbers k and r, the vertices of every r-edge-coloured complete k-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles. We further prove that, for all natural numbers p and r , the vertices of every r -edge-coloured complete graph can be partitioned into a bounded number of p-th powers of cycles, settling a problem of Elekes, Soukup, Soukup and Szentmiklossy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs of bounded independence number.