Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$20,000.00

Transversals, colouring, matchings and covers

FY 2016-17

Summary
The objectives of my research will be to solve various extremal-type problems in graphs and hypergraphs. A hypergraph H is an abstract object consisting of a set of vertices V and a set of hyperedges E such that each element of E is a subset of V. A graph is just a hypergraph in which every (hyper)edge has size 2. Many important problems, both theoretical and practical, can be expressed in terms of basic questions about graphs or hypergraphs. The problems I will address can all be stated in this purely abstract terminology, and usually involve partitions with certain special properties. However in many cases they come from very concrete problems. Two specific applications I have worked on recently involve effective routing protocols in the internet, and the development of effective schemes for performing automatic fault restoration in electrical power systems. Fault restoration is the process of restoring power in an electrical grid by reconfiguring the network, after a power failure caused by a storm or other accidental damage to power lines or other components of the network. With the development of the smart grid, the need for automation in power restoration and other aspects of network operation is becoming much greater. An example of a general problem I will address is the following. Given a graph whose vertex set is partitioned into classes, what properties of the graph guarantee that there exists a set of vertices, one in each class, with the property that no two are joined by an edge? This is a very basic graph theoretical question, and it comes up in many different mathematical circumstances, including such well-studied topics as list colouring, matching problems, and the satisfiability problem (SAT). These in turn have many implications for practical problems. One cannot hope to find an effective characterisation of graphs with this property (unless P=NP), but finding general sufficient conditions for the existence of such a set could lead to important advances in these other areas.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
138677-2010
Name nom
Haxell, Penelope
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2010
Award amount
20000
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
5
Nb partie
5
Application title
Transversals, colouring, matchings and covers
Keyword
NSERC
Application summary
The objectives of my research will be to solve various extremal-type problems in graphs and hypergraphs. A hypergraph H is an abstract object consisting of a set of vertices V and a set of hyperedges E such that each element of E is a subset of V. A graph is just a hypergraph in which every (hyper)edge has size 2. Many important problems, both theoretical and practical, can be expressed in terms of basic questions about graphs or hypergraphs. The problems I will address can all be stated in this purely abstract terminology, and usually involve partitions with certain special properties. However in many cases they come from very concrete problems. Two specific applications I have worked on recently involve effective routing protocols in the internet, and the development of effective schemes for performing automatic fault restoration in electrical power systems. Fault restoration is the process of restoring power in an electrical grid by reconfiguring the network, after a power failure caused by a storm or other accidental damage to power lines or other components of the network. With the development of the smart grid, the need for automation in power restoration and other aspects of network operation is becoming much greater. An example of a general problem I will address is the following. Given a graph whose vertex set is partitioned into classes, what properties of the graph guarantee that there exists a set of vertices, one in each class, with the property that no two are joined by an edge? This is a very basic graph theoretical question, and it comes up in many different mathematical circumstances, including such well-studied topics as list colouring, matching problems, and the satisfiability problem (SAT). These in turn have many implications for practical problems. One cannot hope to find an effective characterisation of graphs with this property (unless P=NP), but finding general sufficient conditions for the existence of such a set could lead to important advances in these other areas.