We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Minors of a random binary matroid.
- Authors
Cooper, Colin; Frieze, Alan; Pegden, Wesley
- Abstract
Let A be an n × m matrix over GF2 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 CM such that m ≥ CMn2 implies that the binary matroid induced by A contains M as a minor. We prove that if the columns of A = An,m,k are chosen randomly, then there are constants kM,LM such that k ≥ kM and m ≥ LMn implies that A contains M as a minor with high probability.
- Subjects
MATROIDS; MINORS
- Publication
Random Structures & Algorithms, 2019, Vol 55, Issue 4, p865
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20881