Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T03:16:54.315Z Has data issue: false hasContentIssue false

Threshold distribution functions for some random representable matroids

Published online by Cambridge University Press:  24 October 2008

James G. Oxley
Affiliation:
Department of Mathematics, IAS, Australian National University, PO Box 4, Canberra, 2600, Australia

Extract

A random submatroid ωr of the projective geometry PG(r − 1, q) is obtained from PG(r − 1, q) by deleting elements so that each element has, independently of all other elements, probability 1 − p of being deleted and probability p of being retained. The properties of such random structures were studied in [5] and [6]. In the first of these papers, p was kept fixed, while in the second, motivated by Erdös and Rényi's work ([3), [4]) on random graphs, p was taken to be a function of r. A recent paper of Bollobás[2] strengthens and extends a number of the results of Erdös and Rényi. In this paper we prove matroid analogues of several of Bollobàs's results thereby extending some of the results of [6].

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1984

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]Billingsley, P.. Probability and Measure (Wiley, 1979).Google Scholar
[2]Bollobás, B.. Threshold functions for small subgraphs. Math. Proc. Cambridge Philos. Soc. 90 (1981), 197206.CrossRefGoogle Scholar
[3]Erdös, P. and Rényi, A.. On random graphs: I. Publ. Math. Debrecen 6 (1959), 290297.CrossRefGoogle Scholar
[4]Erdös, P. and Rényi, A.. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 1761.Google Scholar
[5]Kelly, D. G. and Oxley, J. G.. Asymptotic properties of random subsets of projective spaces. Math. Proc. Cambridge Philos. Soc. 91 (1982), 119130.CrossRefGoogle Scholar
[6]Kelly, D. G. and Oxley, J. G.. Threshold functions for some properties of random subsets of projective spaces. Quart. J. Math. Oxford Ser. (2) 33 (1982), 463469.CrossRefGoogle Scholar
[7]Naranyan, H. and Vartak, M. N.. On molecular and atomic matroids. Combinatorics and Graph Theory (ed. Rao, S. B.). Lecture Notes in Math. vol. 885 (Springer-Verlag, 1981), 358364.CrossRefGoogle Scholar
[8]Welsh, D. J. A.. Matroid Theory. London Math. Soc. Monographs no. 8 (Academic Press, 1976).Google Scholar