EPSRC Reference: 
EP/T016221/1 
Title: 
Graph Minor Theory in three dimensions and Connectivity 
Principal Investigator: 
Carmesin, Dr J 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
EPSRC Fellowship 
Starts: 
01 September 2020 
Ends: 
31 August 2025 
Value (£): 
1,004,277

EPSRC Research Topic Classifications: 
Algebra & Geometry 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 

Related Grants: 

Panel History: 

Summary on Grant Application Form 
Graph Minor Theory sits at the interface between Topology and Graph Theory, with many algorithmic applications. The area started with Kuratowski's characterisation of planarity in terms of forbidden minors as well as the famous Hadwiger Conjecture, which would be a far reaching generalisation of the famous FourColourTheorem. An important aspect of Graph Minor Theory is the connection between embeddings of graphs in 2dimensional surfaces and the Minor Relation. Here a minor of a graph is obtained by deleting edges and contracting connected edge sets to single vertices. In the context of plane graphs the minor relation is particularly natural; it is equivalent to the subgraph relation combined with planar duality. The discovery of this connection began with Kuratowski's theorem in the 1930s and led to the proof of the RobertsonSeymour Theorem, which is often regarded as the deepest theorem of Combinatorics today.
The Graph Minor Theory of Robertson and Seymour has had a transformative impact on Combinatorics as a whole with deep implications to Computer Science. In very rough terms, their structure theorem establishes a connection between the minor relation on graphs and embeddings of graphs in 2dimensional surfaces. The simplest example of this connection is Kuratowski's planarity criterion from 1930, which characterises the class of planar graphs in terms of forbidden minors. Recently, I have been able to prove a 3dimensional analogue of Kuratowski's theorem, answering questions of Lovasz, Pardon and Wagner. This suggests that the ideas and methods of Graph Minors can be extended from 2 to 3 dimensions. Do they offer new approaches to wellknown problems on 3manifolds?
Such problems occur both in Pure Mathematics and Engineering Applications: indeed, Perelman proved that any simply connected compact 3manifold is isomorphic to the 3sphere, solving one of the 7 millennium problems. One of the ingredients of the proof of my new 3DKuratowski theorem is Perelman's theorem, and thus my result provides a link between Combinatorics, Geometry and Topology.
Engineering applications arise from the fact that many structures in the real world can be modelled by so called 2complexes; that is, objects that can be obtained by gluing together triangular faces at their boundaries. Examples include humanbuilt structures like skyscrapers or cars, physical ones like foams and intestines give medical applications. It is a fundamental question when such 2complexes can be embedded in the real 3dimensional world. More specifically, given a 2complex in an abstract way, can you assemble its faces  using bending, stretching and twisting  in 3space so that the faces do not pierce each other? This project will yield a better combinatorial understanding of such problems, which in turn will lead to better algorithms for the corresponding computational problems.
My main aim in this programme is to develop a Graph Minor Theory for 2complexes. I believe that this has the potential to become a rich new theory, with many exciting questions, and connections to Combinatorics (in particular Graph Minors and connectivity), Algebra (more specifically Matroid Theory), Differential Geometry and Topology of 3manifolds and Algorithms. Recent successes in this area include my quadratic time algorithm to check embeddability of simply connected 2complexes in 3space  and during this programme I intend to extend this further.
A second strand of this programme is the development of new methods for extremal questions in graph minors and connectivity. On the one hand connectivity questions arise in applications (such as reliability questions for the internet or electrical power networks), on the other hand they provide fundamental tools for the theory (such as Tutte's Decomposition Theorem or the TangleTree Theorem of Robertson and Seymour). This programme contains a new approach towards a fundamental problem in this area from the 70s.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.bham.ac.uk 