I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof.

Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \dots, n$, and let $V = V_1 \cup \dots \cup V_n$ be the corresponding partition of the vertices. Let $\mu$ be a weighting on the vertices such that each color has total weight $\mu(V_j) = 1$. Suppose $\delta>0$ is such that:

  • every vertex $v$ has weight $\mu(v) \le \delta$;
  • if $v$ has color $i$ then for every color $j>i$, the total weight of vertices of color $j$ adjacent to $v$ is at most $(1+\delta)\mu(v)$.
Then, for every probability vector $t = (t_1, \dots, t_n)$, we can find a nonnegative weighting $\mu_t \le \mu$, depending continuously on $t$, such that the following properties are satisfied:
  • The support of $\mu_t$ is totally disconnected, that is, no edge of $G$ joins two vertices of positive $\mu_t$-weight.
  • If $P_t$ denotes the set of the vertices $v$ such that $\mu_t(v) = \mu(v)$, then for each color $i$ we have $$t_i - C \delta \le \mu(V_i\cap P_t) \le t_i,$$
  • where $C>0$ is a constant (say, $C=10$).

Here's a sketch of proof: We order the vertices in a way compatible with the color ordering. Given $t=(t_1,\dots,t_n)$, let's define $\mu_t$. We distribute the mass $t_1$ among the vertices of color 1, starting from the "lower" vertices. Then we distribute the mass $t_2$ among the vertices of color 2 that are not adjacent to the already charged vertices of color 1. (The $1+\delta$ condition guarantees that not much of the weight $t_2$ will be wasted.) And so on... except that extra care is needed so to assure continuity of $\mu_t$ with respect to $t$. Some bookkeeping is needed to avoid, say, charging much a 2-colored vertex adjacent to a 1-colored one which is "about to" be charged. So the proof gets pretty messy. It is possible to write an "algorithmic" proof, but then it becomes a nightmare to read.

Question. Is there a clean proof for this lemma? Maybe an extremely clever formula? Alternatively (wishful thinking), is there a known reference?


Your Answer

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

Browse other questions tagged or ask your own question.