Permanent URL to this publication: http://dx.doi.org/10.5167/uzh22226
Barbour, A D; Godbole, A; Qian, J (1997). Imperfections in random tournaments. Combinatorics, Probability & Computing, 6(1):115.

PDF (Preprint)
1MB View at publisher 
Abstract
A tournament T on a set V of n players is an orientation of the edges of the complete graph Kn on V; T will be called a random tournament if the directions of these edges are determined by a sequence of independent coin flips. If (y, x) is an edge in a (random) tournament, we say that y beats x. A set A [subset or is implied by] V, A = k, is said to be beaten if there exists a player y [notin N: negated set membership] A such that y beats x for each x [set membership] A. If such a y does not exist, we say that A is unbeaten. A (random) tournament on V is said to have property Sk if each kelement subset of V is beaten. In this paper, we use the Stein–Chen method to show that the probability distribution of the number W0 of unbeaten ksubsets of V can be wellapproximated by that of a Poisson random variable with the same mean; an improved condition for the existence of tournaments with property Sk is derived as a corollary. A multivariate version of this result is proved next: with Wj representing the number of ksubsets that are beaten by precisely j external vertices, j = 0, 1, …, b, it is shown that the joint distribution of (W0, W1, …, Wb) can be approximated by a multidimensional Poisson vector with independent components, provided that b is not too large.
Citations  Altmetrics  Downloads 
Additional indexing
Item Type:  Journal Article, refereed, original work 

Communities & Collections:  07 Faculty of Science > Institute of Mathematics 
DDC:  510 Mathematics 
Language:  English 
Date:  1997 
Deposited On:  07 Apr 2010 14:09 
Last Modified:  23 Nov 2012 14:28 
Publisher:  Cambridge University Press 
ISSN:  09635483 
Additional Information:  Copyright: Cambridge University Press 
Publisher DOI:  10.1017/S0963548396002829 
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page