Population of P people, where each person knows K others, how many people mutually know each other If you have a population of $P$ people, where each person knows $K$ others within the population (does not have to be mutual, i.e., if I know you, you don't necessarily know me), and $1<K<P$, how many people at the least must mutually know each other (i.e., everyone knows everyone)? Is there a general formula for this minimum in terms of $P$ and $K$?
 A: For $x\geq 2$, and $m$ odd, there is a regular digraph of order $P=(x-1)m$ and of out-valency $K=(x-2)m+\frac{m-1}{2}=\frac{(2x-3)m}{2}-\frac{1}{2}$ with no cliques of size $x$: start with the complete $(x-1)$-partite graph with parts of size $m$ and then add directed edges to make each part a regular tournament (of out-valency $\frac{m-1}{2}$). This clearly has the required property. (If there was a clique of size $x$, then it would intersect one of the parts in at least a two-way edge.)
Substituting we find $K=(1-\frac{1}{2x-2})P-\frac{1}{2}$ for these examples.
It's not hard to see that this is tight for $x=2$ (where the example is just a tournament). I am not sure about tightness for larger $x$, but at least these examples show that $K$ must be quite close to $P$...
Note that this almost the directed version of Turan's Theorem 
https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem
except that we ask that the digraph be regular, so I wouldn't be surprised if this is know. (This also inspired the construction.)
A: This is a matching upper bound to verret's lower bound on the minimum out-degree guaranteeing a complete directed $K_x$.  
Let $G$ be a digraph on $n$ vertices of minimum out-degree at least $(1-1/2(x-1))n$.  Then the average in-degree is also at least $(1-1/2(x-1))n$ so some vertex $v$ has in-degree at least $(1-1/2(x-1))n$.
When $x=2$, this means that $v$ has at least $n/2$ out-neighbours and and at least $n/2$ in-neighbours, so the sets of these cannot be disjoint and $G$ contains a double edge, i.e. a directed $K_2$.  For $x>2$, let $U$ be the set of vertices connected to $v$ by an edge in both directions.  Then
$$|U| \geq (1-1/2(x-1)-1/2(x-1))n = (1-1/(x-1))n = \frac{x-2}{x-1}n.$$
Every $u \in U$ has at least 
$$|U| - n/2(x-1) \geq |U| - \frac{1}{2(x-1)}\frac{x-1}{x-2}|U| = (1-1/2(x-2))|U|$$
out-neighbours in $U$, so by induction $U$ contains a complete directed $K_{x-1}$.  Together with $v$ this forms a complete directed $K_x$.
