AATRN Seminar: Robert Ghrist

Today, the promised AATRN seminar series got started with Robert Ghrist as the inaugural speaker. His lecture, through WebEx, builds up the cellular sheaf perspective on networks with capacity, Max Flow / Min Cut, and the work done by Ghrist, Yasu Hiraoka, and Sanjeevi Krishnan on categorifying and sheafifying MF/MC.

Among the novel insights coming from this talk even if one has been following the UPenn developments for a while was the connection to Poincare Duality: “Flow duality is a form of Poincare duality” — S. Krishnan

The approach detailed by Krishnan in his preprint (on http://www.math.upenn.edu/~sanjeevi/papers/mfmc.pdf ) encodes a flow network as a sheaf of semi-modules of capacities over a semi-ring over the directed graph of the network. Flows correspond to homology, cuts to cohomology.

MF/MC translates to:

Theorem (S. Krishnan)

Given a network X, a distinguished (virtual) edge e and a capacity sheaf F, (all) flowvalues at e of flows on F correspond to the homotopy limit over all cuts of cutvalues of cuts on F.

This approach, and connecting flows and cuts to a lattice structure on the constraints produces a setting where multi-kind flows can easily be analyzed with the same tools as ordinary flows, and where the algebra fixes the duality gaps that show up when naively searching for minima and maxima.

The talk culminated in a primer on the homology and cohomology of directed sheaves, to set us up to read Krishnan's paper, constructing compact support cohomology and Borel-Moore homology for sheaves over directed spaces.

The added abstraction levels seem to enable MF/MC theorems for, for instance, probability distributions. It also carries a promise for insights into duality gaps in MF/MC type problems.

Leave a Reply

Your email address will not be published. Required fields are marked *