We construct efficiently computable sequences of random-looking graphs that preserve properties of the canonical random graphs G(2(n,)p(n))(.) We focus on first-order graph properties, namely properties that can be expressed by a formula phi in the language where variables stand for vertices and the only relations are equality and adjacency (e.g. having an isolated vertex is a first-order property there exists x for all y(-EDGE(x,y))). Random graphs are known to have remarkable structure w.r.t. first order properties, as indicated by the following 0/1 law: for a variety of choices of p(n), any fixed first-order property phi holds for G(2(n), p(n)) with probability tending either to 0 or to 1 as n grows to infinity. We first observe that similar 0/1 laws are satisfied by G(2(n), p(n)) even w.r.t. sequences of formulas {phi(n)}(n is an element of N) with bounded quantifier depth, depth(phi(n)) <= n/lg(1/p(n)). We also demonstrate that 0/1 laws do not hold for random graphs w.r.t. properties of significantly larger quantifier depth. For most choices of p(n), we present efficient constructions of huge graphs with edge density nearly p(n) that emulate G(2(n),p(n)) by satisfying Theta(n/lg(1/p(n))-0/1 laws. We show both probabilistic constructions (which also have other properties such as K-wise independence and being computationally indistinguisbable from G(N,p(n))), and deterministic constructions where for each graph size we provide a specific graph that captures the properties of G(2n, p(n)) for slightly smaller quantifier depths.
