Discussiones Mathematicae Graph Theory 33(2) (2013) 277-288
doi: 10.7151/dmgt.1662

[BIBTex] [PDF] [PS]

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

Received 2 March 2011
Revised 3 October 2011
Accepted 5 March 2012