# François Pirot

Institutions Status Location Email Links Interests LISN (ex LRI) Maître de Conférences (Associate Professor) Equipe GALaC, bâtiment 650 (PCRI), bureau 235 CV ResearchGate ORCID dblp Scholar arXiv Graph Theory, Combinatorics, Probabilistic Method

Since September $1^\mbox{st}$ 2021, I am an associate professor (maître de conférences) in Université Paris-Saclay. I am doing my research at the LISN in the team GALaC, and I am teaching at the Faculté des Sciences d'Orsay.

Before that, I have held three postdoctoral positions.

• 01/09/2019 $-$ 30/11/2019:  Three months postdoc at the ULB under the supervision of .
• 01/12/2019 $-$ 30/10/2020:  One year postdoc in the G-SCOP lab under the supervision of .
• 01/11/2020 $-$ 31/08/2021:  One year postdoc in Inria Sophia Antipolis under the supervision of .

I have obtained the degree of doctor in Mathematics from Radboud University, and in Computer Sciences from the Université de Lorraine, on 04/11/2019. My PhD has been supervised by [manuscript, slides]. My thesis has been awarded the prize Charles Delorme, which honours each year an outstanding thesis in Graph Theory.

My main research activities focus on the colouring problem in various contexts, including graph powers, locally sparse graphs, distributed colouring, randomised algorithms. I have also worked on problems from Bio-Informatics related to circular codes, using efficient graph theoretical tools.

## Preprints

• ### Acyclic colourings of graphs with obstructions

with .
arXiv:2211.08417.
Abstract
Given a graph $G$, a colouring of $G$ is acyclic if it is a proper colouring of $G$ and every cycle contains at least three colours. Its acyclic chromatic number $\chi_a(G)$ is the minimum $k$ such that there exists a proper $k$-colouring of $G$ with no bicoloured cycle. In general, when $G$ has maximum degree $\Delta$, it is known that $\chi_a(G) = O(\Delta^{4/3})$ as $\Delta \to \infty$. We study the effect on this bound of further requiring that $G$ does not contain some fixed subgraph $F$ on $t$ vertices. We establish that the bound is constant if $F$ is a subdivided tree, $O(t^{8/3}\Delta^{2/3})$ if $F$ is a forest, $O(\sqrt{t}\Delta)$ if $F$ is bipartite and 1-acyclic, $2\Delta + o(\Delta)$ if $F$ is an even cycle of length at least $6$, and $O(t^{1/4}\Delta^{5/4})$ if $F=K_{3,t}$.
• ### Colouring locally sparse graphs with the first moment method

with .
arXiv:2109.15215.
Abstract
We give a short proof of a bound on the list chromatic number of graphs $G$ of maximum degree $\Delta$ where each neighbourhood has density at most $d$, namely $\chi_\ell(G) \le (1+o(1)) \frac{\Delta}{\ln \frac{\Delta}{d+1}}$ as $\frac{\Delta}{d+1} \to \infty$. This bound is tight up to an asymptotic factor $2$, which is the best possible barring a breakthrough in Ramsey theory, and strengthens results due to Vu, and more recently Davies, P., Kang, and Sereni. Our proof relies on the first moment method, and adapts a clever counting argument developed by Rosenfeld in the context of non-repetitive colourings. As a final touch, we show that our method provides an asymptotically tight lower bound on the number of colourings of locally sparse graphs.
• ### An algorithmic framework for colouring locally sparse graphs

