On connected components with many edges

Fix a $k$-coloring $\chi$ of the edges of $K_{n}$, and suppose that the largest number of edges in a monochromatic connected component in this coloring is $z\binom{n}{2}$. Without loss of generality, let red be the color with the most edges, so there are at least $\frac{1}{k}\binom{n}{2}$ red edges in our coloring. Let $\mathcal{C}_{1}=\{R_{1},R_{2},\dots,R_{m}\}$ be the set of red components, with

$$|V(R_{1})|\geq|V(R_{2})|\geq\cdots\geq|V(R_{m})|,\qquad\sum_{i=1}^{m}|V(R_{i})|=n.$$

(3.1)

Let $x=\frac{1}{\binom{n}{2}}\sum_{i=1}^{m}|E(R_{i})|$, so $x\geq\frac{1}{k}$. By assumption, $|E(R_{i})|\leq z\binom{n}{2}$ for $1\leq i\leq m$. As in the proof of Corollary 4, applying Theorem 3 with $K_{n}$ as $G$ and its red color class (i.e. the spanning subgraph formed by its red edges) as $H$ yields a red component with at least $x^{2}\binom{n}{2}$ edges, so by assumption we have $z\geq x^{2}\geq\frac{1}{k^{2}}$. Define $\delta=k-\frac{1}{\sqrt{z}}\geq 0$, so $z=\frac{1}{(k-\delta)^{2}}$.

For any $j\in[1,m-1]$, let $G_{j}$ be the complete graph on $\bigcup_{i=j+1}^{m}V(R_{i})$, with its coloring induced by $\chi$. Applying Theorem 3 with $G_{j}$ as $G$ and the red color class of $G_{j}$ as $H$ yields a red connected component $H^{\prime}=R_{i}$ with $|E(H^{\prime})|\geq\frac{|E(H)|^{2}}{|E(G_{j})|}$. Since

$$|E(H)|=\sum_{i=j+1}^{m}|E(R_{i})|=x\binom{n}{2}-\sum_{i=1}^{j}|E(R_{i})|\geq x\binom{n}{2}-jz\binom{n}{2},$$

while $|E(G_{j})|=\binom{|V(G_{j})|}{2}=\binom{n-\sum_{i=1}^{j}|V(R_{i})|}{2}$, we have

$$z\binom{n}{2}\geq|E(H^{\prime})|\geq\frac{\max(x-jz,0)^{2}\binom{n}{2}^{2}}{\binom{n-\sum_{i=1}^{j}|V(R_{i})|}{2}}.$$

Since $\frac{\max(x-jz,0)}{\sqrt{z}}\leq\frac{x}{\sqrt{z}}\leq 1$, this implies

$$\binom{n-\sum_{i=1}^{j}|V(R_{i})|}{2}\geq\frac{\max(x-jz,0)^{2}}{z}\binom{n}{2}\geq\binom{\frac{\max(x-jz,0)}{\sqrt{z}}n}{2}.$$

Since $n-\sum_{i=1}^{j}|V(R_{i})|\geq 1$, and the function $f(X)=\binom{X}{2}$ is increasing for $X\geq 1$, this then implies

$$\sum_{i=1}^{j}|V(R_{i})|\leq(1-x/\sqrt{z}+j\sqrt{z})n\qquad\text{for all }j\in[1,m-1].$$

(3.2)

We can now give an upper bound on $\sum_{i=1}^{m}\binom{|V(R_{i})|}{2}$ by solving the corresponding convex optimization problem. The proof of the following technical lemma will be deferred until the end of the section.

Let $v_{i}=\frac{|V(R_{i})|}{n}$. Since (3.1) and (3.2) hold, we can apply Lemma 7 to obtain

