In Semester II of academic year 20192020, the seminar is planned intermittently on Tuesdays at 11h. Contact Ross Kang if you are interested in giving a seminar, or in receiving announcements.
20192020
 12 May 2020 (postponed corona): Joris Mooij (University of Amsterdam).
Title ±
 31 March 2020 (postponed corona): Richard Kraaij (TU Delft).
Title ±
 17 March 2020 (postponed corona): Ton Coolen (Radboud University Nijmegen).
Imaginary replica analysis of loopy regular random graphs ±
We know that many important graphical structures in the world (biological networks, computing and communication networks, resource grids, lattices in physics, etc) are not treelike, and that processes on graphs are affected significantly by the presence of short loops. It is therefore problematic that most of our tools and algorithms for analysing (processes on) finitely connected graphs, such as cavity methods, belief propagation type algorithms, and conventional replica analyses, require topologies that are locally treelike. Some were extended with small loop corrections, but all tend to fail for graphs with many short loops. In this talk I present an analytical approach for describing spectrally constrained maximum entropy ensembles of finitely connected regular loopy graphs, valid in the regime of weak looploop interactions. We derive an expression for the leading two orders of the expected eigenvalue spectrum of the adjacency matrix, through the use of infinitely many replica indices taking imaginary values. We apply the method to models in which the spectral constraint reduces to a soft constraint on the number of triangles, which exhibit `shattering' transitions to phases with extensively many disconnected cliques, to models with controlled numbers of triangles and squares, and to models where the spectral constraint reduces to a count of the number of adjacency matrix eigenvalues in a given interval. Our predictions are supported by MCMC simulations based on edge swaps with nontrivial acceptance probabilities.
 10 March 2020: Christian Hirsch (University of Groningen).
Lower large deviations for geometric functionals ±
This talk presents a methodology for analyzing largedeviation lower tails associated with geometric functionals computed on a homogeneous Poisson point process. The technique applies to characteristics expressed in terms of stabilizing score functions exhibiting suitable monotonicity properties. We apply our results to clique counts in the random geometric graph, intrinsic volumes of PoissonVoronoi cells, as well as powerweighted edge lengths in the random geometric, knearest neighbor and relative neighborhood graph.
Based on joint work with Benedikt Jahnel and András Tóbiás
 3 March 2020: Pim van der Hoorn (TU Eindhoven).
$d$regular graphs with extremely many triangles ±
What is the probability that a random graph has more triangles than expected and what do such graphs look like? These a very active topics in both combinatorics and probability theory, which have led to a great variety of deep mathematical results and new insights into random graphs. In this talk I will focus on a closely related problem: what is the probability that the number of triangles in a random $d$regular graph is a positive fraction of the maximum possible number? The origin of this question comes from finding maximally unbiased graphs with a given expected degree and fraction of triangles.
We treat this as a problem of counting the number of $d$regular graphs with extremely many triangles. More precisely, we are interested in the leading term of the logarithm of the number of these graphs, as they grow in size. I will show that this counting problem can be solved very elegantly by using a probabilistic argument on the number of permutations of node labels. As a consequence of our proof technique, we also obtain a structural result for random $d$regular graphs with many triangles. In particular, we can show that these typically consist of many disjoint $d+1$ cliques and one almost trianglefree part. Moreover, our results extend to cases where $d$ can grow moderately with the size of the graph, as well as cliques of size $k > 3$.
 25 February 2020: Ivan Kryven (Utrecht University).
Mathematical modelling with random graphs ±
Random graphs were introduced as a convenient example for demonstrating the impossibility of `complete disorder' by Erdos, who also thought that these objects will never become useful in applied mathematics. Today, random graphs are already used as null models allowing to detect deviations from the `trivial' behaviour in empirical data. In this talk, I will review random graphs as selfsufficient modes in themselves and discus how the applicationdriven objectives have set the directions for new developments. I will focus on characterising the sizes of connected components in graphs with a given degree distribution, on how such components are affected by percolationlike processes, and on generalisations to the coloured graphs. These questions have interesting implications for studying resilience of networks, and for materials science where they explain reaction kineticsdriven phase transitions. The results also reveal intricate connections between random graphs and nonlinear partial differential equations.
 11 February 2020: Ben Hansen (University of Groningen).
