Metric minors in graphs – Mimetique

The main objective of the ANR pre-proposal «Metric Minors in Graphs» is to undertake a systematic investigation of metric minors in
graphs and to continue the investigation of partial cube minors (pc-minors). We plan to address the most important conjectures about
metric minors and quasi-isometic embeddings, trying to solve them or to make an advance on them. We also plan to investigate notions
and questions related to coarse variants of classical metric notions and to contribute to Coarse Graph Theory. We will use the concept of metric
minor to tackle structural and algorithmic questions about optimal distortion and asymptotic dimension. We will also try to understand
the role of metric minors in various classes of graphs from Metric Graph Theory and in planar graphs. We will continue to investigate
the relationships between the pc-minors and the VC-dimension. We will also consider classes of partial cubes and
pc-minors in relations with sample compression conjecture (coming from machine learning) and domains of conflict event structures
(coming from concurrency).