Monochromatic cycle partitions

Abstract

The first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ vertices of the graph. In the same situation, 18 disjoint monochromatic cycles together cover all vertices. Next we show that given any $2$-local edge-colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most $3$ disjoint monochromatic paths. And, we can cover all vertices of any complete or balanced complete bipartite $r$-locally edge-coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path: Every $2$-local edge-colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices. Finally, we prove that any edge-colouring in red and blue of a graph on $n$ vertices and of minimum degree $2n/3 + o(n)$ admits a partition into three monochromatic cycles. This confirms a conjecture of Pokrovskiy approximately. The second part of this thesis contains two independent results about (proper) edge-colouring and parameter estimation respectively. With regards to edge-colouring, we conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. Concerning parameter estimation we study, for any fixed monotone graph property $\mathcal{P}=\text{Forb}(\mathcal{\mathcal{F}})$, the sample complexity of estimating a bounded graph parameter $z_{\mathcal{\mathcal{F}}}$ that, for an input graph $G$, counts the number of {spanning} subgraphs of $G$ that satisfy $\mathcal{P}$. Using a new notion of vertex partitions, we improve upon previous upper bounds on the sample complexity of estimating $z_{\mathcal{\mathcal{F}}}$.