Numărul de jocuri

Graficul Jocurilor este cel mai mare grafic cunoscut local liniar puternic regulat . Parametrii săi ca un grafic puternic regulat sunt (729,112,1,20). Aceasta înseamnă că graficul are 729 de vârfuri și 40824 de muchii (112 muchii per vârf). Fiecare muchie este într-un singur triunghi (acesta este un grafic cu linie local ) și fiecare pereche de vârfuri non-adiacentă are exact 20 de vecini comuni. Graficul este numit după Richard A. Games, care a propus construirea lui într-o corespondență nepublicată [1] și a scris despre construcții înrudite [2] .

Clădire

Construcția acestui grafic folosește un set unic (până la simetrie) de 56 de puncte ( setul de cap în limba engleză , subseturi de puncte, dintre care trei nu se află pe aceeași linie) în geometrie proiectivă cinci-dimensională pe trei -câmpul elementului [3] . O geometrie proiectivă cu șase dimensiuni, , poate fi descompusă într-un spațiu afin cu șase dimensiuni și o copie ( puncte la infinit dat fiind spațiul afin). Graficul Jocurilor are 729 de puncte din spațiul afin ca vârfuri . Fiecare linie din spațiul afin trece prin trei dintre aceste puncte și un al patrulea punct la infinit. Graficul conține un triunghi pentru orice linie de trei puncte afine care trece printr-un punct al setului cap-set [1] . $PG(5,3)$ $PG(6,3)$ $AG(6,3)$ $PG(5,3)$ $AG(6,3)$

Proprietăți

Unele dintre proprietățile graficului decurg imediat din construcție. Graficul are vârfuri deoarece numărul de puncte dintr-un spațiu afin este egal cu dimensiunea câmpului de bază la puterea dimensiunii. Pentru fiecare punct afin, există 56 de linii prin punctele setului de capac, 56 de triunghiuri care conțin vârful corespunzător și vecine ale vârfului. Și nu pot exista alte triunghiuri decât cele obținute în timpul construcției, deoarece orice alt triunghi ar fi obținut din trei linii diferite care se intersectează într-un plan comun și trei puncte ale setului de trei linii s-ar afla la intersecția acestui plan cu , care dă o linie. Totuși, acest lucru ar încălca proprietatea setului de capac potrivit căreia niciunul dintre punctele sale nu se află pe aceeași linie, deci nu poate exista niciun triunghi suplimentar. Proprietatea rămasă a regularității puternice a graficului, aceea că toate perechile de vârfuri neadiacente au același număr de vecini comuni, depinde de proprietățile setului de cap 5-dimensional. $729=3^{6}$ $112=56\times 2$ $PG(6,3)$ $PG(5,3)$

Grafice înrudite

Împreună cu graficul rook și graficul Brouwer-Hemers , graficul Games este unul dintre cele trei grafice posibile puternic regulate ai căror parametri au forma [4] . $de 3\ ori 3$ ${\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr ))$

Aceleași proprietăți care dau un grafic puternic regulat dintr-un set cap pot fi utilizate cu un set cap cu 11 puncte în , care oferă cel mai mic grafic puternic regulat cu parametrii (243,22,1,2) [5] . Acesta este contele Berlekamp-van Lint-Seidel [6] . $PG(4,3)$

Note

↑ 1 2 van Lint JH, Brouwer AE Strongly regular graphs and partial geometries // Enumeration and Design: Papers from the Conference on Combinatorics ținută la Universitatea din Waterloo, Waterloo, Ont., 14 iunie–2 iulie 1982 / David M. Jackson, Scott A. Vanstone. - Londra: Academic Press, 1984. - S. 85-122. . Vezi în special pp. 114–115.
↑ Richard A. Games. Problema de impachetare pentru geometriile proiective peste GF(3) cu dimensiunea mai mare de cinci // Journal of Combinatorial Theory . - 1983. - T. 35 , nr. 2 . — S. 126–144 . - doi : 10.1016/0097-3165(83)90002-X . . Vezi în special Tabelul VII, p. 139, rândurile și . $r=5$ $d=3$
↑ Raymond Hill. Caps and codes // Matematică discretă . - 1978. - T. 22 , nr. 2 . — p. 111–137 . - doi : 10.1016/0012-365X(78)90120-6 .
↑ Bondarenko Andriy V., Radchenko Danylo V. Pe o familie de grafice puternic regulate cu // Journal of Combinatorial Theory . - 2013. - T. 103 , nr. 4 . — S. 521–531 . - doi : 10.1016/j.jctb.2013.05.005 . $\lambda=1$
↑ Peter J. Cameron. Patrangle parțiale // The Quarterly Journal of Mathematics. - 1975. - T. 26 . — S. 61–73 . - doi : 10.1093/qmath/26.1.61 .
↑ Berlekamp ER, van Lint JH, Seidel JJ Un grafic puternic regulat derivat din codul Golay ternar perfect // A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Amsterdam: Olanda de Nord, 1973. - S. 25–30 . - doi : 10.1016/B978-0-7204-2262-7.50008-9 .