Random Matroids.
Abstract
A simple combinatorial construction capable of producing an arbitrary matroid is introduced, and some of its properties are investigated. The structure of a matroid is defined one rank at a time, and when random choices are made the result might be called a random matroid. Some experimental statistics about such matroids are tabulated. If the subsets of rank = or < k are specified, the construction defines a rank function having the richest possible matroid structure on the remaining subsets, in the sense that no new relationships are introduced except those implied by the given subsets of rank = or < k. An appendix to this paper presents several computer programs for dealing with matroids over small sets. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1974
- Accession Number
- ADA000084
Entities
People
- Donald Knuth
Organizations
- Stanford University