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
      0 references
      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
      0 references

      Identifiers