On Random Representable Matroids
Results are obtained on the likely connectivity properties and sizes of circuits in the column dependence matroid of a random r × n matrix over a finite field, for large r and n. In a sense made precise in the paper, it is shown to be highly probable that when n is less than r such a matroid is the free matroid on n points, while if n exceeds r it is a connected matroid of rank r. Moreover, the connectivity can be strengthened under additional hypotheses on the growth of n and r, using the notion of vertical connectivity; and the values of k for which circuits of size k exist can be determined in terms of n and r.
No Supplementary Data
No Article Media
Document Type: Research Article
Affiliations: 1: University of North Carolina 2: Louisiana State University
Publication date: December 1, 1984