Networks

Extremal, algorithmic, and enumerative problems in graph theory

Summary

The main theme of the project is in the general area of graph theory and combinatorics. Some more specific topics /quesstions include:

1)Extremal combinatorics: what sort of conditions imposed on graphs/networks guarantee the existence of certain desired substructures, e.g. how can we guarantee the existence of a Hamilton cycle in a graph. This is often well understood for "dense" graphs but often more difficult for "sparse" graphs: it has connections to the famous travelling salesman problem.

2)Decomposition problems: when is it possible to partition the vertices or the edges of the graph such that each part has some desired property (vertex/edge colouring of graphs is an example, but there are many others).

3)Computational counting: this is about fast algorithms to approximately count combinatorial objects and more generally to evaluate graph polynomials / partition functions such as matching/chromatic/Tutte polynomials. We are often interested in studying the location of zeros of these partition functions / polynomials.

Supervisors Viresh Patel (UvA), Joanna Ellis-Monaghan (UvA)
PhD Student Mehmet Akif Yildiz
Location University of Amsterdam (UvA)

 

This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement Grant Agreement No 945045.

 

 EC-H2020