The European Associated Laboratory "Structures in Combinatorics"

  • STRUCO Meeting "Graph theory and sparse structures" will take place in October, from 27th to 28th.

There are a significant number of strong links and successful cooperations between Czech and French researchers in the scope of graph theory and, more generally, in discrete mathematics and theoretical computer science. Most of these exchanges are based on isolated and limited projects and fundings (short-term bilateral projects and visiting professorships, for example). In particular, the success of these cooperations has been pretty much based upon individual actions and will.

One of the main goal and interest of the current project is to provide a sustainable and reliable structure to help these researcher cooperate on long-term projects, disseminate the results to students of both countries and create links between these students more systematically. The LEA would also be a natural place to federate and organize these many isolated collaborations. Thus, the project would ensure long-term cooperations and allow young researchers (especially PhD students) to tmaintain the fruitful exchanges between the two countries in the future years, in a structured and federated way.

The primary theme of the laboratory is graph theory, and more specifically:

  • sparsity of graphs (nowhere dense classes of graphs, bounded expansion classes of graphs)
  • extremal graph theory
  • graph coloring
  • Ramsey theory, universality and morphism duality
  • graph and matroids algorithms
  • model checking

The LEA focuses on high-level study of fundamental combinatorial objects, with a particular emphasis on comprehending and disseminating the state-of-the-art theories and techniques developed. The obtained insight shall be applied to obtain new results on existing problems as well as to identify directions and questions for future work.

One of the goals of this project is also to help researchers from different areas communicate and exchange on their concerns so that they could benefit from each other expertise when relevant. This is particularly true for distributed computing (links with (particular types of) graph homomorphisms) and discrete geometry (links with techniques developed in extremal graph theory).

The chosen themes of the project cover timely and difficult questions, for which a stable and significant cooperation structure is needed. By gathering an important number of excellent researchers and students, the LEA will create the required environment for making advances, which shall be achieved not only by short-term exchanges of researchers, but also by a strong involvement of Ph. D students in the learning of state-of-the-art techniques and in the international collaborations, thereby ensuring the continued existence of a productive and world-level network in fields belonging to graph theory, combinatorics and theoretical computer science.


The LEA is run by two Co-directors. The management of the LEA is jointly provided by:

  • Dr Jean-Sébastien Sereni for CNRS, France,
  • Prof. Jaroslav Nešetřil for Charles University, Czech Republic.

Researchers involved in the project:

  • P. Aboulker
  • A. Bouajjani
  • P. Charbit
  • J. Dusart
  • Z. Dvořák
  • P. Habermehl
  • M. Habib
  • J. Hubička
  • J. Kratochvíl
  • M. Loebl
  • L. Mach
  • A. Mamcarz
  • F. de Montgolfier
  • J. Nesetřil
  • P. Ossona de Mendez
  • O. Pangrác
  • J.-S. Sereni
  • J. Sgall
  • J. Volec
  • Z. Yilma