Let $G$ be a complete $k$-partite graph, where each independent set contains $kn$ vertices. We color the edges of $G$ in $k$ different colors. Determine the greatest integer $M$ satisfying the following: in any coloring of $G$, we can choose $M$ vertices and a color $C$, such that between any two of the $M$ chosen vertices, there is a monochromatic path of color $C$.
I'm actually stumped as to how to approach this. I'd appreciate any thoughts.
In this partial answer we shall show that $kn\le M\le 2kn$ and $M=kn$ provided $k$ is a prime number.
Many of the following ideas hold for the general case, so we’ll start from it. For a finite simple graph $H$ and a natural number $k$ by $M(H,k)$ we denote
the greatest integer $M$ satisfying the following: in any coloring [of edges] of $H$ [into $k$ different colors], we can choose $M$ vertices and a color $C$, such that between any two of the $M$ chosen vertices, there is a monochromatic path of color $C$.
It is easy to see that $M(H,k)$ is the minimum (taken wrt. colorings) size of a largest (taken wrt. to a fixed coloring) monochromatic connected component.
Also it is obvious that if $H’$ is a subgraph of $H$ then $M(H’,k)\le M(H,k)$ for each $k$. In particular, if $H$ has $N$ vertices, then $M(H,k)\le M(K_N,k)$, where $K_N$ is a complete graph with $N$ vertices.
Proposition 1. Let $k$ and $N\ge 2$ be natural numbers. Let $k’=k+1$, if $k$ is odd and $k’=k$, if $k$ is even. Then $M(K_N,k)\le 2\lceil N/k’\rceil$.
Proof. Put $r=\lceil N/k’\rceil$. Since $k’r\ge N$, we can cluster the vertices of the graph $K_N$ into $k’$ classes of size and most $r$. Now color edges connecting the vertices inside each of the classes into color $1$. Consider an auxiliary complete graph $K_{k’}$, whose vertices are the classes. Since the chromatic index of the graph $K_{k’}$ equals $k$, there exists its proper edge coloring into $k$ colors. Now we color edges connecting the vertices from different classes into a color of the edge connecting these classes in the graph $K_{k’}$. It is easy to check that each monochromatic connected component of $K_N$ belongs to at most two classes, so it has size at most $2r$. $\square$
The upper bound in Proposition 1 is quite tight, as shows the following
Proposition 2. Let $k$ and $N$ be natural numbers. Then $M(K_N,k)\ge (N-1)/k+1$.
Proof. Put $M=M(K_N,k)$ and fix a $k$-edge coloring such that all monochromatic connected components have size at most $M$. For a fixed color let $H_1,\dots, H_l$ be its connected components with sizes $m_1,\dots, m_l$ respectively. Then each $H_i$ has at most ${m_i\choose 2}=m_i(m_i-1)/2$ edges. Since the components are mutually disjoint, $\sum m_i\le N$. Since each of $m_i$ is at most $M$ and for each $0<m<m’<M$ hold $$m(m-1)/2+ m’(m’-1)/2<$$ $$(m-1)((m-1)-1)/2+ (m’+1)((m+1)’-1)/2,$$ we can easily show that the maximum $\mathcal M$ of the sum $\sum {m_i\choose 2}$ is attained when all (maybe, but one) non-zero $m_i’$s equal $M$. Let $N=qM+r$, where $0\le r< M$. Then
$$\mathcal M=qM(M-1)/2+r(r-1)/2=$$ $$(N-r)(M-1)/2+r(r-1)/2=$$ $$N(M-1)/2-r(M-r)/2\le$$ $$N(M-1)/2.$$
Since each of ${N\choose 2}=N(N-1)/2$ edges of $K_N$ is colored in one of $k$-colors, we have $kN(M-1)/2\ge N(N-1)/2$, which implies $M\ge (N-1)/k+1$. $\square$
Recall that $K_{\underbrace{kn,\dots,kn}_{k~\text{times}}}$. Similarly to the previous proposition we can prove the following
Proposition 3. Let $k$ and $n$ be natural numbers. Then $M(G, k)\ge kn$.
Proof. Put $M=M(G,k)$ and fix a $k$-edge coloring such that all monochromatic connected components have size at most $M$. For a fixed color let $H_1,\dots, H_l$ be its connected components with sizes $m_1,\dots, m_l$ respectively. Since each $H_i$ is $k$-partite, by Turán’s theorem it has at most $(1-1/k)m_i^2/2$ edges. Since the components are mutually disjoint, $\sum m_i\le k^2n=N$. Since each of $m_i$ is at most $M$ and for each $0<m<m’<M$ hold $$m^2+ m’^2<(m-1)^2+ (m’+1)^2,$$ we can easily show that the maximum $\mathcal M$ of the sum $\sum (1-1/k)m_i^2/2$ is attained when all (maybe, but one) non-zero $m_i’$s equal $M$.
Let $N=qM+r$, where $0\le r< M$. Then
$$\mathcal M=(1-1/k)(qM^2+r^2)/2=$$ $$(1-1/k)((N-r)M+r^2)/2=$$ $$(1-1/k)((NM-r(M-r))/2\le$$ $$(1-1/k)NM/2.$$
Since each of $(1-1/k)N^2/2$ edges of $G$ is colored in one of $k$-colors, we have $k(1-1/k)NM/2\ge (1-1/k)N^2/2$, which implies $M\ge N/k=kn$. $\square$
For prime $k$ the lower bound in Proposition 3 is tight.
Proposition 4. For each prime $k$ and natural $n$, $M(G,k)=kn$.
Proof. Since by Proposition 3 $M(G,k)\ge kn$, it suffices to present a $k$-edge coloring of $G$ with monochromatic connected components of size at most $kn$. Let $\Bbb Z_k=\Bbb Z/k\Bbb Z$ be the ring of residues modulo $k$. Since $k$ is prime, $\Bbb Z_k$ is a field. For each independent set $V_i$ of the graph $G$ cluster its vertices into $k$ classes of $n$ vertices each and enumerate the classes by pairs $(i,j)\in \Bbb Z_k\times \Bbb Z_k $. Now consider an auxiliary complete $k$-partite graph $G’=K_{\underbrace{k,\dots,k}_{k~\text{times}}}$, whose vertices are elements of $\Bbb Z_k\times \Bbb Z_k$ and two elements $(i,j)$ and $(i’,j’)$ of $G’$ are connected by an edge iff $i=i’$. Now we color edges of the graph $G’$ in $k$ colors, which are elements of $\Bbb Z_k$, as follows. For each $c\in\Bbb Z_k$ we define an equivalence relation $\sim_c$ on $\Bbb Z_k\times \Bbb Z_k $ by putting $(i,j)\sim_c (i’,j’)$ iff $j’-j=c(i’-i)$. Let $(i,j)$ and $(i’,j’)$ ($i\ne i’$) be elements from $\Bbb Z_k\times \Bbb Z_k $. There exists a unique color $c\in \Bbb Z_k$ such that $(i,j)\sim_c (i’,j’)$ (in fact, $c=(j’-j)(i’-i)^{-1}$). We color an edge connecting $(i,j)$ and $(i’,j’)$ in the color $c$. We see that each monochromatic connected components of the graph $G’$ is contained in an equivalence class of some of the relations $\sim_c$, so it has size at most $k$. Now we color edges connecting the vertices from classes $(i,j)$ and $(i’,j’)$ ($i\ne i’$) of the graph $G$ into a color of the edge connecting vertices $(i,j)$ and $(i’,j’)$ of the graph $G’$. Then each monochromatic connected components of the graph $G$ will have size at most $kn$. $\square$
