Asymptotic Properties of Random Subsets of Projective Spaces.
Abstract
A random graph on n vertices is a random subgraph of the complete graph on n vertices. By analogy with this, the present paper studies the asymptotic properties of a random submatroid omega(r) of the projective geometry PG(r-1,q). The main result concerns Kr, the rank of the largest projective geometry occurring as a submatroid of omega(r). We show that with probability one, for sufficiently large r, Kr takes one of at most two values depending on r. This theorem is analogous to a result of Bollobas and Erdos on the clique number of a random graph. However, whereas from the matroid theorem one can essentially determine the critical exponent of omega(r), the graph theorem gives only a lower bound on the chromatic number of a random graph. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1980
- Accession Number
- ADA094980
Entities
People
- Douglas G. Kelly
- James G. Oxley
Organizations
- University of North Carolina at Chapel Hill