Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Нерозв язана проблема математики Чи існує сильно регулярний граф з параметрами 99 14 1 2 більше нерозв язаних проблем ма

Задача Конвея про 99-вершинний граф

Задача Конвея про 99-вершинний граф
image Нерозв'язана проблема математики:
Чи існує сильно регулярний граф з параметрами (99,14,1,2)?
(більше нерозв'язаних проблем математики)

Зада́ча Ко́нвея про 99-верши́нний граф — нерозв'язана задача, в якій запитується, чи існує неорієнтований граф з 99 вершинами, у якому кожні дві суміжні вершини мають рівно одного спільного сусіда і в якому дві несуміжні вершини мають рівно два спільних сусіди. Еквівалентно, будь-яке ребро має бути частиною єдиного трикутника, а будь-яка пара несуміжних вершин має бути на діагоналі єдиного 4-циклу. Джон Гортон Конвей оголосив про приз у 1000 доларів тому, хто розв'яже цю задачу.

image
Граф із 9 вершинами, у якому кожне ребро належить єдиному трикутнику, а будь-яке не-ребро є діагоналлю в єдиному чотирикутнику. Задача про 99-вершинний граф ставить питання існування графа з 99 вершинами з такими самими властивостями.

Властивості

Якщо такий граф існує, він буде локально лінійним сильно регулярним графом з параметрами (99,14,1,2). Перший, третій і четвертий параметри кодують твердження задачі — граф повинен мати 99 вершин, кожна пара суміжних вершин повинна мати 1 спільного сусіда, а будь-які несуміжні вершини повинні мати 2 спільних сусіди. Другий параметр означає, що граф є регулярним графом із 14 ребрами на вершину.

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

Історія

Можливість існування графа з такими параметрами припускав вже 1969 року [en], а як відкриту задачу існування серед інших поставив Конвей. Конвей сам працював над цією задачою від 1975, але 2014 року оголосив приз тому, хто розв'яже задачу, як частину набору задач, представлених на конференції DIMACS з найважливіших проблем ідентифікації цілочисельних послідовностей. Цей набір задач також включає гіпотезу про трекл, найменшу відстань множин Данцера і питання, хто виграє після ходу 16 у грі в [en].

Пов'язані графи

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

Примітки

  1. John H. Conway. Five $1,000 Problems (Update 2017). — .
  2. Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Not Conway's 99-graph problem. — 2017. — arXiv:1707.08047.
  3. Wilbrink H. A. On the (99,14,1,2) strongly regular graph // Papers dedicated to J. J. Seidel / de Doelder P. J., de Graaf J., van Lint J. H.. — Eindhoven University of Technology. — Т. 84-WSK-03. — С. 342–355. — (EUT Report).
  4. Makhnev A. A., Minakova I. M.,. On automorphisms of strongly regular graphs with parameters image, image // Discrete Mathematics and Applications. — 2004. — Т. 14, вип. 2 (січень). — DOI:10.1515/156939204872374.
  5. Norman L. Biggs. Finite Groups of Automorphisms: Course Given at the University of Southampton, October–December 1969. — London and New York : Cambridge University Press, 1971. — Т. 6. — С. 111. — (London Mathematical Society Lecture Note Series).
  6. Richard K. Guy. Problems // Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974 / Kelly L. M.. — Berlin, New York : Springer-Verlag, 1975. — Т. 490. — С. 233–244. — (Lecture Notes in Mathematics). — DOI:10.1007/BFb0081147.. See problem 7 (J. J. Seidel), pp. 237—238.
  7. Brouwer A. E., Neumaier A. A remark on partial linear spaces of girth 5 with an application to strongly regular graphs // Combinatorica. — 1988. — Т. 8, вип. 1. — С. 57–61. — DOI:10.1007/BF02122552.
  8. Peter J. Cameron. Combinatorics: topics, techniques, algorithms. — Cambridge : Cambridge University Press, 1994. — С. 331. — .

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Nerozv yazana problema matematiki Chi isnuye silno regulyarnij graf z parametrami 99 14 1 2 bilshe nerozv yazanih problem matematiki Zada cha Ko nveya pro 99 vershi nnij graf nerozv yazana zadacha v yakij zapituyetsya chi isnuye neoriyentovanij graf z 99 vershinami u yakomu kozhni dvi sumizhni vershini mayut rivno odnogo spilnogo susida i v yakomu dvi nesumizhni vershini mayut rivno dva spilnih susidi Ekvivalentno bud yake rebro maye buti chastinoyu yedinogo trikutnika a bud yaka para nesumizhnih vershin maye buti na diagonali yedinogo 4 ciklu Dzhon Gorton Konvej ogolosiv pro priz u 1000 dolariv tomu hto rozv yazhe cyu zadachu Graf iz 9 vershinami u yakomu kozhne rebro nalezhit yedinomu trikutniku a bud yake ne rebro ye diagonallyu v yedinomu chotirikutniku Zadacha pro 99 vershinnij graf stavit pitannya isnuvannya grafa z 99 vershinami z takimi samimi vlastivostyami VlastivostiYaksho takij graf isnuye vin bude lokalno linijnim silno regulyarnim grafom z parametrami 99 14 1 2 Pershij tretij i chetvertij parametri koduyut tverdzhennya zadachi graf povinen mati 99 vershin kozhna para sumizhnih vershin povinna mati 1 spilnogo susida a bud yaki nesumizhni vershini povinni mati 2 spilnih susidi Drugij parametr oznachaye sho graf ye regulyarnim grafom iz 14 rebrami na vershinu Yaksho cej graf isnuye vin ne maye bud yakih simetrij poryadku 11 zvidki viplivaye sho jogo simetriyi ne mozhut perevesti bud yaku vershinu v inshu vershinu Vidomi j inshi obmezhennya na mozhlivi grupi simetrij IstoriyaMozhlivist isnuvannya grafa z takimi parametrami pripuskav vzhe 1969 roku en a yak vidkritu zadachu isnuvannya sered inshih postaviv Konvej Konvej sam pracyuvav nad ciyeyu zadachoyu vid 1975 ale 2014 roku ogolosiv priz tomu hto rozv yazhe zadachu yak chastinu naboru zadach predstavlenih na konferenciyi DIMACS z najvazhlivishih problem identifikaciyi cilochiselnih poslidovnostej Cej nabir zadach takozh vklyuchaye gipotezu pro trekl najmenshu vidstan mnozhin Dancera i pitannya hto vigraye pislya hodu 16 u gri v en Pov yazani grafiZagalnishe isnuye tilki p yat mozhlivih kombinacij parametriv dlya yakih silno regulyarnij graf mozhe isnuvati zi vlastivistyu sho kozhne rebro nalezhit yedinomu trikutniku a kozhne nerebro vidsutnye rebro dvoh nesumizhnih vershin utvoryuye diagonal yedinogo chotirikutnika Vidomo lishe sho grafi isnuyut iz dvoma z p yati cih kombinacij Cimi dvoma grafami ye graf Peli z dev yatma vershinami graf z parametrami 9 4 1 2 ta graf Berlekempa van Linta Zejdelya z parametrami 243 22 1 2 Zadacha pro 99 vershinnij graf zapituye pro najmenshu iz cih p yati kombinacij parametriv dlya yakih isnuvannya grafa nevidome PrimitkiJohn H Conway Five 1 000 Problems Update 2017 Sa ar Zehavi Ivo Fagundes David de Olivera Not Conway s 99 graph problem 2017 arXiv 1707 08047 Wilbrink H A On the 99 14 1 2 strongly regular graph Papers dedicated to J J Seidel de Doelder P J de Graaf J van Lint J H Eindhoven University of Technology T 84 WSK 03 S 342 355 EUT Report Makhnev A A Minakova I M On automorphisms of strongly regular graphs with parameters l 1 displaystyle lambda 1 m 2 displaystyle mu 2 Discrete Mathematics and Applications 2004 T 14 vip 2 sichen DOI 10 1515 156939204872374 Norman L Biggs Finite Groups of Automorphisms Course Given at the University of Southampton October December 1969 London and New York Cambridge University Press 1971 T 6 S 111 London Mathematical Society Lecture Note Series Richard K Guy Problems Proceedings of a Conference held at Michigan State University East Lansing Mich June 17 19 1974 Kelly L M Berlin New York Springer Verlag 1975 T 490 S 233 244 Lecture Notes in Mathematics DOI 10 1007 BFb0081147 See problem 7 J J Seidel pp 237 238 Brouwer A E Neumaier A A remark on partial linear spaces of girth 5 with an application to strongly regular graphs Combinatorica 1988 T 8 vip 1 S 57 61 DOI 10 1007 BF02122552 Peter J Cameron Combinatorics topics techniques algorithms Cambridge Cambridge University Press 1994 S 331 ISBN 0 521 45133 7

Дата публікації:
Топ