image/svg+xml Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui héberge deux équipes-projets Inria. Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques. L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), cinq sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences. Présentation Annuaire Contacts Suivre @IRIF_Paris Notion du jour Actualités 15.9.2020 IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Mikael Rabie, an expert in Distributed Computing, in particular on population protocols and distributed models on graphs. 11.9.2020 Thomas Vidick will give a series of lectures on Interactive proofs with quantum devices during his stay at IRIF funded by an FSMP chair, starting on Sep. 22 at IHP. 18.8.2020 IRIF is very pleased to host for 12 months starting in September 2020, Thomas Vidick, professor of computer science and mathematics at the California Institute of Technology. His research is at the interface of theoretical computer science, quantum information and cryptography. The invitation is funded by an FSMP chair together with DIENS, Inria and IRIF. Meet him in office 4024. 1.9.2020 The One World Numeration Seminar is an international online seminar on numeration systems and related topics organised by Wolfgang Steiner (IRIF). It has been well accepted by the community, and the second season starts with a talk by Bill Mance on September 1st. 28.8.2020 Delia Kesner (IRIF) will be on the panel of a debate on the future of the conference system in theoretical computer science, and organized as a special event as part of the Online Worldwide Seminar on Logic and Semantics (OWLS). The event will take place September 2, 5pm on Zoom. 4.9.2020 Baptiste Louf (just graduated from IRIF) has a paper co-authored with Thomas Budzinski published in Inventiones Mathematicae that proves a conjecture of Benjamini & Curien in discrete random geometry. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Événements Graphes Mardi 22 septembre 2020, 15 heures, Salle 3052 Rongxing Xu Multiple list colouring of $3$-choice critical graphs A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in 1998. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. It is true if $G=\Theta_{2,2,2,2}$, which was proved by Voigt and Tuza in 1996. However, this conjecture was disproved by Meng, Puleo, and Zhu in 2017. They showed that if $G=\Theta_{r,s,t}$ where $r,s,t$ have the same parity and $\min\{r,s,t\} \ge 3$, or $G=\Theta_{2,2,2,2p}$ with $p \ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo, and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.