with .
arXiv:2004.07151.
Abstract
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $\Delta$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le \Delta^\frac{2\varepsilon}{1+2\varepsilon}/(\log\Delta)^2$, with $\lfloor(1+\varepsilon)\Delta/\log(\Delta/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs.
• ### Graph structure via local occupancy

with .
arXiv:2003.14361.
Abstract
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lovász local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.
• ### Comma-free codes over finite alphabets

with .
HAL-02376793.
Abstract
Comma-free codes have been widely studied in the last sixty years, from points of view as diverse as biology, information theory and combinatorics. We develop new methods to study comma-free codes achieving the maximum size, given the cardinality of the alphabet and the length of the words. Specifically, we are interested in counting the number of such codes. We provide (two different proofs for) a closed-formula. The approach introduced is further developed to tackle well-known sub-families of comma-free codes, such as self-complementary and (generalisations of) non-overlapping codes. We also study codes that are not contained in strictly larger ones. For instance, we determine the maximal size of self-complementary comma-free codes and the number of codes reaching the bound. We provide a characterisation of $\ell$-letter non-overlapping codes (over an alphabet of cardinality $n$), which allows us to devise the number of such codes that are not contained in any strictly larger one. Our approach mixes combinatorial and graph-theoretical arguments.

## Accepted papers

• ### Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces

with .
To appear in Journal of the European Mathematical Society (JEMS).
arXiv:2012.02435.
Abstract
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science.
We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours.

## Conference papers

• ### Uniformly random colourings of sparse graphs

with .
STOC 2023
arXiv:2303.15367.
Abstract
We analyse uniformly random proper $k$-colourings of sparse graphs with maximum degree $\Delta$ in the regime $\Delta < k\ln k$. This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example of the shattering threshold for random Constraint Satisfaction Problems. We prove a variety of results about the solution space geometry of colourings of fixed graphs, generalising work of Achlioptas, Coja-Oghlan, and Molloy on random graphs, and justifying the performance of stochastic local search algorithms in this regime. Our central proof relies only on elementary techniques, namely the first-moment method and a quantitative induction, yet it strengthens list-colouring results due to Vu, and more recently Davies, Kang, P., and Sereni, and generalises state-of-the-art bounds from Ramsey theory in the context of sparse graphs. It further yields an approximately tight lower bound on the number of colourings, also known as the partition function of the Potts model, with implications for efficient approximate counting.
• ### Distributed algorithms for fractional coloring

with .
Structural Information and Communication Complexity, SIROCCO 2021, Lecture Notes in Computer Science, vol 12810.
arXiv:2012.01752.
Abstract
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, Hirvonen, Rybicki and Suomela (2016) that for every real $\alpha>1$ and integer $\Delta$, a fractional coloring of total weight at most $\alpha(\Delta+1)$ can be obtained deterministically in a single round in graphs of maximum degree $\Delta$, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colorings of total weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. More precisely, we show that for any fixed $\varepsilon > 0$ and $\Delta$, a fractional coloring of total weight at most $\Delta+\varepsilon$ can be found in $O(\log^*n)$ rounds in graphs of maximum degree $\Delta$ with no $K_{\Delta+1}$, while finding a fractional coloring of total weight at most $\Delta$ in this case requires $\Omega(\log \log n)$ rounds for randomized algorithms and $\Omega( \log n)$ rounds for deterministic algorithms. We also show how to obtain fractional colorings of total weight at most $2+\varepsilon$ in grids of any fixed dimension, for any $\varepsilon>0$, in $O(\log^*n)$ rounds. Finally, we prove that in sparse graphs of large girth from any proper minor-closed family we can find a fractional coloring of total weight at most $2+\varepsilon$, for any $\varepsilon>0$, in $O(\log n)$ rounds.
• ### Approximate strong edge-colouring of unit disk graphs

with .
Approximation and Online Algorithms, WAOA 2019, Lecture Notes in Computer Science, vol. 11926.
Extended abstract.
Abstract
We show that the strong chromatic index of unit disk graphs is efficiently $6$-approximable. This improves on $8$-approximability as shown by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan (2006). We also show that strong edge-$6$-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time $(7/6 — \varepsilon)$-approximation unless P=NP.

## Journal papers

• ### Strong chromatic index and Hadwiger number

with .
Journal of Graph Theory, 2021.
arXiv:1905.06031.
Abstract
We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each $k\ge 4$ that any $K_k$-minor-free multigraph of maximum degree $\Delta$ has strong chromatic index at most $\frac32(k-2)\Delta$. We present a construction certifying that if true the conjecture is asymptotically sharp as $\Delta\to\infty$. In support of the conjecture, we show it in the case $k=4$ and prove the statement for strong clique number in place of strong chromatic index. By contrast, we make a basic observation that for $K_k$-minor-free simple graphs, the problem of strong edge-colouring is "between" Hadwiger's Conjecture and its fractional relaxation. We also treat $K_k$-minor-free multigraphs of edge-diameter at most $2$.
• ### Fractional chromatic number, maximum degree and girth

with .
SIAM Journal on Discrete Mathematics, 2021, vol. 35, no 4, p. 2815–2843.
arXiv:1904.05618.
Abstract
We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree $\Delta \ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of $\Delta$, and improves it when $\Delta\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of $\Delta$, we also demonstrate that every graph of girth at least $7$ and maximum degree $\Delta$ has fractional chromatic number at most $1+ \min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth $7$ and maximum degree $\Delta$ is at most $\frac{2\Delta+9}{5}$ when $\Delta \in [3,8]$, at most $\frac{\Delta+7}{3}$ when $\Delta \in [8,20]$, at most $\frac{2\Delta+23}{7}$ when $\Delta \in [20,48]$, and at most $\frac{\Delta}{4}+5$ when $\Delta \in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree $\Delta \in \{3,4,5\}$ and girth $g\in \{6,\dotsc,12\}$, notably $1/3$ when $(\Delta,g)=(4,10)$ and $2/7$ when $(\Delta,g)=(5,8)$.
• ### Occupancy fraction, fractional colouring, and triangle fraction

with .
Journal of Graph Theory, 2021, vol. 97, no 4, p. 557–568.
Abstract
Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le Δ^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $Δ$ in which the neighbourhood of every vertex in $G$ spans at most $Δ^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/Δ)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\varepsilon)Δ/\log f$. These bounds cannot in general be improved by more than a factor $2$ asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model.
• ### Packing and covering balls in graphs excluding a minor

