Grant: Discovery Grants Program - Individual
University of Ottawa
$12,000.00
Graphs and matroids
FY 2010-11
Summary
This research proposal centres on structure in graphs and matroids.
A graph is a set of objects called vertices, some of which are connected by edges. Examples of
things that are modelled by graphs include computer networks and airline routes. Less obvious
examples are scheduling problems and efficient testing suites for large-scale computer systems.
My research focuses on the interaction between the algebraic and structural aspects of graphs.
Partition graphs are related to applications in testing suites. They also connect with deep
mathematical problems: finding the maximum clique in these graphs corresponds to determining
for which orders projective planes exist. They are a class of graphs for which eigenspaces
give us a lot of information. These graphs, and many others, can be usefully analyzed
algebraically: there is a close relationship between eigenspaces and structure. This has
applications in covering arrays and coding theory.
Matroids can be thought of as a generalization of graphs and matrices, but they are
fundamentally a geometrical class of objects. Many theoretical results in graph
theory or linear algebra are in fact theorems about matroids in general. More concretely, they
are useful in combinatorial optimization, since they optimization problems can be solved
efficiently when their feasible sets form a matroid. I am interested in problems of typical
structure in matroids.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
372083-2010
Name nom
Newman, Michael
Department département
Mathematics and Statistics
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2010
Award amount
12000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Graphs and matroids
Keyword
NSERC
Application summary
This research proposal centres on structure in graphs and matroids.
A graph is a set of objects called vertices, some of which are connected by edges. Examples of
things that are modelled by graphs include computer networks and airline routes. Less obvious
examples are scheduling problems and efficient testing suites for large-scale computer systems.
My research focuses on the interaction between the algebraic and structural aspects of graphs.
Partition graphs are related to applications in testing suites. They also connect with deep
mathematical problems: finding the maximum clique in these graphs corresponds to determining
for which orders projective planes exist. They are a class of graphs for which eigenspaces
give us a lot of information. These graphs, and many others, can be usefully analyzed
algebraically: there is a close relationship between eigenspaces and structure. This has
applications in covering arrays and coding theory.
Matroids can be thought of as a generalization of graphs and matrices, but they are
fundamentally a geometrical class of objects. Many theoretical results in graph
theory or linear algebra are in fact theorems about matroids in general. More concretely, they
are useful in combinatorial optimization, since they optimization problems can be solved
efficiently when their feasible sets form a matroid. I am interested in problems of typical
structure in matroids.