GTP

Graph Theory in Paris

An event held once per semester to get graph theorists in Paris together.
Contact: Reza Naserasr

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).

  • 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 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 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.



Next event: Autumn 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/

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 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 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.

ANR project HOSIGRA

ANR=Agence Nationale de la Recherche

LIA STRUCO

LIA=Laboratoire International Associé