Smallest asymmetric relation such that each $k$ elements are dominated by a common element. How large does a non-empty set $X$ need to be if there exists an asymmetric relation $R \subset X^2$ such that for any $k$ elements $x_1,\dots,x_k$ of $X$ there exists a $x \in X$ such that $(x,x_i) \in R$ for all $i$ from $1$ to $k$?
For the purpose of this question we say that a relation is asymmetric if $(x,y) \in R$ implies $(y,x) \not \in R$.
Example: for $k=1$ the answer is $|X| \ge 3$, because the 'rock-paper-scissors' relation does the trick: $X = \{r,p,s\}$ and $R = \{(r,p),(p,s),(s,r)\}$ does the trick, and you can check that it is not possible with $|X| \le 2$. For $k=2$, I believe the answer is $|X| \ge 7$.
Context: I followed the `Topics in Combinatorics' lecture series by Tim Gowers on YouTube [1] (which I warmly recommend) and this problem was the second part of a problem on a question sheet [2]. The first part of the question is to prove that for each $k$, there exists a relation $R \subset X^2$ with this property for some $X$. You can solve this part with an averaging argument.
[1] https://www.youtube.com/watch?v=WcLrT263p2w&list=PLOft35kj95aYT2SgFbYwEOavJ7gagmCVZ
[2] https://drive.google.com/file/d/1OFgVrk1n2zxSF5tcfSe5Fxrva0YVhXEl/view
 A: Let $f(k)$ be the smallest number such that there exists an asymmetric relation $R$ on a set $X$ of size $f(k)$, so that for all $\{x_1,\dots,x_k\}\subseteq X$, there will exist $x\in X$ so that $(x,x_i)\in R$ for all $i\in \{1,\dots,k\}$ (what a mouthful!). One can show that
$$
f(k)\ge 2^{k+1}-1 \, .
$$
Furthermore, this bound is tight for $k=1$ and $k=2$. Erdös himself conjectured that $f(k)=2^{k+1}-1$ for all $k\ge 1$. However, the following paper (1) by Szekeres and Szekeres further shows that
$$
f(k)\ge (k+2)2^{k-1}-1
$$
So $f(3)\ge 19$, and $f(3)\neq 15$. In the same paper, they prove $f(3)\le 19$. Here, the asymmetric relation on $19$ vertices which works is the quadratic residue tournament modulo $19$. That is, $X=\mathbb Z/19\mathbb Z$, and $(x,y)\in R$ whenever there exists $k\in \mathbb Z/19\mathbb Z$ so that $x\equiv y+k^2\pmod{19}$.
Finally, Erdös showed that there exists a constant $C$ for which
$$
f(k)\le Ck^22^k,\qquad \text{for all }k\ge 1
$$
using a probabilistic argument. These are the best bounds I know on $f(k)$.

(1) E. Szekeres, and G. Szekeres. “On a Problem of Schütte and Erdös.” The Mathematical Gazette, vol. 49, no. 369, 1965, pp. 290–293. JSTOR, www.jstor.org/stable/3612854. Accessed 17 Jan. 2021.

