PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 2 | 277-288
Tytuł artykułu

Exact Expectation and Variance of Minimal Basis of Random Matroids

Treść / Zawartość
Warianty tytułu
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).
Wydawca
Rocznik
Tom
33
Numer
2
Strony
277-288
Opis fizyczny
Daty
wydano
2013-05-01
online
2013-04-13
Twórcy
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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1662
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.