Geodesic
Exact Expectation and Variance of Minimal Basis of Random Matroids
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 2, pp. 277-288.

Voir la notice de l'article provenant de la source Library of Science

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).
Keywords: minimal basis, q-analog, finite projective geometry, Tutte polynomial 
@article{DMGT_2013_33_2_a2,
     author = {Kordecki, Wojciech and {\L}yczkowska-Han\'ckowiak, Anna},
     title = {Exact {Expectation} and {Variance} of {Minimal} {Basis} of {Random} {Matroids}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {277--288},
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a2/}
}
TY  - JOUR
AU  - Kordecki, Wojciech
AU  - Łyczkowska-Hanćkowiak, Anna
TI  - Exact Expectation and Variance of Minimal Basis of Random Matroids
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 277
EP  - 288
VL  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a2/
LA  - en
ID  - DMGT_2013_33_2_a2
ER  - 
%0 Journal Article
%A Kordecki, Wojciech
%A Łyczkowska-Hanćkowiak, Anna
%T Exact Expectation and Variance of Minimal Basis of Random Matroids
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 277-288
%V 33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a2/
%G en
%F DMGT_2013_33_2_a2
Kordecki, Wojciech; Łyczkowska-Hanćkowiak, Anna. Exact Expectation and Variance of Minimal Basis of Random Matroids. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 2, pp. 277-288. http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a2/

[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

[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.

[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

[5] A. Frieze and C.J.H. McDiarmid, On random minimum length spanning trees, Combinatorica 9 (1989) 363-374. doi:10.1007/BF02125348

[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).

[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

[9] W. Kordecki, Random matroids, Dissertationes Math. CCCLXVII (1997).

[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

[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

[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.

[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.

[16] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).