Inclusion of forbidden minors in random representable matroids

DOI10.1016/J.DISC.2017.02.017zbMATH Open1361.05119OpenAlexW2962945180MaRDI QIDQ526240FDOQ526240

Authors: Elizabeth Yang, Jason M. Altschuler 

Publication date: 10 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: In 1984, Kelly and Oxley introduced the model of a random representable matroid $M[A_n]$ corresponding to a random matrix $A_{n}inmathbb{F}_q^{m(n)imesn}$, whose entries are drawn independently and uniformly from $mathbb{F}_q$. Whereas properties such as rank, connectivity, and circuit size have been well-studied, forbidden minors have not yet been analyzed. Here, we investigate the asymptotic probability as $noinfty$ that a fixed $mathbb{F}_q$-representable matroid $M$ is a minor of $M[A_n]$. (We always assume $m(n)geqextrank(M)$ for all sufficiently large $n$, otherwise $M$ can never be a minor of the corresponding $M[A_n]$.) When $M$ is free, we show that $M$ is asymptotically almost surely (a.a.s.) a minor of $M[A_n]$. When $M$ is not free, we show a phase transition: $M$ is a.a.s. a minor if $n-m(n)oinfty$, but is a.a.s. not if $m(n)-noinfty$. In the more general settings of $mleqn$ and $m>n$, we give lower and upper bounds, respectively, on both the asymptotic and non-asymptotic probability that $M$ is a minor of $M[A_n]$. The tools we develop to analyze matroid operations and minors of random matroids may be of independent interest. Our results directly imply that $M[A_n]$ is a.a.s. not contained in any proper, minor-closed class $mathcalM$ of $mathbb{F}_q$-representable matroids, provided: (i) $n-m(n)oinfty$, and (ii) $m(n)$ is at least the minimum rank of any $mathbb{F}_q$-representable forbidden minor of $mathcalM$, for all sufficiently large $n$. As an application, this shows that graphic matroids are a vanishing subset of linear matroids, in a sense made precise in the paper. Our results provide an approach for applying the rich theory around matroid minors to the less-studied field of random matroids.

Full work available at URL: https://arxiv.org/abs/1507.05332

Recommendations

• On Random Representable Matroids
• Minors of a random binary matroid
• Threshold distribution functions for some random representable matroids
• scientific article; zbMATH DE number 1070707
• Representability of matroids with a large projective geometry minor

zbMATH Keywords

random matrix theorymatroid theoryforbidden matroid minorsminor-closed matroid classesrandom representable matroids

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Random walks on graphs (05C81)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic properties of random subsets of projective spaces
• Lectures on matroids
• Matroids and Graphs
• On Random Representable Matroids
• On properties of almost all matroids
• On random subsets of projective spaces
• On the asymptotic proportion of connected matroids
• On the connectivity of random subsets of projective spaces
• Random Matrix Theory and Wireless Communications
• Random matrices and codes for the erasure channel
• Random matroids
• Small Submatroids in Random Matroids
• Strictly balanced submatroids in random subsets of projective geometries
• THRESHOLD FUNCTIONS FOR SOME PROPERTIES OF RANDOM SUBSETS OF PROJECTIVE SPACES
• Threshold distribution functions for some random representable matroids

Cited In (3)

• On the rank of a random binary matrix
• Minors of a random binary matroid
• On Random Representable Matroids

This page was built for publication: Inclusion of forbidden minors in random representable matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526240)