×

The width of random graph orders. (English) Zbl 0838.60008

Summary: The random graph order \(P_{n,p}\) is obtained from a random graph \(G_{n,p}\) on \([n]\) by treating an edge between vertices \(i\) and \(j\), with \(i < j\) in \([n]\), as a relation \(i\prec j\), and taking the transitive closure. This paper forms part of a project to investigate the structure of the random graph order \(P_{n,p}\) throughout the range of possible functions \(p = p(n)\). We estimate the width of the random order throughout the range. For \(p \geq 50 (\log \log n)^2/ \log n\), we obtain a very precise estimate which is almost exactly \(\sqrt {2 \log n/ \log (1/q)}\), where \(q = 1 - p\). If \(p \log n \to 0\) and \(pn \to \infty\), we show that the width is almost surely close to some function of the form \(C(p) p^{-1}\), with \(1.455 < C(p) < 2.428\), where \(C(p)\) depends on \(n\) only via \(p\). We leave open the problem of proving that \(C(p)\) tends to a constant as \(p \to 0\).

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite