On connected components with many edges

Abstract

We prove that if $H$ is a subgraph of a complete multipartite graph $G$, then $H$ contains a connected component $H^{\prime }$ satisfying $|E(H^{\prime })||E(G)|\ge |E(H){|}^2$. We use this to prove that every three-coloring of the edges of a complete graph contains a monochromatic connected subgraph with at least $1/6$ of the edges. We further show that such a coloring has a monochromatic circuit with a fraction $1/6-o(1)$ of the edges. This verifies a conjecture of Conlon and Tyomkyn. Moreover, for general $k$, we show that every $k$-coloring of the edges of $K_n$ contains a monochromatic connected subgraph with at least $\frac{1}{k^2-k+\frac{5}{4}}\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges.

arXiv comment12 pages, 2 figures; replaced with version revised according to reviewers' feedback. Includes a significantly improved lower bound for the case of a general number of colors

References in corpus (1)

• Ramsey Numbers of Trails