### Graph Theory in Paris

An event held once per semester to get graph theorists in Paris together.

Contact: Reza Naserasr

## Spring 2019

# 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 *G _{S}* 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

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

_{S}

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

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

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

### ANR project HOSIGRA

ANR=Agence Nationale de la Recherche

### LIA STRUCO

LIA=Laboratoire International Associé