Гипотеза Харборта - Википедия - Harborths conjecture

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Имеет ли каждый планарный граф интегральное вложение Фари?
(больше нерешенных задач по математике)

В математика, Гипотеза Харборта заявляет, что каждый планарный граф имеет плоский Рисование в котором каждое ребро прямое сегмент из целое число длина.[1][2][3] Эта гипотеза названа в честь Хайко Харборт, и (если это правда) усилит Теорема Фари о существовании прямолинейных чертежей для каждого плоского графа. По этой причине чертеж с целочисленной длиной ребра также известен как интегральное вложение Фари.[4] Несмотря на многочисленные последующие исследования, гипотеза Харборта остается нерешенной.[5]

Интегральное вложение Фари октаэдрический граф K2,2,2

Специальные классы графов

Хотя известно, что гипотеза Харборта верна не для всех плоских графов, она была доказана для нескольких специальных видов плоских графов.

Один класс графов, имеющих интегральные вложения Фари, - это графы, которые можно свести к пустой график последовательностью операций двух типов:

  • Удаление вершины степени не выше двух.
  • Замена вершины третьей степени ребром между двумя соседями. (Если такое ребро уже существует, вершину третьей степени можно удалить, не добавляя еще одно ребро между ее соседями.)

Для такого графа рациональное вложение Фари может быть построено постепенно, обращая этот процесс удаления, используя тот факт, что множество точек, находящихся на рациональном расстоянии от двух заданных точек, плотно в плоскости, и что если три точки имеют рациональные расстояние между одной парой и расстояние квадратного корня из рационального между двумя другими парами, то точки на рациональных расстояниях от всех трех снова оказываются плотными на плоскости.[6][7] Расстояния в таком вложении можно преобразовать в целые числа путем масштабирования вложения с помощью соответствующего коэффициента. На основе этой конструкции графы, известные как интегральные вложения Фари, включают двудольный планарные графы, (2,1) -редкий планарные графы, плоские графы ширина дерева не более 3, и графы степени не более 4, которые либо содержат алмаз подграф или нет 4-гранное соединение.[4][8][9]

В частности, графы, которые могут быть сведены к пустому графу путем удаления только вершин степени не выше двух ( 2-вырожденный планарные графы) включают как внешнепланарные графы и последовательно-параллельные графы. Однако для внешнепланарных графов возможно более прямое построение интегральных вложений Фари, основанное на существовании бесконечных подмножеств единичный круг в котором все расстояния рациональны.[10]

Кроме того, интегральные вложения Фари известны для каждого из пяти Платоновы тела.[3]

Связанные предположения

Более сильная версия гипотезы Харборта, сформулированная Клебер (2008), спрашивает, есть ли у каждого плоского графа планарный рисунок, на котором координаты вершин, а также длины ребер являются целыми числами.[11] Известно, что это верно для 3-регулярные графы,[12] для графов с максимальной степенью 4, но не 4-регулярных,[13] и для планарные 3-х деревья.[13]

Еще одна нерешенная проблема в геометрии. Проблема Эрдеша – Улама, касается существования плотные подмножества плоскости, в которой все расстояния равны рациональное число. Если бы такое подмножество существовало, оно бы сформировало универсальный набор точек который можно использовать для рисования всех плоских графов с рациональными длинами ребер (и, следовательно, после их соответствующего масштабирования с целыми длинами ребер). Однако Улам предположил, что плотных множеств с рациональным расстоянием не существует.[14]Согласно Теорема Эрдеша – Эннинга, бесконечные неколлинеарные наборы точек, где все расстояния являются целыми числами, существовать не могут. Это не исключает существования множеств со всеми рациональными расстояниями, но подразумевает, что в любом таком наборе знаменатели рациональных расстояний должны расти произвольно большими.

Смотрите также

Рекомендации

  1. ^ Хартсфилд, Нора; Рингель, Герхард (2013), Жемчуг в теории графов: всестороннее введение, Dover Книги по математике, Courier Dover Publications, п. 247, ISBN  9780486315522, МИСТЕР  2047103. Перепечатка издания Academic Press 1994 года; такое же название дается гипотезе в оригинальной редакции 1990 года.
  2. ^ Кемниц, Арнфрид; Харборт, Хейко (2001), «Плоские интегральные чертежи плоских графов», Дискретная математика, Теория графов (Казимеж Дольны, 1997), 236 (1–3): 191–195, Дои:10.1016 / S0012-365X (00) 00442-8, МИСТЕР  1830610. Кемниц и Харборт приписывают первоначальную публикацию этой гипотезы Harborth et al. (1987).
  3. ^ а б Харборт, Хейко; Кемниц, Арнфрид; Мёллер, Мейнхард; Зюссенбах, Андреас (1987), "Ganzzahlige planare Darstellungen der platonischen Körper", Elemente der Mathematik, 42 (5): 118–122, МИСТЕР  0905393.
  4. ^ а б Сан, Тимоти (2013), «Рисование некоторых 4-регулярных плоских графов с целыми длинами ребер», Proc. Канадская конференция по вычислительной геометрии (CCCG 2013) (PDF).
  5. ^ Брасс, Питер; Мозер, Уильям О. Дж .; Пах, Янош (2005), Проблемы исследования дискретной геометрии, Springer, стр. 250, ISBN  9780387299297, МИСТЕР  2163782.
  6. ^ Альмеринг, Дж. Х. Дж. (1963), «Рациональные четырехугольники», Indagationes Mathematicae, 25: 192–199, Дои:10.1016 / S1385-7258 (63) 50020-1, МИСТЕР  0147447.
  7. ^ Берри, Т. Г. (1992), «Точки на рациональном расстоянии от вершин треугольника», Acta Arithmetica, 62 (4): 391–398, Дои:10.4064 / aa-62-4-391-398, МИСТЕР  1199630.
  8. ^ Бидль, Тереза (2011), «Рисование некоторых плоских графов с целыми длинами ребер», Proc. Канадская конференция по вычислительной геометрии (CCCG 2011) (PDF).
  9. ^ Сан, Тимоти (2011), "Теоретико-жесткие конструкции интегральных вложений Фари", Proc. Канадская конференция по вычислительной геометрии (CCCG 2011) (PDF).
  10. ^ Клее, Виктор; Вагон, Стан (1991), «Проблема 10: есть ли на плоскости плотное рациональное множество?», Старые и новые нерешенные проблемы геометрии плоскости и теории чисел, Математические экспозиции Дольчиани, 11, Cambridge University Press, стр. 132–135, ISBN  978-0-88385-315-3, МИСТЕР  1133201.
  11. ^ Клебер, Майкл (2008), «Встреча в далекой точке», Математический интеллигент, 1: 50–53, Дои:10.1007 / BF02985756.
  12. ^ Гилен, Джим; Го, Анжи; Маккиннон, Дэвид (2008), "Прямые вложения кубических плоских графов с целыми длинами ребер", Журнал теории графов, 58 (3): 270–274, Дои:10.1002 / jgt.20304, МИСТЕР  2419522.
  13. ^ а б Бенедиктович, Владимир И. (2013), «О рациональной аппроксимации геометрического графа», Дискретная математика, 313 (20): 2061–2064, Дои:10.1016 / j.disc.2013.06.018, МИСТЕР  3084247.
  14. ^ Солимоши, Йожеф; де Зеув, Франк (2010), «По вопросу об Эрдёше и Улама», Дискретная и вычислительная геометрия, 43 (2): 393–401, arXiv:0806.3095, Дои:10.1007 / s00454-009-9179-х, МИСТЕР  2579704.