About | Research | Events | People | Reports | Alumni | Contact | Home
|
YEP VII 2010(Young European Probabilists) workshop Probability, random trees and
algorithms Monday-Tuesday-Wednesday-Thursday-Friday Monday, March 8, 2010
Tuesday, March 9, 2010
Wednesday, March 10, 2010
Thursday, March 11, 2010
Friday, march 12, 2010
Louigi Addario-Berry Branching Random Walks and Search Trees Search trees are one of the most commonly used procedures for storing ordered date. It turns out that to analyze their average-case performance turns out to be essentially a problem about extreme positions in branching random walks, which are themselves fundamental probabilistic objects. I will explain this connection, and the fundamentals of the analysis of both objects. Daniel Ahlberg (problem session) First-passage percolation in one dimension: Where does the geodesic go? In this talk we consider standard first-passage percolation on the $\mathbb{Z}\times\{0,1,\ldots,K-1\}^{d-1}$ nearest neighbour graph (which is essentially one-dimensional), for $d,K\geq1$. In the study of this model, the main interest lies in the random time $T(0,\mathbf{n})$ at which the vertex $\mathbf{n}=(n,0,\ldots,0)$ is infected by an infection started at the origin (at time 0). This talk will focus on $\gamma$ (referred to as a geodesic), which denotes the path from the origin to $\mathbf{n}$ of minimal passage time (chosen by some rule when several exists). I will present a one-dimansional behaviour, from which the asymptotic behaviour for $T(0,\mathbf{n})$ and $N(0,\mathbf{n})$, the length of $\gamma$, can be well understood. But the behaviour of $\gamma$ itself is not well understood. In particular, does $P(\mathbf{n}/2\in\gamma)\raw\delta$ as $n\rightarrow\infty$ for some $\delta=\delta(K,d)$? If it does, what can be said about $\delta(K,d)$ as $K\rightarrow\infty$? Nicolas Broutin Cutting down trees with a Markov chainsaw Elisabetta Candellero Phase transitions for random walk, asymptotics on free products of groups Suppose we are given finitely generated groups $\Gamma_1,\dots,\Gamma_m$ equipped with irreducible random walks. We assume that the singular expansions of the corresponding Green functions contain only logarithms or roots as singular terms. We consider transient random walks on the free product $\Gamma_1 \ast \ldots \ast\Gamma_m$, and give a complete classification of the possible asymptotic behaviour of the non-exponential types of $n$-step return probabilities. They either inherit a $n^{-\lambda_i}$-law from one of the free factors $\Gamma_i$, or obey a $n^{-3/2}$-law. Moreover, we characterize the possible phase transitions of the non-exponential types $n^{-\lambda_i}$ in the case $\Gamma_1\ast\Gamma_2$. At the end of the talk, I would like to introduce a couple of open problems about the development of Branching Random Walks on Free Products. (joint work with Lorenz Gilch) Nicolas Curien Recursive triangulations and fragmentation theory Consider the convex regular polygon with n vertices. A triangulation of this polygon is a set of n-3 non crossing diagonals that completely triangulates it. We study random triangulations obtained by adding diagonals progressively, and in particular not sampled for the uniform measure. We establish the convergence of these random triangulations towards a random closed subset of Hausdorff dimension (\sqrt{17}-3)/2. Sander Dommers Ising models on power-law random graphs We study a ferromagnetic Ising model on random graphs with a power-law degree distribution and compute the thermodynamic limit of the pressure when the mean degree is finite (degree exponent $\tau>2$), for which the random graph has a tree-like structure. For this, we adapt and simplify an analysis by Dembo and Montanari, which assumes finite variance degrees ($\tau>3$). We further identify the thermodynamic limits of various physical quantities, such as the magnetization and the internal energy. Predictions by physicists suggest that the critical behavior of these quantities depends sensitively on the degree exponent $\tau>2$. (Joint work with C. Giardina and R. van der Hofstad) Christina Goldschmidt Scaling limits for random trees and graphs In the last 20 years, random combinatorial structures and their limits have been a flourishing area of research in probability. In this course, I hope to show you some of the beautiful theory that arises when considering scaling limits of random trees and, more generally, random graphs. Trees are fundamental objects in combinatorics and the enumeration of different classes of tree is a classical subject which you have doubtless encountered at some point. We will take as our basic object the genealogical tree of a Galton-Watson branching process. (As well as having nice probabilistic properties, this class turns out to include various natural types of random combinatorial tree in disguise.) In the same way as Brownian motion is the universal scaling limit for centred random walks of finite step-size variance, it turns out that all critical Galton-Watson trees with finite offspring variance have a universal scaling limit, Aldous' Brownian continuum random tree (CRT). (In fact, this is not just an analogy!) The CRT is a so-called real tree, a path metric space which is connected and has no cycles. In the first section of this course, I will discuss the convergence to the CRT (and what exactly we mean by convergence of a tree). Along the way, we will see that it is very useful to encode discrete trees using discrete functions. We will make a brief excursion into Ito's theory of Brownian excursions, and will see that the CRT is encoded by a standard Brownian excursion in a way which mirrors the encoding by functions of discrete trees. The second part of the course will deal with more complicated network structures, in which we allow cycles. We will focus on a particular model: the Erdos-Renyi random graph. Since its introduction in 1960, this model has attracted an enormous amount of attention. The set-up is simple: take n nodes and join any pair of them independently with probability p. It is natural to consider the resulting graph as a collection of connected components and to ask about their sizes. It turns out that, if we take p = c/n, there is a phase transition so that (for large n), below a certain critical value of c, the components are all essentially "small", whereas above it, there is one "giant" component which lives on a positive proportion of the vertices, and all of the other components are small. The finer behaviour at the critical point has also been studied in some detail and this is the part on which I will focus. A result of Aldous (who else?!) describes the limits of the rescaled component sizes at the critical point in terms of the lengths of excursions of a Brownian motion with drift. In joint work with Louigi Addario-Berry and Nicolas Broutin, we have been able to give a description of the limiting components as real trees with certain extra "connections" which create the cycle structure for the non-tree components. The distributions which occur are surprisingly simple and we will be able to use the material developed in the first section of the course to understand how they arise. Remco van der Hofstad Critical behavior in inhomogeneous random graphs Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that typical distances are much smaller than the size of the network. Further, many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Therefore, such networks are highly inhomogeneous. Spurred by these empirical findings, models have been proposed for such networks. In this talk, we shall discuss some of the empirical findings of real-world networks, and describe a particular class of random graphs, in which edges are present independently but with unequal edge occupation probabilities that are moderated by appropriate vertex weights. For such models, it is known precisely when there is a giant component, meaning that a positive proportion of the vertices is connected to one another. We discuss what happens at and close to criticality, a problem having strong connections to statistical mechanics. We identify the scaling limit of the connected components ordered by their size. Our results show that, for inhomogeneous random graphs with highly variable vertex degrees, the critical behavior admits a transition when the third moment of the degrees turns from finite to infinite. When the third moment is finite, the largest clusters in a graph of n vertices have size n^{2/3} and the scaling limit equals that on the Erdoes-Renyi random graph. When the third moment is infinite, the largest clusters have size to n^{\alpha} for some \alpha\in (1/2,2/3), and the scaling limit is rather different. Similar phase transitions have been shown to occur for typical distances in such random graphs when the variance of the degrees turns from finite to infinite. Illes Horvath Diffusive bounds and central limit theorem for the true (myopic) self-avoiding walk in three or more dimensions We prove diffusive bounds on the displacement for a class of variants of the myopic self-avoiding random walk in three or more dimensions. A Central limit theorem is also proved in certain Gaussian cases using Varadhan's graded sector condition. (Joint work with B. Toth and B. Veto) Adrien Joseph Phase transition for the heights of a fragmentation tree We are given a conservative, discrete-time fragmentation of the interval (0,1): each interval present at generation k is fragmented at random (but according to a fixed distribution independent of the interval and of the generation) into countably many open intervals which replace the split interval at generation k+1. All the fragmentations are supposed to be independent. One then throws n i.i.d. points uniformly distributed on (0,1). We are interested in the asymptotics of the first generation when every interval contains less than j points (where j is a fixed integer) as the number n of points thrown tends to infinity. We shall see that a phase transition may occur. Malwina Luczak Giant component and cores in random graphs In this lecture, we discuss the phase transition for the emergence of the giant component and the $k$-core in a random (multi)graph on $n$ vertices with a given degree sequence, as $n \to \infty$. Our techniques are based on the analysis of certain balls-and-bins processes, and exploit the properties of empirical distributions of independent random variables, leading to simple proofs. Matthias Meiners An almost sure renewal theorem for branching random walks on the line We consider branching random walks (BRWs) on the real line. These processes can be seen as generalizations of general (CMJ) branching processes. For the latter processes, Nerman (1981) proved a renewal-type theorem. In this theorem, the asymptotic behavior of the paths of general branching processes is determined. We show how an approach using optional lines, which can be seen as the tree-indexed random walk analog of stopping times for ordinary random walks, allow us to extend Nerman's result to BRWs on the line. discrete-time fragmentation of the interval (0,1): each interval present at generation k is fragmented at random (but according to a fixed distribution independent of the interval and of the generation) into countably many open intervals which replace the split interval at generation k+1. All the fragmentations are supposed to be independent. One then throws n i.i.d. points uniformly distributed on (0,1). We are interested in the asymptotics of the first generation when every interval contains less than j points (where j is a fixed integer) as the number n of points thrown tends to infinity. We shall see that a phase transition may occur. Tobias Mueller Hamilton cycles in random geometric graphs Let X_1,..., X_n be independent, uniformly random points from the unit square [0,1]2. I will sketch a proof of the fact that if we add edges between these points one by one by order of increasing edge length then, with probability tending to 1 as the number of points n tends to infinity, the first Hamilton cycle (a cycle that visits every point exactly once) appears at precisely the same time the last vertex of degree less than two disappears. Time permitting, I will speak about a number of additional results on Hamilton cycles in random geometric graphs. (joint work with J. Balogh, B. Bollobas, M. Krivelevich and M. Walters) Eviatar Procaccia Mutually Excited Random Walk Consider two random walks on Z each eating its own favorite kind of cookie. The transition probabilities of each walk is dependent on the number of cookies the other walker has eaten. MERW is an interaction model which introduces non-monotonicity behavior that is not caused by traps. We will start with a quick introduction to random walk in random environment, a subject essential to many of the proofs. We will prove the model has positive speed and show a way to calculate the speed up to any degree of accuracy. Henning Sulzbach A new proof of Donsker's Invariance Principle We give a short introduction to the contraction method and present a new proof of Donsker's Invariance Principle using a contraction argument involving an ideal probability metric of the Zolotarev type in the space of continuous functions on the interval [0,1]. Derek Wan The supermarket model with memory: rapid mixing by coupling We introduce the supermarket model with memory. We define the mixing and rapid mixing of Markov Chains, and the coupling technique. We then show that under certain assumptions, the supermarket model with memory also mixes rapidly. Ariel Yadin LERW on planar graphs: the scaling limit of a random branch Abstract: Consider a uniform spanning of a finite graph. It is well known that the unique path in this tree between two fixed vertices x and y has the same distribution as the LERW from x to y (Loop-Erased Random Walk). One can consider this process on a growing sequence of finite subgraphs of Z2. Lawler, Schramm and Werner proved that the LERW (or random branch) on Z2 converges to SLE(2). Their proof utilizes the lattice structure. We prove that this convergence is universal, in the following sense: If G is any planar graph, such that the random walk on G converges to Brownian motion, then the LERW on G converges to SLE(2). This generalizes Lawler, Schramm and Werner's result to a large class of planar graphs. A notable example is the (random) graph obtained by taking the infinite component of super-critical percolation on Z2. I will not assume prior knowledge of LERW or SLE in this talk. (Joint work with Amir Yehudayoff) Last updated
18-mrt-2010, |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
P.O. Box 513, 5600 MB Eindhoven, The Netherlands |