# Random Structures & Algorithms

Random Structures & Algorithms > 36 > 1 > 80 - 89

*H*(2,

*n*) consists of the

*n*

^{2}vertices (

*i*,

*j*), 1 ≤

*i*,

*j*≤

*n*, two vertices being adjacent when they share a common coordinate. We examine random subgraphs of

*H*(2,

*n*) in percolation with edge probability

*p*, in such a way that the average degree satisfies 2(

*n*− 1)

*p*= 1 + ε. Previous work [8] has shown that in the barely supercritical region

*n*

^{−2/3}ln

^{1/3}

*n*≪ ε ≪ 1, the largest...

Random Structures & Algorithms > 36 > 1 > 26 - 45

Random Structures & Algorithms > 36 > 1 > 90 - 109

*p‐quasi‐random*if it satisfies a long list of the properties that hold in

*G*(

*n*,

*p*) with high probability,...

Random Structures & Algorithms > 36 > 1 > 57 - 79

*G*

_{n,m}according to certain rules without creating a monochromatic copy of some fixed forbidden graph

*H*. Although...

Random Structures & Algorithms > 36 > 1 > 11 - 25

*r*≥ 2 and a collection of

*r*‐uniform hypergraphs $\cal{H}$. What is the minimum number of edges in an $\cal{H}$‐free

*r*‐uniform hypergraph with chromatic number greater than

*k*? We investigate this question for various $\cal{H}$. Our results include the following: An (

*r*,

*l*)‐system is an

*r*‐uniform hypergraph with every two edges sharing at most

*l*vertices. For

*k*sufficiently large, there is an (

*r*,

*l*...

Random Structures & Algorithms > 36 > 1 > 46 - 56

*k*≥ 2,

*r*≥ 2, and

*g*≥ 3, there exist

*r*‐uniform non‐

*k*‐colorable hypergraphs of girth at least

*g*with maximum degree at most ⌈

*r*

*k*

^{r‐1}ln

*k*⌉. This is only 4

*r*

^{2}ln

*k*times greater than the lower bound by Erdős and Lovász (Colloquia Math Soc...

Random Structures & Algorithms > 36 > 1 > 5 - 10

^{n}. The set determines a Voronoĭ tiling of ℝ

^{n}. Construct an infinite graph with vertex set and edges joining vertices when the corresponding Voronoĭ cells share a (

*n*− 1)‐dimensional boundary face. We consider bond percolation models on obtained by declaring each edge

*x*

*y*of open...

Random Structures & Algorithms > 36 > 2 > 185 - 217

*Z*

^{d}with parameter

*p*, and a classical random graph

*G*(

*n*,

*c*/

*n*). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the...

Random Structures & Algorithms > 36 > 2 > 218 - 250

*n*− 1} and putting

*i*below

*j*if there is a path

*i*=

*i*

_{1}…

*i*

_{k}=

*j*in the graph with

*i*

_{1}< … <

*i*

_{k}. Rideout and Sorkin Phys. Rev. D 63 (2001) 104011 provide computational evidence that suitably normalized sequences of random graph orders have a “continuum limit.” We confirm...

Random Structures & Algorithms > 36 > 2 > 111 - 148

*G*(

*n*,

*p*) around the critical probability

*p*

_{c}= is well understood. When

*p*= (1 +

*O*(

*n*

^{1/3}))

*p*

_{c}the components are roughly of size

*n*

^{2/3}and converge, when scaled by

*n*

^{−2/3}, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When

*p*= (1 ‐ ϵ(

*n*))

*p*

_{c}with ϵ(

*n*)

*n*

^{1/3}→∞ (the subcritical regime) the...

Random Structures & Algorithms > 36 > 2 > 149 - 184

*d*‐uniform hypergraph

*H*

_{d}(

*n*,

*p*) with edge probability

*p*=

*c*/$\left(\matrix{n-1 \cr d-1 }\right)$, where

*c*> (

*d*‐ 1)

^{‐1}is a constant. The proof relies on a new, purely probabilistic approach. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010

Random Structures & Algorithms > 36 > 3 > 251 - 272

*𝔾*

_{n,p}uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We assume that there are

*β*

*Δ*colors available, where

*Δ*is the maximum degree of the graph, and we wish to determine the least

*β*=

*β*(

*p*) such that the distribution is close to uniform in

*O*(

*n*log

*n*) steps of the chain. This problem has been previously...

Random Structures & Algorithms > 36 > 3 > 315 - 340

*n*by

*n*torus, in which every vertex is in one of two states and, at each time step

*t*, every vertex goes into the state the majority of its neighbors had at time

*t*‐ 1 with a small chance

*p*of error independently of all other events. We shall show that, if

*n*is fixed and

*p*is sufficiently small, then the process...

Random Structures & Algorithms > 36 > 3 > 341 - 371

Random Structures & Algorithms > 36 > 3 > 273 - 314

*k*≥ 1 in several kinds of series‐parallel labeled graphs of size

*n*satisfy a central limit theorem with mean and variance proportional to

*n*, and quadratic exponential tail estimates. We further prove a corresponding theorem for the number of nodes of degree two in labeled planar graphs. The proof method is based on generating functions and singularity...

Random Structures & Algorithms > 36 > 4 > 477 - 487

Random Structures & Algorithms > 36 > 4 > 373 - 463

Random Structures & Algorithms > 36 > 4 > 464 - 476

*q*‐colorings of the

*n*‐vertex complete

*b*‐ary tree when 3 ≤

*q*≤

*b*/(2ln

*b*). We give both upper and lower bounds on the mixing time. Our upper bound is

*n*

^{O(b/ log b)}and our lower bound is

*n*

^{Ω(b/(q log b))}, where the constants implicit in the

*O*() and Ω() notation do not depend upon

*n*,

*q*or

*b*. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010

Random Structures & Algorithms > 37 > 1 > 1 - 24

*n*labeled vertices. At each round we are presented with

*K*=

*K*(

*n*) edges, chosen uniformly at random from the missing ones, and are asked to add one of them to the current graph. The goal is to create a Hamilton cycle as soon as possible. We show that this problem...