*   Domaine de compétence Optimisation Combinatoire   *
  *    Séminaire
  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 2019 - 2020

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 C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.

17 octobre 2019 Christophe Crespelle
(Université de Bergen)
Modelling complex networks as almost structured graphs
28 novembre 2019 Valentin Gledel
(G-SCOP)
Le jeu de domination Maker-Breaker
12 décembre 2019 Valentin Garnero
(G-SCOP)
Noyaux et méta-noyaux dans les graphes peu denses
19 décembre 2019 Florian Hörsch
(G-SCOP)
An introduction to matroids and a generalization of the graph minor theorem of Robertson and Seymour
9 janvier 2020 François Pirot
(G-SCOP)
Graph representation of circular codes
16 janvier 2020 András Sebő
(G-SCOP)
SIROCO sur le théorème, les algorithmes et les conjectures de Sands-Sauer-Woodrow
23 janvier 2020 Louis Esperet
(G-SCOP)
Coloration non-répétitive
20 février 2020 Marthe Bonamy
(LaBRI, Bordeaux)
Planar graphs: One graph to rule them all
  • 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.