Edges of $K_n$ are colored, connected few-colored subgraph is needed

Question

Assume that all edges of a complete graph $K_n$ are colored in $k$ colors. We want to choose $m$ colors so that the graph formed by edges of chosen colors is connected. It is always possible if $m\geq k/2$ (partition all colors onto two groups of at most $m$ colors, it is impossible that both groups form disconnected graph). If $k=2m+1$ this is already not always possible for large enough $n$. Namely, if $n=\binom{2m+1}{m}$ it may appear that for any $m$-subset $I$ of colors there exists a vertex $v_I$ such that no edge ended in $v$ has color from $I$. The specific question is do we really need such a large $n$? Say, if $n$ grows in $m$ subexponentially, may we choose $m$ colors which form a connected subgraph?

Answer 1

Well, the argument below proves much weaker statement that you've asked for: if $n$ is subexponential in $\sqrt{m}$ (more precisely -if I'm not mistaken,- if $n<\exp(c m/\sqrt{k})$, where $c$ is a constant). But it is clearly suboptimal, so quite probably one can improve it.

The idea is to use a greedy algorithm. That is, assume that you are in a situation $(n,k,m)$, find a color that minimizes the number $n'$ of connected components using this color only. Pick this color and consider the connected components as new vertices (for instance, picking a vertex in each component and forgetting the rest); then, you are in a situation $(n',k-1,m-1)$. Now, if the passage from $n$ to $n'$ reduces the number of vertices sufficiently fast, you will be done (even though the $m-1:k-1$ ratio becomes less and less favorable).

Next remark is that if you pick a color at random, the mean size of a connected component of a given vertex is sufficiently large: it is at least $1+\frac{n-1}{k}$, as this is the expectation of the size of the radius one neighborhood. And, if $n$ is large, it is a lot. So the least possible $n'$ should be noticeably smaller, than~$n$.

If one can get the $n'<0.99n$ in the above argument (say, assuming $m>k/10$), that would lead to a positive answer to your initial question. The argument below leads to a weaker statement. That is: average size of the connected component of a given vertex is $1+\frac{n-1}{k}$. Hence, the sum of all such sizes over all the vertices, in average, is at least $n(1+\frac{n-1}{k})$. Hence, there exists a color, for which such a sum is at least $n(1+\frac{n-1}{k})$. On the other hand, this sum equals to $\sum s_i^2$, where $s_i$ are the sizes of the connected components (each component is counted as many times, as is its size). Hence, we have $$ \sum_i s_i^2 \ge n\left(1+\frac{n-1}{k}\right). $$ Let $n'$ be the number of connected components, and denote $\delta:=n-n'+1$. For a given $n'=n-(\delta-1)$ of positive integer summands $s_i$ with $\sum s_i=n$, the sum $\sum_i s_i^2$ is maximized if all of the components but one consist of one vertex, and the last one consists of $\delta$ vertices. In this case, this sum is equal to $\delta^2+(n-\delta)\cdot 1^2$. Hence, $$ n-\delta+ \delta^2\ge n+ \frac{n(n-1)}{k}, $$ and thus $$ \delta(\delta-1)\ge \frac{n(n-1)}{k}. $$

This leads to $\delta\ge \frac{n}{\sqrt{k}}$, and hence $$ n'= n-(\delta-1) = n\left(1-\frac{1}{\sqrt{k}}+\frac{1}{n}\right). $$

Well, the $1/n$ in the right hand side is almost neglectable, and taking $m$ iterations will reduce to $1$ the number of connected components, if we start with at most $$ \sim \exp \left(\sum_{j=k-m+1}^k \frac{1}{\sqrt{j}}\right)\ge \exp \left(\frac{m}{\sqrt{k}}\right). $$