François Pirot

Institutions G-SCOP (Grenoble, France)
Status Postdoctoral position under the supervision of Louis Esperet
Location Laboratoire G-SCOP, équipe OC, bureau H355, 46 Avenue Félix Viallet, 38000 Grenoble, France
Email
Links
Interests Graph Theory, Combinatorics, Probabilistic Methods

About me

I am currently holding a postdoctal position in the G-SCOP lab under the supervision of Louis Esperet. Before that, I have been a postdoctoral fellow in the Université Libre de Bruxelles under the supervision of Gwenaël Joret.

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 Ross Kang and Jean-Sébastien Sereni [manuscript, slides].

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.

Research

Talks

Teaching

Others

Submissions

  1. An algorithmic framework for colouring locally sparse graphs

    with Ewan Davies, Ross J. Kang, and Jean-Sébastien Sereni.
    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.
  2. Graph structure via local occupancy

    with Ewan Davies, Ross J. Kang, and Jean-Sébastien Sereni.
    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.
  3. Packing and covering balls in graphs excluding a minor

    with Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, and Carole Muller,
    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.
  4. Comma-free codes over finite alphabets

    with Elena Fimmel, Christian J. Michel, Jean-Sébastien Sereni, and Lutz Struengmann,
    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.
  5. Strong chromatic index and Hadwiger number

    with Wouter Cames van Batenburg, Rémi de Joannis de Verclos, and Ross J. Kang
    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$.
  6. Fractional chromatic number, maximum degree and girth

    with Jean-Sébastien Sereni,
    arXiv:1904.05618.
    Abstract
    We prove 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)$. We also demonstrate that every graph of girth at least $7$ and maximum degree $\Delta$ has fractional chromatic number at most $\min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}+k}{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]$.
  7. Occupancy fraction, fractional colouring, and triangle fraction

    with Ewan Davies, Rémi de Joannis de Verclos, and Ross J. Kang,
    arXiv:1812.11152.
    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.

Publications

  1. The relation between $k$-circularity and circularity of codes

    with Elena Fimmel, Christian J. Michel, Jean-Sébastien Sereni, Martin Starman, and Lutz Struengmann,
    To appear in the Bulletin of Mathematical Biology.
    HAL-02466859.
    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.
  2. Strong cliques and forbidden cycles

    with Wouter Cames van Batenburg and Ross J. Kang,
    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.
  3. Variations on the Petersen Colouring Conjecture

    with Jean-Sébastien Sereni and Riste Škrekovski,
    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.
  4. Colouring triangle-free graphs with local list sizes

    with Ewan Davies, Rémi de Joannis de Verclos, and Ross J. Kang,
    To appear in Random Structures & Algorithms.
    arXiv:1812.01534.
    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.
  5. Approximate strong edge-colouring of unit disk graphs

    with Rémi de Joannis de Verclos, Nicolas Grelier, and Ross J. Kang.
    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.
  6. Mixed Circular Codes

    with Elena Fimmel, Christian J. Michel, Jean-Sébastien Sereni, and Lutz Struengmann,
    Mathematical Biosciences, 2019, vol. 317, p. 108231.
    HAL-02188407.
    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.
  7. Bipartite induced density in triangle-free graphs

    with Wouter Cames van Batenburg, Rémi de Joannis de Verclos, and Ross J. Kang,
    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.
  8. Distance Colouring without one cycle length

    with Ross J. Kang,
    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).
  9. Coloring Powers and Girth

    with Ross J. Kang,
    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.