Exact Expectation and Variance of Minimal Basis of Random Matroids

Discussiones Mathematicae Graph Theory

Lyczkowska-Hanćkowiak Anna¹  Kordecki Wojciech² 

[1] 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;University of Business in Wroclaw Department of Management ul. Ostrowskiego 22, 53-238 Wroclaw, Poland;

关键词: minimal basis;    q-analog;    finite projective geometry;    tutte polynomial;   

DOI  :  10.7151/dmgt.1662

来源: DOAJ

【 摘 要 】

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

【 授权许可】

Unknown