In Semester I of academic year 20182019, the seminar is scheduled approximately every two weeks on Tuesdays at 14h. Contact Ross Kang to receive emailed announcements or for further details. Note: there is considerable overlap here with the departmental page.
20172018
 28 November 2018: Viresh Patel (University of Amsterdam).
Decomposing tournaments into paths. ±
In this talk we consider a generalisation of Kelly's conjecture which is due Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for all sufficiently large tournaments. The conjecture of Alspach, Mason, and Pullman concerns general tournaments and asks for the minimum number of paths needed in an edge decomposition of each tournament into paths. There is a natural lower bound for this number in terms of the degree sequence of the tournament and they conjecture this bound is correct for tournaments of even order. Almost all cases of the conjecture are open. In this talk I will discuss some of our techniques for solving many of these cases and in particular a variant of the absorption method.
This is joint work with Allan Lo, Jozef Skokan, and John Talbot.
 8 November 2018: Rémi de Joannis de Verclos (Radboud University Nijmegen).
Testability of chordal graphs. ±
A graph property \(P\) is said to be testable if one can distinguish graphs of \(P\) from graph that are \(\epsilon\)far from being in \(P\) (for the edition distance) with an algorithm that samples an induced subgraph of a size \(m(\epsilon)\) that depends only on \(\epsilon\). The parameter \(m(\epsilon)\) is called the query complexity of the class \(P\). It has been proven that every hereditary graph property is testable with some query complexity \(m(\epsilon)\). However, the general upper bound on \(m(\epsilon)\) is a tower of exponential of size \(1/\epsilon\). A natural question is therefore to know which classes are testable with reasonable query complexity. In this talk, focus on the class chordal graphs, which is the class of graphs without induced cycle of length 3 or more. We show that this class is testable with a query complexity that is polynomial in \(1/\epsilon\).
 9 October 2018: Stijn Cambie (Radboud University Nijmegen).
Asymptotic resolution of a question of Plesník. ±
Fix \(d \ge 3\).
We show the existence of a constant \(c>0\) such that any graph of diameter at most \(d\) has average distance at most \(dc d^{3/2}/\sqrt{n}\), where \(n\) is the number of vertices.
Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of \(c\).
This constitutes an asymptotic solution to a longstanding open problem of Plesník. Furthermore we solve that open problem of Plesník exactly for digraphs in case the order is large compared with the diameter.
In the talk, we will give an elementary, alternative proof for the original result of Plesník on the minimum average distance of (di)graphs with order \(n\) and diameter \(d\) and sketch the proofs for the asymptotic resolution of the question about the maximum average distance given \(d\) and \(n\).
 26 July 2018: António Girão (Cambridge/Birmingham).
Long cycles in Hamiltonion graphs. ±
We prove that if an \(n\)vertex graph with minimum degree at least 3 contains a Hamiltonian cycle, then it contains another cycle of length \(no(n)\); this implies, in particular, that a wellknown conjecture of Sheehan from 1975 holds asymptotically. Our methods, which combine constructive, posetbased techniques and nonconstructive, paritybased arguments, may be of independent interest.
Joint work with Teeradej Kittipassorn and Bhargav Narayanan.
 2627 June 2018: MiniSymposium and PhD Defence for Wouter Cames van Batenburg.
 12 June 2018: Wouter Cames van Batenburg (Université libre de Bruxelles).
A tight ErdősPósa function for planar minors ±
Let \(H\) be a planar graph. We prove that there exists a constant \(c:=c(H)\), such that for all \(k \in \mathbb N\) and all graphs \(G\), either \(G\) contains \(k\) vertexdisjoint subgraphs each containing \(H\) as a minor, or there is a subset \(X\) of at most \(c k \log k\) vertices such that \(GX\) has no \(H\) minor.
This bound is best possible, up to the value of \(c\),
and improves upon the bounds of Robertson and Seymour, and of Chekuri and Chuzhoy. Joint work with Tony Huynh, Gwenaël Joret and JeanFlorent Raymond.
NB: This is an extended version of the minisymposium talk.
 15 May 2018: Neil Olver (VU Amsterdam).