with .
Combinatorica, 2021, vol. 41, no 3, p. 299–318.
arXiv:2001.04517.
Abstract
We prove that for every integer $t\ge 1$ there exists a constant $c_t$ such that for every $K_t$-minor-free graph $G$, and every set $S$ of balls in $G$, the minimum size of a set of vertices of $G$ intersecting all the balls of $S$ is at most $c_t$ times the maximum number of vertex-disjoint balls in $S$. This was conjectured by Chepoi, Estellon, and Vaxès in 2007 in the special case of planar graphs and of balls having the same radius.
• ### The relation between $k$-circularity and circularity of codes

with .
Bulletin of Mathematical Biology, 2020, vol. 82, 105.
Abstract
A code $X$ is $k$-circular if any concatenation of at most $k$ words from $X$, when read on a circle, admits exactly one partition into words from $X$. It is circular if it is $k$-circular for every integer $k$. While it is not a priori clear from the definition, there exists, for every pair $(n,\ell)$, an integer $k$ such that every $k$-circular $\ell$-letter code over an alphabet of cardinality $n$ is circular, and we determine the least such integer $k$ for all values of $n$ and $\ell$. The $k$-circular codes may represent an important evolutionary step between the circular codes, such as the comma-free codes, and the genetic code.
• ### Colouring triangle-free graphs with local list sizes

with .
Random Structures & Algorithms, 2020, vol. 57, p. 730–744.
Abstract
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.
• ### Strong cliques and forbidden cycles

with .
Indagationes Mathematicae, 2020, vol. 31, no 1, p. 64–82.
Public full-text.
Abstract
Given a graph $G$, the strong clique number $\omega_2'(G)$ of $G$ is the cardinality of a largest collection of edges every pair of which are incident or connected by an edge in $G$. We study the strong clique number of graphs missing some set of cycle lengths. For a graph $G$ of large enough maximum degree $\Delta$, we show among other results the following: $\omega_2'(G)\le5\Delta^2/4$ if $G$ is triangle-free; $\omega_2'(G)\le3(\Delta-1)$ if $G$ is $C_4$-free; $\omega_2'(G)\le\Delta^2$ if $G$ is $C_{2k+1}$-free for some $k\ge 2$. These bounds are attained by natural extremal examples. Our work extends and improves upon previous work of Faudree, Gyárfás, Schelp and Tuza (1990), Mahdian (2000) and Faron and Postle (2019). We are motivated by the corresponding problems for the strong chromatic index.
• ### Variations on the Petersen Colouring Conjecture

