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 prob ability p. The random graph Q(2,p)(n) is defined analogously and consi sts of subgraphs of the n-cube, Q(2)(n). In this paper we first derive a bijection between certain equivalence classes of permutations and a cyclic 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 conc entrated at their respective expectation values. (C) 1998 Academic Pre ss.