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

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.