Inclusion of forbidden minors in random representable matroids

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

Abstract: In 1984, Kelly and Oxley introduced the model of a random representable matroid

M [A_{n}]

corresponding to a random matrix

A_{n} i n m a t h b b F_{q}^{m (n) i m e s n}

, whose entries are drawn independently and uniformly from

m a t h b b 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

n o i n f t y

that a fixed

m a t h b b F_{q}

-representable matroid

M

is a minor of

M [A_{n}]

. (We always assume

m (n) g e q e x t r a n k (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) o i n f t y

, but is a.a.s. not if

m (n) - n o i n f t y

. In the more general settings of

m l e q n

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

m a t h c a l M

of

m a t h b b F_{q}

-representable matroids, provided: (i)

n - m (n) o i n f t y

, and (ii)

m (n)

is at least the minimum rank of any

m a t h b b F_{q}

-representable forbidden minor of

m a t h c a l M

, 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.

Recommendations

Cites work

Cited in

(5)

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)