Enumeration of spanning subgraphs with degree constraints

33 mins 50 secs, 468.24 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Wagner, D (Waterloo) Wednesday 23 January 2008, 14:30-15:00 Zeros of Graph Polynomials

Created:

2008-02-07 08:21

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Wagner, D

Language:

eng (English)

Credits:

Author:	Wagner, D
Producer:	Steve Greenham


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.

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	468.24 MB	View	Download
Flash Video	480x360	805.86 kbits/sec	200.29 MB	View	Download
iPod Video	480x360	505.27 kbits/sec	125.58 MB	View	Download
Windows Media Video (for download)	480x360	477.12 kbits/sec	118.58 MB	View	Download
Windows Media Video (for streaming)	480x360	439.77 kbits/sec	109.30 MB	View	Download	Stream
RealMedia	480x360	878.67 kbits/sec	218.38 MB	View	Download	Stream
QuickTime (for download)	384x288	848.39 kbits/sec	210.85 MB	View	Download
QuickTime (for streaming)	480x360	906.71 kbits/sec	225.35 MB	View	Download
MP3	44100 Hz	125.03 kbits/sec	30.86 MB	Listen	Download