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?

  • $\begingroup$ I should think so. Not an argument, but the following might become one. Suppose one tries to select m colors from a colored graph, say by choosing the m most popular colors. If it fails, the complement contains a connected and complete bipartite graph, which presumably has many more edges because n is so large. This should at least give bounds on n. Gerhard "Can't Count: Not Enough Coffee" Paseman, 2015.03.05 $\endgroup$ – Gerhard Paseman Mar 5 '15 at 18:04

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). $$

| cite | improve this answer | |
  • $\begingroup$ I am afraid that greedy algorithm as is does not provide any better bound, since it may easily happen that each color has about $n(1-\delta)$ components for $\delta=O(1/\sqrt{k})$: partition all vertices onto blocks of $\delta n$ vertices and for any pair of blocs A, B color all edges between A,B in a special color. $\endgroup$ – Fedor Petrov Mar 6 '15 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.