In a population of $n$ people, each person knows $k$ other people and if person A knows person B then person B knows person A. However, no two people, A and C, know the same two people B and D. What is the minimum $n$ such that this is possible for a given $k$? Or, in other words, what's the minimum number of nodes that must exist such that it is possible to connect each node to $k$ other nodes while not allowing a circuit of length 4?
I don't have much on this problem yet besides a weak lower bound of $n\geq k^2-k+1$.
In the graphs below, an edge means that the two people it connects know each other. In 1), this is a demonstration of what we don't want, both A and C know D and B. In 2) these are configurations that work for k=2. For k=2, $n=3$ and $n>4$ work. In 3) n=10, and this is the smallest possible configuration for k=3.