Voronoï percolation in the hyperbolic plane ±
We consider site percolation on Voronoï cells generated by a Poisson point process on the hyperbolic plane $\mathbb{H}^2.$ Each cell is coloured black independently with probability $p,$ otherwise the cell is coloured white. Benjamini and Schramm proved the existence of three phases: For $p\in [0,p_c]$ all black clusters are bounded and there is a unique infinite white cluster. For $p\in (p_c,p_u),$ there are infinitely many unbounded black and white clusters. For $p\in [p_u,1]$ there is a unique infinite black cluster and all white clusters are bounded. They also showed $p_u=1p_c$. The critical values $p_c$ and $p_u$ depend on the intensity of the Poisson point process. We prove that $p_c$ tends to $1/2$ as the intensity tends to infinity. This confirms a conjecture of Benjamini and Schramm.
Joint work with Tobias Müller.
 6 December 2019 (Kac seminar, Utrecht): Ross Kang (Radboud University Nijmegen).
The asymptotic structure of locally sparse graphs.
 26 November: MohammadReza Bidgoli (IPM Tehran).
Bootstrap percolation on the Hamming graphs ±
$r$neighbor bootstrap percolation on a graph is an activation process of the vertices. The process starts with some initially activated vertices and then, in each round, any inactive vertex with at least $r$ active neighbors becomes activated.
Denote the minimum size of a percolating set (a set which activates the whole graph) on a graph $G$ by $m(G, r)$. I will present some upper and lower bounds on $m(K_n^d, r)$, where $K_n^d$ is the Hamming graph. These bounds are asymptotically sharp when both $r$ and $d$ go to infinity with $r< n$ and $d=o(\sqrt r)$.
 19 November: Christos Pelekis (Czech Academy of Sciences).
A continuous analogue of Erdős' $k$Sperner theorem ±
A chain in the unit $n$cube is a set $C$ having the property that for any two points in $C$, one is coordinatewise dominating the other. I will show that the $1$dimensional Hausdorff measure of a chain in the unit $n$cube is at most $n$, and that the bound is sharp. Moreover, I will discuss the problem of maximising the $n$dimensional Lebesgue measure of a measurable subset, $A$, of the unit $n$cube, subject to the constraint that the $1$dimensional Hausdorff measure of its intersection with every chain is at most $\kappa$, where $\kappa$ is a fixed real number from the interval $(0,n]$. Our main result provides a sharp upper bound on the $n$dimensional Lebesgue measure of $A$ and may be seen as a continuous analogue of Erdős' theorem on $k$Sperner families of finite sets. This is joint work with Themis Mitsis and Václav Vlasák.
 45 November 2019: MiniSymposium "Structure, Sparsity and Randomness" and PhD Defence for François Pirot.
 24 October 2019: Ross Kang (Radboud University Nijmegen).
The global structure of large locally sparse graphs ±
The structure of trianglefree graphs has long played an influential role in the development of combinatorics and graph theory. Both Mantel's (1907) and Ramsey's (1930) theorems yield global structure from the local property of having no edges in any neighbourhood. I have recently made some basic explorations in this classic area, both beginning and ending in list colouring problems.
The first part concerns a recent conjecture on bipartite induced density in trianglefree graphs, which innocently originated in the study of separation choosability. I will discuss how the conjecture has stimulated and coincided with a small burst of related activity and new directions.
The second part presents a new structural framework (that includes list colouring) for locally sparse graphs. This generalises and strengthens many landmark results in the area, including for example those of Ajtai, Komlós, Szemerédi (1981), Shearer (1983), Johansson (1996), Alon (1996), Alon, Krivelevich, Sudakov (1999), and Molloy (2019). It is built around a technique inspired by statistical physics namely, a local analysis of the hardcore model.
This covers joint work with, variously, Wouter Cames van Batenburg, Ewan Davies, Louis Esperet, Rémi de Joannis de Verclos, François Pirot, JeanSébastien Sereni, and Stéphan Thomassé.
Archived announcements ±
 25 June 2019: François Pirot (Nijmegen/Lorraine).
