Welcome to the webpage of the ANR-funded project Mimétique (Metric Minors in Graphs, ANR-25-CE48-4089). The project started in November 2025 and will finish in October 2029.
The ANR project «Metric Minors in Graphs» is devoted to the study of metric aspects of graphs around three main directions:
(1) Coarse/fat minors
(2) Coarse Graph Theory
(3) Partial-cube minors (pc-minors).
The two notions of metric minors (coarse and pc-minors) extend the classical notion of minor and try to combine the topological power of minors with the metric structure of graphs. Coarse graph theory is the discrete counterpart of coarse geometry of metric spaces. Its main goal is defining and studying coarse analogs of graph parameters and of metric properties of graphs. The main farness-closeness principle of coarse graph theory is that disjointness corresponds to farness, nonempty intersection corresponds to closeness, and isometries corresponds to quasi-isometries. Coarse minors generalize classical minors based on the farness-closeness principle. Finally, pc-minors are defined for subgraphs G of hypercubes and correspond to graphs obtained from G by contracting some coordinates of the hosting hypercube (i.e., to graphs shattered by G).
We plan to address questions relating coarse minors with quasi-isometric embeddings. We will use coarse minors to tackle structural and algorithmic questions about optimal distortion and asymptotic dimension. We will also try to understand the role of coarse 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).