Rémi de Verclos

remi.de.joannis.de.verclos at ens-lyon.org

I obtained my Ph.D. in Computer Science at the G-SCOP Laboratory in Grenoble in 2018. Until November 2020, I was postdoctoral researcher at the Department of Mathematics of Radboud University in Nijmegen.

I like solving math problems, programming and learning new things.

Research

Research interests

I am interested in all aspects of theoretical computer science and discrete mathematics. In the past, I worked for instance on the following topics:

• Graph theory, and particularly graph coloring
• Probabilistic methods
• Algorithms
• Extremal combinatorics
• Graph limits
• Computational Geometry
• Complexity Theory
• Property Testing

Phd Thesis

I did my PhD in G-SCOP Laboratory (Université Grenoble Alpes), under the supervision of Louis Esperet and Jean-Sébastien Sereni. The thesis explores the connections of three topics with limits of combinatorial objects: property testing, computational geometry and flag algebras.

Scientific publications

• Improving Ultrametrics Embeddings Through Coresets

with and . International Conference on Machine Learning (ICML 2021)
• An improved procedure for colouring graphs of bounded local density

with and . SODA 2021 arxiv:2007.07874
Abstract

We develop an improved bound for the chromatic number of graphs of maximum degree $\Delta$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-\sigma)\binom{\Delta}{2}$ for some fixed $0<\sigma<1$. The leading term in the reduction of colours achieved through this bound is best possible as $\sigma\to0$. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erdős-Nešetřil conjecture and Reed's conjecture. We prove that the strong chromatic index is at most $1.772\Delta^2$ for any graph $G$ with sufficiently large maximum degree $\Delta$. We prove that the chromatic number is at most $\lceil 0.881(\Delta+1)+0.119\omega\rceil$ for any graph $G$ with clique number $\omega$ and sufficiently large maximum degree $\Delta$. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-\sigma)\Delta$, and establish what may be considered first progress towards a conjecture of Vu.

• Regular Turán numbers and some Gan-Loh-Sudakov-type problems

with and . arxiv:1911.08452
Abstract

Motivated by a Gan-Loh-Sudakov-type problem, we introduce the regular Turán numbers, a natural variation on the classical Turán numbers for which the host graph is required to be regular. Among other results, we prove a striking supersaturation version of Mantel's theorem in the case of a regular host graph of odd order. We also characterise the graphs for which the regular Turán numbers behave classically or otherwise.

• Approximate strong edge-colouring of unit disk graphs

with , and . WAOA 2019, Lecture Notes in Computer Science
• Bipartite induced density in triangle-free graphs

with , and . Electronic Journal of Combinatorics arxiv:1808.02512
Abstract

We prove that 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$. Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of $n/d$ and $(2+o(1))\sqrt{n/\log n}$ as $n\to\infty$. This is sharp up to constant factors. Similarly, we show that the list chromatic number of any such triangle-free graph is at most $O(\min\{\sqrt{n},(n\log n)/d\})$ as $n\to\infty$.
Relatedly, we also make two conjectures. First, any triangle-free graph on $n$ vertices has fractional chromatic number at most $(\sqrt{2}+o(1))\sqrt{n/\log n}$ as $n\to\infty$. Second, any triangle-free graph on $n$ vertices has list chromatic number at most $O(\sqrt{n/\log n})$ as $n\to\infty$.

• Occupancy fraction, fractional colouring, and triangle fraction

with , and . arxiv:1812.11152
Abstract

Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le \Delta^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $\Delta$ in which the neighbourhood of every vertex in $G$ spans at most $\Delta^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/\Delta)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\varepsilon)\Delta/\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.

• Colouring triangle-free graphs with local list sizes

with , and . 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.

• Chordal graphs are easily testable

Single author paper. arxiv:1902.06135
Abstract

We prove that the class of chordal graphs is easily testable in the following sense. There exists a constant $c>0$ such that, if adding/removing at most $\epsilon n^2$ edges to a graph $G$ with $n$ vertices does not make it chordal, then a set of $(1/\epsilon)^c$ vertices of $G$ chosen uniformly at random induces a graph that is not chordal with probability at least $1/2$. This answers a question of Gishboliner and Shapira.

