# Minimum Number of People Such That No Two People Know the Same Two People

In a population of $n$ people, each person knows $k$ other people and each person is known by the same $k$ people. However, no two people, p1 and p2, know the same two people p3 and p4. 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 cycle of length 4?

Also, if it is possible, is there a program that can generate these graphs?

I don't have much on this problem yet besides a weak lower bound of $n\geq k^2-k+2$.

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 all n>4 work. In 3) n=10, this is the smallest possible configuration for k=3.

• You could try solving it for $k=1,2,3,4,5,6$, then plugging the resulting sequence into the OEIS to see if anything turns up. – D.W. Jul 8 '17 at 7:39
• Isn't this connected to Ramsey's theory? If so, this is more of math question. – rus9384 Jul 8 '17 at 8:57
• @rus9384 The question asks for an algorithm to generate the graphs, so I think it's on-topic here. But it might be a good idea to split it into two parts and ask the Ramsey-theoretic question on Math.SE and keep the algorithmic part here, with links between the two questions for context. – David Richerby Jul 8 '17 at 12:38
• Regarding the lower bound you mention, it is indeed a lower bound and the difference with the minimum $n$ grows rapidly with increasing values of $k$. However, for $k=2$, there is a solution with $n=3$ (see 2.left) while the lower bound you give predicts at least 4 nodes. At best, your lower bound works for $k>2$. – Carlos Linares López Jul 9 '17 at 23:25
• I think a much better lower bound can be found by reasoning as follows: let $T(k)$ denote the minimum number of nodes $n$ you are seeking for a specific value of $k$. Each graph for a given $k$, $G(k)$, can be constructed by considering at least $k$ components that contain $T(k-1)$ nodes each. An additional node is then added to join these $k$ components (with $k$ edges from it to one node from the $k$ different components), yielding $T(k)=kT(k-1)+1$. Obviously, $T(1)=2$ and, from here, $T(2)=3$, $T(3)=10$ ... This formula is inspired by Figure 3. – Carlos Linares López Jul 9 '17 at 23:40

The comment of Carlos actually gives an upper bound. There is a much better (and almost tight) upper bound for $k+1$ being a prime number: $n=k(k+1)$. The construction is a classical result in extremal graph theory, namely $C_4$-free $k$-regular graphs, which can be found here.
The vertices are labeled with $(a,b)$ where $1\leq a\leq k, 0\leq b\leq k$. Two vertices $(a,b)$ and $(c,d)$ are linked if and only if $ac\equiv b+d\mod (k+1)$. Notice that for any given pair $(a,b)$ the number of solutions $(c,d)$ is exactly $k$, so the graph is $k$-regular. To see the graph is $C_4$-free, consider the following congruence equations $$\left\{ \begin{array}{ll}ax\equiv b+y\mod (k+1)\\ cx\equiv d+y\mod (k+1)\end{array} \right.$$ Since these imply $(a-c)x\equiv b-d \mod (k+1)$, and $k+1$ is prime, there is at most one solution whenever $(a,b)\neq (c,d)$, so the graph contains no $4$-cycle.
There are many other constructions among this context, for instance, when $k-1$ is a prime power there is a construction of size $n=2(k^2-k+1)$ with bipartite incidence graph (See, e.g., here).