Гипотеза Хирша: различия между версиями
Перейти к навигации
Перейти к поиску
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Tosha (обсуждение | вклад) Нет описания правки |
Tosha (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
*В мае 2010 года {{iw|Леал, Франсиско Сантос|Леал|en|Francisco Santos Leal}}, предявил контрпример — 43-мерный многогранник с 86 гранями и диметром графа превышающий 43. |
*В мае 2010 года {{iw|Леал, Франсиско Сантос|Леал|en|Francisco Santos Leal}}, предявил контрпример — 43-мерный многогранник с 86 гранями и диметром графа превышающий 43. |
||
**Вопрос о существовании линейной или полиномиальной оценки остаётся открытым. |
**Вопрос о существовании линейной или полиномиальной оценки остаётся открытым. |
||
==Литература== |
|||
*{{citation|last=Dantzig|first=George B.|authorlink=George B. Dantzig|title=Linear Programming and Extensions|publisher=Princeton Univ. Press|year=1963}}. Reprinted in the series ''Princeton Landmarks in Mathematics'', Princeton University Press, 1998. |
|||
*{{cite web|url=http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/|title=Francisco Santos Disproves the Hirsch Conjecture|last=Kalai|first=Gil|accessdate=11 May 2010|date=10 May 2010|ref=harv}} |
|||
*{{citation|last1=Kalai|first1=Gil|authorlink1=Gil Kalai|last2=Kleitman|first2=Daniel J.|authorlink2=Daniel Kleitman|title=A quasi-polynomial bound for the diameter of graphs of polyhedra|journal=[[Bulletin of the American Mathematical Society]]|volume=26|issue=2|year=1992|pages=315–316|arxiv=math/9204233 |mr= 1130448 |doi=10.1090/S0273-0979-1992-00285-9}}. |
|||
*{{citation|last1=Klee|first1=Victor|authorlink1=Victor Klee|last2=Walkup|first2=David W.|title=The ''d''-step conjecture for polyhedra of dimension ''d'' < 6|journal=[[Acta Mathematica]]|volume=133|year=1967|pages=53–78|mr=0206823 |doi=10.1007/BF02395040}}. |
|||
*{{citation|last=Miranda|first=Eva|title=The Hirsch conjecture has been disproved: An interview with Francisco Santos|journal=[[Newsletter of the European Mathematical Society]]|issue=86|year=2012|pages=31–36|url=http://www.ems-ph.org/journals/newsletter/pdf/2012-12-86.pdf}}. |
|||
*{{citation|last=Naddef|first=Denis|title=The Hirsch conjecture is true for (0,1)-polytopes|journal=[[Mathematical Programming]]|volume=45|issue=1|year=1989|pages=109–110|mr=1017214 |doi=10.1007/BF01589099}}. |
|||
*{{citation|last=Santos|first=Francisco|authorlink= Francisco Santos Leal |
|||
|title=A counterexample to the Hirsch conjecture |
|||
|journal=[[Annals of Mathematics]] |publisher=Princeton University and Institute for Advanced Study | volume=176 | issue=1 | pages=383–412|doi=10.4007/annals.2012.176.1.7 |mr=2925387 |
|||
|year=2011|arxiv=1006.2814}} |
|||
*{{citation|last=Ziegler|first=Günter M.|authorlink=Günter M. Ziegler|contribution=The Hirsch Conjecture|title=Lectures on Polytopes|publisher=Springer-Verlag|year=1994|series=Graduate Texts in Mathematics|volume=152|pages=83–93}}. |
|||
[[Категория:Математические гипотезы]] |
[[Категория:Математические гипотезы]] |
||
Версия от 17:20, 21 июля 2016
Гипотеза Хирша — опровергнутая гипотеза о диаметре графа многогранника.
Формулировка
Для -мерного выпуклый многогранника с гранями, граф образованный его ребрами и вершинами имеет диаметр не больше .
То есть, любые две вершины многогранника можно соединенить друг с другом по цепочкой из не более чем рёбер.
История
- Гипотеза была сформулирована в письме Уоррен М. Хирша[нем.] Джордж Данцигу в 1957 году.
- Мотивация пришла из анализа симплекс-метода в линейном программировании.
- Хирш доказал гипотезу в размерности 3, а также в нескольких частных случаях.
- Известно, что верхняя оценка субэкспоненциальна по и
- В мае 2010 года Леал[англ.], предявил контрпример — 43-мерный многогранник с 86 гранями и диметром графа превышающий 43.
- Вопрос о существовании линейной или полиномиальной оценки остаётся открытым.
Литература
- 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 Francisco Santos Disproves the Hirsch Conjecture (10 мая 2010). Дата обращения: 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", Acta Mathematica, 133: 53—78, doi:10.1007/BF02395040, MR 0206823.
- Miranda, Eva (2012), "The Hirsch conjecture has been disproved: An interview with Francisco Santos" (PDF), Newsletter of the European Mathematical Society (86): 31—36.
- Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes", Mathematical Programming, 45 (1): 109—110, doi:10.1007/BF01589099, MR 1017214.
- Santos, Francisco (2011), "A counterexample to the Hirsch conjecture", Annals of Mathematics, 176 (1), Princeton University and Institute for Advanced Study: 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, vol. 152, Springer-Verlag, pp. 83—93.
 | Для улучшения этой статьи желательно:
|