*   Equipe Optimisation Combinatoire   *
  *    Séminaire
  o    2023 - 2024
  o    2022 - 2023
  o    2021 - 2022
  o    2019 - 2020
  o    2018 - 2019
  o    2017 - 2018
  o    2016 - 2017
  o    2015 - 2016
  o    2014 - 2015
  o    2013 - 2014
  o    2012 - 2013
  o    2011 - 2012
  o    2010 - 2011
  o    2009 - 2010
  o    2008 - 2009
  o    2007 - 2008
  o    2006 - 2007
  o    2005 - 2006
  o    2004 - 2005
  o    2003 - 2004
  *    Evènements
  *    Liens

Séminaires 2023 - 2024

Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en salle H208 ou H202. Les responsables sont Moritz Mühlenthaler et Alantha Newman, n'hésitez pas à les contacter.

Pendant la pandémie nous avons organisé un séminaire virtuel (conjointement avec Lyon et Clermont-Ferrand), le Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne.

  • Jeudi 12 octobre 2023 (14h30) : Vincent Cohen-Addad (Google Research) : Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1

    We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter ε>0, constructs an edge-weighted graph H and an embedding η:V(G)→V(H) with the following properties:
    • For any constant size Q, the treewidth of H is polynomial in ε−1, logn, and the logarithm of the stretch of the distance metric in G.
    • The expected multiplicative distortion is (1+ε): for every pair of vertices u,v of G, we have distH(η(u),η(v))≥distG(u,v) always and Exp[distH(η(u),η(v))]≤(1+ε)distG(u,v).
    Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with O(1) expected distortion requires the host graph to have treewidth Ω(logn). It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.

    Joint work with  Hung Le, Marcin Pilipczuk, Michał Pilipczuk


  • Jeudi 5 octobre 2023 (14h30) : Benjamin Peyrille (G-SCOP, Grenoble) : Title TBA

    Abstract TBA


  • Jeudi 28 septembre 2023 (14h30 - salle H202): Ugo Giocanti (G-SCOP, Grenoble) : The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture.

    An infinite graph is quasi-transitive if the action of its automorphism group on its vertex set has finitely many orbits. Roughly speaking, this means that the graph has a lot of symmetries. Starting with the work of Maschke (1896), a lot of work have been done on the structure of planar Cayley graphs, and more generally of planar quasi-transitive graphs. On the opposite, only few research has been done about the more general class of minor-excluded quasi-transitive graphs. In this talk, I will present a structure theorem for such graphs, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. The proof of our result is mainly based on a combination of the work of Thomassen (1992) together with an extensive study of Grohe (2016) on the properties of separations of order 3 in finite graphs. Our proof involves some technical notions from structural graph theory and I will spend some time to present some of the key concepts involved and especially how they must be adapted to take into account the symmetries of the studied graph. Eventually I will explain how such a result can be used to prove the so called domino problem conjecture for minor-excluded groups, extending previous results from Berger (1966) and Aubrun, Barbieri and Moutot (2019). I will also spend time to present other applications both at the group and at the graph level.

    This is a joint work with Louis Esperet and Clément Legrand-Duchesne.


  • Jeudi 14 septembre 2023 (14h30 - attention salle C101) : Felix Klingelhoefer (G-SCOP, Grenoble) : Bounding the chromatic number of dense digraphs by arc neighborhoods

    The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc uv in a tournament T is the set of vertices that form a directed triangle with arc uv. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. This holds more generally for oriented graphs with bounded independence number, and we extend our proof from tournaments to this class of dense digraphs. As an application, we prove the equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number.