Wykres gier

Nie mylić z wykresem turniejowym .

W teorii grafów graf gier jest największym znanym lokalnie liniowym, silnie regularnym grafem . Jego parametry jako silnie regularnego wykresu to (729,112,1,20). Oznacza to, że ma 729 wierzchołków i 40824 krawędzi (112 na wierzchołek). Każda krawędź jest w unikalnym trójkącie (jest to graf lokalnie liniowy ), a każda niesąsiadująca para wierzchołków ma dokładnie 20 wspólnych sąsiadów. Jej nazwa pochodzi od nazwiska Richarda A. Gamesa, który w niepublikowanym komunikacie zasugerował jej budowę i pisał o konstrukcjach z nią związanych.

Budowa

Konstrukcja tego wykresu obejmuje unikalny (do symetrii) 56-punktowy $czapek$ punktów bez trzech pięciu -wymiarowa geometria rzutowa na polu trójelementowym. Sześciowymiarową $sześciowymiarową$ można _ $\ Displaystyle AG (6,3)}$ { $przestrzeni$ punkty w afinicznej Wykres gier ma jako wierzchołki 729 punktów przestrzeni afinicznej ${\ Displaystyle AG (6,3)}$ . Każda linia w przestrzeni afinicznej przechodzi przez trzy z tych punktów i przez czwarty punkt w nieskończoności. Wykres zawiera trójkąt dla każdej linii trzech punktów afinicznych, która przechodzi przez punkt zestawu czapek.

Nieruchomości

Kilka właściwości wykresu wynika bezpośrednio z tej konstrukcji. Ma ${\ displaystyle 729 = 3 ^ {6}}$ wierzchołków, ponieważ liczba punktów w przestrzeni afinicznej jest wielkością pola podstawowego do potęgi wymiaru. Dla każdego punktu afinicznego istnieje 56 linii przechodzących przez ustalone punkty czapki, 56 trójkątów zawierających odpowiedni wierzchołek i ${\ Displaystyle 112 = 56 \ razy 2}$ sąsiedzi wierzchołka. I nie może być innych trójkątów niż te pochodzące z konstrukcji $trójkąt$ musiałby pochodzić z trzech różnych linii spotykających się na , a wszystkie trzy punkty ustawienia czapek trzech linii leżałyby na przecięciu tej płaszczyzny z . ${\ Displaystyle PG (5,3)}$ , która jest linią. Ale to naruszyłoby właściwość definiującą zbiór czapek, że nie ma on trzech punktów na linii, więc taki dodatkowy trójkąt nie może istnieć. Pozostała właściwość grafów silnie regularnych, polegająca na tym, że wszystkie niesąsiadujące pary punktów mają taką samą liczbę wspólnych sąsiadów, zależy od specyficznych właściwości 5-wymiarowego zestawu czapek.

Powiązane wykresy

Z $postać$ i wykresem Brouwera Haemersa wykres gier jest jednym z zaledwie trzech możliwych silnie regularnych wykresów, których parametry ( ${\ Displaystyle {\ bigl (} (n ^ {2} + 3n-1) ^ {2}, n ^ {2} (n + 3), 1, n (n + 1) {\ bigr)}}$ .

$,$ -punktowym zestawem czapek w , , silnie regularny wykres z parametry (243,22,1,2). Ten wykres to wykres Berlekampa – Van Linta – Seidela .