Minors of a random binary matroid. Issue 4 (29th July 2019) - Cooper, Colin; Frieze, Alan; Pegden, Wesley
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 .