The longterm behaviour of a queuebased dynamic traffic model ±
The fluid queueing model, introduced by Vickrey in '69, is probably the simplest model that plausibly captures the notion of timevarying flows. Although the model is quite simple, our current theoretical
understanding of equilibrium behaviour in this model is rather limited, and many fundamental questions remain open. I will discuss the resolution of a deceptively simplesounding problem: do queue
lengths remain bounded in the equilibria under natural necessary conditions? (Joint work with Roberto Cominetti and José Correa.)
 1 May 2018: Ewan Davies (University of Amsterdam).
Gibbs measures in combinatorics ±
Recently, a method for optimising observables of Gibbs distributions has been used to prove several extremal problems in graph theory and discrete geometry. We survey these results with an emphasis on showing the proof techniques for simpler examples.
 17 April 2018: Daniel Valesin (University of Groningen).
The asymmetric multitype contact process. ±
We study a class of interacting particle systems known as the multitype contact process on \({\mathbb Z}^d\). In this model, sites of \({\mathbb Z}^d\) can be either empty or occupied by an individual of one of two species. Individuals die with rate one and send descendants to neighboring sites with a rate that depends on their (the parent's) type. Births are not allowed at sites that are already occupied. We assume that one of the types has a birth rate that is larger than that of the other type, and larger than the critical value of the standard contact process. We prove that, if initially present, the stronger type has a positive probability of never going extinct. Conditionally on this event, it takes over a ball of radius growing linearly in time. We also completely characterize the set of stationary distributions of the process and prove a complete convergence theorem. Joint work with Pedro L. B. Pantoja and Thomas Mountford.
 1213 April 2018: STAR Workshop on Random Graphs 2018
 13 March: Rui Castro (TU Eindhoven).
DistributionFree Detection of Structured Anomalies: Permutation and RankBased Scans. ±
The scan statistic is by far the most popular method for anomaly detection, being popular in syndromic surveillance, signal and image processing and target detection based on sensor networks, among other applications. The use of scan statistics in such settings yields an hypothesis testing procedure, where the null hypothesis corresponds to the absence of anomalous behavior. If the null distribution is known calibration of such tests is relatively easy, as it can be done by MonteCarlo simulation. However, when the null distribution is unknown the story is less straightforward. We investigate two procedures: (i) calibration by permutation and (ii) a rankbased scan test, which is distributionfree and less sensitive to outliers. A further advantage of the rankscan test is that it requires only a onetime calibration for a given data size making it computationally much more appealing than the permutationbased test. In both cases, we quantify the performance loss with respect to an oracle scan test that knows the null distribution. We show that using one of these calibration procedures results in only a very small loss of power in the context of a natural exponential family. This includes for instance the classical normal location model, popular in signal processing, and the Poisson model, popular in syndromic surveillance. Numerical experiments further support our theory and results (joint work with Ery AriasCastro, Meng Wang (UCSD) and Ervin Tánczos (UW Madison)).
 20 February 2018: Timothy Budd (Radboud University Nijmegen).
Geometry of random planar maps with high degrees. ±
For many types of random planar maps, i.e. planar graphs embedded in the
sphere, it is known that their geometry possesses a scaling limit
described by a universal random continuous metric space known as the
Brownian sphere. One way to escape this universality class is to
consider random planar maps that harbor vertices of very high degree.
In this talk I will describe a peeling exploration that allows us to
study distances in such maps. Based on the results we conjecture the
existence of a new oneparameter family of random continuous metric
spaces, referred to tentatively as the stable spheres.
 23 January 2018: Rob van den Berg (CWI).
Nearcritical percolation and applications. ±
Motivated by solgel transitions, David Aldous (2000) introduced and
analysed an interesting percolation model on a tree where clusters
stop growing (`freeze') as soon as they become infinite. I will discuss recent work with Demeter Kiss
and Pierre Nolin on processes of similar flavour on planar lattices.
We focus on the question whether or not the `gel' (i.e. the union of the frozen clusters)
occupies a negligible fraction of space. Sharp versions of some classical scaling results by Harry Kesten
for nearcritical percolation were needed, and developed, to answer this question.
I will also briefly mention current work with Pierre Nolin on a modification of the model which may be interpreted as a `selforganized critical' sensor/communication network. The study of it leads naturally to a more general framework of nearcritical percolation with
`heavytailed' impurities.
 5 December 2017: Jop Briët (CWI).
Codes, Szemerédi's theorem and upper tail probabilities. ±
This talk is about three problems and a common feature that connects them. The three problems concern 1.) special types of error correcting codes (known as locally decodable codes), 2.) random differences in Szemerédi's theorem on arithmetic progressions (more precisely, intersective sets, a.k.a. recurrent sets) and 3.) upper tail probabilities for the number of edges induced by a random vertex subset of a given hypergraph. The common feature lurking beneath them has to do with the average (Gaussian) width of special configurations of points in highdimensional Euclidean space. The aim for this talk is to explain what the three problems are about, mention some of their history and say what bounds on Gaussian widths imply for them. This is based on joint work with Sivakanth Gopi (http://arxiv.org/abs/1711.05624).
 24 October 2017: Wouter Cames van Batenburg (Radboud University Nijmegen).
