Radboud University Nijmegen: Applied Stochastics Seminar

We know that many important graphical structures in the world (biological networks, computing and communication networks, resource grids, lattices in physics, etc) are not tree-like, 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 tree-like. 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 loop-loop 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.

This talk presents a methodology for analyzing large-deviation 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 Poisson-Voronoi cells, as well as power-weighted edge lengths in the random geometric, k-nearest neighbor and relative neighborhood graph.
Based on joint work with Benedikt Jahnel and András Tóbiás

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 triangle-free 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$.

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 self-sufficient modes in themselves and discus how the application-driven 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 percolation-like 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 kinetics-driven phase transitions. The results also reveal intricate connections between random graphs and non-linear partial differential equations.

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=1-p_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.

$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)$.

A chain in the unit $n$-cube is a set $C$ having the property that for any two points in $C$, one is coordinate-wise 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.

The structure of triangle-free 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 triangle-free 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 hard-core model.
This covers joint work with, variously, Wouter Cames van Batenburg, Ewan Davies, Louis Esperet, Rémi de Joannis de Verclos, François Pirot, Jean-Sébastien Sereni, and Stéphan Thomassé.

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 strong-comma-free (the words of $X$ do not overlap), comma-free (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 strong-comma-free codes on $\ell$-nucleotides (words of any fixed length $\ell$), and of maximum comma-free 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, Jean-Sébastien Sereni, and Lutz Struengmann.

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.

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 well-studied 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 spline-type methods. This is joint work with K. Eckle (Leiden).

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.

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 least-cost 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 doubly-exponentially 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 power-law exponent tau and the penalty-exponent. This behaviour is arguably a better representation of information spreading processes in social networks than the case without penalizing factor.

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 well-known 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 Caro-Wei Theorem and implies new bounds on the independence number. Joint work with Luke Postle.

Every $n$-vertex planar triangle-free 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 triangle-free 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 triangle-free 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.

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

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.

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$.

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 $d-c 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$.

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 $n-o(n)$; this implies, in particular, that a well-known conjecture of Sheehan from 1975 holds asymptotically. Our methods, which combine constructive, poset-based techniques and non-constructive, parity-based arguments, may be of independent interest. Joint work with Teeradej Kittipassorn and Bhargav Narayanan.

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$ vertex-disjoint subgraphs each containing $H$ as a minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ 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 Jean-Florent Raymond.
NB: This is an extended version of the mini-symposium talk.

The fluid queueing model, introduced by Vickrey in '69, is probably the simplest model that plausibly captures the notion of time-varying 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 simple-sounding problem: do queue lengths remain bounded in the equilibria under natural necessary conditions? (Joint work with Roberto Cominetti and José Correa.)

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.

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.

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 Monte-Carlo simulation. However, when the null distribution is unknown the story is less straightforward. We investigate two procedures: (i) calibration by permutation and (ii) a rank-based scan test, which is distribution-free and less sensitive to outliers. A further advantage of the rank-scan test is that it requires only a one-time calibration for a given data size making it computationally much more appealing than the permutation-based 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 Arias-Castro, Meng Wang (UCSD) and Ervin Tánczos (UW Madison)).

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 one-parameter family of random continuous metric spaces, referred to tentatively as the stable spheres.

Motivated by sol-gel 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 near-critical 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 `self-organized critical' sensor/communication network. The study of it leads naturally to a more general framework of near-critical percolation with `heavy-tailed' impurities.

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 high-dimensional 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).

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 (non-crossing) 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.

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 set-valued 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 set-valued 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).

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 NP-hard 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

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 6-tuples 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 (Erdos-Szekeres, 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, Jean-Sébastien Sereni and Jan Volec.

The talk is devoted to primitive matrices and synchronizing automata. Recall that a non-negative 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.

In the confetti percolation model, or two-coloured dead leaves model, radius one disks arrive on the plane according to a random process (a space-time Poisson process to be exact). Each disk is colored black with probability p and white with probability 1-p. This defines a two-colouring 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.

https://arxiv.org/abs/1405.2717

https://arxiv.org/abs/1605.05599

https://arxiv.org/abs/1511.08826

https://arxiv.org/abs/1407.3555

In this talk we will discuss about the diameter of a random digraph of order $n$ where every vertex has out-degree $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 Addario-Berry and Borja Balle.

Archived announcements ±