Random graphs and covering graphs of posets

As some of the main practitioners of the associated art demonstrate once again in this very interesting paper, for finite graphs and posets the essential unmanageability of search-and-exhibit methods can often be circumvented by the introduction of probability and statistical tools via the construction of special random-variables and analysis of their associated densities to retrieve desired conclusions. Thus if a probability can be estimated to be positive then this often means that an existence result has been obtained. Thus, using the main result of the paper the authors show somewhat readily that (Nešetřil and Rödl): for any integer g, there is a graph G of girth g which is not a covering graph. Given a (finite) graph G, c(G) is the minimum number of edges which must be deleted in order to make G into a covering graph of some poset P ((x,y) is an edge of G if and only if x covers y or y covers x in P). If \(G_ p=G_{p,n}\) is obtained by joining pairs of n distinguishable vertices independently, each pair joined with probability \(p=p(n)\) then a probability space is constructed in which G's have measures as \(G_{p,n}'s\). The main theorem of the paper is the following best possible result: suppose \(p=n^{-1+\eta (n)}\), where \(0<\eta_ 0\leq \eta (n)\leq 1\) for some \(\eta\). Then there is a constant \(K_ 0=K_ 0(\eta_ 0)\) such that for almost every \(G_ p\), \(c(G_ p)\geq K_ 0n^{1+\eta (n)}=K_ 0pn^ 2\). Here the ``almost every terminology means that \(\lim_{n\to \infty}\Pr \{c(G_{n,p})\geq K_ on^{1+\eta (n)}\}=1\).

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Random graphs and covering graphs of posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580382)