We present a randomised local algorithm that properly
colours most edges of a graph of maximum degree $d$ using $d+1$ colours.
This is applied to descriptive combinatorics to prove that every
graphing of maximum degree $d$ admits a measurable proper
edge-colouring with $d+1$
colours, thus answering a question posed by Miklós Abért.
This is joint work with Jan Grebík (arXiv:1905.01716)
Algorithmic extensions of the Bollobas-Haggkvist conjecture ±
Dirac's Theorem is a classical result in graph theory stating that every $n$-vertex graph with minimum degree at least $n/2$ has a Hamilton cycle. If we restrict to regular graphs (and impose some mild connectivity conditions), we might hope to lower the degree threshold: in that direction, Bollobás and Häggkvist independently conjectured that every $k$-connected, $D$-regular, $n$-vertex graph with $D \geq n/(k+1)$ has a Hamilton cycle. Although the conjecture turns out to be false for $k \geq 4$, one might still wonder whether Hamiltonicity is easier to detect in regular (dense) graphs. We investigate this question. This is joint work with Fabian Stroh.
A classic result of Erdős and Pósa (1965) states that for every graph
$G$ and every integer $k$, either $G$ has $k$ vertex-disjoint cycles, or $G$ has a set of $O( k \log k )$ vertices meeting every cycle.
We give a new proof of this result, using a ball packing and contraction argument.
We then apply the same technique to obtain a relatively short proof that long cycles have the edge-Erdős-Pósa property, improving the previously best known bound.
More precisely, we show that for all integers $l\ge 3$, $k\ge 0$ and every graph $G$,
either $G$ has $k$ edge-disjoint cycles of length at least $l$, or $G$ has a set of $O( lk \log (lk) )$ edges meeting every cycle of length at least $l$.
Joint work with Henning Bruhn, Gwenaël Joret and Arthur Ulmer.
Using hard-core distributions for sparse graph colouring ±
Writing ${\cal I}(G)$ for the collection of independent sets of a given graph $G$, a random independent set ${\bf I}$ drawn according to the hard-core distribution at fugacity $\lambda$ on ${\cal I}(G)$ satisfies for every independent set $I\in {\cal I}(G)$ that
\[
\Pr[{\bf I} = I] = \frac{\lambda^{|I|}}{Z_\lambda(G)}, \mbox{ where } Z_\lambda(G) = \sum_{I\in {\cal I}(G)} \lambda^{|I|}
\]
is a normalising factor, called the independence polynomial of $G$.
Inspired by a method of Molloy and Reed (2002) which demonstrates a fractional version of Reed's conjecture, namely $\chi_f(G) \le (\omega(G)+\Delta(G)+1)/2$ for every graph $G$, we show that a greedy fractional colouring algorithm is really efficient in order to return a fractional colouring of various classes of sparse graphs, when used with the hard-core distribution on independent sets.
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes: 1) Graphs with linear rankwidth at most $r$ are linearly $\chi$-bounded. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 2) Based on a Ramsey-like argument, we prove for every proper hereditary family $\mathcal F$ of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in $\mathcal F$. 3) A class $\mathcal C$ with bounded linear rankwidth the following conditions are equivalent: a) $\mathcal C$ is stable, b) $\mathcal C$ excludes some half-graph as a semi-induced subgraph, c) $\mathcal C$ is a first-order transduction of a class with bounded pathwidth.
An algorithm for max-cut is local if each vertex chooses its side of the cut by
only looking at vertices at a bounded distance (i.e. at a distance bounded by a
constant independent of the number of vertices). While it is very easy to
design randomized local algorithms for max-cut that achieve a constant factor
approximation in average (1/2, or slightly above for triangle-free regular
graphs, and even better for random d-regular graphs) we show that no
deterministic local algorithm can achieve a constant factor approximation in
bipartite d-regular graphs with d-even. When d is odd, we show that no
deterministic local algorithm can achieve an approximation ratio better than
1/d, and that 1/d is very easy to obtain by only looking at balls of radius 1
around each vertex.
Joint work with Etienne Bamas.
On degree thresholds of cycles in oriented graphs ±
Motivated by Caccetta-Häggkvist conjecture, Kelly, Kühn and Osthus initiated
the study of minimum degree conditions which force oriented graphs to contain
cycles of a given length. For every $l \ge 4$, they proved that any sufficiently
large $n$-vertex oriented graph with minimum semi-degree $(n+1)/3$ contains $C_l$,
which is sharp whenever $l$ is not divisible by 3. However, they conjectured that
in case $l$ is a multiple of 3, one can do much better. In this talk, we first
determine the degree threshold of $C_6$, and then discuss the thresholds for all
the other lengths $l \ge 4$.
This is a joint work with Roman Glebov and Andrzej Grzesik.
Nonconvergence in the first order logic of permutations ±
Recently Albert, Bouvel and F\'eray introduced the {\em theory of two total orders} (TOTO) which allows
one to express properties of permutations in first order logic.
We are allowed to use the quantifiers $\forall, \exists$, variables $x,y,z,\dots$,
the logical connectives $\wedge, \vee, \neg$, etc., brackets and the relation symbols
$=, <_1, <_2$.
Thinking of a permutation $\pi$ as a map from $[n]$ two itself, if
$x, y$ represent two elements of $[n]$ then $x <_1 y$ just means that
$x < y$ while $x <_2 y$ means that $\pi(x) < \pi(y)$.
For instance, the occurrence of the pattern $231$ can be expressed as
$$ \exists x,y,z : (x <_1 y)\wedge(y <_1 z ) \wedge (z <_2 x ) \wedge (x <_2 y). $$
We consider the probability that a given property expressible in TOTO holds for a random permutation.
That is, the permutation $\pi_n$ chosen uniformly at random from all $n!$
permutations of $[n] := \{1,\dots,n\}$.
Answering a question of Albert, Bouvel and F\'eray in the negative, we show that there exists
a property $\varphi$ expressible in TOTO, such that
$$ \lim_{n\to\infty} \Pee( \pi_n \text{ satisfies } \varphi ) \text{ does not exist. } $$
That is, we construct a $\varphi \in \text{TOTO}$ such that probability that $\pi_n$ satisfies it
oscillates between zero and one.
The construction builds on the seminal work of Shelah and Spencer on first order properties for the Erd\H{o}s-R\'enyi random graph.
This event was organised in conjunction with the PhD defence of François Pirot.
Congratulations Dr. François Pirot!
Ross Kang and Jean-Sébastien Sereni were François's supervisors, and by coincidence were also the organisers of this meeting.
