RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb. (N.S.), 1975 Volume 97(139), Number 3(7), Pages 395–402 (Mi sm3658)

This article is cited in 1 paper

Systems of distinct representatives for random sets

V. N. Sachkov


Abstract: In this work estimates from below are obtained for the probability that the permanent of a random $n\times m$ $(0,1)$-matrix is positive. Using this estimate, it is shown that a random collection of subsets $X_1,\dots,X_n$ of the set $X$ of $m$ elements as $m\to\infty$ has a system of distinct representatives with probability close to one.
Bibliography: 3 titles.

UDC: 519.2

MSC: 05A05, 60C05, 60F05

Received: 24.01.1975


 English version:
Mathematics of the USSR-Sbornik, 1975, 26:3, 365–371

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025