## Welcome

IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, also hosting one Inria project-team.

The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences.

IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), five are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences.

## Notion of the day

## News

*14.9.2021*

Eugene Asarin (IRIF), Thomas Ferrère, Dejan Ničković and Dogan Ulus receive the **Oded Maler best paper award in Timed Systems** at the conference Formats’2021 for their paper On the complexity of timed pattern matching.

*27.4.2020*

Claire Mathieu (IRIF) has been interviewed by the online news site of CNRS about using graphs to devise a lockdown exit strategy.

*7.9.2021*

IRIF is very pleased to host for three months Sergio Rajsbaum, **full time Researcher** at the Instituto de Matemáticas of the Universidad Nacional Autónoma de México.
This collaboration focuses on the use of **algebraic topology** to study the complexity of distributed algorithms. Algebraic topology tools have been mainly used for shared memory models. The purpose of the visit is to extend this research to **distributed memory models**. Professor Rajsbaum is partially funded by an invitational program from École Polytechnique. Meet him in **office 4028a**.

*3.9.2021*

Guillaume Aubian, Pierre Charbit (IRIF) and Pierre Aboulker study the class of oriented graphs such that the out-neighbourhood of any vertex induces a transitive tournament and prove for it a decomposition theorem. As a consequence, they obtain that oriented graphs in this class have dichromatic number at most $2$ and satisfy Caccetta-Häggkvist conjecture.

*24.8.2021*

Dans le cadre d’un mini-cours donné au 86ème séminaire Lotharingien de combinatoire, Guillaume Chapuy (IRIF) parlera d'un nouveau point de vue sur la **correspondance entre cartes et tableaux de Young**, qui joue un rôle fondamental en combinatoire algébrique. Ce nouveau point de vue, développé dans le cadre des **polynômes de Jack et des surfaces non-orientables**, est issu de ses travaux avec Maciek Dołęga (ancien postdoctorant à l'IRIF/LIAFA).

*3.9.2021*

Yiting Jiang (IRIF) and Jaroslav Nešetřil will present a result that there are infinitely many minimal **asymmetric k-uniform hypergraphs.**

*3.9.2021*

Amos Korman et Robin Vacus (IRIF) publient On the Role of Hypocrisy in Escaping the Tragedy of the Commons dans la revue Scientific Reports. Dans cet article, ils étudient l'émergence de la coopération dans le cadre formel de la théorie des jeux. Ils considèrent 3 comportements stéréotypés : “tricheur”, “hypocrite” et “coopératif”, et un modèle de pression sociale.

*3.9.2021*

Reza Naserasr (IRIF) is an invited speaker at the 29th Workshop on Cycles and Colourings. He will present a joint work with Lan Anh Pham (IRIF), Zhouningxin Wang PhD student (IRIF) and Xuding Zhu (University Jinchua): Density of C –4 -critical signed graphs. There is a classic one-to-one correspondence between (2k+1)-colorability of a graph and mapping of a specific subdivision of it to the (2k+1)-cycle. In this work they present an extension of this to 2k-coloring using homomorphisms of signed graphs.

(These news are displayed using a randomized-priority ranking.)

## Events

**Limited number of events during the Summer break.**

Semantics

Tuesday September 21, 2021, 11AM, Exposé à distance sur Galène – salle 3052 virtuelle

**Tom Hirschowitz** (CNRS, Université Savoie Mont Blanc) *A categorical framework for congruence of applicative bisimilarity [Part one]*

One world numeration seminar

Tuesday September 21, 2021, 2:30PM, Online

**Maria Siskaki** (University of Illinois at Urbana-Champaign) *The distribution of reduced quadratic irrationals arising from continued fraction expansions*

Enumerative and analytic combinatorics

Thursday September 23, 2021, 2PM, Salle 1007

**Séverin Charbonnier** (IRIF) *Weighted enumeration of ciliated maps and applications*

I will first describe the ciliated maps and their weighted enumeration. Second, I will detail Tutte's equation and state how the generating functions are computed via topological recursion. Last, I will discuss applications of this result to intersection theory of Witten's class, to the enumeration of fully simple maps and to free probabilities.

In collaboration with Raphaël Belliard, Gaëtan Borot, Bertrand Eynard and Elba Garcia-Failde.

Graph Transformation Theory and Applications

Friday September 24, 2021, 3PM, online

**Romain Pascual** (MICS laboratory, CentraleSupélec, University Paris-Saclay, France) *Combinatorial maps: transformations and application to geometric modeling*