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

Гіпотеза Гірша спростована гіпотеза про діаметр графу багатогранника ФормулюванняДля d displaystyle d вимірного опуклого

Гіпотеза Гірша

Гіпотеза Гірша

Гіпотеза Гірша — спростована гіпотеза про діаметр графу багатогранника.

Формулювання

Для image-вимірного опуклого багатогранника з image гранями, граф, утворений його ребрами і вершинами, має діаметр не більше image.

Тобто будь-які дві вершини багатогранника можна з'єднати один з одним по ланцюжку з не більше ніж image ребер.

Історія

Гіпотезу сформулював [de] у листі до Джорджа Данціга в 1957 році. Поштовхом до цього став аналіз симплекс-методу в лінійному програмуванні.

Гірш довів гіпотезу для розмірності 3, а також у кількох часткових випадках. Відомо, що верхня оцінка субекспоненціальна за image і image.

В травні 2010 року [ru] з [en] продемонстрував контрприклад — 43-вимірний багатогранник з 86 гранями і діаметром графу, що перевищує 43. Результат представлено на конференції 100 років у Сіетлі: математики [en] та Ґрюнбаум і з'явився в Анналах математики. Контрприклад не має прямих наслідків для аналізу симплекс-методу, оскільки не виключає можливості більшої, але все ж лінійної чи поліноміальної кількості кроків.

Існують різні еквівалентні формулювання задачі, такі як гіпотеза про d-степінь, яка стверджує, що діаметр будь-якого 2d-фасетового багатогранника в d-вимірному евклідовому просторі не більший від d; контрприклад Леала також спростовує цю гіпотезу.

Питання про існування лінійної або поліноміальної оцінки залишається відкритим.

Примітки

  1. Santos, (2011).
  2. Kalai, (2010).
  3. , Gaussianos, 24 травня 2010, архів оригіналу за 3 березня 2016, процитовано 14 листопада 2020
  4. Santos, (2011)
  5. Ziegler, (1994), p. 84.
  6. Klee та Walkup, (1967).

Література

  • Dantzig, George B. (1963), Linear Programming and Extensions, Princeton Univ. Press. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
  • Kalai, Gil (10 травня 2010). . Архів оригіналу за 28 жовтня 2019. Процитовано 11 травня 2010.
  • Kalai, Gil; Kleitman, Daniel J. (1992), A quasi-polynomial bound for the diameter of graphs of polyhedra, Bulletin of the American Mathematical Society, 26 (2): 315—316, arXiv:math/9204233, doi:10.1090/S0273-0979-1992-00285-9, MR 1130448.
  • Klee, Victor; Walkup, David W. (1967), The d-step conjecture for polyhedra of dimension d < 6, , 133: 53—78, doi:10.1007/BF02395040, MR 0206823.
  • Miranda, Eva (2012), (PDF), (Newsletter of the European Mathematical Society) (86): 31—36, архів оригіналу (PDF) за 20 березня 2014, процитовано 14 листопада 2020.
  • Naddef, Denis (1989), The Hirsch conjecture is true for (0,1)-polytopes, , 45 (1): 109—110, doi:10.1007/BF01589099, MR 1017214.
  • Santos, Francisco (2011), A counterexample to the Hirsch conjecture, Annals of Mathematics, Princeton University and Institute for Advanced Study, 176 (1): 383—412, arXiv:1006.2814, doi:10.4007/annals.2012.176.1.7, MR 2925387
  • Ziegler, Günter M. (1994), The Hirsch Conjecture, Lectures on Polytopes, Graduate Texts in Mathematics, т. 152, Springer-Verlag, с. 83—93.

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

Gipoteza Girsha sprostovana gipoteza pro diametr grafu bagatogrannika FormulyuvannyaDlya d displaystyle d vimirnogo opuklogo bagatogrannika z n displaystyle n granyami graf utvorenij jogo rebrami i vershinami maye diametr ne bilshe n d displaystyle n d Tobto bud yaki dvi vershini bagatogrannika mozhna z yednati odin z odnim po lancyuzhku z ne bilshe nizh n d displaystyle n d reber IstoriyaGipotezu sformulyuvav de u listi do Dzhordzha Danciga v 1957 roci Poshtovhom do cogo stav analiz simpleks metodu v linijnomu programuvanni Girsh doviv gipotezu dlya rozmirnosti 3 a takozh u kilkoh chastkovih vipadkah Vidomo sho verhnya ocinka subeksponencialna za n displaystyle n i d displaystyle d V travni 2010 roku ru z en prodemonstruvav kontrpriklad 43 vimirnij bagatogrannik z 86 granyami i diametrom grafu sho perevishuye 43 Rezultat predstavleno na konferenciyi 100 rokiv u Sietli matematiki en ta Gryunbaum i z yavivsya v Annalah matematiki Kontrpriklad ne maye pryamih naslidkiv dlya analizu simpleks metodu oskilki ne viklyuchaye mozhlivosti bilshoyi ale vse zh linijnoyi chi polinomialnoyi kilkosti krokiv Isnuyut rizni ekvivalentni formulyuvannya zadachi taki yak gipoteza pro d stepin yaka stverdzhuye sho diametr bud yakogo 2d fasetovogo bagatogrannika v d vimirnomu evklidovomu prostori ne bilshij vid d kontrpriklad Leala takozh sprostovuye cyu gipotezu Pitannya pro isnuvannya linijnoyi abo polinomialnoyi ocinki zalishayetsya vidkritim PrimitkiSantos 2011 Kalai 2010 Gaussianos 24 travnya 2010 arhiv originalu za 3 bereznya 2016 procitovano 14 listopada 2020 Santos 2011 Ziegler 1994 p 84 Klee ta Walkup 1967 LiteraturaDantzig George B 1963 Linear Programming and Extensions Princeton Univ Press Reprinted in the series Princeton Landmarks in Mathematics Princeton University Press 1998 Kalai Gil 10 travnya 2010 Arhiv originalu za 28 zhovtnya 2019 Procitovano 11 travnya 2010 Kalai Gil Kleitman Daniel J 1992 A quasi polynomial bound for the diameter of graphs of polyhedra Bulletin of the American Mathematical Society 26 2 315 316 arXiv math 9204233 doi 10 1090 S0273 0979 1992 00285 9 MR 1130448 Klee Victor Walkup David W 1967 The d step conjecture for polyhedra of dimension d lt 6 133 53 78 doi 10 1007 BF02395040 MR 0206823 Miranda Eva 2012 PDF Newsletter of the European Mathematical Society 86 31 36 arhiv originalu PDF za 20 bereznya 2014 procitovano 14 listopada 2020 Naddef Denis 1989 The Hirsch conjecture is true for 0 1 polytopes 45 1 109 110 doi 10 1007 BF01589099 MR 1017214 Santos Francisco 2011 A counterexample to the Hirsch conjecture Annals of Mathematics Princeton University and Institute for Advanced Study 176 1 383 412 arXiv 1006 2814 doi 10 4007 annals 2012 176 1 7 MR 2925387 Ziegler Gunter M 1994 The Hirsch Conjecture Lectures on Polytopes Graduate Texts in Mathematics t 152 Springer Verlag s 83 93

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