# 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.

#### Video

**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.

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.