*   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
5 décembre 2019 András Sebő
(G-SCOP)
SIROCO sur le théorème, les algorithmes et les conjectures de Sands-Sauer-Woodrow
12 décembre 2019 Valentin Garnero
(G-SCOP)
tba
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
23 janvier 2019 Louis Esperet
(G-SCOP)
Coloration non-répétitive
13 février 2019 André Bouchet
(Retraité Université du Mans)
Semis enchaînés sur un wari ouvert avec une main de capacité bornée
  • 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 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 23 janvier 2019 (à 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 13 février 2019 (à 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.