Гипотеза Эрдёша о числе различных расстояний — утверждение комбинаторной геометрии, согласно которому между различными точками на плоскости имеется не меньше, чем различных расстояний. Гипотеза сформулирована Палом Эрдёшем в 1946 году, в 2010 году Ларри Гут и объявили о возможном решении этой проблемы. См. также Граница Гута-Каца для проблемы Эрдёша о расстояниях и Решение Гута-Каца проблемы Эрдёша о различных расстояниях ., окончательное доказательство Гута и Каца было завершено в 2015 году.
Гипотеза Пусть минимальное число различных расстояний между точками на плоскости. В 1946 году Эрдёш доказал оценки для некоторой константы . Нижняя оценка получена простым доказательством, верхняя оценка получена на базе квадратной решётки и того, что число целых меньше равных сумме двух квадратов равно согласно результату Ландау — Рамануджана. Эрдёш предположил, что верхняя граница ближе к истинной величине и верно для любого .
Результаты Нижняя граница Эрдёша последовательно улучшалась: — , 1952; — , 1984; — Фан Чун, Эндре Семереди, Уильям Троттер, 1992; — Ласло Секей, 1993; — Йожеф Шоймоши, Чаба Тот, 2001; — , 2003; — Нетс Кац, Габор Тардош, 2004; — Ларри Гут, Нетс Кац, 2015.
Другие размерности Эрдёш рассмотрел также проблему для более высоких размерностей пространства. Пусть минимальное число различных расстояний для точек в евклидовом пространстве размерности . Он доказал, что и и предположил, что верхняя граница является близкой, то есть . В 2008 году Шоймоши и получили нижнюю оценку .
См. также
Граф единичных расстояний
Примечания
Литература .
. . . . .
Ссылки William Gasarch. A Webpage on The Erdos Distance Problem János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem (в блоге ) Подробное доказательство Гута — Каца в блоге Теренса Тао
Категория:Комбинаторная геометрия Категория:Доказанные математические гипотезы Категория:Пал Эрдёш