tailieunhanh - Báo cáo toán học: "Equitable matroids"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Equitable matroids. | Equitable matroids Dillon Mayhew Mathematical Institute University of Oxford 24-29 St Giles Oxford OX1 3LB United Kingdom Submitted Apr 3 2006 Accepted Apr 19 2006 Published Apr 24 2006 Mathematics Subject Classification 05B35 05A05 Abstract One way to choose a basis of a matroid at random is to choose an ordering of the ground set uniformly at random and then use the greedy algorithm to find a basis. We investigate the class of matroids having the property that this procedure yields a basis uniformly at random. We show how this class is related to some other naturally-defined families of matroids and consider how it behaves under well-known matroid operations. 1 Introduction Counting the bases of a matroid is a well-studied problem with many applications. In some cases counting the bases exactly is known to be a computationally intractable problem 3 7 . Therefore a considerable amount of attention has been paid to producing approximations to the number of bases 1 2 . Work by Jerrum Valiant and Vazirani 8 shows that this task is intimately connected to the problem of choosing a basis uniformly at random. Because of this connection between counting bases and choosing them uniformly at random a great deal of effort has been spent in the search for efficient ways to randomly select a basis of a matroid 6 11 . Perhaps the most obvious way to choose a basis of a matroid at random is to use an implementation of the greedy algorithm. Let M be a matroid on the ground set E and let p be a linear order on E. Then p induces a natural lexicographical order on the subsets of E. The greedy algorithm finds the basis that is minimum in this lexicographical order. Current address School of Mathematics Statistics and Computer Science Victoria University of Wellington PO BOX 600 Wellington New Zealand. Email THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R41 1 In general though if p is chosen uniformly at random from all linear orderings of E some bases .