Грэм, Рональд

Родился 31 октября 1935 года в городе Тафт (штат Калифорния). В возрасте 15 лет, не окончив среднюю школу, получил стипендию для обучения в Чикагском университете. Во время службы в ВВС США на Аляске совмещал службу с учёбой и в 1959 году получил степень бакалавра физики в Университете Аляски^[7]. В 1962 году получил степень доктора философии в области математики в Калифорнийском университете в Беркли и начал работать в Лабораториях Белла, а позже — в АТ&Т Labs, откуда ушёл в 1999 году, после 37 лет. С 1999 по 2020 год работал профессором в Калифорнийском университете в Сан-Диего^[8].

Скончался 6 июля 2020 года в Ла-Хойе от осложнений бронхоэктатической болезни^[9].

В своей статье 1977 года рассмотрел проблему теории Рамсея, и нашёл наибольшее возможное число, являющееся решением. Это число являлось наибольшим из когда-либо использовавшихся в математических доказательствах (оно было занесено в Книгу Рекордов Гиннесса), и было названо числом Грэма^[10]. Правда, позже оно уступило первенство числу TREE(3). В 1971 году совместно с Брюсом Ротшильдом доказал теорему Грэма — Ротшильда, ставшую фундаментальным вкладом в теорию Рамсея и значительным обобщением теоремы ван дер Вардена^[11].

В 1971—1972 годах в области теории графов совместно с Генри Поллаком доказал теорему Грэма — Поллака, согласно которой множество рёбер полного графа на n вершинах нельзя разбить на менее чем n−1 полных двудольных подграфов^[12]. В 1972 году внёс значительный вклад в вычислительную геометрию, разработав алгоритм Грэма (обход Грэма) для эффективного построения выпуклой оболочки множества точек на плоскости с временной сложностью O(n log n)^[13].

Грэм популяризировал концепцию числа Эрдёша. У самого Грэма число Эрдёша равно 1. Они написали в соавторстве около 30 работ, а также являлись хорошими друзьями. Эрдёш и Грэм вместе навещали молодого математика Джона Фокмана, когда у того обнаружили рак мозга. Грэм принимал активное участие в его реабилитации.

При жизни Грэм управлял небольшим фондом, оставленным Эрдёшем после своей смерти в 1996 году, чтобы выдавать призы за решение задач Эрдёша. После смерти Грэма в 2020 году официального преемника, принявшего на себя управление фондом, объявлено не было. Первую крупную сумму за решение задачи Эрдёша он выплатил в 1977 году Эндре Семереди, который впоследствии получил Абелевскую премию за работу, основанную на данной задаче. В 1998 году в соавторстве со своей женой написал книгу «Эрдёш о графах: его наследие нерешённых задач», собрав более 200 задач Эрдёша из области теории графов.

Опубликовал около 320 статей и книг.

• «Конкретная математика. Основание информатики» (1989, в соавторстве с Д. Кнутом и О. Паташником)^[14]
• «Теория Рамсея» (1981, 2-е изд. 1990, в соавторстве с Б. Ротшильдом и Дж. Спенсером)^[7]
• «Азы теории Рамсея» (1981)^[7]
• «Старые и новые проблемы и результаты в комбинаторной теории чисел» (1980, в соавторстве с П. Эрдёшем)^[15]
• «Эрдёш о графах: его наследие нерешённых задач» (1998, в соавторстве с Фэн Чанг)^[15]
• «Магическая математика: математические идеи, которые лежат в основе великих фокусов» (2011, в соавторстве с П. Диаконисом)^[15]

Был женат на Фэн Чанг, которая является профессором интернет-математики в Калифорнийском университете в Сан-Диего. Есть двое детей^[16].

Грэм был опытным жонглёром и в 1972 году занимал пост президента Международной ассоциации жонглёров (IJA)^[17].

Среди наград — премия Пойи (SIAM) (1971) и премия Стила в категории «За жизненные достижения» (2003)^[18]. В 2001 и 2015 годах приглашался прочесть Гиббсовскую лекцию.

В период 1993—1994 годов занимал должность президента Американского математического общества. В 1999 году избран почётным членом Ассоциации вычислительной техники, в 2012 году — почётным членом Американского математического общества.

С 1985 года являлся членом Национальной академии наук США, также был членом Американской академии искусств и наук^[9]. В 2009 году избран действительным членом (Fellow) Общества промышленной и прикладной математики (SIAM).

В 2013 году удостоен книжной премии Эйлера за книгу «Magical Mathematics»^[18].

Среди объектов, утверждений и концепций, названных его именем — гипотеза Эрдёша — Грэма, алгоритм Грэхема, число Грэма.