User Tools

Site Tools


Jackie Kaminski (Binghamton)

Flows on Graphs, and Related Topics: I, II

Abstract for the Combinatorics Seminar 2009 May 7, 8

A flow on a graph G is an assignment of values to directed edges such that, at each vertex, the total inflow equals the total outflow. These values are taken from an abelian group A of order q, or from the integers {−q, …, q}. In each case it is known that the number of such flows is a polynomial function of q; these functions are called the flow polynomials of G.

In two new papers, Chen & Stanley take a geometric approach to new and previously known results on flow polynomials, by interpreting flows as lattice points in polytopes. One of their key geometric insights is to decompose the polytopes into orthants indexed by orientations of the graph, and use a condition on orientations that guarantees that their corresponding quadrants contain the same number of lattice points.

The authors also treat the chromatic and tension polynomials similarly.

These talks will examine their geometric approach to polynomials, and compare their approach to some previous approaches.

The talks concern parts of the following papers on counting modular and integral flows and tensions on graphs. The main focus will be on #4.

  1. Martin Kochol, “Polynomials associated with nowhere-zero flows”.

J. Combin. Theory Ser. B 84 (2002), no. 2, 260-269.

  1. Matthias Beck and Thomas Zaslavsky, “The number of nowhere-zero flows on graphs and signed graphs”.

J. Combinatorial Theory Ser. B 96 (2006), 901-918.

  1. Beifang Chen, “Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs”.


  1. Beifang Chen and Richard P. Stanley, “Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs”.


These talks will be Ms. Kaminski's doctoral candidacy exam. They are open to all interested persons. The examining committee consists of Laura Anderson, Emanuele Delucchi, and Thomas Zaslavsky (chair).

seminars/comb/abstract.200905kam.txt · Last modified: 2020/01/29 14:03 (external edit)