Abstract. In the random [Formula: see text]-neighbor bootstrap percolation process on a graph [Formula: see text], a set of initially infected vertices is chosen at random by retaining each vertex of [Formula: see text] independently with probability [Formula: see text], and ‘healthy’ vertices get infected in subsequent rounds if they have at least [Formula: see text] infected neighbors. A graph [Formula: see text] percolates if every vertex becomes eventually infected. A central problem in this process is to determine the critical probability [Formula: see text], at which the probability that [Formula: see text] percolates passes through one half. In this paper, we study random 2-neighbor bootstrap percolation on the [Formula: see text]-dimensional Hamming graph [Formula: see text], which is the graph obtained by taking the Cartesian product of [Formula: see text] copies of the complete graph [Formula: see text] on [Formula: see text] vertices. We extend a result of Balogh and Bollobás [ Probab. Theory Related Fields, 134 (2006), pp. 624–648. MR2214907] about the asymptotic value of the critical probability [Formula: see text] for random 2-neighbor bootstrap percolation on the [Formula: see text]-dimensional hypercube [Formula: see text] to the [Formula: see text]-dimensional Hamming graph [Formula: see text], determining the asymptotic value of [Formula: see text], up to multiplicative constants (when [Formula: see text]), for arbitrary [Formula: see text] satisfying [Formula: see text].

Abstract. We study the random planar graph process introduced by Gerke et al. [ Random Structures Algorithms, 32 (2008), pp. 236–261]: Begin with an empty graph on [Formula: see text] vertices, consider the edges of the complete graph [Formula: see text] one by one in a random ordering, and at each step add an edge to a current graph only if the graph remains planar. They studied the number of edges added up to step [Formula: see text] for “large" [Formula: see text]. In this paper we extend their results by determining the asymptotic number of edges added up to step [Formula: see text] in the early evolution of the process when [Formula: see text]. We also show that this result holds for a much more general class of graphs, including outerplanar graphs, planar graphs, and graphs on surfaces.

Let A(n,m) be a graph chosen uniformly at random from the class of all vertex-labelled outerplanar graphs with n vertices and m edges. We consider A(n,m) in the sparse regime when m=n/2+s for s=o(n). We show that with high probability the giant component in A(n,m) emerges at m=n/2+O (n^{2/3}) and determine the typical order of the 2-core. In addition, we prove that if s=ω(n^{2/3}), with high probability every edge in A(n,m) belongs to at most one cycle.