Minors at large
Lead Research Organisation:
University of Warwick
Department Name: Mathematics
Abstract
The Robertson-Seymour Graph Minor theorem is one of the deepest and most important results in Graph Theory. It asserts that every family F of graphs that is closed under the minor relation can be determined by a finite list of "forbidden" substructures, in the sense that a graph G belongs to F if and only if G does not contain one of these substructures.
This monumental theorem was proved in a series of twenty papers spanning over 500 pages, published from 1983 to 2004. The proof had many side-results that have had an independent impact on the area. An important implication of the Graph Minor theorem is that every family F as above can be recognised by an efficient algorithm. Moreover, many algorithmic problems that are known to be NP-hard in general are known to have efficient algorithms when restricted to such a family F.
This project follows up on recent work by Fujiwara & Papasoglou and Bonamy et al. to develop a "Coarse Graph Minor Theory" that parallels the classical graph minor theory but introduces a coarse perspective following Gromov's paradigm of coarse geometry. Importantly, this new theorem applies not only to graphs, but to a much broader classes of metric spaces including Riemannian manifolds and many discrete metric spaces arising in computer science. We envisage a coarse version of a classical graph colouring problem that would have immediate algorithmic applications in problems of computational geometry. The importance of such problems is expected to grow due to the employment of geometric techniques in data science. We propose geometric analogues of other classical results of graph theory.
In a second part, we attack a well known-conjecture of Thomas that seeks to extend the Robertson-Seymour Graph Minor Theorem to countably infinite graphs. We objerve that Thomas' conjecture would have an important implication for finite graphs as well, and propose a weaker version that would still have this implication and is much more likely to be accessible. We propose concrete steps for attacking the latter.
This monumental theorem was proved in a series of twenty papers spanning over 500 pages, published from 1983 to 2004. The proof had many side-results that have had an independent impact on the area. An important implication of the Graph Minor theorem is that every family F as above can be recognised by an efficient algorithm. Moreover, many algorithmic problems that are known to be NP-hard in general are known to have efficient algorithms when restricted to such a family F.
This project follows up on recent work by Fujiwara & Papasoglou and Bonamy et al. to develop a "Coarse Graph Minor Theory" that parallels the classical graph minor theory but introduces a coarse perspective following Gromov's paradigm of coarse geometry. Importantly, this new theorem applies not only to graphs, but to a much broader classes of metric spaces including Riemannian manifolds and many discrete metric spaces arising in computer science. We envisage a coarse version of a classical graph colouring problem that would have immediate algorithmic applications in problems of computational geometry. The importance of such problems is expected to grow due to the employment of geometric techniques in data science. We propose geometric analogues of other classical results of graph theory.
In a second part, we attack a well known-conjecture of Thomas that seeks to extend the Robertson-Seymour Graph Minor Theorem to countably infinite graphs. We objerve that Thomas' conjecture would have an important implication for finite graphs as well, and propose a weaker version that would still have this implication and is much more likely to be accessible. We propose concrete steps for attacking the latter.
Organisations
People |
ORCID iD |
| Agelos Georgakopoulos (Principal Investigator) |