Minors of a random binary matroid

DOI10.1002/RSA.20881MaRDI QIDQ5216181zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Wesley Pegden, Alan Frieze

Publication date 14 February 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

binarymatroidsminorsrandom

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: Let $$ be a random $nimesm$ matrix over $mathbf{GF}_2$ wher each column consists of $k$ randomly chosen ones. Let $M$ be an arbirary fixed binary matroid. We show that if $m/n$ and $k$ are sufficiently large then as $noinfty$ the binary matroid induced by {�f A} contains $M$ as a minor.

Recommendations

• Inclusion of forbidden minors in random representable matroids
• On Random Representable Matroids
• A bound for the growth rate of binary matroids having no \(\mathrm{PG}(k-1,2)\)-minor
• scientific article; zbMATH DE number 1070707
• Small Submatroids in Random Matroids

Cites work

• Almost all matroids are nonrepresentable
• Cores in random hypergraphs and Boolean formulas
• Growth rates of minor-closed classes of matroids
• Homological connectivity of random 2-complexes
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1436005 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Inclusion of forbidden minors in random representable matroids
• On properties of almost all matroids
• On Random Representable Matroids
• On the number of matroids
• The 3-XORSAT threshold.
• The long-line graph of a combinatorial geometry. II: Geometries representable over two fields of different characteristics
• Topology of random simplicial complexes: a survey

Cited in

(4)

• A bound for the growth rate of binary matroids having no \(\mathrm{PG}(k-1,2)\)-minor
• Expected value of the minimal basis of random matroid and distributions of q-analogs of order statistics
• Inclusion of forbidden minors in random representable matroids
• Minors of matroids represented by sparse random matrices over finite fields

This page was built for publication: Minors of a random binary matroid

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