Exact Expectation and Variance of Minimal Basis of Random Matroids

Wojciech Kordecki; Anna Lyczkowska-Hanćkowiak

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 277-288
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Wojciech Kordecki, and Anna Lyczkowska-Hanćkowiak. "Exact Expectation and Variance of Minimal Basis of Random Matroids." Discussiones Mathematicae Graph Theory 33.2 (2013): 277-288. <http://eudml.org/doc/267680>.

@article{WojciechKordecki2013,
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).},
author = {Wojciech Kordecki, Anna Lyczkowska-Hanćkowiak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {minimal basis; q-analog; finite projective geometry; Tutte polynomial; -analog},
language = {eng},
number = {2},
pages = {277-288},
title = {Exact Expectation and Variance of Minimal Basis of Random Matroids},
url = {http://eudml.org/doc/267680},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Wojciech Kordecki
AU - Anna Lyczkowska-Hanćkowiak
TI - Exact Expectation and Variance of Minimal Basis of Random Matroids
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 277
EP - 288
AB - 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).
LA - eng
KW - minimal basis; q-analog; finite projective geometry; Tutte polynomial; -analog
UR - http://eudml.org/doc/267680
ER -

References

top
  1. [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] Zbl0913.05085
  2. [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. Zbl0769.05026
  3. [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. [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. [5] A. Frieze and C.J.H. McDiarmid, On random minimum length spanning trees, Combinatorica 9 (1989) 363-374. doi:10.1007/BF02125348[Crossref] Zbl0712.05050
  6. [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. [7] J.W.P. Hirschfeld, Projective Geometries over Finite Fields (Clarendom Press, Oxford, 1979). Zbl0418.51002
  8. [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. [9] W. Kordecki, Random matroids, Dissertationes Math. CCCLXVII (1997). Zbl0934.05034
  10. [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] Zbl1202.05019
  11. [11] W. Kordecki and A. Lyczkowska-Han´ckowiak, q-analogs of order statistics, Probab. Math. Statist. 30 (2010) 207-214. 
  12. [12] E.G. Mphako, Tutte polynomials of perfect matroid designs, Combin. Probab. Comput. 9 (2000) 363-367. doi:10.1017/S0963548300004338[Crossref] Zbl0964.05017
  13. [13] J.G. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992). 
  14. [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. Zbl0979.05030
  15. [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. Zbl1032.60007
  16. [16] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.