Acyclic orientations of random graphs

An acyclic orientation of an undirected graph is an orientation of its edges such that the resulting directed graph contains no cycles. The random graph G(n,p) is a probability space consisting of subgraphs of K-n that are obtained by selecting each K-n-edge with independent probability p. The random graph Q(2,p)(n) is defined analogously and consists of subgraphs of the n-cube, Q(2)(n). In this paper we first derive a bijection between certain equivalence classes of permutations and acyclic orientations. Second, we present a lower and an upper bound on the r.v. a(G(n,p)) that counts the number of acyclic orientations of G(n,p). Finally we study the distribution of a(G(n,p)) and a(Q(2,p)(n)) and show that log(2)a(G(n,p)) and log(2)a(Q(2,p)(n)) are sharply concentrated at their respective expectation values. (C) 1998 Academic Press.