with .
Electronic Journal of Combinatorics, 2020, vol. 27, no 1, paper 1.8.
Abstract
The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with $5$ colours such that for every edge $e$, the set of colours assigned to the edges adjacent to $e$ has cardinality either $2$ or $4$, but not $3$. We prove that every bridgeless cubic graph $G$ admits an edge-colouring with $4$ colours such that at most $\frac45\cdot|V(G)|$ edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a $4$-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.
• ### Bipartite induced density in triangle-free graphs

with .
Electronic Journal of Combinatorics, 2020, vol. 27, no 2, paper 2.34.
Abstract
Any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$. This is sharp up to a logarithmic factor in $n$. We also provide a related extremal result for the fractional chromatic number.
• ### Mixed Circular Codes

with .
Mathematical Biosciences, 2019, vol. 317, p. 108231.
Public full-text.
Abstract
By an extensive statistical analysis in genes of bacteria, archaea, eukaryotes, plasmids and viruses, a maximal $C^3$-self-complementary trinucleotide circular code has been found to have the highest average occurrence in the reading frame of the ribosome during translation. Moreover, dinucleotide circular codes have been observed in non-coding regions of eukaryotic genomes. By using a graph-theoretical approach of circular codes recently developed, we study mixed circular codes $X \subseteq \mathcal{B}_2 \cup \mathcal{B}_3 \cup \mathcal{B}_4$, which are the union of a dinucleotide circular code $X_2 \subseteq \mathcal{B}_2$, a trinucleotide circular code $X_3 \subseteq \mathcal{B}_3$ and a tetranucleotide circular code $X_4 \subseteq \mathcal{B}_4$ where $\mathcal{B} = \{A, C, G, T\}$ is the $4$-letter genetic alphabet. Maximal mixed circular codes $X$ of (di,tri)- nucleotides, (tri,tetra)-nucleotides and (di,tri,tetra)-nucleotides are constructed, respectively. In particular, we show that any maximal dinucleotide circular code $D \subseteq \mathcal{B}_2$ of size $6$ can be embedded into a maximal mixed circular code $X \subseteq \mathcal{B}_2 \cup \mathcal{B}_3$ such that $X \cap \mathcal{B}_3$ is a maximal $C^3$-comma-free code. The growth function of self-complementary mixed circular codes of dinucleotides and trinucleotides is given. Self-complementary mixed circular codes could have been involved in primitive genetic processes and an evolutionary model based on mixed circular codes is also proposed.
• ### Distance Colouring without one cycle length

with .
Combinatorics, Probability and Computing, 2018, vol. 27, no 5, p. 794–807.
Abstract
We consider distance colourings in graphs of maximum degree at most $d$ and how excluding one fixed cycle of length $\ell$ affects the number of colours required as $d \to \infty$. For vertex-colouring and $t \geqslant 1$, if any two distinct vertices connected by a path of at most $t$ edges are required to be coloured differently, then a reduction by a logarithmic (in $d$) factor against the trivial bound $O(d^t)$ can be obtained by excluding an odd cycle length $\ell \geqslant 3t$ if $t$ is odd or by excluding an even cycle length $\ell \geqslant 2t+2$. For edge-colouring and $t\geqslant 2$, if any two distinct edges connected by a path of fewer than $t$ edges are required to be coloured differently, then excluding an even cycle length $\ell \geqslant 2t$ is sufficient for a logarithmic factor reduction. For $t\geqslant 2$, neither of the above statements are possible for other parity combinations of $\ell$ and $t$. These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014).
• ### Coloring Powers and Girth

with .
SIAM Journal on Discrete Mathematics, 2016, vol. 30, no 4, p. 1938–1949.
Public full-text.
Abstract
Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi(G^t)$, the chromatic number of the $t$-th power of $G$? For $t\geqslant 3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $d\to \infty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.