Search

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the graph. Suppose also that $r < m$, where $2m$ is the average degree. We determine a critical function $a_c(t)$ such that when $a(t) \gg a_c(t)$, complete infection occurs with high probability as $t \rightarrow \infty$, but when $a(t) \ll a_c (t)$, then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to $a(t)$., This paper is significantly different to the previous version

This paper studies a higher dimensional generalization of Frieze's $\zeta(3)$-limit theorem in the Erd\"os-R\'enyi graph process. Frieze's theorem states that the expected weight of the minimum spanning tree converges to $\zeta(3)$ as the number of vertices goes to infinity. In this paper, we study the $d$-Linial-Meshulam process as a model for random simplicial complexes, where $d=1$ corresponds to the Erd\"os-R\'enyi graph process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in $O(n^{d-1})$., Comment: 24 pages

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

We consider consecutive random subdivision of polygons described as follows. Given an initial convex polygon with $d\ge 3$ edges, we choose a point at random on each edge, such that the proportions in which these points divide edges are i.i.d. copies of some random variable $\xi$. These new points form a new (smaller) polygon. By repeatedly implementing this procedure we obtain a sequence of random polygons. The aim of this paper is to show that under very mild non-degenerateness conditions on $\xi$, the shapes of these polygons eventually become "flat" The convergence rate to flatness is also investigated; in particular, in the case of triangles ($d=3$), we show how to calculate the exact value of the rate of convergence, connected to Lyapunov exponents. Using the theory of products of random matrices our paper greatly generalizes the results of Volkov (2013) which are achieved mostly by using ad hoc methods., Comment: 35 pages, 2 figures

Staircase tableaux are combinatorial objects that were first introduced due to a connection with the asymmetric simple exclusion process (ASEP) and Askey-Wilson polynomials. Since their introduction, staircase tableaux have been the object of study in many recent papers. Relevant to this paper, Hitczenko and Janson proved that distribution of parameters on the first diagonal is asymptotically normal. In addition, they conjectured that other diagonals would be asymptotically Poisson. Since then, only the second and the third diagonal were proven to follow the conjecture. This paper builds upon those results to prove the conjecture for the kth diagonal where k is fixed. In particular, we prove that the distribution of the number of α's (β's) on the kth diagonal, k > 1, is asymptotically Poisson with parameter 1/2. In addition, we prove that symbols on the kth diagonal are asymptotically independent and thus, collectively follow the Poisson distribution with parameter 1. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 795–818, 2016

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016

We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014

Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].

A recent result of Condon, Kim, K\"{u}hn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. Moreover, this implies that for any $\alpha>0$ and an $n$-vertex almost $\alpha n$-regular graph $G$, with high probability, the randomly perturbed graph $G\cup \mathbf{G}(n,O(\frac{1}{n}))$ has an approximate decomposition into all collections of bounded degree trees of size at most $(1-o(1))n$ simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey-Tur\'an theory and the randomly perturbed graph model., Comment: 15 pages

