Id Photo
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 post-doc a Concordia University in Montréal with Vašek Chvátal, in Santiago de Chile at Andres Bello university with José Aliste, in Sophia-Antipolis 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é Grenoble-Alpes.

Research interests

I am interested in graph theory (non-oriented 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 Chen-Chvátal Conjecture, that proposes a vast generalisation of the geometric de Bruijn-Erdö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 4-wheels, (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.

  • Chen-Chvà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.

  • Wheel-free planar graphs (P. Aboulker, M. Chudnovsky, P. Seymour and N. Trotignon), European Journal of Combinatorics, 57-67, 2015.

  • Excluding clock (P. Aboulker, Z. Li, S. Thomassé), Electronic Notes in Discrete Mathematics, pp. 103-108, 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 Bruijn-Erd\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 Chen-Chv\'atal Conjecture (P. Aboulker, M. Matamala, P. Rochet and J. Zamora).

  • Chi-bounded families of oriented graphs (P. Aboulker, J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, J. Zamora).

  • A tight Erd\H{o}s-P\'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 out-degree 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 wheel-free graphs, (P. Aboulker, F. Havet, N. Trotignon),

    Enseignement

  • Algorithmique et programmation

  • Initiation à la programmation pour non-informaticiens en Python

    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 Latin-American Algorithms, Graphs and Optimization Symposium, in Fortaleza, Brasil, Mai 2015.

  • Avancées sur la conjecture de Chen-Chvátal, JGA, Dijon, november 2014.

  • Lines, betweenness and metric spaces, STRUCO, Prague, octber 2014.

  • Avancées sur la conjecture de Chen-Chvá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 4-wheels, séminaire Optimisation Combinatoire du G-SCOP (Grenoble), Avril 2012.

  • Around wheel-free 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.

    Quelques liens

  • La page personnelle de Nicolas Trotignon mon directeur de thèse.
  • Excellent blog sur la chanson française.