Список математических утверждений и объектов, названных в честь Пала Эрдёша

В данном списке приводятся математические утверждения и объекты, названные именем венгерского математика Пала Эрдёша.

Теоремы

• Теорема де Брёйна — Эрдёша (теория графов) (1951, совместно с Николасом де Брёйном) — всякий ${\displaystyle k}$-хроматический граф содержит ${\displaystyle k}$-хроматический подграф с конечным числом вершин.
• Теорема де Брёйна — Эрдёша и двойственная ей теорема Эрдёша — де Брёйна (1948, совместно с Николасом де Брёйном) — проективные аналоги теоремы Сильвестра: утверждения о нижней оценке количества прямых, которые можно провести через заданный набор точек.
• Теорема Эрдёша — Эннинга (1945, совместно с Норманом Эннингом^[англ.]) — утверждение о том, что бесконечное множество точек на плоскости может иметь целые расстояния между точками множества только в том случае, когда все точки лежат на одной прямой^[1].
• Теорема Эрдёша — Бека^[англ.] (сформулирована Эрдёшем в 1978 году как гипотеза, доказана в 1984 году Йожефом Беком (венг. Beck József)) — утверждение в дискретной геометрии.
• Теорема Эрдёша — Душника — Миллера
• Теорема Эрдёша — Галлаи — (1960^[2], совместно с Тибором Галлаи^[венг.]) — теоретико-графовое утверждение, задающее условие сопоставимости конечной последовательности натуральных чисел последовательности степеней вершин некоторого графа.
• Теорема Эрдёша — Ко — Радо^[англ.].
• Теорема Эрдёша — Сёкефальви-Надя (предположено Эрдёшем в 1935 году, доказано в 1939 году Белой Сёкефальви-Надем) — многоугольник без самопересечений может быть преобразован в слабовыпуклый путём конечного числа зеркальных отражений «карманов» — связных компонентов относительно ребер выпуклой оболочки.
• Теорема Эрдёша — Радо (1954, совместно с Рихардом Радо (нем. Richard Rado)).
• Теорема Эрдёша — Стоуна^[англ.] (1946, совместно с Артуром Стоуном (англ. Arthur Harold Stone)).
• Теорема Эрдёша — Секереша о монотонных подпоследовательностях.(1935, совместно с Дьёрдем Секерешем)
• Теорема Эрдёша — Секереша о выпуклых многоугольниках (известная как «задача со счастливым концом», 1935, совместно с Дьёрдем Секерешем и Эстер Секереш (венг. Eszter Szekeres)).

Гипотезы

• Гипотеза Эрдёша — Турана об арифметических прогрессиях в плотных множествах, 1936, совместно с Палом Тураном (доказана в 1975 году теоремой Семереди).
• Гипотеза Эрдёша — Турана для аддитивных базисов^[англ.], 1941, совместно с Палом Тураном (не доказана по состоянию на 2013 год).
• Гипотеза Эрдёша об арифметических прогрессиях.
• Гипотеза Эрдёша о минимальном числе различных расстояний между ${\displaystyle n}$ различными точками в евклидовом пространстве (для плоскости доказана в 2010 году Ларри Гутом и Нецем Кацем (англ. Nets Hawk Katz)).
• Гипотеза Кэмерона — Эрдёша о количестве свободных от сумм подмножеств, 1988, совместно с Питером Кэмероном^[англ.] (доказана в 2003 году Беном Грином).
• Гипотеза Эрдёша — Бура о числах Рамсея на графах.
• Гипотеза Эрдёша — Фабера — Ловаса о раскраске объединений клик.
• Гипотеза Эрдёша — Грэма о представлении единицы одноцветной египетской дробью (доказана Эрнестом Крутом^[англ.] в 2003 году).
• Гипотеза Эрдёша — Дьярфаша о длине циклов в графе со степенью вершин не менее 3.
• Гипотеза Эрдёша — Штрауса о египетской дроби ${\displaystyle 4/n=1/x+1/y+1/z}$.
• Гипотеза Эрдёша — Моллина — Уолша о последовательных тройках полнократных чисел.
• Гипотеза Эрдёша — Сэлфриджа о том, что покрывающее множество содержит по крайней мере одно нечётное число.
• Гипотеза Эрдёша — Вудса о том, что ${\displaystyle k}$ чисел любого отрезка натурального ряда для любого достаточно большого фиксированного ${\displaystyle k}$ однозначно определяются списком своих различных простых делителей. С ней связано число Эрдёша — Вудса
• Гипотеза Эрдёша — Секереша о числе точек в общем положении, обязательно включающих вершины выпуклого n-угольника.
• Гипотеза Эрдёша — Хайналя о том, что в семействе графов, получаемом удалением порожденного подграфа, каждый граф либо является большой кликой, либо большим независимым множеством^[3].
• Гипотеза Эрдёша — Хейльбронна в комбинаторной теории чисел о числе сумм двух множеств вычетов по простому модулю (доказана Диашем да Силвой (J. A. Dias da Silva) и Хамидоне (Y. O. Hamidoune) в 1994 году).
• Гипотеза Эрдёша — Менгера о разделяющих путях в бесконечных графах (доказана Роном Ахарони и Эли Бергером).
• Гипотеза Эрдёша — Стюарта о диофантовом уравнении ${\displaystyle n!+1={p_{k}}^{a}{p_{k+1}}^{b}}$ (доказана Люком^[4]).
• Гипотеза Эрдёша — Ловаса о слабых и сильных дельта-системах (доказана Мишелем Деза).
• Проблема Нелсона — Эрдёша — Хадвигера или вопрос о хроматическом числе пространства. Каково минимальное число цветов, в которые можно раскрасить точки ${\displaystyle n}$-мерного пространства так, чтобы никакие одноцветные точки не находились на расстоянии ${\displaystyle 1}$.

Константы

• Постоянная Коупленда — Эрдёша (1946, совместно с Артуром Коуплендом^[англ.] доказана нормальность числа) — иррациональное число, являющееся записью простых чисел в десятичной системе счисления по порядку в дробной части после нуля: 0,235711131719232931374143…^[5].
• Константа Эрдёша — Борвейна (Эрдёш в 1946 году доказал иррациональность, Питер Борвейн^[англ.] в 1992 году дал альтернативное доказательство) — сумма обратных величин чисел Мерсенна.
• Кардинальное число Эрдёша^[англ.] (1958, совместно с Андрашем Хайналем^[венг.]).

Неравенства

• Неравенство Эрдёша — Турана.
• Неравенство Эрдёша — Морделла.

Прочее

• Граф Эрдёша — Диофанта
• Пространство Эрдёша
• Модель Эрдёша — Реньи

Примечания

1. Anning, Norman H.; Erdős, Paul (1945), "Integral distances", Bulletin of the American Mathematical Society, 51 (8): 598—600, doi:10.1090/S0002-9904-1945-08407-9, Архивировано из оригинала 12 августа 2007, Дата обращения: 23 февраля 2013
2. Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok, 11: 264—274, Архивировано из оригинала (PDF) 20 января 2022, Дата обращения: 23 февраля 2013
3. Ramsey-type theorems, Discrete Applied Mathematics 25 (1989) 37-52
4. MR: 2001g:11042
5. последовательность A33308 в OEIS

Ссылки

• Fan Chung, «Open problems of Paul Erdős in graph theory»