Graph representation of circular codes ±
The discovery of the DNA structure by Watson and Crick in 1953 spurred a new branch of mathematical biology, which overlaps the theory of block codes, that is, codes consisting of words of a fixed length over some finite alphabet. There are several relevant notions associated to block codes; from most to less restrictive, a block code $X$ can be strongcommafree (the words of $X$ do not overlap), commafree (no word from $X$ appears as a proper factor of a word in $X^2$), or $k$circular (every word of $X^k$ admits a unique decomposition into words of $X$ when read of a cycle)  if $X$ is $k$circular for every $k\in \mathbb{N}$, we say that it is circular. In biology, all these properties imply that it is always possible to retrieve the reading frame in a DNA sequence in order to decompose it into codons (words of length $3$).
We describe a graph representation of codes which encapsulates its various properties. By taking advantage of this representation, we are able to give a full characterisation of maximum codes on dinucleotides (words of length $2$), of maximal strongcommafree codes on $\ell$nucleotides (words of any fixed length $\ell$), and of maximum commafree codes on trinucleotides (words of length $3$). Finally, we will discuss the optimal value of $k(n,\ell)$ such that $k(n,\ell)$circularity implies circularity, for all codes on $\ell$nucleotides over an alphabet of cardinality $n$.
Joint work with Elena Fimmel, Christian J. Michel, JeanSébastien Sereni, and Lutz Struengmann.
 6 June 2019: Augusto Gerolin (VU Amsterdam).
An Optimal Transport approach for the Schrödinger Bridge problem and convergence of Sinkhorn algorithm ±
This talk gives a gentle introduction to some theoretical and numerical aspects of optimal transport theory. Moreover, we exploit the equivalence between the Schrödinger Bridge problem and the entropy penalized optimal transport in order to find a different approach to the duality, in the spirit of optimal transport. As a byproduct we give a proof of convergence of the Sinkhorn algorithm (aka IPFP, DAD, RAS, ...) that works for both one and many marginal case.
 21 May 2019: Johannes SchmidtHieber (University of Twente).
Statistical theory for deep ReLU networks ±
We derive risk bounds for fitting deep neural networks to data generated from the multivariate nonparametric regression model. It is shown that estimators based on sparsely connected deep neural networks with ReLU activation function and properly chosen network architecture achieve the minimax rates of convergence (up to logarithmic factors) under a general composition assumption on the regression function. The framework includes many wellstudied structural constraints such as (generalized) additive models. While there is a lot of flexibility in the network architecture, the tuning parameter is the sparsity of the network. Specifically, we consider large networks with number of potential parameters being much bigger than the sample size. We also discuss some theoretical results that compare the performance to other methods such as wavelets and splinetype methods. This is joint work with K. Eckle (Leiden).
 14 May 2019: N.R. Aravind (IIT Hyderabad).
Chromatic discrepancy of graphs ±
Given a proper coloring of a graph G, the discrepancy of an induced subgraph H with respect to this coloring is defined to be the number of colors seen by H minus the chromatic number of H. The chromatic discrepancy of G is the maximum of this value over all induced subgraphs H, and minimised over all proper colorings. In this talk, we will see upper and lower bounds for this parameter for general graphs and for random graphs.
 29 April 2019: Júlia Komjáthy (TU Eindhoven).
