Except for the dinner and photo exhibition, all events will take place at Université Paris Diderot, Batiment Sophie Germain, Amphi Turing
09:15 | Welcome Cofee, Tea and Pastries |
09:45 -- 10:30 | Bjarne Toft -- HEX & REX & T-REX & C-HEX Slides.pdf
Sperner’s Simplex Lemma and its relation to graph colouring I learned from Tibor Gallai. Later I discovered Klaus Wagner’s very simple proof of the lemma, and I discussed these topics with Adrian when I came to Waterloo as a postdoc in the early 1970'ies. This was in a golden period of Waterloo. Some of the arguments subsequently found their way into the first Bondy & Murty. Later I became interested in theoretical aspects of the game of Hex, and the talks with Adrian popped up again in relation to the result that the game of Hex cannot end in a draw and Brouwer’s Fixpoint Theorem. In continuation, new proofs and results have been obtained on Reverse Hex and Cylindrical Hex by Ryan Hayward, Steve Alpern, Samuel Huneke and myself. I shall report on some of these.
|
10:30 -- 11:15 | Vasek Chvatal -- Lines and Closure in Metric Spaces Slides.ppt
The notion of lines in a Euclidean spaces can be generalized to a
definition of lines in metric spaces in at least two distinct ways.
The classical Sylvester-Gallai theorem of Euclidean geometry has been
generalized to all metric spaces with one of the two definitions of
lines (I will sketch Xiaomin Chen's proof of this generalization); its
corollary, customarily and not quite correctly referred to as a De
Bruijn-Erdos theorem, has been conjectured to allow a generalization
to all metric spaces with the other definition of lines. I will survey
results supporting this conjecture and, in particular, contributions
by the birthday boy.
|
11:15 | Cofee Break |
11:30 -- 12:15 | Bill Jackson -- Generic rigidity of point-line frameworks A point-line framework is a collection of points and lines in the Euclidean plane which are linked by constraints which fix the angles between some pairs of lines, and the distances between some pairs of points and between some pairs of points and lines. It is rigid if the only continuous motion of the points and lines which preserve the constraints are translations or rotations of the whole plane. The rigidity of a framework depends only on its underlying `point-line graph' when the framework is generic i.e there are no algebraic dependencies between the coordinates of its points and lines. We characterize when a generic point-line framework is rigid. This is joint work with John Owen.
|
12:30 | Lunch at Restaurant Buffon, 17 Rue Helène Brion (see the map ) |
14:00 -- 14:45 | Jan Volec -- Semidefinite method and Caccetta-Häggvist conjecture Slides.pdf
In 1978, Caccetta and Häggkvist conjectured that every n-vertex digraph with
minimum out-degree at least k contains an oriented cycle of length at most
n/r.
The case of particular interest is when k = n/3, which asserts that every
n-vertex digraph with minimum out-degree at least n/3 contains an oriented
triangle. We use the semidefinite method from flag algebra framework to show
a
weaker statement, namely that every n-vertex digraph with minimum out-degree
at
least 0.3386n must contain a triangle. This is a joint work with Rémi de
Joannis de Verclos and Jean-Sébastien Sereni.
|
14:45 -- 15:30 | André Raspaud -- Vertex colourings of signed graphs
|
16:00 | Cofee Break |
16:00 -- 16:45 | Pierre Charbit -- Large Chromatic Number and Forbidden Induced Subgraphs Slides.pdf |