“Ma thèse s'intéresse à la coloration de graphes dirigés. Un graphe, c'est juste un ensemble de trucs, que l'on appelle des sommets, ainsi que des paires de trucs, qu'on appelle des arêtes. Par exemple, on peut considérer le graphe dont les sommets correspondent à des utilisateurs d'un réseau social, et dont les arêtes sont les paires d'utilisateurs qui sont amis.” Guillaume Aubian, ancien doctorant.
Lien de sa thèse : Colouring Digraphs

Je m'appelle Guillaume Aubian. Originaire des Pyrénées, j'ai intégré l'ENS Cachan en 2014. Mon parcours m'a conduit au M2 Master Parisien de Recherche en Informatique (MPRI) à l'ENS Paris-Saclay, durant lequel j'ai particulièrement apprécié le cours de Pierre Aboulker. Celui-ci a alors accepté de me prendre en thèse, avec Pierre Charbit.

Depuis mon enfance, j'ai toujours été passionné par les énigmes et les casse-tête mécaniques, comme le Rubik's Cube. En grandissant, mon intérêt s'est tourné vers les compétitions d'algorithmique et les Escape Games. C'est ainsi que l'idée de résoudre des problèmes abstraits de manière professionnelle m'a attiré. Après ma prépa, cherchant à être financièrement indépendant, j'ai choisi d'aller à l'ENS, qui offre une rémunération à ses étudiants, tout en m'ouvrant des opportunités en R&D. Après un premier M2, je suis donc parti chez Google, que j'ai quitté un an et demi plus tard pour faire le MPRI. Comme j'avais adoré mon stage de L3 en théorie des graphes avec Stéphan Thomassé, j'ai pris tous les cours qui touchaient de près ou de loin aux graphes, pour continuer en thèse par la suite.

Ma thèse s'intéresse à la coloration de graphes dirigés. Un graphe, c'est juste un ensemble de trucs, que l'on appelle des sommets, ainsi que des paires de trucs, qu'on appelle des arêtes. Par exemple, on peut considérer le graphe dont les sommets correspondent à des utilisateurs d'un réseau social, et dont les arêtes sont les paires d'utilisateurs qui sont amis. Mais on peut aussi considérer le graphe dont les sommets sont des villes et les arêtes correspondent à des routes reliant des paires de villes, ou le graphe dont les sommets sont des pays avec une arête pour chaque paire de pays frontaliers. C'est donc un objet très général, et un théorème/algorithme qui manipule des graphes peut aussi bien être utilisé pour des réseaux routiers, des réseaux sociaux, des cartes du monde etc. Dans la vraie vie, pour coller aux différentes application, on va parfois vouloir élargir un peu la définition des graphes : ça peut se faire par exemple en mettant des poids sur les arêtes ou sur les sommets, en autorisant des arêtes entre plusieurs sommets ou encore en mettant des directions sur les arêtes. Dans ce dernier cas, on parle de graphes dirigés.

Un des concepts les plus importants en théorie des graphes est celui de coloration : colorer un graphe, c'est assigner une couleur à chaque sommet de façon à ce que les sommets reliés par une arête aient des couleurs distinctes. La coloration de graphes a connu de nombreuses applications : l'assignation de fréquences radios, l'allocation de registres en compilation etc. Quelle serait une notion équivalente pour les graphes dirigés ? En 1982, Victor Neumann-Lara a proposé une telle notion qui semble depuis s'imposer : colorer un graphe dirigé, c'est assigner une couleur à chaque sommet de sorte à ce qu'il n'y ait pas de cycle dirigé d'une seule couleur. Depuis, beaucoup ont cherché à traduire des théorèmes sur la coloration des graphes aux graphes non-dirigés en utilisant cette notion, et ma thèse s'inscrit dans cette droite lignée.

Durant ma thèse, j'ai essayé de m'attaquer à des problèmes divers sur la coloration et les graphes dirigés. Néanmoins, un problème en particulier se retrouve dans quasiment la moitié des articles écrits durant ma thèse, et a captivé une grande partie de mon travail durant ces trois années. Mais pour l'introduire, revenons aux graphes non-orientés : une des grandes interrogations en théorie des graphes est de savoir à quoi ressemblent les graphes qui ne peuvent pas être colorés avec peu de couleurs. Par exemple, on peut se demander quels autres graphes on peut trouver dans de tels graphes : c'est le sens de la conjecture de Gyárfás-Sumner, un problème très important et largement ouvert. Il y a quelques années, mes directeurs de thèse, accompagnés de Reza Naserasr, ont entrepris une démarche similaire pour les graphes dirigés, et sont arrivés à une conjecture raisonnable cherchant à caractériser quels graphes dirigés se retrouvent dans les graphes dirigés durs à colorier. Durant ma thèse, j'ai résolu plusieurs instances de cette conjecture, en démontrant que certaines classes naturelles de graphes dirigés pouvaient être colorés avec peu de couleurs. Inversement, j'ai aussi trouvé une classe de graphes dirigés dont il était conjecturée qu'elle pouvait être colorée avec peu de couleurs, et ai réfuté ceci.

À rien, ou presque, les applications étant encore rares et souvent anecdotiques. Néanmoins, il y a des raisons d'espérer qu'on puisse à terme trouver des applications concrètes : la coloration de graphes a connu de très nombreuses applications, et comme notre notion généralise celle-ci, on peut espérer un jour ouvrir de nouvelles perspectives. Il faudra probablement d'abord que la notion soit plus développée, mais aussi plus connue. Je pense qu'on en est encore aux balbutiements et j'aimerais beaucoup participer à faire émerger de telles applications.

À Google, je travaillais sur la détection automatique de violations de droits d'auteur dans les vidéos, ce qui est assez éloigné de ce que j'ai fait en thèse. Même si c'était intéressant, je ne m'y plaisais pas autant que je l'aurais espéré, notamment car il n'y avait pas beaucoup de recherche, d'où mon choix d'arrêter pour faire une thèse. Je ne pense pas que ça ait joué un rôle dans mon choix de sujet de thèse, mais je pense par contre que mon profil de codeur a été une grande force durant ma thèse, puisque j'ai souvent eu l'occasion d'écrire des programmes pour m'aider dans mes preuves : le fait de savoir coder rapidement et efficacement est nécessaire pour intégrer cet outil dans une démarche de recherche.

Je commence un postdoc à l'Université Charles (à Prague) avec Zdeněk Dvořák dès septembre. Après ce postdoc, j'aimerais rentrer en France pour continuer la recherche dans le monde académique.