On a Problem of Schütte and Erdös (Q5345647)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3218579
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On a Problem of Schütte and Erdös |
scientific article; zbMATH DE number 3218579 |
Statements
On a Problem of Schütte and Erdös (English)
0 references
1965
0 references
Let \(f(k)\) denote the least integer \(n\) for which there exists a tournament \(T_n\) such that for every \(k\) nodes of \(T_n\) there is some node \(p\) such that all the edges joining \(p\) and these \(k\) nodes are oriented away from \(p\). \textit{P. Erdős} [Math. Gaz. 47, 220--223 (1963; Zbl 0117.17402)] showed that \(2^{k+1}-1 \leq f(k) \leq C \cdot 2^k k^2 \) for a suitable constant \(C\). In the present paper it is shown, by first considering a more general problem, that \(f(k) \ge (k+2) 2^{k-1}-1\). In particular, it is shown that \(f(3)=19\).
0 references