Name
Abstract | ||
|---|---|---|
Let A be an n x m matrix over GF(2) where each column consists of k ones, and let M be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant C-M such that m >= C(M)n(2) implies that the binary matroid induced by A contains M as a minor. We prove that if the columns of A = A(n,m,k) are chosen randomly, then there are constants k(M),L-M such that k >= k(M) and m >= L(M)n implies that A contains M as a minor with high probability . |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1002/rsa.20881 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
Binary,Matroids,Minors,Random | Discrete mathematics,Combinatorics,Matrix (mathematics),Binary matroid,Mathematics | Journal |
Volume | Issue | ISSN |
55.0 | 4.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 287 | 30.73 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| wesley pegden | 3 | 30 | 11.07 |