GTP Graph Theory in Paris An event held once per semester to get graph theorists in Paris together. Contact: Reza Naserasr Spring 2019 Location Time Program Slides Sponsor Building Sophie Germain, Amphitheater Turing (level -1) Address: 8 place Aurélie Nemours, 75013, Paris. To arrive to amphi, after entering Sophie Germain, turn left and take stairs down to the lower level (or follow the signs for Amphi-Turing). To arrive to Bâtiment Sophie Germain using public transport you have 5 possibilities: Tram 3a, station Avenue de France, walk two blocks on avenue de France, Bâtiment Sophie Germain is on your right, behind a silver-bronze apartment building. RER C, station Biblitheque Francoise Miteran (follow the signs for T3a for a correct exit), Metro 14, station Biblitheque Frencoise Miteran (follow the signs for Avenue de France), must walk a few more block toward south. Bus 89 or bus 62, stations Port de France or Avenue de France (last stations for both bus) they are normally very close to the place. For scheduling your trip and availabilities of these public transports see: https://www.ratp.fr/ or vianavigo.com Friday April 26, at 14:00 Schedule of the talks are rather relaxed. There will be a coffee break between the two talks. Penny Haxell Title of talk: Algorithms for independent transversals vs. small dominating sets Abstract: An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. There are several known criteria that guarantee the existence of an IT, of the following general form: the graph G has an IT unless the subgraph GS of G , induced by the union of some subset S of vertex classes, has a small dominating set. These criteria have been used over the years to solve many combinatorial problems. The known proofs of these IT theorems do not give efficient algorithms for actually finding an IT or a subset $S$ of classes such that GS has a small dominating set. Here we present appropriate weakenings of such results that do have effective proofs. These result in algorithmic versions of many of the original applications of IT theorems. We will discuss a few of these here, including hitting sets for maximum cliques, circular edge colouring of bridgeless cubic graphs, and hypergraph matching problems. Patrice Ossona De Mendez Title: A model theoretic approach to sparsity Abstract: What does it mean for a structure to be sparse or dense? What is the point of differentiating between sparse and dense structures? Is there an objective and essential boundary between sparse and dense structures? The aim of this talk is to address, at least partially, these questions, from the points of view of model theory, structural graph theory, and theoretical computer science. Slides of Penny Haxell's Talk Slides of Patrice Ossona de Mendez' Talk ANR project HOSIGRA ANR=Agence Nationale de la Recherche GT GO of GDR-RO GDR =Groupement De Recherche, RO=Recherche Opérationnelle, GO=Graphes et Optimisation Previous events Autumn 2018 Location Time Program Slides Sponsor Building Sophie Germain, Amphitheater Turing (level -1) Address: 8 place Aurélie Nemours, 75013, Paris. To arrive to amphi, after entering Sophie Germain, turn left and take stairs down to the lower level (or follow the signs for Amphi-Turing). To arrive to Bâtiment Sophie Germain using public transport you have 5 possibilities: Tram 3a, station Avenue de France, walk two blocks on avenue de France, Bâtiment Sophie Germain is on your right, behind a silver-bronze apartment building. RER C, station Biblitheque Francoise Miteran (follow the signs for T3a for a correct exit), Metro 14, station Biblitheque Frencoise Miteran (follow the signs for Avenue de France), must walk a few more block toward south. Bus 89 or bus 62, stations Port de France or Avenue de France (last stations for both bus) they are normally very close to the place. For scheduling your trip and availabilities of these public transports see: https://www.ratp.fr/ Friday November 23rd, at 14:00 Schedule of the talks are rather relaxed. There will be a coffee break between the two talks. Monique Laurent Title: Ordering Robinsonian matrices with graph algorithms Abstract: Robinson matrices are structured matrices, introduced in the 1950’s by W.S. Robinson, and motivated by their application to archaeology for the chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterisation by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem. Lex Schrijver Title: Bounds on the Shannon capacity of a graph Abstract: We survey old and new results bounding the Shannon capacity of a graph (by Lovasz, Haemers, Zuiddam, Bukh & Cox and others), and consider topological observations and questions emerging from them. Slides of Monique Laurent's Talk Slides of Lex Schrijver's Talk ANR project HOSIGRA ANR=Agence Nationale de la Recherche LIA STRUCO LIA=Laboratoire International Associé