Hypergraph cycle partitions

Abstract

The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ with $k \geq 2$, the vertices of every $r(k-1)$-edge-coloured countably infinite complete $k$-uniform hypergraph can be core-partitioned into at most $r$ monochromatic Berge-cycles of different colours. We further describe a construction showing that this result is best possible. The second part deals with $\ell$-cycles. We show that for all $\ell, k, n \in \N$ with $\ell \leq k/2$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete graph on $n$ vertices has at most two disjoint monochromatic $\ell$-cycles in different colours that together cover all but a constant number of vertices, where the constant depends on $k$ and $\ell$. Furthermore, we can cover all vertices with at most $4$ ($3$ if $\ell \leq k/3$) disjoint monochromatic $\ell$-cycles. The third part deals with tight-cycles in $2$-edge-colourings of complete $3$-uniform hypergraphs. We show that for every $\eta > 0$ there exists an integer $n_0$ such that every $2$-edge-colouring of the $3$-uniform complete hypergraph on $n \geq n_0$ vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most $\eta n$ vertices. Finally, the fourth part deals with tight-cycles in a more general setting. We prove that for every $k,r \in \N$, 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, confirming a conjecture of Gy\'arf\'as. We further prove that for every $r,p \in \N$, 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, D. Soukup, L. Soukup and Szentmikl\'ossy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs with bounded independence number.