# zbMATH — the first resource for mathematics

A problem on tournaments. (English) Zbl 0129.34701
A tournament on a set $$X$$ (whose elements are called players) is a subset $$E$$ of $$X \times X$$ such that $$(p,q) \in E$$ if and only if $$p \neq 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(2^{n(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.

##### MSC:
 90-XX Operations research, mathematical programming
##### Keywords:
operations research
Full Text: