Γνωριμίες

Mikesar · #1

Έστω μια παρέα

ατόμων. Αν δύο άτομα γνωρίζονται τότε δεν έχουν κανένα κοινό γνωστό, ενώ αν δεν γνωρίζονται έχουν ακριβώς δύο κοινούς γνωστούς. Να βρεθούν όλα τα

για τα οποία υπάρχει μια τέτοια παρέα.

Σημείωση:
Το πρόβλημα 827 του Putnam and Beyond ζητά να αποδειχθεί ότι όλα τα άτομα έχουν ίδιο πλήθος γνωστών. Στην προσπάθειά μου να λύσω αυτό, προέκυψε ως αποτέλεσμα και το παραπάνω. Δεν έχω πλήρη λύση, με την έννοια ότι έχω βρει ότι αν γίνεται, το

θα είναι μιας συγκεκριμένης μορφής, αλλά για αυτά τα

δεν έχω κάνει κατασκευή.

#2

Ας λύσουμε πρώτα το αρχικό ερώτημα από το Putnam & Beyond.

Αρκεί να δείξουμε ότι κάθε δύο άτομα που γνωρίζονται έχουν το ίδιο πλήθος κοινών γνωστών. Τότε όλοι θα έχουν το ίδιο πλήθος κοινών γνωστών αφού αν οι A,B

δεν γνωρίζονται τότε έχουν έναν κοινό φίλο

. Εφόσον ο

και ο

έχουν το ίδιο πλήθος κοινών γνωστών με τον

τότε θα έχουν το ίδιο πλήθος κοινών γνωστών και μεταξύ τους.

Έστω λοιπόν δυο άτομα A,B

οι οποίοι γνωρίζονται. Έστω $A_1,\ldots,A_k$ οι γνωστοί του

και $B_1,\ldots,B_{\ell}$ οι γνωστοί του

. Από την δεδομένη συνθήκη όλοι αυτοί είναι διαφορετικοί. Αφού ο A_1

δεν γνωρίζεται με τον

, τότε θα έχουν δύο κοινούς γνωστούς. Ο ένας είναι ο

. Οπότε ο

έχει ακριβώς έναν γνωστό μεταξύ των $B_1,\ldots,B_{\ell}$ . Ομοίως ο A_i

(για $1\leqslant i \leqslant k$ ) έχει ακριβώς έναν γνωστό μεταξύ των $B_1,\ldots,B_{\ell}$ . Οπότε έχουμε ακριβώς

γνωριμίες μεταξύ των A_i

και

. Ομοίως έχουμε ακριβώς $\ell$ γνωριμίες και άρα $k = \ell$ .

Κατασκευάζουμε το γράφημα

με κορυφές τα άτομα και με τις ακμές να δηλώνουν τις γνωριμίες. Μετράμε όλες τις δυάδες $(x,\{y,z\})$ όπου $y \neq z$ και οι κορυφές y,z

είναι γειτονικές της

. Για κάθε

υπάρχουν $\binom{d}{2}$ ζεύγη $\{y,z\}$ οπότε συνολικά έχουμε $n \binom{d}{2}$ δυάδες.

Από την άλλη αν οι y,z

είναι γειτονικές δεν έχουμε τέτοιες δυάδες, ενώ αν δεν είναι γειτονικές τότε έχουμε δύο τέτοιες δυάδες. Αφού έχουμε dn/2

ακμές, τότε ο αριθμός των πιο πάνω δυάδων είναι $\displaystyle{ 2\left[ \binom{n}{2} - \frac{dn}{2}\right]}$

Εξισώνοντας καταλήγουμε στο $\displaystyle{ n = \frac{d^2+d+2}{2}}$

Θα δείξουμε όμως ότι μπορούμε να πούμε πολύ περισσότερα.

Γραφήματα για τα οποία υπάρχουν d,a,b

ώστε να ισχύουν τα εξής:
- Κάθε κορυφή έχει ακριβώς

γείτονες
- Κάθε δύο γειτονικές κορυφές έχουν ακριβώς

κοινούς γείτονες
- Κάθε δύο μη γειτονικές κορυφές έχουν ακριβώς

κοινούς γείτονες
ονομάζονται strongly regular

Εδώ είναι a=0,b=2

Θέματα σχετικά με strongly regular graphs αντιμετωπίζονται όπως πιο κάτω.

Γράφουμε

για το adjacency matrix του

. Δηλαδή αν $v_1,\ldots,v_n$ οι ακμές τότε $A_{ij} = 1$ αν οι v_i,v_j

είναι γειτονικές, και $A_{ij} = 0$ σε διαφορετική περίπτωση.

Υπολογίζουμε τώρα το A^2

. Είναι $A_{ii} = d$ για κάθε