$$\sum_{i=1}^{m}v_{i}^{2}\leq(1-x/\sqrt{z}+\sqrt{z})^{2}+\left(\left\lfloor\frac{x}{z}\right\rfloor-1\right)z+\left(\left(x/z-\left\lfloor\frac{x}{z}\right\rfloor\right)\sqrt{z}\right)^{2}\leq(1-x/\sqrt{z}+\sqrt{z})^{2}+(x/z-1)z,$$

so that we have

$\displaystyle\sum_{i=1}^{m}\binom{|V(R_{i})|}{2}$

$\displaystyle=\frac{n^{2}\sum_{i=1}^{m}v_{i}^{2}-n}{2}\leq\frac{n^{2}((1-x/\sqrt{z}+\sqrt{z})^{2}+(x/z-1)z)-n}{2}.$

Finally, let $G$ be the complete $m$-partite graph obtained from $K_{n}$ by removing all edges within each $V(R_{i})$, with its coloring induced by $\chi$. There are no red edges in $G$, so by the pigeonhole principle, one of the $k-1$ remaining colors has at least $\frac{1}{k-1}|E(G)|$ edges in $G$. Let $H$ be the spanning subgraph of $G$ induced by the edges in that color. Applying Theorem 3 then yields a monochromatic connected component $H^{\prime}$ with at least $\frac{1}{(k-1)^{2}}|E(G)|$ edges. Then by assumption we have

	$\displaystyle z$	$\displaystyle\geq\frac{1}{(k-1)^{2}}\frac{|E(G)|}{\binom{n}{2}}=\frac{1}{(k-1)^{2}}\left(1-\frac{\sum_{i=1}^{m}\binom{|V(R_{i})|}{2}}{\binom{n}{2}}\right)$
		$\displaystyle\geq\frac{1}{(k-1)^{2}}\left(1-\frac{n^{2}((1-x/\sqrt{z}+\sqrt{z})^{2}+(x/z-1)z)-n}{n^{2}-n}\right)$
		$\displaystyle\geq\frac{1}{(k-1)^{2}}\left(1-(1-x/\sqrt{z}+\sqrt{z})^{2}-(x/z-1)z\right),$

which rearranges to give

$$1-(k-1)^{2}z\leq(1-x/\sqrt{z}+\sqrt{z})^{2}+(x/z-1)z=\frac{1}{z}x^{2}-(1+2/\sqrt{z})x+(1+2\sqrt{z}).$$

The right hand side is a quadratic in $x$ that is decreasing for $x\leq\frac{z}{2}+\sqrt{z}$. Since by assumption $\sqrt{z}\geq x\geq\frac{1}{k}$, we then have

$$1-(k-1)^{2}z\leq\frac{1}{zk^{2}}-(1+2/\sqrt{z})\frac{1}{k}+(1+2\sqrt{z}).$$

Substituting in $z=\frac{1}{(k-\delta)^{2}}$ yields

$$1-\frac{(k-1)^{2}}{(k-\delta)^{2}}\leq\frac{(k-\delta)^{2}}{k^{2}}-\frac{1+2(k-\delta)}{k}+1+\frac{2}{k-\delta},$$

which upon rearrangement becomes

	$\displaystyle 0$	$\displaystyle\leq(k-1)^{2}k^{2}+(k-\delta)^{4}-k(k-\delta)^{2}-2(k-\delta)^{3}k+2(k-\delta)k^{2}$
		$\displaystyle=-k^{3}+k^{2}-k\delta^{2}+2k^{3}\delta-2k\delta^{3}+\delta^{4}$
		$\displaystyle=(k-\delta^{2})^{2}-k(k^{2}-\delta^{2})(1-2\delta).$

This implies

$$1-2\delta\leq\frac{(k-\delta^{2})^{2}}{k(k^{2}-\delta^{2})}<\frac{1}{k},$$

so that $\delta>\frac{k-1}{2k}$. Thus, the coloring $\chi$ contains a monochromatic connected component with at least $z\binom{n}{2}$ edges, where

