Введение
Американский математик (1935–2020)
Рональд Льюис Грэм (31 октября 1935 года – 6 июля 2020 года) – американский математик, признанный Американским математическим обществом как «один из главных архитекторов быстрого развития дискретной математики во всем мире в последние годы». Он был президентом как Американского математического общества, так и Математической ассоциации Америки, а его награды включали премию Лероя П. Стила за достижения за всю жизнь и избрание в Национальную академию наук. После обучения в Калифорнийском университете в Беркли Грэм много лет работал в Bell Labs, а затем в Калифорнийском университете в Сан-Диего. Он внес значительный вклад в теорию расписаний, вычислительную геометрию, теорию Рамсея и квазислучайность, и многие математические понятия названы в его честь. Он опубликовал шесть книг и около 400 статей, а также имел почти 200 соавторов, включая многочисленные совместные работы с его женой Фан Чунг и Полом Эрдошем. Грэм был упомянут в «Рипли: Верь или нет!» как не только «один из ведущих математиков мира», но и талантливый акробат на батуте и жонглер. Он был президентом Международной ассоциации жонглеров. Его отец работал на нефтяных месторождениях, а затем стал моряком торгового флота. Несмотря на более поздний интерес Грэма к гимнастике, он был невысокого роста и не отличался атлетизмом. Он рос, часто переезжая между Калифорнией и Джорджией, пропуская несколько классов в школе из-за этих переездов и не оставаясь в одной школе дольше года. Затем он перешел в Калифорнийский университет в Сан-Диего (UCSD) в качестве профессора компьютерных и информационных наук имени Ирвина и Джоан Джейкобс. В UCSD он также стал главным научным сотрудником Калифорнийского института телекоммуникаций и информационных технологий. В 2003–2004 годах он был президентом Математической ассоциации Америки. Скончался 6 июля 2020 года в возрасте 84 лет в Ла-Холье, Калифорния.
Вклад
Грэм внес значительный вклад в различные области математики и теоретической информатики. Он опубликовал около 400 научных работ, четверть из которых в соавторстве с Чангом, и шесть книг, включая «Конкретную математику» в соавторстве с Дональдом Кнутом и Ореном Паташником. Проект Erdős Number Project указывает почти 200 его соавторов. Он был научным руководителем девяти аспирантов: по одному в Городском университете Нью-Йорка и Университете Рутгерса, когда работал в Bell Labs, и семерых в Калифорнийском университете в Сан-Диего.
Теория чисел
Докторская диссертация Грэма была посвящена теории чисел, египетским дробям, как и проблема Эрдоша — Грэма, которая спрашивает, существует ли для любого разбиения целых чисел на конечное число классов конечный подкласс, сумма обратных величин элементов которого равна единице. Доказательство было опубликовано Эрни Крутом в 2003 году. Другая работа Грэма по египетским дробям была опубликована в 2015 году совместно со Стивеном Батлером и (почти через 20 лет после смерти) Эрдосом; это была последняя опубликованная работа Эрдоса, сделавшая Батлера его 512-м соавтором. В статье 1964 года Грэм начал изучение последовательностей, свободных от простых чисел, заметив, что существуют последовательности чисел, определяемые тем же рекуррентным соотношением, что и числа Фибоначчи, в которых ни один элемент последовательности не является простым числом. Задача построения большего числа таких последовательностей позже была подхвачена Дональдом Кнутом и другими исследователями. Книга Грэма и Эрдоша 1980 года «Старые и новые результаты в комбинаторной теории чисел» представляет собой сборник нерешенных задач из широкого круга областей теории чисел.
Теория Рамзи
Теорема Грэма — Ротшильда в теории Рамзи была опубликована Грэмом и Брюсом Ротшильдом в 1971 году и применяет теорию Рамзи к комбинаторным кубам в комбинаторике слов. Грэм привел большое число в качестве верхней оценки для конкретного случая этой теоремы, теперь известного как число Грэма, которое было занесено в Книгу рекордов Гиннеса как самое большое число, когда-либо использованное в математическом доказательстве, хотя впоследствии оно было превзойдено еще большими числами, такими как TREE(3). Грэм объявил денежный приз за решение задачи о булевых пифагорейских тройках, другой задачи в теории Рамзи; приз был получен в 2016 году. Грэм также опубликовал две книги по теории Рамзи.
Теория графов
Теорема Грэма — Поллака, опубликованная Грэмом совместно с Генри О. Поллаком в двух статьях в 1971 и 1972 годах, утверждает, что если рёбра полного графа с *n* вершинами разбиты на полные двудольные подграфы, то требуется не менее *n-1* подграфов. Грэм и Поллак предложили простое доказательство с использованием линейной алгебры; несмотря на комбинаторную природу утверждения и многочисленные публикации альтернативных доказательств после их работы, все известные доказательства требуют применения линейной алгебры. Вскоре после начала исследований квазислучайных графов, с работ Эндрю Томасона, Грэм опубликовал в 1989 году результат совместно с Чунгом и Р. М. Уилсоном, который получил название «фундаментальной теоремы квазислучайных графов», утверждающей, что многие различные определения этих графов эквивалентны. Гипотеза Грэма о камешках, представленная в статье Чанга в 1989 году, касается числа камешков для декартовых произведений графов. По состоянию на 2019 год она остаётся нерешённой.
Алгоритмы упаковки, планирования и приближения
Ранняя работа Грэма в области планирования задач для цехов внедрила понятие наихудшего коэффициента аппроксимации в изучение алгоритмов аппроксимации и заложила основы для последующей разработки конкурентного анализа онлайн-алгоритмов. Позднее эта работа была признана важной и для теории упаковки рюкзаков, области, в которой Грэм впоследствии работал более целенаправленно. Алгоритм Коффмана — Грэма, опубликованный Грэмом совместно с Эдвардом Г. Коффманом-младшим в 1972 году, предоставляет оптимальный алгоритм для планирования на двух машинах и гарантированный алгоритм аппроксимации для большего числа машин. Он также находит применение в построении слоистых графов. В обзорной статье об алгоритмах планирования, опубликованной в 1979 году, Грэм и его соавторы предложили трехсимвольную нотацию для классификации теоретических задач планирования в зависимости от системы машин, на которых они выполняются, характеристик задач и ресурсов, таких как требования к синхронизации или непрерывности, и критерия оптимизации. Эта классификация иногда называется «нотацией Грэма».
Дискретная и вычислительная геометрия
Сканирование Грэма — широко используемый и практичный алгоритм для построения выпуклых оболочек двухмерных наборов точек, основанный на сортировке точек и последующем добавлении их в оболочку в отсортированном порядке. Грэм опубликовал этот алгоритм в 1972 году. Задача о многоугольнике наибольшей площади при заданном диаметре (также известная как "проблема самого большого маленького многоугольника") ставит вопрос о поиске многоугольника максимальной площади для заданного диаметра. Удивительно, но, как заметил Грэм, ответ не всегда является правильным многоугольником. Гипотеза Грэма 1975 года относительно формы этих многоугольников была окончательно доказана в 2007 году. В другой публикации 1975 года Грэм и Эрдош отметили, что при упаковке единичных квадратов в больший квадрат с нецелочисленной длиной стороны можно использовать наклонные квадраты, чтобы оставить незаполненную область, площадь которой растет медленнее, чем длина стороны большого квадрата, в отличие от очевидной упаковки квадратами, ориентированными по осям координат. Клаус Рот и Боб Воган доказали, что в некоторых случаях может потребоваться незаполненная область, площадь которой пропорциональна квадратному корню из длины стороны; получение точной оценки для площади незаполненной области остаётся нерешённой проблемой.
Жонглирование
Грэм стал опытным жонглером, начиная с 15 лет, и практиковался в жонглировании до шести мячей. Он также был одним из двух первых лауреатов медали Эйлера Института комбинаторики и его приложений, другим был Клод Берге. В 1985 году Грэм был избран в Национальную академию наук. В 1999 году он был удостоен звания Fellow ACM «за основополагающий вклад в анализ алгоритмов, в частности, анализ наихудшего случая эвристик, теорию расписаний и вычислительную геометрию». В 2009 году он стал членом Общества промышленной и прикладной математики; эта награда была присуждена за его «вклад в дискретную математику и ее приложения». В 2012 году он стал членом Американского математического общества. Грэм был приглашенным докладчиком на Международном конгрессе математиков 1982 года (прошедшем в 1983 году в Варшаве) и получил премию Лестера Р. Форда за статью «Экспресс-курс вычислительной геометрии» в соавторстве с Франсис Яо, опубликованную в American Mathematical Monthly (1990). Его книга «Магическая математика» в соавторстве с Перси Диаконисом удостоилась премии Эйлера за лучшую книгу. Материалы конференции Integers 2005 были опубликованы в виде сборника статей, посвященного 70-летию Рона Грэма. Еще один сборник статей, подготовленный по материалам конференции, посвященной 80-летию Грэма в 2015 году, был опубликован в 2018 году под названием «Связи в дискретной математике: празднование творчества Рона Грэма».