2003 Fulkerson Prize Citation
J. F. Geelen, A. M. H. Gerards, A. Kapoor,
"The Excluded Minors for GF(4)Representable Matroids",
Journal of Combinatorial Theory B 79 (2000), 247299.
Matroid representation theory studies the question of when a matroid is representable by the
columns of a matrix over some field. The matroids representable over GF(2) and GF(3) were
characterized by their excluded minors in the 1950s and the 1970s respectively. Rota then
conjectured that the matroids representable over any finite field GF(q) could be
characterized in terms of a finite list of excluded minors. For more than twenty five years,
progress on Rota's conjecture stalled. The proofs for GF(2) and GF(3) relied on the
uniqueness properties of representations over these fields, properties that do not hold for
other fields. Thus the result of Geelen, Gerards and Kapoor came as a big surprise. The
paper of Geelen, Gerards and Kapoor gives an excluded minor characterization for matroids
represented over GF(4) by working around the nonuniqueness of the representation. It has
reawakened interest in the area of matroid representation and brought renewed hope of
progress towards the solution of Rota's conjecture.
B. Guenin,
"A characterization of weakly bipartite graphs",
Journal of Combinatorial Theory B 83 (2001), 112168.
A longstanding area of interest in the field of discrete optimization is finding conditions
under which a given polyhedron has integer vertices, so that integer optimization problems
can be solved as linear programs. In the case of a particular set covering formulation for
the maximum cut problem, a graph is called weakly bipartite if the polyhedron has integer
vertices for that graph. Guenin's result gives a precise characterization of the graphs that
are weakly bipartite in terms of an excluded minor. This solves the graphical case of a
famous conjecture about ideal binary clutters made by Seymour in his 1977 Fulkerson
Prizewinning paper. Guenin's proof makes an ingenious use of a deep theorem of Lehman, also
itself a Fulkerson Prize winner. Guenin's work has motivated several remarkable subsequent
papers.
S. Iwata, L. Fleischer, and S. Fujishige,
"A combinatorial, strongly polynomialtime algorithm for minimizing submodular functions",
Journal of the ACM 48 (2001), 761777, and
A. Schrijver,
"A combinatorial algorithm minimizing submodular functions in strongly polynomial time",
Journal of Combinatorial Theory B 80 (2000), 346355.
Submodular functions provide a discrete analog of convex functions, and submodular function
minimization arises in such diverse areas as dynamic and submodular flows, facility location
problems, multiterminal source coding, and graph connectivity problems. The first
polynomialtime algorithm for submodular function minimization was given by Grötschel,
Lovász, and Schrijver in 1981; however, the algorithm relies on the ellipsoid method,
requires advance knowledge of bounds on the function values, and is not combinatorial. In
1999, the papers of Iwata, Fleischer, and Fujishige, and of Schrijver independently gave
combinatorial, strongly polynomialtime algorithms for this fundamental problem. These
results are a significant step in the history of combinatorial, strongly polynomialtime
algorithms for discrete optimization problems, and can be compared with the EdmondsKarp
algorithm for the maximum flow problem and Tardos's algorithm for the minimumcost flow
problem.
