In Semester I of academic year 20172018, 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
 1213 April 2018: STAR Workshop on Random Graphs 2018
 23 January 2018 (note: this seminar starts at 11h!): 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.
