My PhD project is entitled **Excluded Minors for Isometric Embeddings and Network Design** or simply **EMIEND**. It is an extension of the work which I did for my Master's thesis.

My supervisors are Prof. Samuel Fiorini (Algebra and Combinatorics Research Group, Mathematics Department, ULB) and Prof. GwenaĆ«l Joret (Algorithms Research Group, Computer Science Department, ULB).

### Abstract

Networks are ubiquitous in modern life: communication networks, social networks, and biological networks are a few examples.
Graph theory, which is the mathematical theory of networks, has arisen to prominence as a model for numerous real-world problems
and as a fundamental component of modern mathematics.
Many properties of graphs are preserved by edge deletions, vertex deletions, and edge contractions (such as planarity);
these properties are said to be closed under taking minors.

The Graph Minor Theorem of Robertson and Seymour, one of the deepest theorems within mathematics, asserts that every graph
property closed under taking minors can be characterized by excluding some finite set of graphs as minors.
The proposed project aims at characterizing the set of excluded minors for minor-closed properties arising in two distinct contexts:

(i) Metric embeddings, where one seeks to represent certain metrics in l_p spaces of small dimension while preserving a subset of the distances

(ii) Combinatorial optimization, where it is desirable to bound fractionalities of extreme points of the standard linear programming relaxation
of the Traveling Salesman Problem.

### Funding acknowledgement

This PhD Project is funded by the Luxembourg National Research Fund (FNR) under the AFR PhD scheme. The grant agreement is registered under the number 11628910.