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

Probl. Peredachi Inf., 1993 Volume 29, Issue 4, Pages 58–66 (Mi ppi201)

This article is cited 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.

UDC: 621.394/395.74:519.2

Received: 17.02.1993


 English version:
Problems of Information Transmission, 1993, 29:4, 350–357

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024