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 -
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 - SEMINAIRE
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) .