Asymptotic properties of random subsets of projective spaces
Published online by Cambridge University Press: 24 October 2008
Extract
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 ωr of the projective geometry PG(r−l, q). The main result concerns Kr, the rank of the largest projective geometry occurring as a submatroid of ω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 Bollobás and Erdös on the clique number of a random graph. However, whereas from the matroid theorem one can essentially determine the critical exponent of ωr, the graph theorem gives only a lower bound on the chromatic number of a random graph.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 91 , Issue 1 , January 1982 , pp. 119 - 130
- Copyright
- Copyright © Cambridge Philosophical Society 1982
References
REFERENCES
- 9
- Cited by