GALaC team at LRI, Paris-Sud

GALaC is a research group at LRI, Paris-Sud University. We are focused on graph theory, combinatorics and network distributed systems algorithmic.

A global presentation of research activities in GALaC was made in 2013 for the AERES evaluation: Slides AERES 2013 and projet.

Recent Posts

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

Une nouvelle description des treillis m-cambriens

-- Clément Chenevière (LISN, GALaC)

summary: 

Les treillis cambriens, introduits par N. Reading en 2006, sont une généralisation du treillis de Tamari, à tout choix d'élément de Coxeter, dans tout groupe de Coxeter fini. Le treillis de Tamari correspond au "type A linéaire". Ces ordres partiels admettent plusieurs descriptions, non trivialement équivalentes. Celles-ci donnent ...

Proper conflict-free colourings of graphs

-- Quentin Chuet (LISN, GALaC)

summary: Given a graph \(G\) of maximum degree \(\Delta\), the proper colouring problem asks for the minimum number of colours that can be assigned to the vertices of \(G\) such that no pair of adjacent vertices are given the same colour; it is easy to show that at most \(\Delta ...

Alternating and nondeterministic plane-walking automata

-- Pacôme Perrotin (LISN, Galac)

summary: Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic ...

See all

Edit this page / How to edit

Translations: fr