Matroid Theory: Mathematician Solves 40-Year-Old Problem

Aug. 28, 2013 — A team of mathematicians
has solved a problem first posed more than 40
years ago that has confounded modern
mathematicians, until now.
Professor Jim Geelen of the University of
Waterloo and his colleagues, Professor Bert
Gerards of Centrum Wiskunde & Informatica
and the University of Maastricht in the
Netherlands, and Professor Geoff Whittle of
Victoria University of Wellington in New
Zealand have proved the famous Rota's
Conjecture.

The three men worked for almost 15 years to
solve this problem posed by the famous
mathematician and philosopher Gian-Carlo
Rota in 1970. Earlier this year, in Waterloo,
the trio completed the final step in their epic
project.
Rota's Conjecture relates to a specialized area
of mathematics known as matroid theory, a
modern form of geometry, which was
pioneered by the mathematician Bill Tutte.
The theory investigates the embedding of
abstract geometric structures, or matroids,
into concrete geometric frameworks - namely,
projective geometries over a given finite field.

The conjecture is that, for each finite field,
there is a finite set of obstructions preventing
such a realization. The conjecture was posed by
Rota at the International Congress of
Mathematics in 1970, serendipitously, one
week before Geelen was born.
"For me the most rewarding part of the
research project has been the collaboration
with Bert and Geoff. We work together about
three times a year typically for periods of
three weeks either here in Waterloo or in New
Zealand or the Netherlands," said Professor
Geelen. "Those visits are intense; we sit in a
room together, all day every day, in front of a
whiteboard. The discussion can be very lively
at times, while at other times, when we are
stuck, we might sit there for two hours without
saying a word; each just thinking about ways
to overcome the particular obstacle."
In 1999, Geelen, Gerards and Whittle joined
forces to work on Rota's Conjecture as well as
generalizing the famous Graph Minor Theory
developed by Robertson and Seymour to
matroids.

Last year they completed their Matroid Minor
Theory which gives deep insights into the
structure of matroids. The proof of Rota's
Conjecture relies on the full power of that
theory and, in addition, required
groundbreaking new results on matroid
connectivity.

According to the trio, the real hard work only
just began when early this year they started
writing up the results of their work. The Graph
Minors Theory itself filled more than 600
journal pages and the Matroid Minors Theory
is set to be at least as long. The team expects
that it will take them at least three years to
complete the writing.
Jim Geelen is a Professor in the Department of
Combinatorics and Optimization at the
University of Waterloo and holds a Canada
Research Chair.

Story Source:

The above story is based on materials provided
by University of Waterloo .

And ( science daily magazine ).