Spel graf

Ej att förväxla med turneringsdiagram .

Inom grafteorin är spelgrafen den största kända lokalt linjära, starkt regelbundna grafen . Dess parametrar som en starkt regelbunden graf är (729,112,1,20). Det betyder att den har 729 hörn och 40824 kanter (112 per hörn). Varje kant är i en unik triangel (det är en lokalt linjär graf ) och varje icke-intilliggande hörnpar har exakt 20 delade grannar. Den är uppkallad efter Richard A. Games, som föreslog dess konstruktion i ett opublicerat meddelande och skrev om relaterade konstruktioner.

Konstruktion

Konstruktionen av denna graf involverar den unika (upp till symmetri) 56-punkts cap-uppsättningen (en delmängd av punkter utan tre i linje) i $PG(5,3)$ , de fem -dimensionell projektiv geometri över ett treelementfält. Den sexdimensionella projektiva geometrin, $PG(6,3)$ , kan delas upp i ett sexdimensionellt affint utrymme $AG(6,3) )$ och en kopia av $PG(5,3)$ ( punkterna i oändligheten med avseende på det affina rummet). Spelgrafen har som hörn de 729 punkterna i det affina rummet $AG(6,3)$ . Varje linje i det affina rummet går genom tre av dessa punkter och genom en fjärde punkt i oändligheten. Grafen innehåller en triangel för varje linje med tre affinpunkter som passerar genom en punkt i capset.

Egenskaper

Flera av grafens egenskaper följer direkt av denna konstruktion. Den har $729=3^{6}$ hörn, eftersom antalet punkter i ett affint utrymme är storleken på basfältet i dimensionens potens. För varje affin punkt finns det 56 linjer genom cap-setpunkter, 56 trianglar som innehåller motsvarande vertex och $112=56\x 2$ grannar till vertexet. Och det kan inte finnas några andra trianglar än de som kommer från konstruktionen, eftersom vilken annan triangel som helst måste komma från tre olika linjer som möts i ett gemensamt plan för P G ( 6 , 3 ) $}$ , och de tre övre börvärdena för de tre linjerna skulle alla ligga på skärningspunkten för detta plan med ${\displaystyle PG(5,3)} ,$ som är en linje. Men detta skulle bryta mot den definierande egenskapen hos en capuppsättning att den inte har några tre punkter på en linje, så ingen sådan extra triangel kan existera. Den återstående egenskapen hos starkt regelbundna grafer, att alla icke-intilliggande par av punkter har samma antal delade grannar, beror på de specifika egenskaperna hos den 5-dimensionella lockuppsättningen.

Relaterade grafer

Med $3\times 3$ Rooks graf och Brouwer–Haemers-grafen är Games-grafen en av endast tre möjliga starkt regelbundna grafer vars parametrar har formen ${\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+ 3),1,n(n+1){\bigr )}$ .

Samma egenskaper som producerar en starkt regelbunden graf från en capuppsättning kan också användas med en 11-punkts capuppsättning i ${\displaystyle PG(4,3)} ,$ vilket ger en mindre starkt regelbunden graf med parametrar (243,22,1,2). Denna graf är Berlekamp–Van Lint–Seidel-grafen .