Перегляд вихідного коду сторінки Задача Конвея про 99-вершинний граф

{{Нерозв'язано|математики|Чи існує [[сильно регулярний граф]] з параметрами (99,14,1,2)?}}
[[Файл:33-duoprism_graph.svg|міні| Граф із 9 вершинами, у якому кожне ребро належить єдиному трикутнику, а будь-яке не-ребро є діагоналлю в єдиному чотирикутнику. Задача про 99-вершинний граф ставить питання існування графа з 99 вершинами з такими самими властивостями.]]
'''Зада́ча Ко́нвея про 99-верши́нний граф'''&nbsp;— нерозв'язана задача, в якій запитується, чи існує [[Граф (математика)|неорієнтований граф]] з 99 [[Вершина (теорія графів)|вершинами]], у якому кожні дві суміжні вершини мають рівно одного спільного сусіда і в якому дві несуміжні вершини мають рівно два спільних сусіди. Еквівалентно, будь-яке ребро має бути частиною єдиного трикутника, а будь-яка пара несуміжних вершин має бути на діагоналі єдиного 4-циклу. [[Джон Конвей|Джон Гортон Конвей]] оголосив про приз у 1000 доларів тому, хто розв'яже цю задачу{{R|con}}.

== Властивості ==
Якщо такий граф існує, він буде [[Локально лінійний граф|локально лінійним]] [[Сильно регулярний граф|сильно регулярним графом]] з параметрами (99,14,1,2). Перший, третій і четвертий параметри кодують твердження задачі&nbsp;— граф повинен мати 99 вершин, кожна пара суміжних вершин повинна мати 1 спільного сусіда, а будь-які несуміжні вершини повинні мати 2 спільних сусіди. Другий параметр означає, що граф є [[Регулярний граф|регулярним графом]] із 14 ребрами на вершину{{R|zd}}.

Якщо цей граф існує, він не має будь-яких симетрій порядку 11, звідки випливає, що його симетрії не можуть перевести будь-яку вершину в іншу вершину{{R|wil}}. Відомі й інші обмеження на можливі групи симетрій{{R|mm}}.

== Історія ==
Можливість існування графа з такими параметрами припускав вже 1969 року {{Нп|Норман Біггз|Норман Л. Біггз|en|Norman L. Biggs}}{{R|big}}, а як відкриту задачу існування серед інших поставив Конвей{{R|wil|guy|bn|cam}}. Конвей сам працював над цією задачою від 1975{{R|guy}}, але 2014 року оголосив приз тому, хто розв'яже задачу, як частину набору задач, представлених на конференції DIMACS з найважливіших проблем ідентифікації цілочисельних послідовностей. Цей набір задач також включає [[Трекл|гіпотезу про трекл]], найменшу відстань [[Множина Данцера|множин Данцера]] і питання, хто виграє після ходу 16 у грі в {{Не перекладено|Гра «чеканку»|«чеканку»|en|sylver coinage}}{{R|con}}.

== Пов'язані графи ==
Загальніше, існує тільки п'ять можливих комбінацій параметрів, для яких сильно регулярний граф може існувати зі властивістю, що кожне ребро належить єдиному трикутнику, а кожне неребро (відсутнє ребро двох несуміжних вершин) утворює діагональ єдиного чотирикутника. Відомо лише, що графи існують із двома з п'яти цих комбінацій. Цими двома графами є [[граф Пелі]] з дев'ятьма вершинами (граф [[3-3 дуопризма|3-3 дуопризми]]) з параметрами (9,4,1,2) та [[граф Берлекемпа — ван Лінта — Зейделя]] з параметрами (243,22,1,2). Задача про 99-вершинний граф запитує про найменшу із цих п'яти комбінацій параметрів, для яких існування графа невідоме{{R|mm}}.

== Примітки ==
{{Reflist|2|refs=<ref name=big>{{книга-ру
|ref=Biggs 
|автор =Norman L. Biggs
|mr=0327563
|страницы=111
|издательство=Cambridge University Press|место=London and New York
|серия=London Mathematical Society Lecture Note Series
|заглавие=Finite Groups of Automorphisms: Course Given at the University of Southampton, October–December 1969
|ссылка=https://books.google.com/books?id=flA4AAAAIAAJ&pg=PA111
|том=6
|год=1971}}</ref>

<ref name=bn>{{статья
|автор=Brouwer A. E., Neumaier A.
|ref=Brouwer, Neumaier
|doi=10.1007/BF02122552
|выпуск=1
|издание=Combinatorica
|mr=951993
|страницы=57–61
|заглавие=A remark on partial linear spaces of girth 5 with an application to strongly regular graphs
|том=8
|год=1988}}</ref>

<ref name=cam>{{книга-ру
|ref=Cameron
|автор=Peter J. Cameron
|isbn=0-521-45133-7
|mr=1311922
|страницы=331
|издательство=Cambridge University Press|место=Cambridge
|заглавие=Combinatorics: topics, techniques, algorithms
|ссылка=https://books.google.com/books?id=_aJIKWcifDwC&pg=PA331
|год=1994}}</ref>

<ref name=con>{{книга-ру
|автор=[[Джон Конвей|John H. Conway]]
|ref=Conway
|accessdate=2019-02-12
|издательство=[[On-Line Encyclopedia of Integer Sequences]]
|заглавие=Five $1,000 Problems (Update 2017)
|ссылка=https://oeis.org/A248380/a248380.pdf}}</ref>

<ref name=guy>{{книга-ру
|автор=[[Річард Ґай|Richard K. Guy]]
|ref=Guy
|ответственный=Kelly L. M.
|часть=Problems
|doi=10.1007/BFb0081147
|место=Berlin, New York
|mr=0388240
|страницы=233–244
|издательство=Springer-Verlag
|серия=Lecture Notes in Mathematics
|заглавие=Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974
|том=490
|год=1975}}. See problem 7 (J. J. Seidel), pp. 237—238.</ref>

<ref name=mm>{{статья
|автор=Makhnev A. A., Minakova I. M.,
|ref=Makhnev, Minakova 
|месяц=January
|год=2004
|doi=10.1515/156939204872374
|выпуск=2
|издание=Discrete Mathematics and Applications
|mr=2069991
|заглавие=On automorphisms of strongly regular graphs with parameters <math>\lambda=1</math>, <math>\mu=2</math>
|том=14}}</ref>

<ref name=wil>{{книга-ру
|автор=Wilbrink H. A.
|ref=Wilbrink
|ответственный=de Doelder P. J., de Graaf J., van Lint J. H.
|часть=On the (99,14,1,2) strongly regular graph
|date=August 1984
|страницы=342–355
|издательство=Eindhoven University of Technology
|серия=EUT Report
|заглавие=Papers dedicated to J. J. Seidel
|ссылка=https://research.tue.nl/files/2449333/256699.pdf
|том=84-WSK-03}}</ref>

<ref name=zd>{{статья
|автор=Sa'ar Zehavi, Ivo Fagundes, David de Olivera
|ref=Zehavi, Fagundes, de Olivera
|arxiv=1707.08047
|заглавие=Not Conway's 99-graph problem
|год=2017}}</ref>}}
[[Категорія:Нерозв'язані проблеми математики]]
[[Категорія:Сильно регулярні графи]]
[[Категорія:Джон Конвей]]