$$z=\frac{1}{(k-\delta)^{2}}>\frac{1}{(k-\frac{1}{2}+\frac{1}{2k})^{2}}\geq\frac{1}{k^{2}-k+\frac{1}{4}+1-\frac{1}{4k}+\frac{1}{4k^{2}}}\geq\frac{1}{k^{2}-k+\frac{5}{4}},$$

as desired. ∎

Since the feasible region is compact, there exists a choice of the $v_{i}$ such that the desired maximum is attained. Fix such a maximizing choice of the $v_{i}$. For $j\in[m]$, let $A_{j}$ denote the given constraint on $\sum_{i=1}^{j}v_{i}$, and let $S$ be the set of $j$ for which equality holds in $A_{j}$. Let $m^{\prime}=\lfloor\frac{x}{z}\rfloor$. Since $\sum_{i=1}^{m}v_{i}=1$, the constraints $A_{j}$ for $j>m^{\prime}$ cannot be tight, so $S\subseteq[m^{\prime}]$. For any $i<j$ and any $\varepsilon\in(0,v_{j}]$, replacing $(v_{i},v_{j})$ with $(v_{i}+\varepsilon,v_{j}-\varepsilon)$ increases the value of $\sum_{i=1}^{m}v_{i}^{2}$, so by maximality, no such “smoothing” operation is possible. That is, we can assume the following equality condition for all $(i,j)$ with $i<j$: Either $v_{i}=v_{i-1}$, or $v_{j}=v_{j+1}$, or $S\cap[i,j-1]\neq\emptyset$. If $S=[m^{\prime}]$, then we are in exactly the maximizing case described (since by the equality conditions for $(m^{\prime}+1,i)$ we have $v_{i}=0$ for all $i\geq m^{\prime}+2$), so assume otherwise.

First, suppose there is some $i_{0}\in[m^{\prime}]$ such that $v_{i_{0}}<\sqrt{z}$, and pick the smallest such index $i_{0}$. Let $i_{1}\in[m]$ be the largest index such that $v_{i_{1}}>0$, and note that $i_{1}>i_{0}$ since $\sum_{i=1}^{i_{0}}v_{i}<1$. Then we have $v_{i_{0}}<v_{i_{0}-1}$ and $v_{i_{1}}>v_{i_{1}+1}$. But as $\sum_{i=1}^{j}v_{i}\leq(1-x/\sqrt{z}+(j-1)\sqrt{z})+v_{j}<(1-x/\sqrt{z}+(j-1)\sqrt{z})+\sqrt{z}$ for any $j\geq i_{0}$, we have $S\cap[i_{0},i_{1}]=\emptyset$, contradicting the equality condition for $(i_{0},i_{1})$. So, we can assume $v_{i}\geq\sqrt{z}$ for all $i\leq m^{\prime}$. In particular, if $j\in S$ for some $j\in[m^{\prime}]$, then we recursively obtain $v_{i}=\sqrt{z}$ for all $i\in[j+1,m^{\prime}]$, so $[j,m^{\prime}]\subseteq S$.

Thus, we can assume $1\notin S$, i.e. $v_{1}<1-x/\sqrt{z}+\sqrt{z}$. By the equality condition for $(1,2)$, we must then have $v_{2}=v_{3}$. Let $j_{0}\geq 3$ be the smallest index such that $v_{j_{0}+1}\neq v_{j_{0}}$. By the equality condition for $(1,j_{0})$, there is some $j_{1}\in S\cap[2,j_{0}-1]$. Then

$$1-x/\sqrt{z}+j_{1}\sqrt{z}=\sum_{i=1}^{j_{1}}v_{i}=v_{1}+(j_{1}-1)v_{2}<1-x/\sqrt{z}+\sqrt{z}+(j_{1}-1)v_{2},$$