Let $\{G_i\}$ be the random graph process: starting with an empty graph $G_0$ with $n$ vertices, in every step $i \geq 1$ the graph $G_i$ is formed by taking an edge chosen uniformly at random among the non-existing ones and adding it to the graph $G_{i - 1}$. The classical `hitting-time' result of Ajtai, Koml\'{o}s, and Szemer\'{e}di, and independently Bollob\'{a}s, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches $2$, that is if $\delta(G_i) \ge 2$ then $G_i$ is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for $m \geq (\tfrac{1}{6} + o(1))n\log n$ edges, the $2$-core of the graph $G_m$ remains Hamiltonian even after an adversary removes $(\tfrac{1}{2} - o(1))$-fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings., Comment: 23 pages; small updates to the paper after anonymous reviewers' reports

A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(n,p) for a wide range of edge-probabilities p=p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function., 25 pages

An oriented tree $T$ on $n$ vertices is unavoidable if every tournament on $n$ vertices contains a copy of $T$. In this paper we give a sufficient condition for $T$ to be unavoidable, and use this to prove that almost all labelled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on $n + o(n)$ vertices contains a copy of every oriented tree $T$ on $n$ vertices with polylogarithmic maximum degree, improving a result of K\"uhn, Mycroft and Osthus.

Consider the random graph G(Pn,r) whose vertex set Pn is a Poisson point process of intensity n on (-12,12]d,d2. Any two vertices Xi,XjPn are connected by an edge with probability g(d(Xi,Xj)r), independently of all other edges, and independent of the other points of Pn. d is the toroidal metric, r > 0 and g:0,)0,1] is non-increasing and =dg(|x|)dx ) does not have any isolated nodes satisfies lim?nnMndlog?n=1. Let =inf?{x > 0:xg(x)> 1}, and be the volume of the unit ball in d. Then for all >, G(Pn,(log?nn)1d) is connected with probability approaching one as n. The bound can be seen to be tight for the usual random geometric graph obtained by setting g=10,1]. We also prove some useful results on the asymptotic behavior of the length of the edges and the degree distribution in the connectivity regime. The results in this paper work for connection functions g that are not necessarily compactly supported but satisfy g(r)=o(r-c).

Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $\Delta=\Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $\sigma$, in terms of $n$, $k$ and $\Delta$, which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $\sigma(n) = \omega(n^{1/k^2} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ and $\Delta= \Omega(n^{1/2})$, then the same conclusion holds provided that $\sigma=\omega(\Delta)$. We also give related results for other bounds on $\Delta$, when $k$ is constant or a strictly increasing function of $n$.

Let $H$ be a fixed graph and $\mathcal{G}$ a subcritical graph class. In this paper we show that the number of occurrences of $H$ (as a subgraph) in a uniformly at random graph of size $n$ in $\mathcal{G}$ follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations. As a case study, we get explicit expressions for the number of triangles and cycles of length four for the family of series-parallel graphs., Comment: 32 pages, 6 figures

Permutations that avoid given patterns are among the most classical objects in combinatorics and have strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Madras and Pehlivan [25] and Miner and Pak [29] as well as to understand many of the interesting phenomena that had previously gone unexplained. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 394-419, 2017

We continue our study of the full set of translation-invariant splitting Gibbs measures TISGMs, translation-invariant tree-indexed Markov chains for the q-state Potts model on a Cayley tree. In our previous work Kulske et al., J Stat Phys 156 2014, 189-200 we gave a full description of the TISGMs, and showed in particular that at sufficiently low temperatures their number is 2q-1. In this paper we find some regions for the temperature parameter ensuring that a given TISGM is non-extreme in the set of all Gibbs measures. In particular we show the existence of a temperature interval for which there are at least 2q-1+q extremal TISGMs. For the Cayley tree of order two we give explicit formulae and some numerical values. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 636-678, 2017

Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollob\'as and Morris considered graph bootstrap percolation for $G = G(n,p)$ and studied the critical probability $p_c(n,K_r)$, for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time $t$ for all $1 \leq t \leq C \log\log n$., Comment: 18 pages, 3 figures

The classical Corr adi-Hajnal theorem claims that every n-vertex graph G with (G) 2n=3 contains a triangle factor, when 3jn. In this paper we asymptotically determine the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with (G) = o(n) and (G) (1=2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratic many edges, and (G) (1=2 +o(1))n, then G has a Kr-factor for n suciently large. We also propose many related open problems whose solutions could show a relationship with RamseyTur an theory. Additionally, we also consider a fractional variant of the Corr adi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t2 (0; 1) and w : E(Kn)! [0; 1]. We call a triangle in Kn heavy if the sum of the weights on its edges is more than 3t. We prove that if 3jn and w is such that for every vertex v the sum of w(e)

We consider a model for complex networks that was introduced by Krioukov et al. (Phys Rev E 82 (2010) 036106). In this model, N points are chosen randomly inside a disk on the hyperbolic plane according to a distorted version of the uniform distribution and any two of them are joined by an edge if they are within a certain hyperbolic distance. This model exhibits a power-law degree sequence, small distances and high clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power-law and ν controls the average degree. In this paper we focus on the probability that the graph is connected. We show the following results. For α > 1/2 and ν arbitrary, the graph is disconnected with high probability. For α < 1/2 and ν arbitrary, the graph is connected with high probability. When α = 1/2 and ν is fixed then the probability of being connected tends to a constant f(ν) that depends only on ν, in a continuous manner. Curiously, f(ν) = 1 for ν ≥ Π while it is strictly increasing, and in particular bounded away from zero and one, for 0 < ν < Π. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 65–94, 2016.

Suppose that are independent identically distributed Bernoulli random variables with mean p, so and . Any estimate of p has relative error . This paper builds a new estimate of p with the remarkable property that the relative error of the estimate does not depend in any way on the value of p. This allows the easy construction of exact confidence intervals for p of any desired level without needing any sort of limit or approximation. In addition, is unbiased. For ∊ and δ in (0, 1), to obtain an estimate where , the new algorithm takes on average at most samples. It is also shown that any such algorithm that applies whenever requires at least samples on average. The same algorithm can also be applied to estimate the mean of any random variable that falls in . The used here employs randomness external to the sample, and has a small (but nonzero) chance of being above 1. It is shown that any nontrivial where the relative error is independent of p must also have these properties. Applications of this methodology include finding exact p-values and randomized approximation algorithms for # P complete problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016

In 2002, Bollobas and Scott posed the following problem: for an integer k≥2 and a graph G of m edges, what is the smallest f(k, m) such that V(G) can be partitioned into V 1,…,Vk in which e(Vi∪Vj)≤f(k,m) for all 1≤i≠j≤k, where e(Vi∪Vj) denotes the number of edges with both ends in Vi∪Vj? In this paper, we solve this problem asymptotically by showing that f(k,m)≤m/(k−1)+o(m). We also show that V(G) can be partitioned into V1,…,Vk such that e(Vi∪Vj)≤4m/k2+4Δ/k+o(m) for 1≤i≠j≤k, where Δ denotes the maximum degree of G. This confirms a conjecture of Bollobas and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017

In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph G(n, p), where is a fixed constant. Our proof is based on bounding the characteristic function of the number of triangles, and uses several different conditioning arguments for handling different ranges of t. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016

We prove a conjecture dating back to a 1978 paper of D.R. Musser [11], namely that four random permutations in the symmetric group Sn generate a transitive subgroup with probability for some independent of n, even when an adversary is allowed to conjugate each of the four by a possibly different element of . In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of An or except for probability as . The analysis is closely related to the following random set model. A random set is generated by including each independently with probability . The sumset is formed. Then at most four independent copies of are needed before their mutual intersection is no longer infinite. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015

We study the Maker-Breaker H-game played on the edge set of the random graph . In this game two players, Maker and Breaker, alternately claim unclaimed edges of , until all edges are claimed. Maker wins if he claims all edges of a copy of a fixed graph H; Breaker wins otherwise. In this paper we show that, with the exception of trees and triangles, the threshold for an H-game is given by the threshold of the corresponding Ramsey property of with respect to the graph H. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015

A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph ${\mathcal D}(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $p \gg \log n/\sqrt{n}$, then a.a.s. every subdigraph of ${\mathcal D}(n,p)$ with minimum out-degree and in-degree at least $(1/2 + o(1)) n p$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs., Comment: 35 pages, 1 figure

Two models of a random digraph on n vertices, D(n; Prob(arc) = p) and D(n; number of arcs = m) are studied. In 1990, Karp for D(n;p) and independently T. Luczak for D(n;m = cn) proved that for c > 1, with probability tending to 1, there is an unique strong component of size of order n. Karp showed, in fact, that the giant component has likely size asymptotic to n 2 , where = (c) is the unique positive root of 1 = e c . In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector n (c), (c) := ( 2 ;c 2 ) and two distinct 2 2 covariance matrices, nB(c) and n B(c) +c( 0 (c)) T ( 0 (c))) . To this end, we introduce and analyze a randomized deletion process which determines the directed (1; 1)-core, the maximal digraph with minimum in-degree and out-degree at least 1. This (1; 1)-core contains all nontrivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the (1; 1)-core, those outside the largest strong component, are of polylog order, thus dwarfed by anticipated uctuations, on the scale of n 1=2 , of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.

Let f be an edge ordering of Kn: a bijection . For an edge , we call f(e) the label of e. An increasing path in Kn is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvatal and Komlos raised the question of estimating m(n): the minimum value of S(f) over all orderings f of Kn. The best known bounds on m(n) are , due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n – 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/ e. We also prove that with probability 1- o(1), there is an increasing path of length at least 0.85 n, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015

In this paper we determine the threshold for d-collapsibility in the probabilistic model Xdn,p of d-dimensional simplicial complexes. A lower bound for this threshold p=i¾?dn was established in Aronshtam and Linial, Random Struct. Algorithms 46 2015 26-35, and here we show that this is indeed the correct threshold. Namely, for every c>i¾?d, a complex drawn from Xdn,cn is asymptotically almost surely not d-collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260-269, 2016

The area of judicious partitioning considers the general family of partitioning problems in which one seeks to optimize several parameters simultaneously, and these problems have been widely studied in various combinatorial contexts. In this paper, we study essentially the most fundamental judicious partitioning problem for directed graphs, which naturally extends the classical Max Cut problem to this setting: we seek bipartitions in which many edges cross in each direction. It is easy to see that a minimum outdegree condition is required in order for the problem to be nontrivial, and we prove that every directed graph with M edges and minimum outdegree at least two admits a bipartition in which at least (1/6 + o(1))M edges cross in each direction. We also prove that if the minimum outdegree is at least three, then the constant can be increased to 1/5. If the minimum outdegree tends to infinity with N, then the constant increases to 1/4. All of these constants are best-possible, and provide asymptotic answers to a question of Alex Scott., 23 pages

The classical result of Erdo˝s and R´enyi shows that the random graph G(n,p) experiencessharp phase transition around p = 1n – for any ǫ > 0 and p = 1−ǫn , all connected componentsof G(n,p) are typically of size O ǫ (logn), while for p = 1+ǫn , with high probability there existsa connected component of size linear in n. We provide a very simple proof of this fundamentalresult; in fact, we prove that in the supercritical regime p = 1+ǫn , the random graph G(n,p)contains typically a path of linear length. We also discuss applications of our technique to otherrandom graph models and to positional games. 1 Introduction In their groundbreaking paper [5] from 1960, Paul Erd˝os and Alfr´ed R´enyi made the followingfundamental discovery: the random graph G(n,p) has a remarkable phase transition around theedge probability p(n) = 1n . For any constant ǫ > 0, if p = 1−ǫn , then the random graph G(n,p)has whp 1 all connected components of size at most logarithmic in n, while for p =

Let $t$ be a rooted tree and $n_i(t)$ the number of nodes in $t$ having $i$ children. The degree sequence $(n_i(t),i\geq 0)$ of $t$ satisfies $\sum_{i\ge 0} n_i(t)=1+\sum_{i\ge 0} in_i(t)=|t|$, where $|t|$ denotes the number of nodes in $t$. In this paper, we consider trees sampled uniformly among all trees having the same degree sequence $\ds$; we write $`P_\ds$ for the corresponding distribution. Let $\ds(\kappa)=(n_i(\kappa),i\geq 0)$ be a list of degree sequences indexed by $\kappa$ corresponding to trees with size $\nk\to+\infty$. We show that under some simple and natural hypotheses on $(\ds(\kappa),\kappa>0)$ the trees sampled under $`P_{\ds(\kappa)}$ converge to the Brownian continuum random tree after normalisation by $\nk^{1/2}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollobas in 1968, and is defined as follows. Given a graph H, and a set \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}G \subset E(K_n)\end{align*} \end{document} **image** of initially ‘infected’ edges, we infect, at each time step, a new edge e if there is a copy of H in \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_n\end{align*} \end{document} **image** such that e is the only not-yet infected edge of H. We say that G percolates in the H-bootstrap process if eventually every edge of \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_n\end{align*} \end{document} **image** is infected. The extremal questions for this model, when H is the complete graph \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_r\end{align*} \end{document} **image** , were solved (independently) by Alon, Kalai and Frankl almost thirty years ago. In this paper we study the random questions, and determine the critical probability \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}p_c(n,K_r)\end{align*} \end{document} **image** for the \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_r\end{align*} \end{document} **image** -process up to a poly-logarithmic factor. In the case \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}r = 4\end{align*} \end{document} **image** we prove a stronger result, and determine the threshold for \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}p_c(n,K_4)\end{align*} \end{document} **image** . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 (Supported by CNPq bolsa de Produtividade em Pesquisa.)

We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the notion of convergence of dense graph sequences, defined by Lovasz and Szegedy (J. Combin. Theory Ser B 96 (2006) 933–957). We investigate how the limit object evolves under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limit object from its initial state up to the stationary state, which is described in the companion paper (Rath and Szakacs, in press). In our proofs we use the theory of exchangeable arrays, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits subaging. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.

In this paper, we prove the semi-circular law for the eigenvalues of regular random graph Gn,d in the case d →∞, complementing a previous result of McKay for fixed d. We also obtain a upper bound on the infinity norm of eigenvectors of Erdős–Renyi random graph G(n,p), answering a question raised by Dekel–Lee–Linial. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2013 Wiley Periodicals, Inc.

This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erdős-Renyi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012 © 2012 Wiley Periodicals, Inc.

The classical result in the theory of random graphs, proved by Erdős and Renyi in 1960, concerns the threshold for the appearance of the giant component in the random graph process. We consider a variant of this problem, with a Ramsey flavor. Now, each random edge that arrives in a sequence of rounds must be colored with one of r colors. The goal can be either to create a giant component in every color class, or alternatively, to avoid it in every color. One can analyze the offline or online setting for this problem. In this paper, we consider all these variants and provide nontrivial upper and lower bounds; in certain cases (like online avoidance) the obtained bounds are asymptotically tight. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011 © 2011 Wiley Periodicals, Inc.

In this paper we analyze: (i) a storage allocation algorithm (D.E. Knuth, The Art of Computer Programming-Vol. I, Addison-Wesley, Reading, MA, 1969, Ex. 2.2.2.13) which permits one to maintain two stacks inside a shared (continuous) memory area of a fixed size, and (ii) the well-known banker algorithm which plays a fundamental role in parallel processing (J. Francon, Combinatoire et Parallelisme; Journees Informatique et Mathematique; Lumigny, October 15-17, 1987; A. N. Habermann, in Current Trends in Programming Methodology, Vol. 3, K. M. Chandy and R. T. Yeh, Eds., Prentice-Hall, Englewood Cliffs, NJ, 1987; J. Peterson and A. Silberschatz, Operating Systems Concepts, Addison-Wesley, Reading, MA, 1983). The natural formulation of the problems to be solved here is in terms of random walks. For (i) the random walk Ym(-) takes place in a triangle in a two-dimensional lattice space with two reflecting barriers along the axes (a deletion has no effect on an empty stack) and one absorbing barrier along the diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (ii) the random walk takes place in a rectangle with broken corner and has four reflecting barriers and one absorbing barrier (see Fig. 10). With the help of diffusion techniques, we obtain, asymptotically as m: ∞. the distributions of the hitting place (Zm) and hitting time (Tm) on the absorbing boundary. the joint distribution of Zm and Tm. the distribution P[Ym(n) ≦ ym, n < Tm].