Exact Expectation and Variance of Minimal Basis of Random Matroids

• Autorzy: Wojciech Kordecki , Anna Lyczkowska-Hanćkowiak
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

minimal basis; q-analog; finite projective geometry; Tutte polynomial

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 2
• Strony: 277-288

Daty

wydano

2013-05-01

online

2013-04-13

Twórcy

autor

Wojciech Kordecki

• University of Business in Wroclaw Department of Management ul. Ostrowskiego 22, 53-238 Wroclaw, Poland

autor

Anna Lyczkowska-Hanćkowiak

• Poznán University of Economics Faculty of Informatics and Electronic Economy Department of Operations Research al. Niepodleg lo´sci 10, 61-875 Poznán, Poland

Bibliografia

• [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]
• [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[Crossref]
• [5] A. Frieze and C.J.H. McDiarmid, On random minimum length spanning trees, Combinatorica 9 (1989) 363-374. doi:10.1007/BF02125348[Crossref]
• [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[Crossref]
• [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[Crossref]
• [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[Crossref]
• [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).

Identyfikatory

DOI

10.7151/dmgt.1662