Minors of a random binary matroid. Issue 4 (29th July 2019)

• Record Type: Journal Article
• Authors: Cooper, Colin; Frieze, Alan; Pegden, Wesley
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 865
• Page End: 880
• Publication Date: 2019-07-29
• Subjects: binary -- matroids -- minors -- random; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20881
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : LetA be an n × m matrix overGF 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 byA contains M as a minor. We prove that if the columns ofA = 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 thatA contains M as a minor with high probability .