# CSM

## Seminar

### Enumeration of spanning subgraphs with degree constraints

Seminar Room 1, Newton Institute

#### Abstract

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.

## Comments

Start the discussion!