Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T13:55:19.813Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic properties of random subsets of projective spaces

Published online by Cambridge University Press:  24 October 2008

Douglas G. Kelly  and
James G. Oxley
Douglas G. Kelly
Affiliation:
Departments of Statistics and Mathematics, University of North Carolina
James G. Oxley
Affiliation:
Departments of Statistics and Mathematics, University of North Carolina
Get access Rights & Permissions [Opens in a new window]

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Andrews, G. E.The theory of partitions, Encyclopedia of Mathematics and its Applications, vol. 2 (Addison-Wesley, Reading, Massachusetts, 1976).Google Scholar
(2)Bollobás, B.Graph Theory: an Introductory Course, Graduate Texts in Mathematics, no. 63 (Springer-Verlag, New York, Heidelberg, Berlin, 1979).CrossRefGoogle Scholar
(3)Bollobás, B. and Erdös, P.Cliques in random graphs. Math. Proc. Cambridge Phil. Soc. 80 (1976), 419–427.CrossRefGoogle Scholar
(4)Cravetz, A. E. Essentials for matroid erection (M.S. Thesis, Department of Mathematics, University of North Carolina, Chapel Hill, 1978).Google Scholar
(5)Goldman, J. and Rota, G.-C. The number of subspaces of a vector space, Recent Progress in Combinatorics, ed. Tutte, W. T. (Academic Press, New York, London, 1969), pp. 75–83.Google Scholar
(6)Grimmett, G. R. and Mcdiarmid, C. J. H.On colouring random graphs. Math. Proc. Cambridge Phil. Soc. 77 (1975), 313–324.CrossRefGoogle Scholar
(7)Knuth, D. E.Random matroids. Discrete Math. 12 (1975), 341–358.CrossRefGoogle Scholar
(8)Loève, M.Probability Theory, 2nd ed. (D. Van Nostrand, Princeton, New Jersey, 1960).Google Scholar
(9)Matula, D. W. On the complete subgraphs of a random graph. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (U.N.C. Press, Chapel Hill, 1970), pp. 356–369.Google Scholar
(10)Matula, D. W. Graph-theoretic cluster analysis. Classification and Clustering, ed. Van Ryzin, J. (Academic Press, New York, San Francisco, London, 1977), pp. 95–129.CrossRefGoogle Scholar
(11)Oxley, J. G. and Welsh, D. J. A. The Tutte polynomial and percolation. Graph Theory and Belated Topics, ed. Bondy, J. A. and Murty, U. S. R. (Academic Press, New York, San Francisco, London, 1979), pp. 329–339.Google Scholar
(12)Welsh, D. J. A.Matroid Theory. London Math. Soc. Monographs no. 8 (Academic Press, London, New York, San Francisco, 1976).Google Scholar