Skip to content



Enumeration of spanning subgraphs with degree constraints

Wagner, D (Waterloo)
Wednesday 23 January 2008, 14:30-15:00

Seminar Room 1, Newton Institute


For a finite (multi-) graph G=(V,E) and functions f,g: V ---> N and natural number j, consider the number of (f,g)-factors of G with exactly j edges. We investigate logarithmic concavity properties of such sequences (as j varies with f and g fixed) by considering the location of zeros of their generating functions. The case f==0 and g==1 is that of the Heilmann-Lieb theorem on matching polynomials. The more general case f<=g<=f+1 appears in earlier work of mine, and the case f==0 and g==2 was considered by Ruelle. We provide a unified approach to these cases via the half-plane property and the Grace-Walsh-Szego coincidence theorem. As a byproduct we find a "circle theorem'' for the zeros of a weighted generating function for the set of all spanning subgraphs of G.


[ppt ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