We formulate and prove a formula to compute the expected value of the minimal random basis of an arbitrary finite matroid whose elements are assigned weights which are independent and uniformly distributed on the interval [0, 1]. This method yields an exact formula in terms of the Tutte polynomial. We give a simple formula to find the minimal random basis of the projective geometry PG(r − 1, q).
@article{bwmeta1.element.doi-10_7151_dmgt_1662,
author = {Wojciech Kordecki and Anna Lyczkowska-Han\'ckowiak},
title = {Exact Expectation and Variance of Minimal Basis of Random Matroids},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {277-288},
zbl = {1294.05048},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1662}
}
Wojciech Kordecki; Anna Lyczkowska-Hanćkowiak. Exact Expectation and Variance of Minimal Basis of Random Matroids. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 277-288. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1662/
[1] A. Beveridge, A. Frieze and C.J.H. McDiarmid, Random minimum length spanning trees in regular graphs, Combinatorica 18 (1998) 311-333. doi:10.1007/PL00009825[Crossref] | Zbl 0913.05085
[2] T. Brylawski and J. Oxley, The Tutte polynomials and its applications, in: Encyclopedia of Mathematics and Its Applications, vol. 40, Matroid Applications, N. White (Ed(s)), (Cambridge University Press, 1992) 121-225. | Zbl 0769.05026
[3] J.A. Fill and J.M. Steele, Exact expectation of minimal spanning trees for graphs with random edge weights, in: Stein’s Method and Applications, A. Barbour and L. Chen (Ed(s)), (World Publications, Singapore, 2005) 169-180.
[4] A. Frieze, On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10 (1985) 47-56. doi:10.1016/0166-218X(85)90058-7[Crossref]
[5] A. Frieze and C.J.H. McDiarmid, On random minimum length spanning trees, Combinatorica 9 (1989) 363-374. doi:10.1007/BF02125348[Crossref] | Zbl 0712.05050
[6] A. Frieze, M. Ruszink´o, and L. Thoma, A note on random minimum length spanning trees, Electron. J. Combin. 7 (2000) 1-5.
[7] J.W.P. Hirschfeld, Projective Geometries over Finite Fields (Clarendom Press, Oxford, 1979). | Zbl 0418.51002
[8] D.G. Kelly and J.G. Oxley, Asymptotic properties of random subsets of projective spaces, Math. Proc. Cambridge Philos. Soc. 91 (1982) 119-130. doi:10.1017/S0305004100059181[Crossref]
[9] W. Kordecki, Random matroids, Dissertationes Math. CCCLXVII (1997). | Zbl 0934.05034
[10] W. Kordecki and A. Lyczkowska-Han´ckowiak, Expected value of the minimal basis of random matroid and distributions of q-analogs of order statistics, Electron. Notes Discrete Math. 24 (2006) 117-123. doi:10.1016/j.endm.2006.06.020[Crossref] | Zbl 1202.05019
[11] W. Kordecki and A. Lyczkowska-Han´ckowiak, q-analogs of order statistics, Probab. Math. Statist. 30 (2010) 207-214.
[12] E.G. Mphako, Tutte polynomials of perfect matroid designs, Combin. Probab. Comput. 9 (2000) 363-367. doi:10.1017/S0963548300004338[Crossref] | Zbl 0964.05017
[13] J.G. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992).
[14] J.G. Oxley. On the interplay between graphs and matroids, in: vol. 288 of London Math. Soc. Lecture Note Ser. (Cambridge University Press, 2001) 199-239. | Zbl 0979.05030
[15] J.M. Steele, Minimal spanning trees for graphs with random edge lengths, in: Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, B. Chauvin, P. Flajolet, D. Gardy, and A. Mokkadem (Ed(s)), (Birkh¨auser, Boston, 2002) 223-245. | Zbl 1032.60007
[16] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).