Minors of matroids represented by sparse random matrices over finite fields

Pu Gao; Peter Nelson

paper

Minors of matroids represented by sparse random matrices over finite fields

arXiv:2307.15685

Abstract

Consider a random $n \times m$ matrix $A$ over the finite field of order $q$ where every column has precisely $k$ nonzero elements, and let $M [A]$ be the matroid represented by $A$ . In the case that q=2, Cooper, Frieze and Pegden (RS\&A 2019) proved that given a fixed binary matroid $N$ , if $k \geq k_{N}$ and $m / n \geq d_{N}$ where $k_{N}$ and $d_{N}$ are sufficiently large constants depending on N, then a.a.s. $M [A]$ contains $N$ as a minor. We improve their result by determining the sharp threshold (of $m / n$ ) for the appearance of a fixed matroid $N$ as a minor of $M [A]$ , for every $k \geq 3$ , and every finite field.