Počet her

Herní graf je největší známý lokálně lineární silně pravidelný graf . Jeho parametry jako silně regulárního grafu jsou (729,112,1,20). To znamená, že graf má 729 vrcholů a 40824 hran (112 hran na vrchol). Každá hrana je v jednom trojúhelníku (toto je lokálně spojnicový graf ) a každá nesousedící dvojice vrcholů má přesně 20 společných sousedů. Graf je pojmenován po Richardu A. Games, který navrhl jeho konstrukci v nepublikované korespondenci [1] a psal o souvisejících konstrukcích [2] .

Budova

Konstrukce tohoto grafu využívá jedinečnou (až symetrii) 56bodovou cap set ( anglicky cap set , podmnožiny bodů, z nichž žádné tři neleží na stejné čáře) v pětirozměrné projektivní geometrii přes tři -pole prvku [3] . Šestirozměrnou projektivní geometrii, lze rozložit na šestirozměrný afinní prostor a kopii ( body v nekonečnu dané afinním prostorem). Herní graf má 729 bodů afinního prostoru jako vrcholy . Každá přímka v afinním prostoru prochází třemi z těchto bodů a čtvrtým bodem v nekonečnu. Graf obsahuje trojúhelník pro libovolnou přímku tří afinních bodů, která prochází bodem množiny čepiček [1] . $PG(5,3)$ $PG(6,3)$ $AG(6,3)$ $PG(5,3)$ $AG(6,3)$

Vlastnosti

Některé vlastnosti grafu vyplývají bezprostředně z konstrukce. Graf má vrcholy, protože počet bodů v afinním prostoru se rovná velikosti základního pole k mocnině dimenze. Pro každý afinní bod existuje 56 čar procházejících body množiny čepiček, 56 trojúhelníků obsahujících odpovídající vrchol a sousedy vrcholu. A nemohou existovat žádné jiné trojúhelníky než ty, které byly získány během konstrukce, protože jakýkoli jiný trojúhelník by byl získán ze tří různých čar protínajících se ve společné rovině a tři body horní sady tří čar by ležely v průsečíku této roviny s , což dává čáru. To by však porušilo vlastnost cap-set, že žádné tři z jejích bodů neleží na stejné přímce, takže žádný další trojúhelník nemůže existovat. Zbývající vlastnost silné pravidelnosti grafu, že všechny nesousedící dvojice vrcholů mají stejný počet společných sousedů, závisí na vlastnostech 5-rozměrné cap-set. $729=3^{6}$ $112=56\times 2$ $PG(6,3)$ $PG(5,3)$

Související grafy

Spolu s věžovým grafem a Brouwer-Hemersovým grafem je graf Games jedním ze tří možných silně regulárních grafů, jejichž parametry mají tvar [4] . $3\krát 3$ ${\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )))$

Stejné vlastnosti, které dávají silně pravidelný graf z cap-setu, lze použít s 11-bodovým cap-setem v , který dává nejmenší silně regulární graf s parametry (243,22,1,2) [5] . Toto je hrabě hrabě Berlekamp-van Lint-Seidel [6] . $PG(4,3)$

Poznámky

↑ 1 2 van Lint JH, Brouwer AE Silně pravidelné grafy a částečné geometrie // Enumeration and Design: Příspěvky z konference o kombinatorice konané na University of Waterloo, Waterloo, Ont., 14. června–2. července 1982 / David M. Jackson, Scott A. Vanstone. - London: Academic Press, 1984. - S. 85-122. . Viz zejména s. 114–115.
↑ Richard A. Hry. Řešení problémů pro projektivní geometrie nad GF(3) s rozměrem větším než pět // Journal of Combinatorial Theory . - 1983. - T. 35 , no. 2 . — S. 126–144 . - doi : 10.1016/0097-3165(83)90002-X . . Viz zejména tabulka VII, str. 139, řádky a . $r=5$ $d=3$
↑ Raymond Hill. Caps and codes // Diskrétní matematika . - 1978. - T. 22 , no. 2 . — s. 111–137 . - doi : 10.1016/0012-365X(78)90120-6 .
↑ Bondarenko Andriy V., Radchenko Danylo V. O rodině silně regulárních grafů s // Journal of Combinatorial Theory . - 2013. - T. 103 , č.p. 4 . — S. 521–531 . - doi : 10.1016/j.jctb.2013.05.005 . $\lambda=1$
↑ Peter J. Cameron. Částečné čtyřúhelníky // 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 Silně pravidelný graf odvozený z dokonalého ternárního Golayova kódu // Přehled kombinatorické teorie (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Amsterdam: North-Holland, 1973. - S. 25–30 . - doi : 10.1016/B978-0-7204-2262-7.50008-9 .