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? Is there a general formula for this minimum in terms of $P$ and $K?$
 A: Here's an elementary start on investigating this interesting problem

Let $M$ be the minimum number of people in a clique. Then $M$ is non-zero if and only if $K>\frac{P-1}{2}.$

If $M=0$ then there is no pair such that each knows the other. The number of 'knowings', $KP$ , is therefore no greater than $\begin{pmatrix}P\\2\\\end{pmatrix}$ and so $K\le \frac{p-1}{2}.$
Conversely, suppose $K\le \frac{P-1}{2}.$ Consider the population arranged in a circle with everyone knowing the next $K$ people in the circle. Then no pair know each other.
A: I did a computer search with z3. Let $C(p, k)$ denote the number of smallest possible clique number of a directed graph of $p$ nodes in which each nodes has $k$ out arcs. Then
C(4, 2)=2
C(4, 3)=4
C(5, 2)=1
C(5, 3)=2
C(5, 4)=5
C(6, 2)=1
C(6, 3)=2
C(6, 4)=2
C(6, 5)=6
C(7, 2)=1
C(7, 3)=1
C(7, 4)=2
C(7, 5)=3
C(7, 6)=7
C(8, 2)=1
C(8, 3)=1
C(8, 4)=2
C(8, 5)=2
C(8, 6)=3
C(8, 7)=8
C(9, 2)=1
C(9, 3)=1
C(9, 4)=1
C(9, 5)=2
C(9, 6)=2
C(9, 7)=3
C(9, 8)=9

Note that $C(p,p-1)=p$, which is obvious.
The code is as follows. You can call search(p) for $p > 9$ for more results. Though it gets much slower for $p=10$ on my laptop.
import z3
import itertools
import math

class DRamseySolver():

    def __init__(self, p, k, m):
        self.p = p
        self.k = k
        self.m = m

        self.solver = z3.Solver()
        self.add_var()
        self.add_clause()

    def add_var(self):
        self.var = {}
        for i in range(self.p):
            varlist = []
            for j in range(self.p):
                if i != j:
                    v = z3.Bool('x_{0}_{1}'.format(i, j))
                    self.var[i,j] = v
                    varlist.append(v)
            self.solver.add(z3.PbEq([(x,1) for x in varlist], self.k))

    def add_clause(self):
        for s in itertools.combinations(range(self.p), self.m):
            varlist = []
            for edge in itertools.combinations(s, 2):
                v1 = self.var[edge[0], edge[1]]
                v2 = self.var[edge[1], edge[0]]
                varlist.append(v1)
                varlist.append(v2)
            if varlist:
                self.solver.add(z3.Or([z3.Not(v) for v in varlist]))

    def check(self):
        return self.solver.check()

    def model(self):
        return self.solver.model()

def search(p_up):
    for p in range(4, p_up+1): 
        for k in range(2, p): 
            for m in range(2, p+2): 
                if DRamseySolver(p, k, m).check() == z3.sat: 
                    print("C({0}, {1})={2}".format(p, k, m-1)) 
                    break

