Scientific Committee
Comité scientifique
Mikołaj Bojańczyk (University of Warsaw)
Maryanthe Malliaris (University of Chicago)
Claire Mathieu (CNRS – Collège de France)
Nicole Schweikardt (Humboldt University Berlin)
Saharon Shelah (Hebrew University of Jerusalem)
Organizing Committee
Comité d’organisation
Mirna Džamonja (CNRS – IRIF – Université Paris Cité)
Sylvain Schmitz (CNRS – IRIF – Université Paris Cité)
Philippe Schnoebelen (CNRS – ENS Paris-Saclay)
Jouko Väänänen (University of Helsinki)
Mathematics and theoretical computer science are closely connected by their interest in discrete phenomena, either the structural aspects that one can express through combinatorial properties, or algorithmic aspects, or finally, the numerous logical aspects. We concentrate on a specific part of this interaction, which is the study of the structural passage from the finite to the infinite structures. Traditionally, in combinatorics, this passage has been studied ever since the 1930s through the work of pioneers such as Paul Erdös, who compared the combinatorics of a single finite with a single infinite structure, for example through the Ramsey properties. In the last fifteen years or so, the emphasis has been on studying the infinite families of finite structures and the manner in which they are arranged to form an infinite one. This can be done either through the classical notion of the Fraïssé limit, through the Lovász’s notion of a graphon and connected notions of combinatorial limits studied by an ever-growing community of researchers, and finally, the set-theoretic limits such as the ones obtained by un ultraproduct or a morass. This type of question is what our school attempts to address. The school is the first, to our knowledge, to address this very timely topic from the point of view of both mathematics and theoretical computer science, with a half of the participants and speakers coming from each subject.
L’informatique théorique et les mathématiques s’approchent par leur intérêt dans les phénomènes discrètes, soit par d’aspects structurels exprimés par la combinatoire, soit par d’aspects algorithmiques, ou, finalement, par de nombreux aspects logiques. L’aspect spécifique de cette approche interdisciplinaire que nous adressons dans l’École est le passage des structures finies aux structures infinies. Ce passage est étudié classiquement depuis les années 30s du XXe siècle, par les mathématiciens tels que Paul Erdös, qui se concentrait, par exemple, sur les propriétés de Ramsey, en comparant une structure finie à une structure infinie. Dernièrement, disons dans les quinze ans précédents, il y a une tendance différente, ce qui est d’étudier une famille infinie de structures finies et la manière dont on peut les arranger pour former une structure infinie. Cela peut se faire par la notion classique de la limite de Fraïssé, par la notion de graphon par Lovász, aussi bien que par d’autres notions de limites combinatorielles – étudiées par un nombre important de chercheurs- ou éventuellement par des limites ensemblistes telles que les ultraproduits ou les morasses. La conférence s’intéresse par ce type de recherche. À notre connaissance, c’est la première fois qu’une école de recherche soit consacrée à ces questions par une approche interdisciplinaire entre les mathématiques et l’informatique. Une moitié de participants et de conférenciers provient des mathématiques et l’autre d’informatique théorique.
INTRODUCTION
The aim of this research school is to explore the view that computer scientists and mathematicians take on a theme that has proved to be of the interest to both communities. The general theme of the conference is the study of the _passage from the finite to the infinite_.
Traditionally, in combinatorics, this passage has been studied ever since the 1930s through the work of pioneers such as Paul Erdös, who compared the combinatorics of a single finite with a single infinite structure, for example through the Ramsey properties. In the last fifteen years or so, the emphasis has been on studying the _infinite families of finite structures_ and the manner in which they are arranged to form an infinite one. This can be done either through the classical notion of the Fraïssé limit, through the Lovász’s notion of a graphon and connected notions of combinatorial limits studied by an ever-growing community of researchers, and finally, the set-theoretic limits such as the ones obtained by an ultraproduct or a morass. This type of question is what our school attempts to address.
The main topic is twofold. Firstly, we can ask to what extent the properties of the limit influence the properties of the family that was used to build it. For example the algorithmic properties such as studied in computer science, or amalgamation properties such as studied in mathematics. It has turned out that the model-theoretic properties of the limit, studied in the classical model theory many years before any of these questions have been around, have an enormous influence on the finite objects that have been used to build it. It is only recently that these connections have been discovered and therefore it is very timely to expose the available knowledge in the form of a research school.
The other direction is, of course, the dual: to what extent the known properties of the family of the finite objects influence the structure of the infinite object that they form. This type of question has arisen in various parts of mathematics and in recent years has been studied mostly in logic and combinatorics, to be applied to questions coming from mathematical subjects as wide as theory of groups and topology. One can think of the founding paper 2003 of Kechris, Pestov and Todorčević, where they have characterised the Fraïssé families that lead to a limit whose automorphism group is amenable, much work on combinatorial limits and also the work on small and big Ramsey degrees.
Both directions offer a variety of interesting research questions and a novelty that is of interest to any researcher, but especially to a junior one trying to find an own direction of research.
If the two directions described are dual to each other, so are to a large extent the communities of interest, with the first type of questions being more of interest to the computer scientists and the second more to logicians and mathematicians. In both cases the relevant communities are faced with the lack of access to the knowledge of the other community, often with duplication of results spread in the journals whose lectureship is almost disjoint. Not only
that our programme will address the very interesting and timely scientific issues that we have mentioned above, but by bringing the mathematicians and the computer scientists together, it will also help close the gap in communication.
PLANNING
The School will have three main themes, involving model theory, graph theory and decidability theory.
• The interaction between the finite and the infinite model theory
• Automata, decidability and complexity
• Combinatorial and other limits and graph theory
We plan to have eight main speakers (4 from mathematics, 4 from theoretical computer science), so that each main topic will be covered by a mathematician and by a computer scientist. The programme will also include shorter talks and poster sessions by the participants, since the school will equally serve as a networking opportunity for them.
The programme will be organised as follows:
Monday, Tuesday, Thursday and Friday 2 x 50 min talks by the invited speakers (one mathematician, one computer scientist) + a selection of 30 minutes talks from the participants. The participants will be encouraged to break into smaller research and discussion groups as well and the schedule will be made so to allow this.
Wednesday morning: reserved to presentations by the junior participants. It will include 1 poster session and 6 talks of 20 minutes each.
Wednesday afternoon: free with an organised event visiting Marseille and a dinner in the city.
INVITED SPEAKERS
The 30 and 20 minutes talks presenters and poster session presenters will be selected from the suggestions of the confirmed participants closer to the time of the event. The following are the eight envisioned speakers for the 50 minutes lectures. They will be asked to prepare talks that correspond to a research school, so keeping in mind the benefit for the junior participants.
Patricia Bouyer-Decitre (Université Paris-Saclay, LMF)
(likely topic: timed automata, games)
Jouko Väänänen (University of Helsinki)
(likely topic: finite and infinite model theory)
Thomas Colcombet (CNRS, IRIF)
(likely topic: algebraic automata techniques and decision procedures)
Saharon Shelah (Hebrew University, Jerusalem)
(likely topic: decision procedures in logic)
Arnaud Durand (Université Paris Cité, IMJ)
(likely topic: finite model theory)
Nicole Schweikardt (Humbolt University, Berlin)
(likely topic: database theory)
Szymon Toruńczyk (University of Warsaw)
(likely topic: finite and infinite graphs)
Patrice Ossona de Mendez (CNRS, EHESS)
(likely topic: combinatorial limits)
SPONSORS
