Mathematical Sciences Research Institute

Home » MSRI-UP » Schedules » Multivariate flow and tension polynomials of graphs

Multivariate flow and tension polynomials of graphs

MSRI-UP 2012: Enumerative Combinatorics June 16, 2012 - July 29, 2012

July 29, 2012 (09:00 AM PDT - 10:00 AM PDT)
Speaker(s): Alyssa Cuyjet, Gordon Kirby, Molly Stubblefield
Location: MSRI: Baker Board Room


Flows and tensions of graphs are somewhat analogous to colorings, but one labels edges. Let's be more precise.Given a graph, orient it (i.e., give each edge an orientation) in some arbitrary but fixed way. A flow is a labelling of the edgessuch that at each node v, the sum of the labels at edges pointing towards v equals the sum of the labels at edges pointing away from v.A tension is a labelling of the edges such that the sum of the labels on any cycle of the graph (taken with signs given by theorientations of the edges of the cycle) is zero.One is typically interested in nowhere-zero flows and tensions, i.e., we're not allowed to use the label 0 anywhere.Some fairly recent theorems of Kochol and Chen say that if the flow/tension labelsare integers between -k and k, the number of nowhere-zero flows/tensions is a polynomial in k.Moreover, there are interpretations of these polynomials when they are evaluated at negative integers; these are reciprocity theorems due to Beck-Zaslavsky, and Chen-Stanley.We will try to generalize these counting functions to the multivariable case, i.e., for each edge e, we are allowed to use labelsbetween -ke and ke, for some given values ke.Now the flow and tension counting functions depend on several variables ke (one for each edge of the graph). We will study these counting functions. 

Supplements No Notes/Supplements Uploaded
Video/Audio Files


Quicktime msriup20129am.mov 394 MB video/quicktime rtsp://videos.msri.org/msriup20129am/msriup20129am.mov Download
H.264 Video msriup20129am.m4v 269 MB video/mp4 rtsp://videos.msri.org/msriup20129am/msriup20129am.m4v Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath - Streaming Video page.