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/

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

Alex Scott

Title: Graphs with forbidden induced subgraphs

Abstract: It is well known that a graph on n vertices need not have complete subgraphs or independent sets of size more than about log n. But what if we consider graphs which do not contain some specific induced subgraph? Erdos and Hajnal conjectured in the 1980s that for every graph H there is a constant c such that every graph on n vertices without an induced copy of H contains a clique or stable set of size n^c . The Erdos-Hajnal conjecture is still very much open, but we will discuss some recent progress and related results.

Joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.

To be added

ANR project HOSIGRA

ANR=Agence Nationale de la Recherche

GDR-RO

GDR =Groupement De Recherche, RO=Recherche Opérationnelle

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/

Firday 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é