Grant: Discovery Grants Program - Individual
University of Waterloo
$24,000.00
Extremal and stability results for graphs and hypergraphs
FY 2017-18
Summary
A graph is an abstract configuration consisting of a set of verticesand a set of edges, where each edge is a subset of thevertex set of size two. A hypergraph is similar except that edges canhave any size. Many real-world phenomena can be modelled as graphs orhypergraphs, and contributions to the theory of graphs and hypergraphscan have important practical applications, for example in efficiencyand reliability of communication or power systems networks. My research is in extremal problems for graphs and hypergraphs. Thegeneral extremal problem is to maximize or minimize oneparameter in terms of another (or others). For example, a naturalgraph parameter is the maximum degree, the largest number of edgescontaining any given vertex. Here is a typical extremal question: whatis the smallest M such that every vertex partition of a graph G withmaximum degree d into classes of size at least M contains anindependent transversal (a choice of one vertex in each class suchthat no edge of G joins any two chosen vertices)? This verygeneral problem comes up in many different settings inmathematics and computer science. I answered itin my work some years ago, showing that M=2d is the correctvalue. Moreover this is best possible, in that there existgraphs with partition class size 2d-1 that do not have independenttransversals (such graphs are called extremal for theproblem). This theorem now has many applications by various authors,to results in graph theory (including many different aspects of graphcolouring), hypergraph matching, group theory, ring theory andresource allocation problems in computer science. An important problem associated with any extremal question is theso-called stability version: if the chosen parameter of a given graphG isclose to the maximum (or minimum) possible value, is the structure ofG close to that of an extremal configuration? The significance ofthe stability version of an extremal theorem is seen in its applications:if in an application one knows structural information about the graphsinvolved that shows they are not close to extremal examples, thenimproved bounds will result. One of the main aims of my proposed research is to obtain stabilityversions of certain extremal problems in graphs and hypergraphs, e.g.the one described above. Because of the large number of existingapplications of the results I intend to address, stability versions would havesignificant impact in many areas. Other aspects of my current research are more directly tied toapplications. For example, I have worked with a team of power systemsengineers on using graph theory for efficient modelling of powersupply networks in thesetting of the new Smart Grid in Ontario, and I expect to continueon similar projects with this same team. With colleagues in computerscience I have developed algorithms for morphing planar graphs, a problem that arisesin 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 - 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
2017
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 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
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
1
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 verticesand a set of edges, where each edge is a subset of thevertex set of size two. A hypergraph is similar except that edges canhave any size. Many real-world phenomena can be modelled as graphs orhypergraphs, and contributions to the theory of graphs and hypergraphscan have important practical applications, for example in efficiencyand reliability of communication or power systems networks. My research is in extremal problems for graphs and hypergraphs. Thegeneral extremal problem is to maximize or minimize oneparameter in terms of another (or others). For example, a naturalgraph parameter is the maximum degree, the largest number of edgescontaining any given vertex. Here is a typical extremal question: whatis the smallest M such that every vertex partition of a graph G withmaximum degree d into classes of size at least M contains anindependent transversal (a choice of one vertex in each class suchthat no edge of G joins any two chosen vertices)? This verygeneral problem comes up in many different settings inmathematics and computer science. I answered itin my work some years ago, showing that M=2d is the correctvalue. Moreover this is best possible, in that there existgraphs with partition class size 2d-1 that do not have independenttransversals (such graphs are called extremal for theproblem). This theorem now has many applications by various authors,to results in graph theory (including many different aspects of graphcolouring), hypergraph matching, group theory, ring theory andresource allocation problems in computer science. An important problem associated with any extremal question is theso-called stability version: if the chosen parameter of a given graphG isclose to the maximum (or minimum) possible value, is the structure ofG close to that of an extremal configuration? The significance ofthe stability version of an extremal theorem is seen in its applications:if in an application one knows structural information about the graphsinvolved that shows they are not close to extremal examples, thenimproved bounds will result. One of the main aims of my proposed research is to obtain stabilityversions of certain extremal problems in graphs and hypergraphs, e.g.the one described above. Because of the large number of existingapplications of the results I intend to address, stability versions would havesignificant impact in many areas. Other aspects of my current research are more directly tied toapplications. For example, I have worked with a team of power systemsengineers on using graph theory for efficient modelling of powersupply networks in thesetting of the new Smart Grid in Ontario, and I expect to continueon similar projects with this same team. With colleagues in computerscience I have developed algorithms for morphing planar graphs, a problem that arisesin computer animation, medical imaging and motion planning.