Grant: Discovery Grants Program - Individual
University of Waterloo
$34,000.00
Partitions, transversals and colouring in graphs and hypergraphs
EF 2024-25
Résumé
A graph is an abstract configuration consisting of a set of vertices and a set of edges, where each edge is a subset of vertices of size 2. A hypergraph is similar except that edges can
have any size. Many real--world phenomena can be modelled in these terms, so contributions to the theory of these structures can have important practical applications, for example in scheduling,
fair allocation of resources, and efficiency and reliability in networks.
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 (IT), i.e. a choice of one vertex in each class such that no edge of G joins any two chosen vertices? This fundamental problem comes up in many different settings in
mathematics, computer science and applications. I solved it some years ago, showing that M=2d is precisely the correct value. This theorem now has many applications by various authors,
in combinatorics, group theory, ring theory, optimization and more. However, its proof does not supply an efficient algorithm to actually find an IT. Recently I have developed efficient algorithms to find an IT under only very slightly stronger conditions, e.g. when d is bounded and M=2d+1, and several other settings. This has important algorithmic implications for many previously known applications of the IT theorem, and leads to new ones as well. I will continue this work with targeted applications in mind, including algorithms for various graph colouring and fair division problems.
A different guarantee of existence of IT's (established by R. Aharoni and myself some years ago) uses a topological notion. Recently I initiated the application of this approach to a fundamental question in discrete optimization, namely the Max--min Allocation problem. I obtained substantially improved approximation algorithms for this general problem, and an important special case. This new method is very versatile and I will use it to address several other key optimization problems that are similarly based on hypergraph matching. These have important applications to machine scheduling, fair division of goods and more.
Another focus of my research will be graph colouring, in which one seeks to partition a graph into as few independent sets as possible. Recently I proved a broad generalization of the current best known bounds for the famous Borodin-Kostochka Conjecture (BKC) from 1977, which proposes an extension to the classical theorem of Brooks. This cornerstone of graph theory precisely characterizes graphs that need d+1 colours in every colouring, where d is the maximum degree. The BKC asks the same question for d colours. The new approach has strong potential and I will apply it to obtain further improvements to this and other closely related results, thus strengthening countless applications of Brooks' Theorem. The method also provides efficient algorithms for colouring graphs with high chromatic number.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2024-03831
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
2024
Competition year année de concours
2024
Award amount
34000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Partitions, transversals and colouring in graphs and hypergraphs
Keywords
graphs; hypergraphs; independent transversals; colouring; topological methods in combinatorics; resource allocation; discrete optimization; approximation algorithms
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 vertices of size 2. A hypergraph is similar except that edges can
have any size. Many real--world phenomena can be modelled in these terms, so contributions to the theory of these structures can have important practical applications, for example in scheduling,
fair allocation of resources, and efficiency and reliability in networks.
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 (IT), i.e. a choice of one vertex in each class such that no edge of G joins any two chosen vertices? This fundamental problem comes up in many different settings in
mathematics, computer science and applications. I solved it some years ago, showing that M=2d is precisely the correct value. This theorem now has many applications by various authors,
in combinatorics, group theory, ring theory, optimization and more. However, its proof does not supply an efficient algorithm to actually find an IT. Recently I have developed efficient algorithms to find an IT under only very slightly stronger conditions, e.g. when d is bounded and M=2d+1, and several other settings. This has important algorithmic implications for many previously known applications of the IT theorem, and leads to new ones as well. I will continue this work with targeted applications in mind, including algorithms for various graph colouring and fair division problems.
A different guarantee of existence of IT's (established by R. Aharoni and myself some years ago) uses a topological notion. Recently I initiated the application of this approach to a fundamental question in discrete optimization, namely the Max--min Allocation problem. I obtained substantially improved approximation algorithms for this general problem, and an important special case. This new method is very versatile and I will use it to address several other key optimization problems that are similarly based on hypergraph matching. These have important applications to machine scheduling, fair division of goods and more.
Another focus of my research will be graph colouring, in which one seeks to partition a graph into as few independent sets as possible. Recently I proved a broad generalization of the current best known bounds for the famous Borodin-Kostochka Conjecture (BKC) from 1977, which proposes an extension to the classical theorem of Brooks. This cornerstone of graph theory precisely characterizes graphs that need d+1 colours in every colouring, where d is the maximum degree. The BKC asks the same question for d colours. The new approach has strong potential and I will apply it to obtain further improvements to this and other closely related results, thus strengthening countless applications of Brooks' Theorem. The method also provides efficient algorithms for colouring graphs with high chromatic number.