• Chromatic structure in triangle-free graphs

with , , , and . arxiv:1912.13328
Abstract

Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $χ$ contains a rainbow independent set of size $\lceil\frac12χ\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $χ$ contains an induced cycle of length $Ω(χ\logχ)$ as $χ\to\infty$. Even if one only demands an induced path of length $Ω(χ\logχ)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with "triangle-free" replaced by "regular girth $5$".

• Strong chromatic index and Hadwiger number

with , and . 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 $Δ$ has strong chromatic index at most $\frac32(k-2)Δ$. We present a construction certifying that if true the conjecture is asymptotically sharp as $Δ\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$.

• Exact distance coloring in trees

with , and . Combinatorics, Probability and Computing arxiv:1703.06047
Abstract

For an integer $q\ge 2$ and an even integer $d$, consider the graph obtained from a large complete $q$-ary tree by connecting with an edge any two vertices at distance exactly $d$ in the tree. This graph has clique number $q+1$, and the purpose of this short note is to prove that its chromatic number is $\Theta\big(\tfrac{d \log q}{\log d}\big)$. It was not known that the chromatic number of this graph grows with $d$. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant $C$ such that for any odd integer $d$, any planar graph can be colored with at most $C$ colors such that any pair of vertices at distance exactly $d$ have distinct colors. Finally, we study interval coloring of trees (where vertices at distance at least $d$ and at most $cd$, for some real $c>1$, must be assigned distinct colors), giving a sharp upper bound in the case of bounded degree trees.

• Additive bases and flows in graphs

with , and . SIAM Journal on Discrete Mathematics arxiv:1701.03366
Abstract

It was conjectured by Jaeger, Linial, Payan, and Tarsi in 1992 that for any prime number $p$, there is a constant $c$ such that for any $n$, the union (with repetition) of the vectors of any family of $c$ linear bases of $\mathbb{Z}_p^n$ forms an additive basis of $\mathbb{Z}_p^n$ (i.e. any element of $\mathbb{Z}_p^n$ can be expressed as the sum of a subset of these vectors). In this note, we prove this conjecture when each vector contains at most two non-zero entries. As an application, we prove several results on flows in highly edge-connected graphs, extending known results. For instance, assume that $p\ge 3$ is a prime number and $\vec{G}$ is a directed, highly edge-connected graph in which each arc is given a list of two distinct values in $\mathbb{Z}_p$. Then $\vec{G}$ has a $\mathbb{Z}_p$-flow in which each arc is assigned a value of its own list.

• Colouring squares of claw-free graphs

