Structure, Sparsity and Randomness 4 & 5 November 2019

We were delighted to host the following set of talks on the campus of Radboud University Nijmegen.

#### Monday

 10:00 Welcome & coffee/tea 10:20 - 11:05 Oleg Pikhurko Measurable version of Vizing's theorem  ± 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) 11:15 - 12:00 Viresh Patel 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. 12:00 Lunch 13:45 - 14:30 Wouter Cames van Batenburg Edge-Erdős-Pósa through packing and contraction  ± 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. 14:30 Coffee/tea/open problems 16:30 François Pirot PhD defence: "Colouring Sparse Graphs" 19:00 Workshop dinner

#### Tuesday

 10:00 Coffee/tea 10:20 - 11:05 François Pirot 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. 11:15 - 12:00 Patrice Ossona de Mendez Linear rankwidth meets stability  ± 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. 12:00 Lunch 13:45 - 14:30 Louis Esperet Local algorithms for Max-cut in regular graphs ± 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. 14:30 Coffee/tea 15:00 - 15:45 Jan Volec 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. 16:00 - 16:45 Tobias Müller 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.

The meeting was made possible through the support of Radboud University, Université de Lorraine, and NWO.

Last modification: