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

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.

24 mars 2016 Michael Hebdige
(University of Warwick)
tba
17 mars 2016 Julien Bensmail ?
(Technical University of Denmark)
tba
18 février 2016 Jan Volec
(ETH Zürich)
Graph limit approach in extremal combinatorics
10 décembre 2015 Tereza Klimosová
(LIP, ENS de Lyon)
Finitely forcible limits of graphs and permutations
7 décembre 2015 Ilkyoo Choi
(KAIST, Daejeon, Corée du Sud)
Conjectures regarding chi-bounded classes of graphs
26 novembre 2015 Ágnes Cseh
(TU Berlin)
Arranged marriages in the stable matching and popular matching problems
1er octobre 2015 Lucas Pastor
(G-SCOP, Grenoble)
Coloration par liste dans les graphes parfaits sans griffe
  • Jeudi 18 février 2016 (à 14h30): Jan Volec (ETH Zürich) : Graph limit approach in extremal combinatorics

    In the last decade, various theories of combinatorial limits emerged, and attracted a substantial attention. In the first part of the talk, we focus on limits of dense graphs and describe a counterexample to a conjecture of Lovasz and Szegedy on the structure of the topological space of typical vertices of the limit objects. In the second part of the talk, we will apply the so-called flag algebra method to a conjecture of Erdős and Sos on the maximum number of rainbow triangles in 3-edge-colored graphs. We will also use flag algebras to show that weakly quasirandom 3-graphs where every 4 vertices span at most two edges have density at most 1/4. This was conjectured by Erdős, and the constant 1/4 is best possible.

  • Jeudi 10 décembre 2015 (à 15h15): Tereza Klimosová (LIP, ENS de Lyon) : Finitely forcible limits of graphs and permutations

    Graphons and permutons are analytic objects associated with convergent sequences of graphs and permutations, respectively. Problems from extremal combinatorics and theoretical computer science led to a study of graphons and permutons determined by finitely many substructure densities, which are referred to as finitely forcible. The talk will contain several results on finite forcibility, focusing on the relation between finite forcibility of graphons and permutons. We also disprove a conjecture of Lovasz and Szegedy about the dimension of the space of typical vertices of finitely forcible graphons.

    The talk is based on joint work with Roman Glebov, Andrzej Grzesik and Dan Kral.

  • Lundi 7 décembre 2015 (à 14h30): Ilkyoo Choi (KAIST, Daejeon, Corée du Sud) : Conjectures regarding chi-bounded classes of graphs

    The clique number is a trivial lower bound for the chromatic number of a graph. Since Erdős showed the existence of graphs with arbitrarily high chromatic number and arbitrarily high girth (so clique number is 2), in general, the chromatic number of a graph cannot be upper bounded by a function of its clique number. A class of graphs is said to be chi-bounded if such a function exists.
    Vertex-minor and pivot-minors are graph containment properties such as (induced) subgraphs, subdivisions, and minors. Geelen conjectured that for any fixed graph H, the class of graphs with no H-vertex-minor is chi-bounded. This conjecture was known to be true only for one graph (proved by Dvorak and Kral'), but recently Chudnovsky, Scott, and Seymour proved it for any cycle. We add another class of graphs for which Geelen's Conjecture is true, namely, fan graphs.
    We also ask the following question of whether Geelen's Conjecture can be generalized to pivot-minors: for any fixed graph H, are the class of graphs with no H-pivot-minor chi-bounded? We give some positive evidence to this question by proving that it is true for all cycles, which is a strengthening of the aforementioned result by Chudnovsky, Scott, and Seymour. This result can also be viewed as a partial result of the last open conjecture among the three conjectures made by Gyárfás in 1985.

  • Jeudi 26 novembre 2015 (à 14h30): Ágnes Cseh (TU Berlin) : Arranged marriages in the stable matching and popular matching problems

    In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. We are given a not necessarily perfect matching M consisting of acceptable pairs of these agents. If any two agents mutually prefer each other to their partner, then they block M, otherwise, M is said to be stable. A matching M is popular if there is no matching M' such that the number of vertices that prefer M' to M exceeds the number of vertices that prefer M to M'. While stable matchings capture the notion of local optimality, popular matchings provide a useful alternative to the well-studied stable matchings in the collective setting, aiming at the welfare of an entire group.
    In this talk we investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. In the former case a solution must contain all of the forced pairs, while in the latter case none of the forbidden pairs must appear in a solution.

    Joint work with David F. Manlove and Telikepalli Kavitha.

  • Jeudi 1er octobre 2015 (à 14h30): Lucas Pastor (G-SCOP, Grenoble) : Coloration par liste dans les graphes parfaits sans griffe

    Vizing (et d'autres après lui) a conjecturé en 1975 que pour tout line-graph, le nombre chromatique est égal au nombre chromatique par liste (égalité chromatique).
    Il est facile de voir qu'un line-graph ne peux pas contenir le graphe griffe comme sous-graphe induit. A partir de cela, Gravier et Maffray ont conjecturé en 1997 que pour tout graphe sans griffe, le nombre chromatique est égal au nombre chromatique par liste. Nous nous intéressons à une version plus faible de cette conjecture, réduite aux graphes parfaits. Basé sur un résultat structurel de Maffray et Reed, nous montrons que pour tout graphe parfait sans griffe, avec la taille maximum d'une clique bornée par 4, l'égalité chromatique est vérifiée.

    Travail en collaboration avec Sylvain Gravier et Frédéric Maffray.