Coloring Jordan regions and Jordan curves. ±
A Jordan region is a subset of the plane that is homeomorphic to a closed disk. Consider a family F of Jordan regions whose interiors are pairwise disjoint, and such that any two Jordan regions intersect in at most one point. If any point of the plane is contained in at most kelements of F (with k sufficiently large), then we show that the elements of F can be colored with at most k+1 colors so that intersecting Jordan regions are assigned distinct colors. In other words, the chromatic number of the intersection graph of F equals its clique number (a trivial lower bound for the chromatic number) plus one. This is best possible and answers a question raised by Reed and Shepherd in 1996. The proof makes use of the discharging method, which is a popular tool for addressing problems on planar graphs.
We also investigate the chromatic number of the intersection graph of touching (noncrossing) Jordan curves. If any point of the plane is contained in at most k such Jordan curves, then the chromatic number of its intersection graph is at most 15.95*k. The proof involves upper bounding the number of edges in the intersection graph, which is done by analyzing a certain planar subgraph of the intersection graph of a uniformly random subset of the Jordan curves.
This is joint work with Louis Esperet and Tobias Müller.
 18 October 2017 (Quantum Gravity lunch seminar): Ross Kang (Radboud University Nijmegen).
Guarantees of sparse or dense subgraphs.
 3 October 2017: Derong Kong (Leiden University).
On the bifurcation set of badly approximable numbers in \(\beta\)dynamical systems ±
Badly approximable numbers as a subject of Diophantine approximation in analytic number theory has received much more attention since the work of Dirichlet (1842). In this talk we will consider an analogous problem in a dynamical setting. To be more precise, given $\beta\in(1,2]$ let $T_\beta: x\mapsto \beta x\pmod 1$ be the expanding map on the circle $[0,1)$. For $t\in[0,1)$ let
\[
K_\beta(t):=\{x\in[0,1): T_\beta^n(x)\ge t\textrm{ for all }n\ge 0\}
\]
be the set of badly approximable numbers of order $t$ under the map $T_\beta$. We show that the setvalued map $F: t\mapsto K_\beta(t)$ is locally constant almost everywhere on $[0, 1)$. Denote by $E_\beta$ the bifurcation set containing all parameters $t\in[0, 1)$ where the setvalued map $F$ vibrates. Some topological, measure theoretical and dimensional properties of the bifurcation set $E_\beta$ will be discussed.
This is a joint work with C. Kalle (Leiden), N. Langeveld (Leiden) and W. Li (Shanghai).
 19 September 2017: Guus Regts (University of Amsterdam).
Zerofree regions of graph polynomials and algorithms for evaluating graph polynomials. ±
Evaluations of graph polynomials such as the independence polynomial and the chromatic polynomial of a graph capture many important properties of graphs. In general it is NPhard to evaluate such polynomials exactly. Therefore research has shifted to approximately computing evaluations. Until recently there were essentially two methods: 1) Monte Carlo Markov Chain and 2) the correlation decay method.
In this talk I will discuss a third method, due to Barvinok, for designing efficient approximation algorithms for certain graph polynomials. This method is based on approximating the logarithm of the polynomial and gives good approximations in regions where the polynomial does not vanish.
This is based on joint work with Viresh Patel and Han Peters both from the University of Amsterdam
Archived announcements ±
 12 July 2017: Jerrold R. Griggs (University of South Carolina).
