DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(2) (2000) 209-217
DOI: 10.7151/dmgt.1120

ON THE RANK OF RANDOM SUBSETS OF FINITE AFFINE GEOMETRY


Wojciech Kordecki

Institute of Mathematics
Wrocław University of Technology
Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

e-mail: kordecki@im.pwr.wroc.pl

Abstract

The aim of the paper is to give an effective formula for the calculation of the probability that a random subset of an affine geometry AG(r −1,q) has rank r. Tables for the probabilities are given for small ranks. The expected time to the first moment at which a random subset of an affine geometry achieves the rank r is derived.

Keywords: finite affine geometry, random matroids, hitting time.

2000 Mathematics Subject Classification: Primary: 05B25; Secondary: 51E20.

References

[1] C.J. Colbourn and J.H. Dinitz, The CRC Handbook of Combinatorial Designs (CRC Press, Boca Raton, 1996).
[2] W. Kordecki, On the rank of a random submatroid of projective geometry, in: Random Graphs, Proc. of Random Graphs 2 (Poznań 1989, Wiley, 1992) 151-163.
[3] W. Kordecki, Random matroids, Dissert. Math. CCCLXVII (PWN, Warszawa, 1997).
[4] W. Kordecki, Reliability bounds for multistage structures with independent components, Statist. Probab. Lett. 34 (1997) 43-51, doi: 10.1016/S0167-7152(96)00164-2.
[5] M.V. Lomonosov, Bernoulli scheme with closure, Probl. Inf. Transmission 10 (1974) 73-81.
[6] J.G. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992).
[7] B. Voigt, On the evolution of finite affine and projective spaces, Math. Oper. Res. 49 (1986) 313-327.
[8] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).

Received 15 November 1999
Revised 24 November 2000