. Αν $A_{ij} = 1$ , τότε $(A^2)_{ij} = 0$ και αν $A_{ij}=0$ τότε $(A^2)_{ij} = 2$ . Καταλήγουμε στο

$\displaystyle{ A^2 = 2J - 2A + (d-2)I }$

όπου με

συμβολίζουμε τον πίνακα που έχει παντού άσσους.

Πολλαπλασιάζοντας με

και χρησιμοποιώντας ότι AJ = dJ

παίρνουμε

$\displaystyle{\begin{aligned}A^3 &= 2dJ - 2A^2 + (d-2)A \\ &= d[A^2 + 2A - (d-2)I] - 2A^2 + (d-2)A \\ &= (d-2)A^2 + (3d-2)A - d(d-2)I \end{aligned}}$

Άρα το ελάχιστο πολυώνυμο του

διαιρεί το

$\displaystyle{ x^3 - (d-2)x^2 - (3d-2)x + d(d-2) = (x-d)(x^2+2x -(d-2))}$

Άρα το

έχει ιδιοτιμές τα

και $-1 \pm \sqrt{d-1}$ .

Ισχυρίζομαι ότι η ιδιοτιμή

έχει πολλαπλότητα

. Πράγματι, έστω $x = (x_1,\ldots,x_n)$ ένα ιδιοδιάνυσμα του

με ιδιοτιμή

και έστω $x_i = \max\{x_1,\ldots,x_n\}$ . Τότε
$\displaystyle{ dx_i = Ax_i = \sum_{\{j:x_i \sim x_j\}} x_j \leqslant dx_i}$
Η ισότητα ισχύει αν και μόνο αν x_j = x_i

για κάθε

με $x_i \sim x_j$ . Επαγωγικά καταλήγουμε στο x_j = x_i

για κάθε

. (Με επαγωγή στην απόσταση του x_j

από το

και χρησιμοποιώντας την συνεκτικότητα του

.)

Ας υποθέσουμε πως η ιδιοτιμή $-1+\sqrt{d-1}$ έχει πολλαπλότητα

και η ιδιοτιμή $-1-\sqrt{d-1}$ έχει πολλαπλότητα

.

Τότε r+s = n-1

. Επίσης έχουμε

$\displaystyle{ 0 = \mathrm{tr}(A) = d + r(-1+\sqrt{d-1}) + s(-1-\sqrt{d-1}) = d-(r+s) + (r-s)\sqrt{d-1}}$

Άρα $\displaystyle{ (r-s)\sqrt{d-1} = d+1-n}$ και άρα $\displaystyle{ r-s = \frac{d+1-n}{\sqrt{d-1}}}$ .

Καταλήγουμε λοιπόν στο

$\displaystyle{ r = \frac{1}{2}\left(n-1 + \frac{d+1-n}{\sqrt{d-1}} \right)}$

Αφού o

είναι φυσικός πρέπει n = d+1

ή $\sqrt{d-1}$ φυσικός.

Στην πρώτη περίπτωση έχουμε $\displaystyle{ d+1 = n = \frac{d^2+d+2}{2}}$ που δίνει $d \in \{0,1\}$ και άρα $n=\{1,2\}$ . Και οι δύο αυτές περιπτώσεις μπορούν όντως να συμβούν.

Στην δεύτερη περίπτωση πρέπει d = t^2+1

για κάποιο φυσικό

. Τότε έχουμε

$\displaystyle{ n = \frac{d^2+d+2}{2} = \frac{t^4+3t^2+4}{2}}$

και

$\displaystyle{ \begin{aligned} r &= \frac{1}{2}\left(n-1 + \frac{t^2+2-n}{t} \right) \\ &= \frac{1}{2}\left(\frac{t^4+3t^2+2}{2} + \frac{t^2+2-n}{t} \right) \\ &= \frac{t^4+3t^2+2}{4} - \frac{t^4+t^2}{4t} \\ &= \frac{t^4-t^3+3t^2-t+2}{4} \end{aligned}}$

Οπότε πρέπει επίσης να είναι $t^4 - t^3 + 3t^2 - t \equiv 2 \bmod 4$ που δίνει $t \equiv 1,2,3 \bmod 4.$

$\rule{500pt}{1pt}$
$\rule{500pt}{1pt}$

Μέχρι στιγμής έχουμε δείξει ότι n=1,2

ή

για κάποιο $t\neq 0 \bmod 4$ .

Για t=1

είναι

και έχουμε το γράφημα C_4

.
Για

είναι

και έχουμε το γράφημα Clebsch.
Για t=3

είναι

και έχουμε το γράφημα Gewirtz.

Σύμφωνα με την τελευταία παράγραφο εδώ, δεν γνωρίζουμε αν υπάρχουν άλλα παραδείγματα που να δουλεύουν.

Γνωριμίες

Γνωριμίες

Re: Γνωριμίες

Μέλη σε σύνδεση