MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It seems that there's a general way to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.

Furthermore, polynomials with subset expansion formulas often have a representation as a sum over all possible vertex labelings of some "local interactions" model.

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.

  1. Are there other interesting examples of graph polynomials with "sum over labelings" representation?

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

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

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.