Grant: Discovery Grants Program - Individual

In the everyday world, the concept of a graph has seen an increasing number of applications, as for example in computer and transportation networks. Of central importance to graph theory and many of its applications is the concept of a cycle. Many algorithms and methods rely heavily on its properties, and much more needs to be discovered in order to shed some light on some of the fundamental problems of combinatorics. As one example, a famous problem known as the ""travelling salesman problem,"" asks one to find a ""shortest"" route for a salesman, starting from home, to visit several cities once, and return home. In combinatorics, problems of this type are modelled by cycles in a graph. While finding a ""good algorithm"" for a problem like this is unlikely, research on cycles may yield much improved methods. Cycles in graphs are connected with the abstract notion of dependence, a concept found in numerous branches of mathematics. In the 1930s, the American mathematician Hassler Whitney invented the concept of a matroid. Whitney showed that various diverse mathematical objects, both combinatorial and otherwise, have certain common traits, and these traits can be elegantly described in terms of a matroid. Since this time, the study of matroids has evolved into an important theory which has numerous applications, as for example in operations research. Graph theory and cycles lie at the very heart of matroids, and there is a lively interplay between the two. One of the early and distinguished pioneers of matroid theory, W. Tutte, once wrote ""If a theorem about graphs can be expressed in terms of edges and circuits only it probably exemplifies a more general theorem about matroids."" In recent years, there has been a rising interest in the connection between graphs and matroids. My research seeks to deepen this connection and show that graphs play a much bigger role in matroid theory than was previously thought.