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.

• Jeudi 30 juin 2016 (à 14h30): Csaba Király (Eötvös Loránd University, Budapest) : Generic global rigidity of body-hinge frameworks
  
  A d-dimensional body-hinge framework is a structure consisting of rigid bodies in d-space in which some pairs of bodies are connected by a hinge, restricting the relative position of the corresponding bodies. The framework is said to be globally rigid if every other arrangement of the bodies and their hinges can be obtained by a congruence of the space. The combinatorial structure of a body-hinge framework can be encoded by a multigraph H, in which the vertices correspond to the bodies and the edges correspond to the hinges. We prove that a generic body-hinge realization of a multigraph H is globally rigid in R^d, where d is at least 3, if and only if ((d+1)d/2-1)H-e contains (d+1)d/2 edge-disjoint spanning trees for all edges e of ((d+1)d/2-1)H. (For a multigraph H and integer k we use kH to denote the multigraph obtained from H by replacing each edge e of H by k parallel copies of e.) This implies an affirmative answer to a conjecture of Connelly, Jordán and Whiteley.
  We also consider bar-joint frameworks and show, for each dimension d at least 3, an infinite family of graphs satisfying Hendrickson's well-known necessary conditions for generic global rigidity in R^d (that is, (d+1)-connectivity and redundant rigidity) which are not generically globally rigid in R^d. The existence of these families disproves a number of conjectures, due to Connelly, Connelly and Whiteley, and Tanigawa, respectively.
  
  A joint work with Tibor Jordán and Shin-ichi Tanigawa.
  
  
  
• Jeudi 23 juin 2016 (à 14h30): Anke van Zuylen (College of William & Mary, USA) : Graph-TSP on cubic bipartite graphs
  
  In this talk, we discuss results motivated by two famous conjectures related to the metric traveling salesman problem (TSP):
  The first conjecture by Barnette states that every cubic planar bipartite 3-connected graph is Hamiltonian. The second conjecture states that the integrality gap of the subtour elimination linear programming relaxation for the TSP is at most 4/3. It was shown by Mömke and Svensson in 2011 that this conjecture is true for the graph-TSP on subcubic graphs.
  Inspired by these conjectures, we study the approximability and integrality gap of the graph-TSP on cubic bipartite graphs. The result we will present in this talk is a "local improvement" algorithm which finds a 2-factor with an average cycle length of at least 8 on cubic bipartite graphs. This implies a 5/4-approximation algorithm and a corresponding bound on the integrality gap for the graph-TSP on these graphs.
  
  
  
• Jeudi 2 juin 2016 (à 14h30): Péter Frankl (Rényi Institute, Budapest) : Extremal problems for finite sets
  
  
  
• Jeudi 28 avril 2016 (à 14h30): Wouter Cames van Batenburg (Radboud University, Pays-Bas) : Packing graphs of bounded (co)degree
  
  Two graphs G1 and G2 of order n are said to pack if there exist injective mappings of their vertex sets into 1,...,n such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobas and Eldridge and, independently, Catlin, asserts that, if (Delta(G1)+1) (Delta(G2)+1) > n, then G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t>3 that if G1 does not contain a copy of the complete bipartite graph K_{2,t} and Delta(G1) > 17 t Delta(G2), then (Delta(G1)+1) (Delta(G2)+1) > n implies that G1 and G2 pack. We also provide a mild improvement if moreover G2 contains no copy of the complete tripartite graph K_{1,1,s}.
  
  
• Jeudi 7 avril 2016 (à 15h30): Tobias Müller (Utrecht University, Pays-Bas) : Line arrangements and geometric representations of graphs
  
  A graph is a disk graph if it is the intersection graph of disks in the plane. That is, we can represent each vertex by a disk in such a way that two vertices are adjacent if and only if the corresponding disks intersect. Similarly one can define a segment graph as the intersection graph of line segments in the plane.
  A d-dot product graph is a graph that can be represented by vectors in d-space such that two vertices are adjacent if and only if the inner product of the corresponding vectors is at least one.
  I will discuss some results on these graph classes whose proofs make use of classical results in algebraic geometry, results on pseudoline arrangements (also known as oriented matroids of rank 3) and on the Colin de Verdiere parameter.
  
  (based on joint works with Ross Kang, Erik Jan van Leeuwen, Jan van Leeuwen, Laszlo Lovasz, Colin McDiarmid and Ed Scheinerman).
  
  
• Jeudi 24 mars 2016 (à 15h30): Michael Hebdige (University of Warwick, UK) : Cyclic Colourings of Graphs
  
  A cyclic colouring of a plane graph is a colouring where vertices incident with the same face are coloured differently. The Cyclic Colouring Conjecture asserts that the vertices of every plane graph with maximum face size D can be cyclically coloured using at most 3D/2 colours. So far, the Cyclic Colouring Conjecture has been proven only for two values of D: the cases D=3 (Four Colour Theorem) and D=4 (Borodin's Six Colour Theorem). We prove the case D=6 of the conjecture.
  
  
• Jeudi 17 mars 2016 (à 14h30): Aurélie Lagoutte (LIP, ENS de Lyon) : Coloring perfect graphs with bounded clique number
  
  Perfect graphs are graphs for which the chromatic number matches the trivial lower bound consisting in the clique number (and the same holds for every induced subgraph). After the long study that led to the Strong Perfect Graph Theorem, the main open question concerning them is about finding an optimal coloring with a combinatorial algorithm. Indeed, deciding if the chromatic number of a graph is at most k is NP-complete in general, and even if k=3. A famous result of Lovasz, Grötchel and Schrijver provides a polynomial-time algorithm that optimally colors any perfect graph, however this algorithm uses the ellipsoid method which makes it unpractical and not combinatorial. We design a purely combinatorial algorithm that, given in input a perfect graph, outputs an optimal coloring in time O(n^f) where f is quadratic in the clique number omega(G).
  
  This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.
  
  
• Lundi 14 mars 2016 (à 11h00): Bruno Scherrer (INRIA Nancy) : On the complexity of Policy Iteration (in particular for deterministic problems)
  
  Policy Iteration is an algorithm for solving discrete-time optimal control problems that is very efficient in practice. Until recent results by Ye (2012) and Post & Ye (2013), the reasons of its efficiency were essentially mysterious. I shall describe this algorithm, some results from the literature on its complexity. I will then describe a few results about a question that is still open: the complexity of this algorithm for deterministic problems (the best lower bound is quadratic, while the best upper bound is exponential).
  
  
• Jeudi 10 mars 2016 (à 14h30): Andrey Kupavskii (G-SCOP) : Intersection theorems for (-1,0,1)-vectors
  
  In the spirit of the classical theorem of Erdos, Ko, and Rado, we ask for the maximum size of a family of (-1,0,1)-vectors with certain restrictions on the number of -1's and 1's and on the admissible scalar products between the vectors of the family. We are going to discuss several recent results on the topic and its relation to classical extremal set theory questions.
  
  
• 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.