Bounds on probability of connectedness of a random graph (Q803174)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Bounds on probability of connectedness of a random graph
scientific article

    Statements

    Bounds on probability of connectedness of a random graph (English)
    0 references
    0 references
    1990
    0 references
    Let G(V,E) be a connected graph with the vertex set V and set of edges E and M(E,T) its cyclic matroid. Acyclic subgraphs of G are the independent sets of the matroid M and spanning trees are the bases of M. The question of connectivity of a random graph (G,Q) obtained by random deleting edges of G is interpreted as determining a rank of a random matroid (M,Q) defined by random deleting of edges from M in the same way as in the graph G. By P(M,Q) is denoted the probability that a random subset of E includes a basis of the matroid M. The main result of this paper is an estimation of P(M,Q) in terms of the values of basic spectrum of the matroid M, defined by means of ranks of iterated sums of the matroid M. The probability P(M,Q) can be estimated as \(\prod^{r}_{i=1}(1- q^{\delta_ i})\leq P(M,Q)\) where q is a probability of deleting a single edge from G.
    0 references
    random matroid
    0 references

    Identifiers