Séminaires 2019 - 2020

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

A cause de la situation sanitaire, le séminaire d'équipe a été temporairement remplacé par un séminaire virtuel organisé conjointement avec Lyon et Clermont-Ferrand, le Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne.

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en Salle C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.

• Jeudi 17 octobre 2019 (à 14h30): Christophe Crespelle (Université de Bergen) : Modelling complex networks as almost structured graphs
  
  In this talk we explore the possibility to represent real-world complex networks as almost cographs, i.e. cographs where a relatively small number of modifications have been performed (some edges have been deleted and some others have been added). We develop heuristics that 1) test whether a given arbitrary graph G is close to being a cograph and that 2) provide a set of modifications to turn the graph G into a cograph. We then run these heuristics on a collection of real-world networks coming from various contexts and we show how to exploit the proximity of some of these networks with the family of cographs in order to generate synthetic graphs having similar properties.
  
  
  
• Jeudi 28 novembre 2019 (à 14h30): Valentin Gledel (G-SCOP) : Le jeu de domination Maker-Breaker
  
  Le jeu de domination Maker-Breaker est un jeu à deux joueur sur un graphes. Les deux joueurs, Dominator et Staller, sélectionnent alternativement des sommets du graphe. Dominator gagne si l'ensemble des sommets qu'il a sélectionné forment un ensemble dominant et Staller gagne si elle réussit à empêcher Dominator de former un tel ensemble.
  Dans cet exposé, nous ferons dans un premier temps une brève introduction des jeux Maker-Breaker en général. Puis nous introduirons plus en détails le jeu de domnation Maker-Breaker ainsi que les deux questions que nous nous posons sur ce jeu : quel joueur a une stratégie gagnante et, si Dominator gagne, combien de coups lui faut-il pour gagner. Nous montrerons que ces problèmes sont PSPACE-complets dans le cas général et étudierons des solutions polynomiales dans le cas des arbres et des cographes.
  
  
  
