Séminaires 2024 - 2025

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 ou C101. 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 24 octobre 2024 (14h30) : Alantha Newman (CNRS, G-SCOP) : Recent progress on correlation clustering
  
  In the correlation clustering problem, we are given a complete graph with each edge labeled as + (similar) or - (dissimilar).  The goal is to find a clustering (a partition) of the vertices that minimizes the number of dissimilar intracluster edges and the number of similar intercluster edges.  Until recently, the best known approximation guarantee was 2.06, based on a modification of the natural LP-based pivot algorithm.  We now know how to go below 1.5 using various new tools and insights.  In this talk, we will give an overview of these recent developments and discuss some of the open questions.
  
  Based on joint work with Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li and Lucas Vogl.
  
  
  
• Jeudi 17 octobre 2024 (14h30) : Louis Esperet (CNRS, G-SCOP) : The clustered Hadwiger conjecture
  
  We prove that every K_h-minor-free graph has an (h-1)-coloring in which every monochromatic component has size bounded by some function of h. The number of colors is optimal, and this proves a conjecture of Edwards, Kang, Kim, Oum and Seymour (2015). The proof of our result heavily relies on 2 recent technical ingredients: the Product Structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood, and a clustered coloring lemma for K_{s,t}-subgraph-free graphs of bounded treewidth by Liu and Wood.
  
  This is joint work with V. Dujmović, P. Morin, and D. Wood.
  
  
  
• Jeudi 10 octobre 2024 (14h30) : Rémi Coulon (CNRS, Université de Bourgogne) : Croissance dans les graphes de Cayley des groupes de type fini
  
  Étant donné un groupe G engendré par une partie finie S, on y associe naturellement un graphe homogène, appelé graphe de Cayley, sur lequel on peut lire la table de multiplication du groupe. Naturellement, la géométrie de ce graphe nous informe sur la structure algébrique du groupe. Dans cet exposé on illustrera ce phénomène au travers de la notion de "croissance". L'idée est d'étudier le comportement asymptotique lorsque r tend vers l'infini du cardinal d'une boule de rayon r. Par le biais d'exemples variés on présentera les différents phénomènes qui peuvent apparaître, ainsi que divers problèmes ouverts sur le sujet.
  
  
  
• Jeudi 19 septembre 2024 (14h30) : Nicolas Trotignon (LIP, Lyon) : A tamed family of triangle-free graphs with unbounded chromatic number
  
  We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every graph on at least three vertices either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative a question of Chudnovsky, Penev, Scott and the speaker. These graphs are structurally simple in several ways, in particular regarding their twinwidth. Also, we show how to obtain such graphs with arbitrarily large odd girth.
  
  This is joint work with Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet and Stéphan Thomassé.
  
  
  
• Vendredi 13 septembre 2024 (11h00) : Felix Hommelsheim (Université de Bremen) : Two-Edge Connectivity via Pac-Man Gluing
  
  We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph G, compute a connected subgraph H of G with the minimum number of edges such that H is spanning, i.e., V(H) = V(G), and H is 2-edge-connected, i.e., H remains connected upon the deletion of any single edge, if such an H exists. The 2-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time (5/4+epsilon)-approximation for the problem for an arbitrarily small epssilon>0, improving the previous best approximation ratio of 13/10+epsilon. Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge-connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.
  
  
  
• Vendredi 13 septembre 2024 (10h00) : Jan van den Heuvel (London School of Economics & Political Science) : Partial Colourings (aka "Timetabling with not Enough Time")
  
  Suppose you have a graph G for which you know the vertices can be properly coloured with t colours, but you only have s < t colours available. Then it is an easy observation that you can still properly colour at least a fraction s/t of the vertices of G. (More formally: there exists an induced subgraph H of G such that H is s-colourable and |V(H)| ≥ s/t|V(G)|.) But the situation is less clear when we look at other types of colourings, such as list-colourings, fractional colourings, multi-colourings, etc. In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question forces us to have to look at some surprising parts of combinatorics.
  
  This is joint work with Xinyi Xu.
  
  
  
• Jeudi 5 septembre 2024 (14h30) : Sébastien Zeitoun (LIRIS, Université Lyon 1) : Local certification of forbidden subgraphs
  
  Local certification is a distributed mechanism in which nodes of a network have to verify a property of the network. This is done thanks to small pieces of information, called certificates, which are attributed to the vertices by an external entity, often called the prover. It is known that any property can be certified with certificates of size O(n^2) (where n is the number of nodes in the network), simply by writing the map of the whole graph in the certificate of each node. However, for some properties, we can do much better (many properties admit certificates of size polylog(n)). In local certification, for every graph property, the aim is to find the optimal size of the certificates. Here, we will focus on lower and upper bounds for the property that the graph does not contain some other fixed graph H as an induced subgraph (this is also called H-freeness).