Back to Search Start Over

Minors of matroids represented by sparse random matrices over finite fields

Authors :
Gao, Pu
Nelson, Peter
Publication Year :
2023

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\ge k_N$ and $m/n\ge 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\ge 3$, and every finite field.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2307.15685
Document Type :
Working Paper