4
$\begingroup$

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.

Various setups for nodes

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 8 '17 at 7:39
  • $\begingroup$ Isn't this connected to Ramsey's theory? If so, this is more of math question. $\endgroup$ – rus9384 Jul 8 '17 at 8:57
  • $\begingroup$ @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. $\endgroup$ – David Richerby Jul 8 '17 at 12:38
  • 1
    $\begingroup$ 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$. $\endgroup$ – Carlos Linares López Jul 9 '17 at 23:25
  • $\begingroup$ 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. $\endgroup$ – Carlos Linares López Jul 9 '17 at 23:40
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.