patternMinor
Minimum Number of People Such That No Two People Know the Same Two People
Viewed 0 times
suchsamenumbertheknowminimumtwothatpeople
Problem
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.
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.
Solution
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).
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).
Context
StackExchange Computer Science Q#77696, answer score: 2
Revisions (0)
No revisions yet.