GALaC team seminar

The GALaC team seminar is organized on a regular basis on Friday at 14:00 in the PCRI building (650) at LISN.

Recent and up-coming seminars

Faster diameter computation in graphs of bounded Euler genus

-- Giannos Stamoulis (CNRS, IRIF)

Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs ...


Les méandres arcs-en-ciel sur des chemins de Dyck

-- Benjamin Dequêne (Université de Leeds)

Un méandre (de longueur n) est une paire de correspondences non-croisées sur {1,...,n}. On peut le représenter sur le plan réel comme un paire d'ensemble de demi-cercles, qui ne s'intersentent pas deux à deux, reliant n points sur une droite. Cette représentation géométrique permet d'introduire différentes ...

Lattice structures of Gog and Magog triangles

-- Ludovic Schwob (LIGM, Combi)

summary: Gog and Magog triangles are simple combinatorial objects which are equienumerated. Howewer, the problem of finding an explicit bijection between these has been an open problem since the 80’s. These are related to other interesting objects such as alternating sign matrices, plane partitions or aztec diamond tillings.
All ...

Non-intersecting paths and the determinant of the distance matrix of a tree

-- Mercedes Rosas (Universidad de Sevilla)

summary: We present a combinatorial proof of the Graham–Pollak formula for the determinant of the distance matrix of a tree, via sign-reversing involutions and the Lindström–Gessel–Viennot Lemma.
This is joint work with Emmanuel Briand, Luis Esquivias-Quintero, Álvaro Gutierrez, and Adrián Lillo.

See all

Translations: fr