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.