which implies $v_{2}>\sqrt{z}$. But then $\sum_{i=1}^{j_{1}+1}v_{i}=1-x/\sqrt{z}+\sqrt{z}+j_{1}v_{2}>1-x/\sqrt{z}+(j_{1}+1)\sqrt{z}$, violating $A_{j_{1}+1}$. This is a contradiction, so in fact $S=[m^{\prime}]$, and we are in the desired maximizing case. ∎

Fix a $k$-coloring of $E(K_{n})$. As in [1], we can remove from each color class a forest that meets all odd degree vertices, leaving a coloring where every color class, and hence every monochromatic connected component, is Eulerian. Let $\chi$ be the resulting partial $k$-coloring of $E(K_{n})$, where the (at most $kn$) removed edges are left uncolored, and let $z\binom{n}{2}$ be the largest number of edges in a monochromatic component in this coloring. It suffices to show that $z\geq\frac{1}{k^{2}-k+\frac{5}{4}}+O_{k}(n^{-1})$, since every monochromatic component is Eulerian, and thus contains an Eulerian circuit. Fix a color (say, red) with $x\binom{n}{2}$ edges, where $x\geq\frac{1}{k}\frac{\binom{n}{2}-nk}{\binom{n}{2}}=\frac{1}{k}-\frac{2}{n-1}$. As before, applying Theorem 3 with $G=K_{n}$ immediately yields $z\geq x^{2}\geq\frac{1}{k^{2}}-O(n^{-1})$. Note that this means there is a monochromatic circuit with at least $\left(\frac{1}{k^{2}}-O(n^{-1})\right)\binom{n}{2}=\frac{1}{k^{2}}\binom{n}{2}+O(n)$ edges.

To improve this lower bound further, we proceed as in the proof of Theorem 1. Letting $R_{1},\dots,R_{m}$ be the red components, such that (3.1) holds, we obtain (3.2) in the same manner as before, so we can once again apply Lemma 7 to obtain the same upper bound on $\sum_{i=1}^{m}\binom{|V(R_{i})|}{2}$ in terms of $x$ and $z$. Let $G$ be the complete $m$-partite graph with parts $V(R_{1}),\dots,V(R_{m})$, with its partial coloring induced by $\chi$. Since $G$ has no red edges, and at most $kn$ edges are uncolored, one of its color classes $H$ has at least $\frac{1}{k-1}(|E(G)|-kn)=\left(\frac{1}{k-1}-O_{k}(n^{-1})\right)|E(G)|$ edges. Applying Theorem 3 as before yields

	$\displaystyle z$	$\displaystyle\geq\left(\frac{1}{k-1}-O_{k}(n^{-1})\right)^{2}\frac{|E(G)|}{\binom{n}{2}}\geq\left(\frac{1}{(k-1)^{2}}-O_{k}(n^{-1})\right)\left(1-\frac{\sum_{i=1}^{m}\binom{|V(R_{i})|}{2}}{\binom{n}{2}}\right)$
		$\displaystyle\geq\left(\frac{1}{(k-1)^{2}+O_{k}(n^{-1})}\right)\left(1-(1-x/\sqrt{z}+\sqrt{z})^{2}-(x/z-1)z\right).$

Letting $z=\frac{1}{(k-\delta)^{2}}$ and noting that $x\geq\frac{1}{k}-O(n^{-1})$, we can perform the same rearrangements and substitutions as in the proof of Theorem 1, simply separating out the $O_{k}(n^{-1})$ terms at each step, to derive the inequality $1-2\delta<\frac{1}{k}+O_{k}(n^{-1})$, and thus

$$z\geq\frac{1}{k^{2}-k+\frac{5}{4}-O_{k}(n^{-1})}=\frac{1}{k^{2}-k+\frac{5}{4}}+O_{k}(n^{-1}).$$

Then the coloring $\chi$ contains a monochromatic connected component, and hence a monochromatic Eulerian circuit, with at least $z\binom{n}{2}\geq\frac{1}{k^{2}-k+\frac{5}{4}}\binom{n}{2}+O_{k}(n)$ edges, as claimed. ∎