Posetfree Families of Subsets. ±
 2223 June 2017: Quantum Probability and Information Theory
 19 May 2017 (High Energy Physics seminar): Eric Cator (Radboud University Nijmegen).
Last passage percolation
 12 April 2017: Rémi de Joannis de Verclos (Grenoble Alps University).
Limits of order types. ±
The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5 or 6tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (ErdosSzekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.
Joint work with Xavier Goaoc, Alfredo Hubard, JeanSébastien Sereni and Jan Volec.
 24 January 2017: Vladimir Gusev (Université catholique de Louvain).
Synchronizing automata and primitive matrices. ±
The talk is devoted to primitive matrices and synchronizing automata. Recall that a nonnegative square matrix is primitive if one of its powers is positive. Primitive matrices are tightly related to regular Markov chains, ranking of websites, population modelling, etc. In my talk I will speak about a recent generalization of this notion to sets of matrices and its combinatorial and algorithmic properties. I will also give an introduction to synchronizing automata  a "counterpart" of primitive matrices in automata theory. I will present its connections to industrial automation, group theory and tell you about the famous Cerny Conjecture and Road Coloring Theorem.
The talk is not technical and assumes no special knowledge of the audience.
 12 January 2017 (IMAPP colloquium): Ross Kang (Radboud University Nijmegen).
Colourings of graph powers.
 6 December 2016: Tobias Müller (Utrecht University).
The critical probability for confetti percolation equals 1/2 ±
In the confetti percolation model, or twocoloured dead leaves model,
radius one disks arrive on the plane according to a random process (a
spacetime Poisson
process to be exact).
Each disk is colored black with probability p and white with
probability 1p. This defines a twocolouring of the plane, where the
color of a point on the plane is determined by the last disk to arrive
that covers it.
In this talk we will show that the critical probability for confetti
percolation equals 1/2.
That is, if p>1/2 then (with probability one) there is an unbounded
curve in the plane
all of whose points are black; while if p <= 1/2 then (with
probability one) all
connected components of the set of black points are bounded.
This answers a question of Benjamini and Schramm.
The proof makes use of earlier work by Hirsch and an asymmetric
version of a "sharp threshold" result of Bourgain.
 24 November 2016: Mathew Penrose (University of Bath).
Continuum AB percolation and AB random geometric graphs ±
 19 April 2016 (Brouwer seminar): Henk Don (Radboud University Nijmegen).
The Cerny conjecture and 1contracting automata
 21 March 2016: Wouter Cames van Batenburg (Radboud University Nijmegen).
Packing graphs of bounded codegree. ±
 7 March 2016 (Huygens colloquium): Eric Cator (Radboud University Nijmegen).
How does a virus spread on large networks?
 27 May 2015: François Pirot (ENS Lyon).
Distance colouring and girth. ±
 910 April 2015: STAR Workshop on Random Graphs 2015.
 19 November 2014: Ross Kang (Radboud University Nijmegen).
Bounded monochromatic components for random graphs. ±
 4 November 2014: Guillem Perarnau (McGill University).
On the diameter of random kout digraphs. ±
In this talk we will discuss about the diameter of a random
digraph of order $n$ where every vertex has outdegree $k$. This
model of random digraphs is of special interest since, up to a
labeling of the arcs, it models a random deterministic finite
automaton. Trakhtenbrot and Barzdin proved in 1973 that with high
probability its diameter is $O(\log{n})$. We show that for every
$k\geq 2$ there exists a constant $c_k$ such that the diameter of a
random $k$out digraph is $(1+o(1))c_k\log{n}$ with high probability.
This result has some implications on the stationary distribution of a
random walk in this model. This is joint work with Louigi
AddarioBerry and Borja Balle.
 14 October 2014: Tom Alberts (University of Utah). ±
 30 September 2014: Eric Cator (Radboud University Nijmegen).
Estimating under shape constraints. ±
 10 July 2014: Felix Joos (University of Ulm).
Induced Matchings in Graphs. ±
In contrast to matchings in graphs, one might say that induced
matchings do not behave nicely (structurally and algorithmically). We
survey some recent results on induced matchings and give some
explanations why induced matchings are more complicated than
matchings.
