Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 129.34701
Autor: Erdös, Pál; Moser, L.
Title: A problem on tournaments (In English)
Source: Can. Math. Bull. 7, 351-356 (1964).
Review: A tournament on a set X (whose elements are called players) is a subset E of X × X such that (p,q) in E if and only if p \ne q and (q,p)\not in E. We interpret (p,q) in E as meaning that p wins a game against q. Let k be a fixed positive integer. The authors prove that there exists a positive \alpha such that, in all but o(2n(n-1)/2) of the tournaments on n given players, every pair S,T of disjoint sets of players with |S \cup T| \leq k have the property that at least \alpha n/2 |S \cup T| of the remaining players beat all members of S and lose to all members of T. The stronger result that \alpha can be chosen arbitrarily near to 1 is stated. Some related problems and results are discussed: inter alia the authors mention that they have characterized the minimum number of edges in an undirected graph with n vertices and no loops or multiple edges such that every k vertices have a vertex to which they are all joined.
Reviewer: C.St.J.A.Nash-Williams
Classif.: * 90
Index Words: operations research
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag