Groupe de travail ALCOLOCO
Le groupe de travail AlCoLoCo (Algorithmique, Combinatoire, Logique et Complexité), fondé en 2010, compte principalement des membres du thème Algorithmique, Graphes, Complexité de l'axe MAAD du LIMOS, mais aussi des membres d'autres thèmes (en particulier Optimisation Combinatoire) et d'autres axes du laboratoire. Il s'agit d'étudier la théorie et l'algorithmique des structures discrètes : graphes, ordres, géométrie, structures relationnelles... Le groupe de travail se réunit pour des séminaires, des sessions de travail collaboratif, ou encore des groupes de lecture. Site web: https://alcoloco.limos.fr
Responsable communication :
FOUCAUD Florent
Membres : Florent FOUCAUD - Laurent BEAUDOU - Gaetan BERTHE -
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative definitions of merge-width, thus demonstrating the robustness of the notion. Our characterisation via definable merge-width uses vertex orderings inspired by generalised colouring numbers from sparsity theory, and enables us to obtain the first non-trivial approximation algorithm for merge-width, running in time n^O(1)·2^n. Using these alternative definition we also establish that graphs of bounded merge-width admit sparse quotients with bounded strong colouring numbers, are quasi-isometric to graphs of bounded expansion, and admit neighbourhood covers with constant overlap.
Clément Legrand-Duchesne, Dirac’s theorem and the geometry of perfect matchings - 8 janvier 2026 - CONFERENCE
Dirac's theorem states that all n-vertex graphs with minimum degree n/2 contain a perfect matching. This is tight and graphs with minimum degree cn are more generally called c-Dirac graphs. In fact, a phase transition occurs at c=1/2: c-Dirac graphs with c ≥ 1/2 contain (\frac{cn}{e+o(1)})^{n/2} perfect matchings [Cuckler, Kahn 2009]. Moreover, for any fixed c-Dirac graph G with c ≥ 1/2, there exist nice probability distributions on the perfect matchings of G called spread distributions [Pham, Sah, Sawhney, Simkin 2024]; as a result, if the edges of G are sampled with probability O(log(n)/n), the resulting graph still contains a perfect matching with good probability, thereby witnessing that these matchings are "everywhere" in G.
With Ross Kang, we give a new understanding of this phase transition by describing how the perfect matchings of a Dirac graph cluster. More precisely, we analyse the geometrical properties of the space of perfect matchings of G, endowed with the graph metric such that perfect matchings differing on at most k edges are at distance one. For any fixed k, we pinpoint sharp thresholds at which this space is shattered into exponentially many components, has isolated perfect matchings, becomes connected, or becomes an expander.
Mauricio Yépez, The twin-width of powers of graphs with bounded tree-width - 4 décembre 2025 - CONFERENCE
Twin-width is a new graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant. Graphs classes with bounded twin-width include those with bounded tree-width, clique-width, and also planar graphs and proper minor-closed classes. Moreover, they preserve most of the nice algorithmic properties of clique-width. In this work, we study the twin-width of power of graphs with bounded tree-width. This is known to be bounded but existing bounds are implicit and very large. We provide a bound of k for the twin-width of the k-th power of any tree and show that this
bound is tight. We also show that if G has tree-width at most t, then the twin-width of the k-th power of G is at most (1 + 2k ) · 2k·(t−1) .