• Jeudi 12 décembre 2019 (à 14h30): Valentin Garnero (G-SCOP) : Noyaux et méta-noyaux dans les graphes peu denses
  
  Afin de présenter une palette variée de mes thématiques de recherche, je présenterai divers résultats obtenus pendant ma thèse.
  Dans un premier temps je présenterai la méthode de "décomposition en régions" introduite par Alber Fellow et Niedermeier. Cette méthode permet d’exhiber un noyau linéaire pour certains problèmes dans le cas des graphes planaires ; en d'autres termes elle permet de montrer que pour toute instance (planaire) du problème considérer, il est possible de construire en temps polynomial une instance équivalente dont la taille est bornée par la taille de la solution au problème. J'illustrerai cette méthode sur le problème de Domination Rouge Bleu : il s'agit d'une variante de la Domination sur les graphes bipartis, dans laquelle l'ensemble des sommets dominants (la partie bleue) est distinct de l'ensemble des sommets à dominer (la partie rouge).
  Dans un second temps, je présenterai un méta-algorithme (c'est-a-dire un algorithme qui fonctionne pour une large famille de problème) permettant de construire un noyau linéaire ou polynomial dans le cadre des graphes peu denses (excluant un mineur). Cet algorithme générique se base à la fois sur un résultat de Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos; et sur les principes de la programmation dynamique sur décomposition arborescente.
  
  
  
• Jeudi 19 décembre 2019 (à 14h30): Florian Hörsch (G-SCOP) : An introduction to matroids and a generalization of the graph minor theorem of Robertson and Seymour
  
  Matroids are combinatorial objects generalizing concepts of both graph theory and linear algebra. In the first part of the talk, I will introduce basic concepts of matroid theory.
  For a minor-closed class of graphs, a forbidden minor is a graph which is not in the class but all of whose proper minors are. Robertson and Seymour [JCTB,2004] proved in a series of papers that the number of forbidden minors is finite for every minor-closed class of graphs. This result is considered one of the deepest theorems ever seen in graph theory.
  Nevertheless, Geelen, Gerards and Whittle [Notices of the AMS, 2014] announced a proof of a generalization of the result of Robertson and Seymour to certain classes of matroids, known as Rota's Conjecture. I will introduce this conjecture and a vague idea of its proof. If time allows, I will make a connection to the results in this paper.
  
  
  
• Jeudi 9 janvier 2020 (à 14h30): François Pirot (G-SCOP) : Graph representation of circular codes
  
  The discovery of the DNA structure by Watson and Crick in 1953 spurred a new branch of mathematical biology, which overlaps the theory of block codes, that is, codes consisting of words of a fixed length over some finite alphabet. There are several relevant notions associated to block codes; from most to less restrictive, a block code X can be strong-comma-free (the words of X do not overlap), comma-free (no word from X appears as a proper factor of a word in X^2), or k-circular (every word of X^k admits a unique decomposition into words of X when read of a cycle) - if X is k-circular for every k in N, we say that it is circular. In biology, all these properties imply that it is always possible to retrieve the reading frame in a DNA sequence in order to decompose it into codons (words of length 3).
  We describe a graph representation of codes which encapsulates its various properties. By taking advantage of this representation, we are able to give a full characterisation of maximum codes on dinucleotides (words of length 2), of maximal strong-comma-free codes on l-nucleotides (words of any fixed length l), and of maximum comma-free codes on trinucleotides (words of length 3). Finally, we will discuss the optimal value of k(n,l) such that k(n,l)-circularity implies circularity, for all codes on l-nucleotides over an alphabet of cardinality n.
  
  
  
  
• Jeudi 23 janvier 2020 (à 14h30): Louis Esperet (G-SCOP) : Coloration non-répétitive
  
  On montre que l'on peut colorier les graphes planaires avec un nombre constant de couleurs, de manière à ce que sur tout chemin de taille paire, la suite de couleurs sur la première motié du chemin diffère de la suite de couleurs sur la seconde moitié. Cela avait été conjecturé par Alon, Grytczuk, Haluszczak et Riordan en 2002.
  
  Travail en commun avec Vida Dujmovic, Gwenaël Joret, Bartosz Walczak, et David Wood.
  
  
  
• Jeudi 20 février 2020 (à 14h30): Marthe Bonamy (G-SCOP) : Planar graphs: One graph to rule them all
  
  Consider all planar graphs on n vertices. What is the smallest graph that contains them all as induced subgraphs? We provide an explicit construction of such a graph on n^(4/3+o(1)) vertices, which improves upon the previous best upper bound of n^(2+o(1)), obtained in 2007 by Gavoille and Labourel.
  In this talk, we will gently introduce the audience to the notion of so-called universal graphs (graphs containing all graphs of a given family as induced subgraphs), and devote some time to a key lemma in the proof. That lemma comes from a recent breakthrough by Dujmovic et al. regarding the structure of planar graphs, and has already many interesting consequences. This is based on joint work with Cyril Gavoille and Michal Pilipczuk.
  
  
  
• Jeudi 12 mars 2020 (à 14h30): Simon Mauras (IRIF, Paris) : How to aggregate Top-lists
  
  A top-list is a possibly incomplete ranking of elements: only a subset of the elements are ranked, with all unranked elements tied for last. Top-list aggregation takes as input a collection of top-lists and aggregates them into a single complete output ranking, aiming to minimize the number of upsets (pairs ranked in opposite order in the input and in the output).
  This talk will start with a quick survey on rank aggregation (the special case where every input list is a complete ranking of the elements), its relation to Feedback Arc Sets in directed graphs, NP-Hardness, and approximation algorithms. Then we will discuss how such results can be extended to the aggregation of top-lists.
  
  
  
• Jeudi 14 mai 2020 (à 14h30): André Bouchet (Retraité Université du Mans) : Semis enchaînés sur un wari ouvert avec une main de capacité bornée
  
  Un wari est constitué de trous disjoints et d'un ensemble fini non vide de pions répartis dans ces trous. Nous nous intéressons au cas où les trous sont le long d'une courbe orientée de telle façon que chaque trou soit compris entre deux voisins. Tel est le cas par exemple du jeu africain traditionnel, l'awele avec 12 trous creusés sur un plateau en bois. Nous considérons ici le cas d'un wari ouvert avec une infinité de trous.
  Un joueur réalise une opération de semis en prenant dans une main les pions contenus dans un trou pour les déposer un par un dans les trous qui suivent. Dans certains jeux traditionnels tels que le palankulli le joueur enchaîne une nouvelle opération en semant à partir du trou non vide suivant.
  Les propriétés des semis enchaînés sur un wari ouvert sont maintenant assez bien connues. Nous considérons maintenant le cas où la main a une capacité bornée c. C'est à dire que la main ramasse tous les pions d'un trou si leur nombre est au plus égal à l'entier c, sinon la main ne ramasse que c d'entre eux.
  Lorsque la capacité est égale à 1 on peut prouver quelques propriétés intéressantes. Néanmoins subsiste une conjecture que nous énoncerons.
  Nous profiterons de cet exposé pour énoncer une autre conjecture relative aux semis enchaînés sur un wari ouvert.