RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 1990 Volume 26, Issue 1, Pages 90–98 (Mi ppi597)

This article is cited in 3 papers

Large Systems

Bounds on Probability of Connectedness of a Random Graph

V. P. Polesskii


Abstract: Let $(M,q)$ be a random matroid, i.e., a matroid $M$ on the set $E$ whose elements are deleted independently of one another with probability $q$, and let $P(M,q)$ be the probability that the rank of a random subset of the set $E$ is equal to the rank $r$ of the matroid $M$. The following effective and exact lower bound on the probability $P(M,q)$ is proved: $\prod\limits_1^r(1-q^{\delta_i})\le P(M,q)$ where $(\delta_1\dots,\delta_r)$ is the so-called base spectrum of the matroid $M$, $\sum\limits_1^r\delta_i=|E|$.

UDC: 621.391.1:519.17

Received: 15.04.1987
Revised: 01.03.1989


 English version:
Problems of Information Transmission, 1990, 26:1, 75–82

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024