4
$\begingroup$

You are in a strange party where everyone knows exactly 22 other person and any two who don’t know each other have exactly 6 mutual friends. How many are there in the party?

Source 40- Strange Party

My research:

I know that the adjacency matrix $M$ is symmetrical and if $M[i,j] = 0$ then i-th and j-th rows have 6 times 1 at the same index position. I am thinking about encoding problem into SAT formulae and trying to brute force SAT solver with different number of literals (elements of upper triangle matrix of adjacency matrix).

I have read some articles about Moore graphs and it seems that the upper limit for the vertices is $22^2 + 1 = 485$.

Do you have any hints to the solution?

$\endgroup$
2
  • 1
    $\begingroup$ What is a party? I didn't think that people can be in groups of more than 6 people, let alone where they know 22. $\endgroup$
    – Asaf Karagila
    Nov 2 '20 at 21:07
  • $\begingroup$ There's a trivial answer of 23 people (everyone knows everyone, so the 6 mutual friends rule doesn't get used). I'm guessing that's not what you're looking for though. $\endgroup$
    – Dave
    Nov 2 '20 at 21:25
4
$\begingroup$

This is not a solution. This just demonstrate that $ n \leq 100$.

Take the typical graph theoretic representation.
Let friend be represented by a red edge, stranger be represented by a blue edge.
We have $d_r (v_i) = 22, d_b (v_i) = n - 23$, so total number of red edges is $11n$ and total number of blue edges is $ \frac{n(n-23)}{2}$.

We count the number of triples of red-red-blue triangles.
For each blue edge, the condition gives us exactly 6 red-red-blue triangles.
For each red-red emanating from a vertex, it could give us a red-red-red or red-red-blue triangle.

Hence, $ 6 \times \frac{ n ( n-23) } { 2 } \leq n \times { 22 \choose 2 } \Rightarrow n \leq 100$.

$\endgroup$
0
4
$\begingroup$

A partial answer: the possible numbers of vertices are $23, 40, 100$, and some unknown subset of $\{51,52, \dots, 99\}$.

For a vertex to have degree $22$, we need at least $23$ vertices. This is possible: take the clique $K_{23}$. The second condition is satisfied trivially.

If we want the second condition to be satisfied nontrivially, then there must be non-adjacent vertices $v$ and $w$. This requires $6$ more vertices in $N(v) \cap N(w)$, $16$ more in $N(v) \setminus N(w)$, and $16$ more in $N(w) \setminus N(v)$, for at least $40$ total.

$40$ vertices is possible: consider the graph with vertex set $\{v_1, \dots, v_{20}, w_1, \dots, w_{20}\}$, with a complete graph on the first $20$ and the last $20$ vertices. Additionally, add edges $v_i w_i$, $v_i w_{i+1}$, and $v_i w_{i-1}$ (with arithmetic modulo $20$). Two non-adjacent vertices $v_i$ and $w_j$ have $\{w_{i-1}, w_i, w_{i+1}, v_{j-1}, v_j, v_{j+1}\}$ as common neighbors.

If there are more than $40$ vertices, then in the lower bound above there must be at least one vertex $u$ not adjacent to $v$ or $w$. Let's say that $|N(u) \cap N(v) \cap N(w)| = k$. Then there are $6-k$ vertices in each pairwise intersection of $N(u), N(v), N(w)$ leaving $22 - k - 2(6-k) = k+10$ vertices adjacent to only one of $u,v,w$. That's a total of at least $51$ vertices.

I don't know if this is achievable, but there's an upper bound. On the high end, the Higman–Sims graph has $100$ vertices, and is an example because it is strongly regular. Every vertex has degree $22$, every two non-adjacent vertices have $6$ common neighbors, and for a bonus every two adjacent vertices have no common neighbors. As the other answer argues, this is the largest possible number of vertices.

$\endgroup$
4
  • $\begingroup$ The first was clever. I'm not seeing your second example though... $\endgroup$
    – Mike
    Nov 2 '20 at 18:45
  • $\begingroup$ I see it now. Thanks! $\endgroup$
    – Mike
    Nov 2 '20 at 18:49
  • $\begingroup$ I also found the 40 vertices example, but wasn't able to adapt it to > 40. $\endgroup$
    – Calvin Lin
    Nov 2 '20 at 19:25
  • $\begingroup$ @CalvinLin $41, \dots, 50$ are also impossible, and I have serious doubts about $51$. $\endgroup$ Nov 2 '20 at 19:38

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.