How to stop explosion by penalising transmission to hubs ±
In this talk we study the spread of information in infinite inhomogeneous spatial random graphs.
To model the spread of information in social networks, we take a spatial random graph that is scale free, that is, the degree of a vertex follows a power law with exponent tau in $(2,3)$. One common approach to model the spread information is then to equip each edge with a random and iid transmission cost $L$, and study the cost of the leastcost past between vertices. In these graphs, it was observed earlier than it is possible to reach infinitely many vertices within finite cost, as long as the cumulative distribution function of $L$ is not doublyexponentially flat close to $0$. This phenomenon is called explosion, and it seems off from reality for cases where individual contact is necessary, e.g., spreading of viruses, etc.
We introduce a penalty to transmit the information to hubs, and increase the cost of transmission through an edge with expected degrees $W$ and $Z$ by a factor that is a power of the product $WZ$.
We find a threshold behaviour between explosion, depending on how steep the cumulative distribution function of $L$ increases at $0$: it should be at least polynomially steep, where the exponent depends on both the powerlaw exponent tau and the penaltyexponent.
This behaviour is arguably a better representation of information spreading processes in social networks than the case without penalizing factor.
 2 April 2019: Tom Kelly (University of Waterloo).
Fractional Coloring with Local Demands ±
In a fractional coloring, vertices of a graph are assigned subsets of the $[0, 1]$interval such that adjacent vertices receive disjoint subsets. The fractional chromatic number of a graph is at most $k$ if it admits a fractional coloring in which the amount of "color" assigned to each vertex is at least $1/k$. We investigate fractional colorings where vertices "demand" different amounts of color, determined by local parameters such as the degree of a vertex. Many wellknown results concerning the fractional chromatic number and independence number have natural generalizations in this new paradigm. We discuss several such results as well as open problems. In particular, we will sketch a proof of a "local demands" version of Brooks' Theorem that considerably generalizes the CaroWei Theorem and implies new bounds on the independence number. Joint work with Luke Postle.
 5 March 2019: Wouter Cames van Batenburg (Université libre de Bruxelles).
Large independent sets in trianglefree graphs: beyond planarity ±
Every $n$vertex planar trianglefree subcubic graph has an independent set of size at least $\frac{3}{8}n$.
This sharp result was first conjectured by Albertson, Bollobás and Tucker, and was later proved by Heckman and Thomas.
Fraughnaugh and Locke conjectured that the planarity requirement could be relaxed into just forbidding a few specific nonplanar graphs as an (induced) subgraph.
They described a family $\mathcal{F}$ of six nonplanar graphs (each of order at most $22$) and conjectured that every $n$vertex subcubic trianglefree graph having no subgraph isomorphic to a member of $\mathcal{F}$ has an independent set of size at least $\frac{3}{8}n$.
In our recent work, we have proved this conjecture.
As a sharp corollary, we also obtain that every $2$connected $n$vertex trianglefree subcubic graph has an independent set of size at least $\frac{3}{8}n$, with the exception of the six graphs in $\mathcal{F}$.
This confirms a conjecture made independently by Bajnok and Brinkmann, and by Fraughnaugh and Locke.
Joint work with Jan Goedgebeur and Gwenaël Joret.
 12 February 2019: Henk Don (Radboud University Nijmegen).
Synchronization of deterministic and partial automata ±
An automaton is a directed graph with labeled edges. The vertices represent states in which the automaton can be. The labels serve as input to bring the automaton to an other state.
In a deterministic automaton, for each label there is exactly one outgoing edge from each state. Given the starting state and a sequence of labels (input word), there is a unique way to follow the edges with these labels, leading to the state of the automaton after reading the input word. If there exists a word for which the final state does not depend on the starting state, the automaton is called synchronizing. For a synchronizing automaton, one can ask for the length of the shortest synchronizing word. In this talk I will show that this length is at most cubic in the number of states.
In a partial automaton, for each label there is at most one outgoing edge from each state. If the automaton is in a state with zero outgoing edges with a particular label, then this label is forbidden as input. Still there might exist a synchronizing word which for each starting state avoids all forbidden input. However, in this case the shortest synchronizing word can have length exponential in the number of states, for which a construction will be presented.
Joint work with Hans Zantema and Michiel de Bondt
 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
 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.
