A flow on a graph assigns a direction to each edge e and a value phi(e) to that directed edge such that at each edge, the sum of the flow into that vertex equals the flow out of that vertex. Usually the flows are required to be integered values, but we allow real-valued flows. The goal is to get a flow where all of the values are as equal as possible. At first glance this would appear to be impossible: a vertex of odd degree cannot have the same number of edges giving a flow in than as edges giving a flow out. However, this can be roughly balanced if the indegree and the outdegree are both large. In particular, we might be possible to get the flows between 1 and 1+epsilon provided that the degrees are sufficiently large. The same type of argument applies over small edge cuts, so we want large edge connectivity.

The problem is phrased precisely as follows. An x-flow on the graph gives a direction and a flow to each edge, where the flow is at least 1 and at most x-1. So a (2+epsilon)-flow has values between 1 and 1+epsilon. The following is due to Goddyn and Seymour, and is called the (2+epsilon)-flow Conjecture.

Conjecture: For every epsilon > 0, there is a k>0 such that every k-edge-connected graph has a (2+epsilon)-flow. 

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA. (with thanks to Matt DeVos)

Send comments to dan.archdeacon@uvm.edu

December 2003.