5
$\begingroup$

The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices connected by an edge). I am interested in a related quantity. In my problem, I am given a probability distribution $P$ on the vertices of $G$ and I am interested in minimizing the (Shannon) entropy of the induced probability distribution on the colors over all proper colorings of the vertices of $G.$ Let this quantity be denoted by $\rho(G,P).$ We have trivially,

$$\rho(G,P)\leq \log_2\chi(G).$$

Note that the entropy minimizing coloring need not use the minimum possible number of colors. Eg. Consider a 6-cycle with probabilities 0.48,0.01,0.01,0.48,0.01,0.01 in that order. The three-coloring that pairs the two heavy diametrically opposite points will have a lower entropy than any two-coloring.

More generally, I want to understand what happens when one considers tensor powers of the graph. Consider the AND product of graphs where an edge exists between $(v_1,v_2)$ and $(w_1,w_2)$ if and only if there exist edges $(v_1,w_1)$ and $(v_2,w_2)$ or if $v_1=w_1$ and $(v_2,w_2)$ is an edge or if $v_2=w_2$ and $(v_1,w_1)$ is an edge. It is easy to show that the sequence $\chi(G^{\otimes n})$ is sub-multiplicative and so the limit $\lim_{n\to\infty}\chi(G^{\otimes n})^{\frac{1}{n}}$ exists (sometimes called Witsenhausen's rate of $G$). An analogous quantity for $\rho$ may be defined as below and existence of the limit follows from subadditivity again:

$$\lim_{n\to\infty} \frac{\rho(G^{\otimes n},P^{\otimes n})}{n}.$$

Note here we also take the tensor product of the specified probability distribution $P$. Do we know anything about these quantities? Any related references would be useful. Thanks!

$\endgroup$
  • $\begingroup$ Unless I am mistaken, in the definition of the product of graphs, I think that you need an edge also in the case where v_1=w_1 and (v_2,w_2) is an edge and in the case where (v_1,w_1) is an edge and v_2=w_2. Otherwise I think χ(G^⊗n) would be equal to χ(G). $\endgroup$ – Tsuyoshi Ito Oct 12 '14 at 9:53
  • $\begingroup$ I think that submultiplicativity can be shown exactly in the same way as in the case of chromatic number and that therefore the limit in question always exists…or am I missing something? $\endgroup$ – Tsuyoshi Ito Oct 12 '14 at 9:55
  • $\begingroup$ Just a clarification: Is the question asking about the limit tensor products or about minimum entropy coloring in general? Is there an easy example of a specific graph, $G$, and a distribution where a minimum entropy coloring uses more than $\chi(G)$ colors? $\endgroup$ – Pat Morin Oct 14 '14 at 3:01
  • $\begingroup$ Pat: Yes, the question is about minimum entropy coloring in general. I want to know if there is such an example. Thanks. $\endgroup$ – user7823 Oct 14 '14 at 12:56
  • $\begingroup$ Pat: I found a simple example showing the minimum entropy coloring may use more colors than the chromatic number. I included it in the question. $\endgroup$ – user7823 Oct 14 '14 at 15:08

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.