Grant: Discovery Grants Program - Individual
University of Waterloo
$24,000.00
Extremal and stability results for graphs and hypergraphs
FY 2019-20
Summary
A graph is an abstract configuration consisting of a set of vertices and a set of edges, where each edge is a subset of the vertex set of size two. A hypergraph is similar except that edges can have any size. Many real-world phenomena can be modelled as graphs or hypergraphs, and contributions to the theory of graphs and hypergraphs can have important practical applications, for example in efficiency and reliability of communication or power systems networks.******My research is in extremal problems for graphs and hypergraphs. The general extremal problem is to maximize or minimize one parameter in terms of another (or others). For example, a natural graph parameter is the maximum degree, the largest number of edges containing any given vertex. Here is a typical extremal question: what is the smallest M such that every vertex partition of a graph G with maximum degree d into classes of size at least M contains an independent transversal (a choice of one vertex in each class such that no edge of G joins any two chosen vertices)? This very general problem comes up in many different settings in mathematics and computer science. I answered it in my work some years ago, showing that M=2d is the correct value. Moreover this is best possible, in that there exist graphs with partition class size 2d-1 that do not have independent transversals (such graphs are called extremal for the problem). This theorem now has many applications by various authors, to results in graph theory (including many different aspects of graph colouring), hypergraph matching, group theory, ring theory and resource allocation problems in computer science.******An important problem associated with any extremal question is the so-called stability version: if the chosen parameter of a given graph G is close to the maximum (or minimum) possible value, is the structure of G close to that of an extremal configuration? The significance of the stability version of an extremal theorem is seen in its applications: if in an application one knows structural information about the graphs involved that shows they are not close to extremal examples, then improved bounds will result.******One of the main aims of my proposed research is to obtain stability versions of certain extremal problems in graphs and hypergraphs, e.g. the one described above. Because of the large number of existing applications of the results I intend to address, stability versions would have significant impact in many areas.******Other aspects of my current research are more directly tied to applications. For example, I have worked with a team of power systems engineers on using graph theory for efficient modelling of power supply networks in the setting of the new Smart Grid in Ontario, and I expect to continue on similar projects with this same team. With colleagues in computer science I have developed algorithms for morphing planar graphs, a problem that arises in computer animation, medical imaging and motion planning.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2017-04215
Name nom
Haxell, Penny
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
2019
Competition year année de concours
2017
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
Installment
inst:3 - 5
Partie
3
Nb partie
5
Application title
Extremal and stability results for graphs and hypergraphs
Keyword
NSERC
Application summary
A graph is an abstract configuration consisting of a set of vertices and a set of edges, where each edge is a subset of the vertex set of size two. A hypergraph is similar except that edges can have any size. Many real-world phenomena can be modelled as graphs or hypergraphs, and contributions to the theory of graphs and hypergraphs can have important practical applications, for example in efficiency and reliability of communication or power systems networks.******My research is in extremal problems for graphs and hypergraphs. The general extremal problem is to maximize or minimize one parameter in terms of another (or others). For example, a natural graph parameter is the maximum degree, the largest number of edges containing any given vertex. Here is a typical extremal question: what is the smallest M such that every vertex partition of a graph G with maximum degree d into classes of size at least M contains an independent transversal (a choice of one vertex in each class such that no edge of G joins any two chosen vertices)? This very general problem comes up in many different settings in mathematics and computer science. I answered it in my work some years ago, showing that M=2d is the correct value. Moreover this is best possible, in that there exist graphs with partition class size 2d-1 that do not have independent transversals (such graphs are called extremal for the problem). This theorem now has many applications by various authors, to results in graph theory (including many different aspects of graph colouring), hypergraph matching, group theory, ring theory and resource allocation problems in computer science.******An important problem associated with any extremal question is the so-called stability version: if the chosen parameter of a given graph G is close to the maximum (or minimum) possible value, is the structure of G close to that of an extremal configuration? The significance of the stability version of an extremal theorem is seen in its applications: if in an application one knows structural information about the graphs involved that shows they are not close to extremal examples, then improved bounds will result.******One of the main aims of my proposed research is to obtain stability versions of certain extremal problems in graphs and hypergraphs, e.g. the one described above. Because of the large number of existing applications of the results I intend to address, stability versions would have significant impact in many areas.******Other aspects of my current research are more directly tied to applications. For example, I have worked with a team of power systems engineers on using graph theory for efficient modelling of power supply networks in the setting of the new Smart Grid in Ontario, and I expect to continue on similar projects with this same team. With colleagues in computer science I have developed algorithms for morphing planar graphs, a problem that arises in computer animation, medical imaging and motion planning.