|
Problemy Peredachi Informatsii, 1990, Volume 26, Issue 1, Pages 90–98
(Mi ppi597)
|
|
|
|
This article is cited in 3 scientific papers (total 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|$.
Received: 15.04.1987 Revised: 01.03.1989
Citation:
V. P. Polesskii, “Bounds on Probability of Connectedness of a Random Graph”, Probl. Peredachi Inf., 26:1 (1990), 90–98; Problems Inform. Transmission, 26:1 (1990), 75–82
Linking options:
https://www.mathnet.ru/eng/ppi597 https://www.mathnet.ru/eng/ppi/v26/i1/p90
|
Statistics & downloads: |
Abstract page: | 479 | Full-text PDF : | 357 |
|