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) 
PhD Student Mehmet Akif Yildiz
Location Universiteit van Amsterdam (UvA)