Analysis of matroids reveals the threshold for minors in binary structures, suggesting new insights into combinatorial theory.
Consider a random n × m n× m matrix A A over the finite field of order q q where every column has precisely k k nonzero elements, and let M [ A ] M[A] be the matroid represented by A A . In the case that q=2, Cooper, Frieze and Pegden [Random Structures Algorithms 55 (2109), pp. 865–880] proved that given a fixed binary matroid N N , if k ≥ k N k≥ k_N and m / n ≥ d N m/n≥ d_N where k N k_N and d N d_N are sufficiently large constants depending on N, then a.a.s. M [ A ] M[A] contains N N as a minor. We improve their result by determining the sharp threshold (of m / n m/n ) for the appearance of a fixed matroid N N as a minor of M [ A ] M[A] , for every k ≥ 3 k≥ 3 , and every finite field.
No takes yet. Share an insight, caveat, or question.
Gao et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: