Author 
Topic: Barely compatible gatherings (Read 1056 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


Barely compatible gatherings
« on: Jun 6^{th}, 2008, 9:06pm » 
Quote Modify

A barely compatible gathering of people, BCP, is a set of people with the following properties. 1) Every person in the set is friends with the same number, k, of people in the set. 2) If person a is not friends with person b, then a and b have exactly one friend in common in the set. If a and b are friends, then a and b have no friend in common in the set. Show that there are only a finite number of integers n such that there exists a barely compatible gathering of n people. Examples. n=2. Two friends. n=5. People equal the vertices of a pentagon. Two vertices are friends if they are adjacent. n=10. People equal the ten 2subsets of {1,...,5}. Two 2subsets are friends if they are disjoint. (The Petersen graph)


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Barely compatible gatherings
« Reply #1 on: Jun 7^{th}, 2008, 3:16pm » 
Quote Modify

In graphtheoretic terms, there are only finitely many regular graphs of girth => 5 and diameter <= 2.

« Last Edit: Jun 7^{th}, 2008, 3:26pm by Obob » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Barely compatible gatherings
« Reply #2 on: Jun 8^{th}, 2008, 11:21am » 
Quote Modify

Here is an attempt Let A be the adjacency matrix of the graph. Then we can easily see that A^2 + A = (k1)I + J, where J is the all ones matrix. now if s is an eigenvalue of A with eigenvector x, then we have that [s^2 + s  (k1)] x = Jx. Thus we have that either s = k (in which case x is [1 1 ... 1]) or 2s = 1 + sqrt(4k3) (roots of s^2 + s  (k1) = 0) We can also show that the multiplicity of the eigenvalue k is 1. (true for any regular graph of degree k) So since trace of A is zero, for some integers P and Q we must have that P (1 + sqrt(4k3)) + Q(1  sqrt(4k3)) + k = 0. i.e k + P + Q = (PQ) sqrt(4k3) We also have the P+Q = n1 = k^2 (the eigenvalue corresponding to [1 1 ... 1] of A^2 is n1, and must be square of corresponding for A, which is k) So PQ = (k + k^2)/sqrt(4k3) Thus we must have that 4k3 = t^2 for some integer t. and that k(k1)/t is an integer. Thus we have that (t^2+3)(t^21)/16t is an integer. Thus we have that (t^4 + 2t^2 3)/t is also an integer. (Mutiply by 16 and expand the numberator) Thus t divides 3. Hence there are only a finite number of such k.

« Last Edit: Jun 8^{th}, 2008, 11:35am by Aryabhatta » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Barely compatible gatherings
« Reply #3 on: Jun 9^{th}, 2008, 1:27am » 
Quote Modify

Very close...but you're missing a factor of 2 in the trace equation. Here is a similar problem: There are n>3 people such that any two of them have exactly one common friend. Show that there is one person who is friends with everybody else.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Barely compatible gatherings
« Reply #4 on: Jun 9^{th}, 2008, 2:50pm » 
Quote Modify

If I'm not mistaken, eigenray, your problem is known as the Friendship Theorem. I learned of this problem in the form: if there are n people with the property that any two of them have exactly one friend in common, then Dale Carnegie is there. Eons ago Dale Carnegie wrote a book entitled "How to Win Friends and Inflluence People". About a year ago I saw online a purely combinatorial proof of the Friendship Theorem.


IP Logged 



