Correlation in graph coloring - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T07:50:47Z http://mathoverflow.net/feeds/question/35430 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35430/correlation-in-graph-coloring Correlation in graph coloring fkenter 2010-08-13T03:30:55Z 2010-08-13T09:39:59Z <p>Let $G$ be a (simple) graph.</p> <p>Given $k \ge \chi(G)$, define $Cor(G,k,u,v)$ to be the proportion among all $k$-colorings of $G$ for which the vertices $u$ and $v$ have the same color. </p> <p>Questions:</p> <p>Question 1. Given a graph $G$ and a positive integer $k \ge \chi(G)$, is there a better-than-greedy way to calculate $Cor(G,k,u,v)$?</p> <p>I suspect the answer to this question is "Yes, but not really."; for is there was an efficient way to calculate $Cor$, we would probably get $P=NP$.</p> <p>Question 2. If not, is there a good'' way to estimate it?</p> <p>Question 3. Is there any other information (e.g., the chromatic polynomial, etc.) that would yield an efficient way to calculate $Cor$?</p> http://mathoverflow.net/questions/35430/correlation-in-graph-coloring/35431#35431 Answer by Tracy Hall for Correlation in graph coloring Tracy Hall 2010-08-13T04:08:50Z 2010-08-13T04:08:50Z <p>As regards question 3: Chromatic polynomials provide the answer quite directly--but calculating them is anything but efficient.</p> <p>Naturally if $u$ and $v$ are joined by an edge, the proportion you are asking about is 0. If they are not adjacent, then let $q$ be the chromatic polynomial of $G$ and $p$ be the chromatic polynomial of $G/\{u,v\}$, i.e. the result of identifying $u$ and $v$. The proportion you seek is then the rational function $p/q$ evaluated at $k$, which as you point out is only defined for $k$ at least the chromatic number.</p> http://mathoverflow.net/questions/35430/correlation-in-graph-coloring/35433#35433 Answer by Yaroslav Bulatov for Correlation in graph coloring Yaroslav Bulatov 2010-08-13T05:06:58Z 2010-08-13T05:06:58Z <p>Question 1. Yes, efficient algorithm for Cor exists for graphs of low tree-width</p> <p>Cast this in the framework of probabilistic graphical models and then use the junction tree algorithm, which scales exponentially in tree-width of the graph.</p> <p>In particular, let $G$ be a graph over $n$ vertices with edges $E$. Let $x \in [1,2,\ldots, k]^n$. Define probability distribution over $x$ as follows</p> <p>$$p(x)=\exp{(\sum_{(ij)\in E} \mathbf{I}(x_i\ne x_j))}/Z$$</p> <p>Where $Z$ is a constant chosen to make this a valid probability distribution. Then $$\text{Cor}(G,k,u,v)=\sum_{c=1}^k p(x_u=c,x_v=c)$$</p> <p>Computing p in the formula above in graphs that are not trees is not trivial, but can be done efficiently if the tree-width is low, look at page 370 of Koller's "Probabilistic Graphical Models" for details on that particular form of query.</p> <p>Question 2. Yes, for graphs with low degree or large number of colors. For instance, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.7388" rel="nofollow">here</a> the authors conjecture that colorings on graphs with degree at most k and at least k+1 number of colors exhibits "strong spatial mixing", which would imply that the algorithm they give to approximate the marginals could also give a guaranteed approximation to your problem in polynomial time</p>