with and . Canadian Journal of Mathematics arxiv:1609.08645
Abstract

Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\chi(G^2) \le (2-\varepsilon) \omega(G)^2$, where $\omega(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erdős and Nešetřil.

• Equitable Colorings of $K_4$-minor-free Graphs

with . Journal of Graph Algorithms and Applications arxiv:1703.02250
Abstract

We demonstrate that for every positive integer $\Delta$, every $K_4$-minor-free graph with maximum degree $\Delta$ admits an equitable coloring with k colors wherek $\ge$ ($\Delta$+3)/2. This bound is tight and confirms a conjecture by Zhang and Whu. We do not use the discharging method but rather exploit decomposition trees of $K_4$-minor-free graphs.

• Limits of order-types

with , , and . 31st International Symposium on Computational Geometry (SOCG 2015) arxiv:1811.02236
Abstract

We apply ideas from the theory of limits of dense combinatorial structures to study order types, which are combinatorial encodings of finite point sets. Using flag algebras we obtain new numerical results on the Erdős problem of finding the minimal density of 5-or 6-tuples in convex position in an arbitrary point set, and also an inequality expressing the difficulty of sampling order types uniformly. Next we establish results on the analytic representation of limits of order types by planar measures. Our main result is a rigidity theorem: we show that if sampling two measures induce the same probability distribution on order types, then these measures are projectively equivalent provided the support of at least one of them has non-empty interior. We also show that some condition on the Hausdorff dimension of the support is necessary to obtain projective rigidity and we construct limits of order types that cannot be represented by a planar measure. Returning to combinatorial geometry we relate the regularity of this analytic representation to the aforementioned problem of Erdős on the density of k-tuples in convex position, for large k.

• On Fixed-Polynomial Size Circuit Lower Bounds for Uniform Polynomials in the Sense of Valiant

with and . Information and Computation arxiv:1304.5910
Abstract

Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficients in MA having no arithmetic circuits of size $O(n^k)$ over the complex field (allowing any complex constant). We also build a family of polynomials that can be evaluated in AM having no arithmetic circuits of size $O(n^k)$. Then we investigate the link between fixed-polynomial size circuit bounds in the Boolean and arithmetic settings. In characteristic zero, it is proved that $NP \not\subset size(n^k)$, or $MA \subset size(n^k)$, or NP=MA imply lower bounds on the circuit size of uniform polynomials in n variables from the class VNP over the complex field, assuming GRH. In positive characteristic p, uniform polynomials in VNP have circuits of fixed-polynomial size if and only if both VP=VNP over $F_p$ and Mod_pP has circuits of fixed-polynomial size.

• The worst case behavior of randomized gossip protocols

with Hervé Baumann, and Hovhannes Harutyunyan. Theorical Computer Science (2014)

Co-authors

Alfredo Hubard, Ararat Harutyunyan, N.R. Aravind, Eoin Hurley, Ewan Davies, François Pirot, Guillaume Lagarde, Hervé Baumann, Hervé Fournier, Hovhannes Harutyunyan, Jan Volec, Jean-Sébastien Sereni, Louis Esperet, Lucas Pastor, Nicolas Bousquet, Nicolas Grelier, Pierre Fraignaud, Ross Kang, Stéphan Thomassé, Stijn Cambie, Sylvain Périfel, Tien-Nam Le, Vincent Cohen-Addad, Viresh Patel, Wouter Cames van Batenburg, Xavier Goaoc.

Coding

Flag algebras

Flag algebras is a theory that uses Semi-Definite Programming to produce some kind of computer-assisted proofs.

During my postdoc, I developed an implementation of flag algebras written in Rust to help me in my own research. The documentation can be found there. If you have any trouble using it, don't hesitate to contact me.

An earlier (and slower) version in OCaml can be found there.

Other project

Smaller projects can be found on my GitHub page. A non-exhaustive list:

• fast-ultrametrics, an implementation of hierarchical clustering based on this research paper. This algorithm beats the quadratic running time (and space) used by the classical linkage algorithms, which makes them impractical for huge datasets.
• Lettreries, an automatic writer of french poetry that randomly produces grammatically correct text with constraints of verse form and rhymes by backtracking on a Markov chain. The programs computes phonetics representations (IPA) of words with a finite transducer built from a set of rules. You can read some of its creations there.
• A Rust crate to reduce graphs and other structures modulo isomorphism.

Teaching

Supervision

I supervised the master thesis of two students.
• In 2019-2020: Eoin Hurley, MSc in Mathematical Sciences thesis, Mathematical Institute, Utrecht, 2019-2020.
• In 2018: Nicolas Grelier, MSc in Engineering research internship in Nijmegen, IMT Atlantique, 2018.

Teaching experience

• 2017-2020: Guest teacher in Probabilistic and Extremal Combinatorics for the Dutch national Mastermath program.
• 2014-2017: Graph Theory. L2 Computer science. Université Grenoble Alpe. Courses, Tutorials, Practical sessions in C++.
• 2014-2017: Production Management. M1 MIAGE. Université Grenoble Alpe. Tutorials and Practical sessions in R.

Award

I took part in the 49th International Mathematical Olympiad in Madrid (2008) as a member of the French team. I was awarded a bronze medal.