Research papers by two University of Waterloo faculty members, Jim Geelen and Bertrand Guenin, have been awarded prestigious Fulkerson Prizes.
The Fulkerson Prize, for outstanding papers in the area of discrete mathematics, is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society. Up to three awards are presented at each (triennial) International Symposium on Mathematical Programming. Three winners were announced at the 2003 Symposium in August in Copenhagen.
J. F. Geelen, A. M. H. Gerards, A. Kapoor, "The Excluded Minors for GF(4)-Representable Matroids", Journal of Combinatorial Theory B 79 (2000), 247-299.
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 non-uniqueness 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), 112-168.
A long-standing 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 Prize-winning 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.