Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Random Sampling of Labeled Tournaments. | Random Sampling of Labeled Tournaments Lisa McShine School of Mathematics Georgia Institute of Technology Atlanta GA 30332-1060 USA mcshine@ Submitted January 5 2000 Accepted February 23 2000 Abstract This note extends a recent result of Kannan Tetali and Vempala to completely solve via a simple proof the problem of random generation of a labeled tournament with a given score vector. The proof uses the method of path coupling applied to an appropriate Markov chain on the set of labeled tournaments with the same score vector. MRS 65C05 05C20. 1 Introduction A tournament is an oriented complete graph which models a real-life round robin tournament with no ties. The score vector of a tournament is the sequence of out-degrees of the vertices of the tournament. In general given a score vector with n scores there can be an exponential in n number of labeled and unlabeled tournaments which have the given score vector see . 7 6 and references therein . Although the problem of counting the number of labeled or unlabeled tournaments with the same score vector exactly seems very difficult no P-hardness result is known to that effect. In this work we show that a simple algorithm based on the Markov chain Monte Carlo method is actually a very efficient algorithm for generating a labeled tournament uniformly at random from among the set of all tournaments with a given score vector. The problem we consider is one of two problems studied in a recent paper of Kan-nan Tetali and Vempala 6 namely randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score vector. For each of the two problems they designed an appropriate Markov This research is in part supported by P. Tetali s NSF Grant DMS-9800351. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R8 2 chain whose stationary distribution is uniform on the state space of the desired structures namely bipartite graphs and tournaments and .
