Annals of Combinatorics 1 (1997) 1-15

The Polytope of Win Vectors

J.E. Bartels1 and J. Mount2 and D.J.A. Welsh1
1Mathematical Institute, University of Oxford, 27-29 St Giles, Oxford, OX1 3LB, UK
  {bartels, dwelsh}

2Arris Pharmaceutical, 385 Oyster Pt., Blvd., Suite 3, South San Francisco, CA 94080, USA

Received December 23, 1996

AMS Subject Classification: 05C20, 05C90

Abstract. Imagine a graph as representing a fixture list with vertices corresponding to teams, and the number of edges joining u and v as representing the number of games in which u and v have to play each other. Each game ends in a win, loss, or tie and we say a vector $\vct{w} $ =(w1,...,wn) is a win vector if it represents the possible outcomes of the games, with wi denoting the total number of games won by team i. We study combinatorial and geometric properties of the set of win vectors and, in particular, we consider the problem of counting them. We construct a fully polynomial randomized approximation scheme for their number in dense graphs. To do this we prove that the convex hull of the set of win vectors of G forms an integral polymatroid and then use volume approximation techniques.

Keywords: score vector, polytope, polymatroid, competition, random generation, approximate counting, fully polynomial, randomized approximation scheme


1.  N. Alon, A. Frieze, and D. Welsh, Polynomial time randomized approximation schemes for Tutte-Grothendieck invariants: the dense case, Random Structures and Algorithms 6(4) (1995) 459–478.

2.  J.D. Annan, A randomised approximation algorithm for counting the number of forests in dense graphs, Combin., Probab. and Comput. 3 (1994) 273–283.

3.  M. Crawley and R. May, Population dynamics and plant community structure: competition between annuals and perennials, J. Theoret. Biology 125 (1987) 475–489.

4.  M. Dyer, R. Kannan, and J.~Mount, Sampling contingency tables, Random Structures and Algorithms, to appear.

5.  J. Edmonds, Submodular functions, matroids, and certain polyhedra, In: Combinatorial Structures and their Applications, Proc. Calgary Internat. Conf., Calgary, Alta., 1969, H.~Hanani, N. Sauer, and J. Schönheim, Eds., Gordon and Breach, New York, 1970, pp. 69–87.

6.  J.D. Gibbons, I. Olkin, and M. Soebel, Baseball competitions: are enough games played? Amer. Statistician 32 (1978) 89–95.

7.  F. Jaeger, D. Vertigan, and D. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos.~Soc. 108 (1990) 35–53.

8.  T. Jech, The ranking of incomplete tournaments: a mathematician's guide to popular sports, Amer. Mathemat. Monthly 90 (1983) 246–266.

9.  R. Kannan, P. Tetali, and S. Vempala, Simple Markov chain algorithms for generating bipartite graphs and tournaments, preprint, 1996.

10.  D.J. Kleitman and K.J. Winston, Forests and score vectors, Combinatorica 1 (1981) 49–54.

11.  H. Kullmann, Personal communication, 1996.

12.  L. Lovasz and M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures and Algorithms 4(4) (1993) 359–412.

13.  C.A. cGilchrist and B.R. Trenbath, A revised analysis of plant competition experiments, Biometrics 27 (1971) 659–671.

14.  R. Mead, Competition experiments, Biometrics 35 (1979) 41–54.

15.  J. Moon, Topics on Tournaments, Holt, Rinehart and Winston, New York, 1968.

16.  K. Reid and L. Beineke, Tournaments In: Selected Topics in Graph Theory, L. Beineke and R. Wilson, Eds., Academic Press, New York, 1978, pp. 169–204.

17.  G. Shephard, Combinatorial properties of associated zonotopes, Canad. J. Math. 26(2) (1974) 302–321.

18.  R.P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth & Brooks/cole, Monterey, California, 1986.

19.  R.P. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math. 6(6) (1980) 333–342.

20.  D.M. Topkis, Adjacency on polymatroids, Math. Programming 30 (1984) 229–237.

21.  D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.

22.  D.J.A. Welsh, Counting colourings and flows in random graphs, In: Combinatorics - Paul Erdös is Eighty, Janos Bolyai Math. Soc., Budapest, 1996, pp. 491–505.

23.  H.S. Wilf, Generatingfunctionology, Academic Press, London, 1990.

Get the LaTex | DVI | PS file of this abstract.