 Pierre Aboulker

Département Informatique de l'ENS,
45 Rue d'Ulm,
75005 Paris  FRANCE.Tel: A remplir
Courriel: pierreaboulker@gmail.com
Short bio
Since 2018 I am an Assistant Professor in the Talgo (Theory, ALgorithms, Graphs, and Optimization) team at the Computer Science Department of École normale supérieure, Paris, France.Before: I have done my PhD with Nicolas Trotignon between 2010 and 2013. I have been a postdoc a Concordia University in Montréal with Vašek Chvátal, in Santiago de Chile at Andres Bello university with José Aliste, in SophiaAntipolis under the direction of Frédéric Havet, in Université Libre de Bruxelles under the direction of Samuel Fiorini and a I was an ATER in Université GrenobleAlpes.
Research interests
I am interested in graph theory (nonoriented and oriented), in some problems related to geometry in metric spaces and betweenness. I have also done incursions in combinatorial optimization and distributed algorithms.In graph theory I am particularly interested in substructures that must apear in a graph or a digraph with particular property. Typical examples: if a graph has large chromatic number, what can you say about its induced subgraphs? Or if a digraph has large minimum outdegree, what can we say about its subgraphs? In geometry, I mainly work on the ChenChvátal Conjecture, that proposes a vast generalisation of the geometric de BruijnErdös Theorem.
Published papers
Graphs that do not contain a cycle with a node that has at least two neighbors on it (P. Aboulker, M. Radovanovic, N. Trotignon, K. Vuskovic), SIAM Journal on Discrete Mathematics, 26(4):1510–1531, 2012.
Linear balanceable and subcubic balanceable graphs (P. Aboulker, M. Radovanovic, N. Trotignon, T. Trunck, K. Vuskovic), Journal of Graph Theory, 75: 15–166, 2013.
Excluding 4wheels, (P. Aboulker) Journal of Graph Theory, 75: 311–322, 2014.
Number of lines in hypergraphs (P. Aboulker, A. Bondy, X. Chen, E. Chiniforooshan, V. Chvátal, P. Miao) Journal of Graph Theory, 171: 137–140, 2014.
Excluding cycles with a fixed number of chords (P. Aboulker, N. Bousquet), Discrete Applied Mathematics, 180: pp. 11–24, 2015.
ChenChvàtal conjecture for distance hereditary graphs (P. Aboulker, R. Kapadia), European Journal of Combinatorics, 43: pp. 1–7, 2015.
Vertex elimination orderings for hereditary graph classes (P. Aboulker, P. Charbit, N. Trotignon, K. Vušković), Discrete Mathematics, 338(5): 825–834, 2015.
Wheelfree planar graphs (P. Aboulker, M. Chudnovsky, P. Seymour and N. Trotignon), European Journal of Combinatorics, 5767, 2015.
Excluding clock (P. Aboulker, Z. Li, S. Thomassé), Electronic Notes in Discrete Mathematics, pp. 103108, 2015.
Lines, metric spaces and betweenness (P. Aboulker, X. Chen, G. Huzhang, R. Kapadia, C. Supko), Discrete & Computational Geometry, 56.2, pp 427–448, 2016.
De BruijnErd\H{o}s type theorems for graphs and posets ( P. Aboulker, G. Lagarde, D. Malec, A. Methuku, C. Tompkins) submitted to Discrete Mathematics.
Colouring graphs with constraints on connectivity (P. Aboulker, N. Bretell, F. Havet, N. Trotignon).
A new class of graphs that satisfies the ChenChv\'atal Conjecture (P. Aboulker, M. Matamala, P. Rochet and J. Zamora).
Chibounded families of oriented graphs (P. Aboulker, J. BangJensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, J. Zamora).
A tight Erd\H{o}sP\'osa function for wheel minors (P. Aboulker, S. Fiorini, T. Huynh, G. Joret, J.F. Raymond et I. Sau)
Distributed coloring in sparse graphs with fewer colors (P. Aboulker, M. Bonamy, N. Bousquet, L. Esperet)
Submitted papers
Subdivisions in digraphs of large outdegree or large dichromatic number (P. Aboulker, N. Cohen, W. Lochet, F. Havet, P. Mourra, S. Thomassé).
Extension complexity of the correlation polytop (P. Aboulker, S. Fiorini, T.~Huynh, M.~Macchia, J.~Seif)
Manucripts
On wheelfree graphs, (P. Aboulker, F. Havet, N. Trotignon),
Enseignement
Initiation à la programmation pour noninformaticiens en Python
Graph Minor Theory and its algorithmic consequences. Supports:
 Graph Theory by Diestel This is a textbook on graph theory, chapter 12 can be used as companion notes for this class.
 Graph Minor Theory by Lovasz A short overview of graph minor theory. It is a particularly enlightening lecture, I strongly advice you to read it
 Slides of the course
 Notes and exercises for course 1
 List of subjects for presentation (you can also choose your on subject):
 Combinatorial Topology of Surfaces This article gives a classification of all surfaces. Graph embedding on surfaces play a crucial role in graph minor theory.
 Survey on Perfect Graphs This is a very nice survey on perfect graphs, it contains more then enough material for a beautiful presentation.
Some recent talks
Subdivisions in oriented graphs, JGA 2016, November 2016.
Subdivisions in oriented graphs, SIWAG, september 2016.
Configurations in oriented graphs, Workshop STINT, january 2016.
Lines induced by betweenness relations, Conference: Connection in Discrete mathematics, in Simon Fraiser University (Vancouver, Canada), June 2015
Excluding clocks, VIII LatinAmerican Algorithms, Graphs and Optimization Symposium, in Fortaleza, Brasil, Mai 2015.
Avancées sur la conjecture de ChenChvátal, JGA, Dijon, november 2014.
Lines, betweenness and metric spaces, STRUCO, Prague, octber 2014.
Avancées sur la conjecture de ChenChvátal, séminaire Algorithmique distribuée et Graphes, Paris VII, october 2014.
A generalisation of a de Bruijn Erdos Theorem, SIAM Conference on Discrete Math, Minneapolis, United states, june 2014
Graphs with no 4wheels, séminaire Optimisation Combinatoire du GSCOP (Grenoble), Avril 2012.
Around wheelfree graphs, séminaire Graphes et Structures Discrètes, ENS Lyon, Février 2012.
Autour des graphes sans roues, séminaire de Combinatoire Algébrique et Géométrique ( Paris 6), Décembre 2011.
Les graphes sans roues, JGA, Lyon, Novembre 2011.