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.

90-XX Operations research, mathematical programming
Full Text: DOI