Inclusion of forbidden minors in random representable matroids

DOI10.1016/J.DISC.2017.02.017zbMATH Open1361.05119arXiv1507.05332OpenAlexW2962945180MaRDI 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?)
• Matroids and Graphs
• Title not available (Why is that?)
• Lectures on matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the asymptotic proportion of connected matroids
• Random Matrix Theory and Wireless Communications
• On properties of almost all matroids
• Random matroids
• On the connectivity of random subsets of projective spaces
• Strictly balanced submatroids in random subsets of projective geometries
• Threshold distribution functions for some random representable matroids
• On Random Representable Matroids
• Asymptotic properties of random subsets of projective spaces
• On random subsets of projective spaces
• Small Submatroids in Random Matroids
• THRESHOLD FUNCTIONS FOR SOME PROPERTIES OF RANDOM SUBSETS OF PROJECTIVE SPACES
• Random matrices and codes for the erasure channel

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)