Discussiones Mathematicae Graph Theory 33(2) (2013)
277-288
DOI: https://doi.org/10.7151/dmgt.1662
Exact expectation and variance of minimal basis of random matroids
Wojciech Kordecki
University of Business in Wrocław | Anna Łyczkowska-Hanćkowiak
Poznań University of Economics |
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
Close