Random graphs and covering graphs of posets

Abstract

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+η(n),where η(n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )≥k ₀ n ^1+η(n).In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+η(n), where η(n)→0, thenc(G _p )=o(n ^1+η(n)), almost surely.