Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Mixing time for a random walk on rooted trees. | Mixing time for a random walk on rooted trees Jason Fulman Department of Mathematics University of Southern California Los Angeles CA USA fulman@usc.edu Submitted Aug 8 2009 Accepted Nov 3 2009 Published Nov 13 2009 Mathematics Subject Classification 60J10 05E99 Abstract We define an analog of Plancherel measure for the set of rooted unlabeled trees on n vertices and a Markov chain which has this measure as its stationary distribution. Using the combinatorics of commutation relations we show that order n2 steps are necessary and suffice for convergence to the stationary distribution. 1 Introduction The Plancherel measure of the symmetric group is a probability measure on the irreducible representations of the symmetric group which chooses a representation with probability proportional to the square of its dimension. Equivalently the irreducible representations of the symmetric group are parameterized by partitions A of n and the Plancherel measure chooses a partition A with probability n 1 II h x 2 where the product is over boxes in the partition and h x is the hooklength of a box. The hooklength of a box x is defined as 1 number of boxes in same row as x and to right of x number of boxes in same column of x and below x. For example we have filled in each box in the partition of 7 below with its hooklength 3 0 0 0 3 h 1 and the Plancherel measure would choose this partition with probability 6x4J3x2 2 . There has been significant interest in statistical properties of partitions chosen from Plancherel THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R139 1 measure of the symmetric group for this the reader can consult 4 5 11 and the many references therein. In this paper we define a similar measure on the set of rooted unlabeled trees on n vertices. We place the root vertex on top and the four rooted trees on 4 vertices are depicted below This measure chooses a rooted tree with probability n 2n-1 isG t in. h v 2 2 where h v is the size of the subtree with root v and .