Ойындар графигі - Games graph

Графикалық теорияда Ойындар графигі ең танымал болып табылады жергілікті сызықтық тұрақты граф. Оның параметрлері өте тұрақты график ретінде (729,112,1,20). Бұл оның 729 төбесі және 40824 шеті бар екенін білдіреді (бір шыңға 112). Әрбір шеті ерекше үшбұрышта орналасқан (ол а жергілікті сызықтық график ) және әрбір жақын емес шыңдардың жұптары тура 20 ортақ көршісіне ие. Бұл оның құрылуын жарияланбаған коммуникацияда ұсынған Ричард А. Ойынның есімімен аталады[1] байланысты конструкциялар туралы жазды.[2]

Құрылыс

Бұл графиктің құрылысы бірегей (симметрияға дейін) 56 нүктеден тұрады қақпақ орнатылды (жолдың үшеуі жоқ нүктелер жиынтығы) in , бес өлшемді проективті геометрия үш элементті өріс үстінде.[3] Алты өлшемді проективті геометрия, , алты өлшемді бөлуге болады аффиналық кеңістік және көшірмесі ( шексіздікке бағытталған аффиналық кеңістікке қатысты). Ойындар графигінде аффиналық кеңістіктің 729 нүктесі бар . Аффиналық кеңістіктегі әрбір сызық осы үш нүктеден, ал шексіздіктегі төртінші нүктеден өтеді. Графикте қақпақ жиынының нүктесінен өтетін үш аффиндік нүктенің әрбір сызығы үшін үшбұрыш бар.[1]

Қасиеттері

Графиктің бірнеше қасиеттері осы конструкциядан бірден шығады. Онда бар төбелер, өйткені аффиналық кеңістіктегі нүктелер саны өлшем өрісіне дейінгі негізгі өрістің өлшемі болып табылады. Әр аффиндік нүкте үшін қақпақ жиынтық нүктелері арқылы 56 сызық, сәйкес шыңдары бар 56 үшбұрыш және шыңның көршілері. Құрылыс кезіндегі үшбұрыштан басқа үшбұрыш болуы мүмкін емес, өйткені кез-келген басқа үшбұрыш жалпы жазықтықта кездесетін үш түрлі түзуден шығуы керек еді. , және үш түзудің үш қақпақ жиынтық нүктелері барлығы осы жазықтықтың қиылысында орналасады , бұл сызық. Бірақ бұл қақпақ жиынтығының анықтайтын қасиетін бұзады, оның түзуде үш нүктесі болмайды, сондықтан мұндай қосымша үшбұрыш болмайды. Күшті тұрақты графиктердің қалған қасиеті, көршілес емес жұптардың барлық жұптарының көршілерінің саны бірдей болатындығы, 5 өлшемді қақпақ жиынының нақты қасиеттеріне байланысты.

Байланысты графиктер

Бірге Рук графигі және Brouwer – Haemers графигі, ойындар графигі - бұл параметрлері бар үш тұрақты графиктің бірі .[4]

Қақпақтар жиынтығынан қатты тұрақты графикті шығаратын дәл осындай қасиеттерді 11 нүктелі қақпақпен орнатуға болады , (243,22,1,2) параметрлері бар кішігірім тұрақты графикті шығарады.[5]Бұл график Берлекамп-ван Линт-Зайдель графигі.[6]

Әдебиеттер тізімі

  1. ^ а б ван Линт, Дж. Х.; Brouwer, A. E. (1984), «Қатты тұрақты графиктер және бөлшек геометриялар» (PDF), жылы Джексон, Дэвид М.; Ванстоун, Скотт А. (ред.), Санақ және дизайн: Ватерлоо университетінде өткен комбинаторика бойынша конференция материалдары, Ватерлоо, Онт., 14 маусым - 2 шілде 1982 ж., Лондон: Academic Press, 85–122 б., МЫРЗА  0782310. 114–115 беттерді қараңыз.
  2. ^ Ойындар, Ричард А. (1983), «GF (3) өлшемі бестен жоғары проективті геометрияға арналған орау мәселесі», Комбинаторлық теория журналы, А сериясы, 35 (2): 126–144, дои:10.1016 / 0097-3165 (83) 90002-X, МЫРЗА  0712100. Әсіресе VII кестені қараңыз, б. 139, кіру және .
  3. ^ Хилл, Раймонд (1978), «Қақпақтар мен кодтар», Дискретті математика, 22 (2): 111–137, дои:10.1016 / 0012-365X (78) 90120-6, МЫРЗА  0523299
  4. ^ Бондаренко, Андрий В .; Радченко, Данило В. (2013), «тұрақты графиктердің отбасы туралы ", Комбинаторлық теория журналы, B сериясы, 103 (4): 521–531, arXiv:1201.0383, дои:10.1016 / j.jctb.2013.05.005, МЫРЗА  3071380
  5. ^ Кэмерон, Питер Дж. (1975), «Жартылай төртбұрыштар», Математика тоқсан сайынғы журнал, Екінші серия, 26: 61–73, дои:10.1093 / qmath / 26.1.61, МЫРЗА  0366702
  6. ^ Берлекамп, Э.Р.; ван Линт, Дж. Х.; Зайдель, Дж. Дж. (1973), «Мықты үштік Голай кодынан алынған тұрақты график», Комбинаторлық теорияны зерттеу (Proc. Internat. Sympos., Колорадо штаты университеті, Форт Коллинз, Кол., 1971), Амстердам: Солтүстік-Голландия: 25-30, дои:10.1016 / B978-0-7204-2262-7.50008-9, ISBN  9780720422627, МЫРЗА  0364015