|
Problemy Peredachi Informatsii, 1993, Volume 29, Issue 4, Pages 58–66
(Mi ppi201)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Large Systems
Lower Bounds on Full Rank Probability in Random Matroids
V. P. Polesskii
Abstract:
Let $M$ be a matroid on the set $E$ whose elements are missing jointly independently with probability $Q$. The probability $P(M,q)$ of full rank of a random matroid $(M,q)$ is the probability that the random set $(E,q)$ contains a base of this matroid. It is proved that every partition of $E$ into independent sets of $M$ that contains a base of $M$ generates an effectively computable lower estimate of $P(M,q)$ in terms of the conjugate partition. A partition that yields the best such estimate is determined.
Received: 17.02.1993
Citation:
V. P. Polesskii, “Lower Bounds on Full Rank Probability in Random Matroids”, Probl. Peredachi Inf., 29:4 (1993), 58–66; Problems Inform. Transmission, 29:4 (1993), 350–357
Linking options:
https://www.mathnet.ru/eng/ppi201 https://www.mathnet.ru/eng/ppi/v29/i4/p58
|
Statistics & downloads: |
Abstract page: | 225 | Full-text PDF : | 100 | First page: | 1 |
|