## Exact expectation and variance of minimal basis of random matroids

 Wojciech Kordecki University of Business in Wrocław Department of Management ul. Ostrowskiego 22, 53-238 Wrocław, Poland Anna Łyczkowska-Hanćkowiak Poznań University of Economics Faculty of Informatics and Electronic Economy Department of Operations Research al. Niepodległości 10, 61-875 Poznań, Poland

## Abstract

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

2010 Mathematics Subject Classification: 05B35, 05C80.

## References

 [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, ed(s), N. White 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, ed(s), A. Barbour and L. Chen 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ó, 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. Łyczkowska-Hanćkowiak, 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. Łyczkowska-Hanćkowiak, 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)), (Birkhauser, Boston, 2002) 223?245. [16] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).