Exact Expectation and Variance of Minimal Basis of Random Matroids
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....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1662 |
| _version_ | 1827844603954331648 |
|---|---|
| author | Kordecki Wojciech Lyczkowska-Hanćkowiak Anna |
| author_facet | Kordecki Wojciech Lyczkowska-Hanćkowiak Anna |
| author_sort | Kordecki Wojciech |
| collection | DOAJ |
| description | 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). |
| first_indexed | 2024-03-12T08:45:14Z |
| format | Article |
| id | doaj.art-d04e07e5b4b740739323cc4fc0b84013 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:45:14Z |
| publishDate | 2013-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-d04e07e5b4b740739323cc4fc0b840132023-09-02T16:30:01ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-05-0133227728810.7151/dmgt.1662Exact Expectation and Variance of Minimal Basis of Random MatroidsKordecki Wojciech0Lyczkowska-Hanćkowiak Anna1University of Business in Wroclaw Department of Management ul. Ostrowskiego 22, 53-238 Wroclaw, PolandPoznán University of Economics Faculty of Informatics and Electronic Economy Department of Operations Research al. Niepodleg lo´sci 10, 61-875 Poznán, PolandWe 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).https://doi.org/10.7151/dmgt.1662minimal basisq-analogfinite projective geometrytutte polynomial |
| spellingShingle | Kordecki Wojciech Lyczkowska-Hanćkowiak Anna Exact Expectation and Variance of Minimal Basis of Random Matroids Discussiones Mathematicae Graph Theory minimal basis q-analog finite projective geometry tutte polynomial |
| title | Exact Expectation and Variance of Minimal Basis of Random Matroids |
| title_full | Exact Expectation and Variance of Minimal Basis of Random Matroids |
| title_fullStr | Exact Expectation and Variance of Minimal Basis of Random Matroids |
| title_full_unstemmed | Exact Expectation and Variance of Minimal Basis of Random Matroids |
| title_short | Exact Expectation and Variance of Minimal Basis of Random Matroids |
| title_sort | exact expectation and variance of minimal basis of random matroids |
| topic | minimal basis q-analog finite projective geometry tutte polynomial |
| url | https://doi.org/10.7151/dmgt.1662 |
| work_keys_str_mv | AT kordeckiwojciech exactexpectationandvarianceofminimalbasisofrandommatroids AT lyczkowskahanckowiakanna exactexpectationandvarianceofminimalbasisofrandommatroids |