Random graphs and covering graphs of posets |
| |
| Authors: | Béla Bollobás Graham Brightwell Jaroslav Nešetřil |
| |
| Affiliation: | (1) Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana, USA;(2) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, England;(3) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, England;(4) Department of Mathematics, Charles University, Prague, Czechoslovakia |
| |
| 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 k0>0 such that, for a.e. Gp, c(Gp) k0n1+(n).In other words, to make Gp 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(Gp)=o(n1+(n)), almost surely.Partially supported by MCS Grant 8104854. |
| |
| Keywords: | 06A10 60C05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
