most recent 30 from http://mathoverflow.net 2013-05-23T16:56:21Z http://mathoverflow.net/feeds/question/46708 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46708/sum-over-labelings-representations-of-graph-polynomials Yaroslav Bulatov 2010-11-20T03:33:00Z 2010-11-23T02:53:57Z

<p>It seems that there's a general <a href="http://arxiv.org/abs/0812.1364" rel="nofollow">way</a> to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.</p> <p>Furthermore, polynomials with subset expansion formulas often have a representation as a sum over all possible vertex labelings of some "local interactions" model.</p> <p>For instance, generating function for Eulerian subgraphs becomes Ising model partition function, generating function of independent sets becomes partition function of the hard-core model and Potts model has both "sum over labelings" and "sum over subgraphs" representation.</p> <ol> <li><p>Are there other interesting examples of graph polynomials with "sum over labelings" representation?</p></li> <li><p>When is it possible to get this representation of a graph polynomial? More specifically, to represent it as a sum over labelings of some quantity that is a product of functions each depending only on the variables corresponding to some edge of the graph. IE, if a graph has edges (1,2),(2,3) the term being summed over has to factor into f(x1,x2)*g(x2,x3)</p></li> </ol> <p>Motivation: there's a general algorithm to efficiently compute "sum over labelings" for functions decomposing over graph or hyper-graph of bounded tree-width, and it's interesting to see which graph polynomials I can use it for</p>