Рональд Грэм

Рональд Грэм
Грэм в 1998 году
Родившийся	Рональд Льюис Грэм ( 1935-10-31 )31 октября 1935 г. Тафт, Калифорния , США
Умер	6 июля 2020 г. (2020-07-06)(84 года) Сан-Диего , Калифорния, США
Альма-матер	Univ. Аляски (BS) Калифорнийский университет в Беркли (доктор философии)
Известен	Алгоритм Коффмана – Грэма Проблема Эрдеша – Грэма Число Грэма Сканирование Грэма Теорема Грэма – Поллака.
Супруг (а)	Фань Чунг (женат в 1983 году)
Награды	Премия Полии (1971) Nat. Акад. Sci. (1985) Премия Стила (2003)
Научная карьера
Поля	Математика Информатика
Учреждения	Bell Labs AT&T Labs Калифорнийский университет в Сан-Диего
Тезис	О конечных суммах рациональных чисел  (1962)
Докторант	Деррик Генри Лемер

Рональд Льюис Грэм (31 октября 1935 г. - 6 июля 2020 г.) ^[1] был американским математиком, признанным Американским математическим обществом «одним из главных архитекторов быстрого развития дискретной математики во всем мире в последние годы». ^[2] Он был президентом Американского математического общества и Математической ассоциации Америки , и его награды включали премию Лероя П. Стила за достижения в жизни и избрание в Национальную академию наук .

После аспирантуры в Калифорнийском университете в Беркли Грэм много лет проработал в Bell Labs, а затем в Калифорнийском университете в Сан-Диего . Он делал важную работу по теории расписаний , вычислительной геометрии , теории Рэмси , и квази-хаотичности , ^[3] и многие темы в математике названы в его честь. Он опубликовал шесть книг и около 400 статей и имел около 200 соавторов, в том числе много совместных работ с его женой Фан Чанг и Полом Эрдёшем .

Грэм был показан в фильме Рипли "Хотите верьте, хотите нет!" за то, что он не только «один из выдающихся математиков мира», но также является опытным батутом и жонглером. Он был президентом Международной ассоциации жонглеров . ^{[3] [4] [5]}

Биография [ править ]

Грэм родился в Тафте, Калифорния , 31 октября 1935 года; ^[6] его отец был нефтяником, а затем торговым флотом. Несмотря на более поздний интерес Грэма к гимнастике, он был маленьким и не спортивным. ^[7] Он рос, часто переезжая из Калифорнии в Джорджию, пропуская из-за этого несколько классов школы и никогда не оставаясь в одной школе дольше года. ^{[1] [7]} Подростком он переехал во Флориду со своей теперь разведенной матерью, где он учился, но не окончил среднюю школу. Вместо этого в возрасте 15 лет он выиграл стипендию Фонда Форда для обучения в Чикагском университете , где он изучал гимнастику, но не посещал курсы математики.^[1]

Через три года, когда его ученость истек, он переехал в Университете Калифорнии, Беркли , официально как студент электротехники , а также изучение теории чисел под Деррик Генри Лехмер , ^[1] и выиграть титул чемпиона штата Калифорния батут. ^[7] Он поступил на службу в ВВС США в 1955 году, когда он достиг возраста, соответствующего критериям отбора, ^[8] покинул Беркли, не получив ученой степени, и поселился в Фэрбенксе, Аляска , где в 1959 году наконец получил степень бакалавра физики. в Университете Аляски в Фэрбенксе . ^[1]Вернувшись в Калифорнийский университет в Беркли для обучения в аспирантуре, он получил докторскую степень. в математике в 1962 году. Его диссертация, руководимая Лемером, была « О конечных суммах рациональных чисел» . ^[9] Будучи аспирантом, он зарабатывал себе на жизнь выступлениями на батуте в цирке ^[8] и женился на Нэнси Янг, студентке-математике в Беркли; у них было двое детей. ^[1]

После получения докторской степени Грэм начал работать в 1962 году в Bell Labs, а затем стал директором по информационным наукам в AT&T Labs в Нью-Джерси . В 1963 году на конференции в Колорадо он встретил плодовитого венгерского математика Пола Эрдеша (1913–1996) ^[1], который стал близким другом и частым соавтором исследований. Грэхема огорчило то, что Эрдёш избил его в пинг- понге, тогда он был уже среднего возраста; он вернулся в Нью-Джерси, решив улучшить свою игру, и в конце концов стал чемпионом Bell Labs и выиграл титул штата в игре. ^[1] Позже Грэм популяризировал понятие числа Эрдеша., мера удаленности от Эрдеша в сети сотрудничества математиков; ^{[10] [8]} его многочисленные работы с Эрдёшем включают две книги открытых проблем ^{[B1] [B5]} и последнюю посмертную статью Эрдёша. ^[A15] Грэм развелся в 1970-х годах; в 1983 году он женился на своей коллеге по Bell Labs и постоянном соавторе Фан Чанге . ^[1]

Работая в Bell Labs, Грэм также занял должность профессора математических наук в Университете Рутгерса в 1986 году и проработал президентом Американского математического общества с 1993 по 1994 год. Он стал главным научным сотрудником лаборатории в 1995 году ^{[1]. ]} Он ушел из AT&T в 1999 году после 37 лет работы там ^[11] и перешел в Калифорнийский университет в Сан-Диего (UCSD) в качестве профессора компьютерных и информационных наук Ирвина и Джоан Джейкобс. ^{[1] [8]} В UCSD он также стал главным научным сотрудником Калифорнийского института телекоммуникаций и информационных технологий . ^{[8] [5]}В 2003–04 годах он был президентом Математической ассоциации Америки . ^[1]

Грэм умер от бронхоэктаза ^[12] 6 июля 2020 года в возрасте 84 лет в Ла-Хойе , Калифорния. ^{[6] [13]}

Вклады [ править ]

Грэм внес важный вклад во многие области математики и теоретической информатики. Он опубликовал около 400 статей, четверть из которых с Чангом ^[14] и шесть книг, включая « Конкретную математику» с Дональдом Кнутом и Ореном Паташником . ^[B4] Проект числа Эрдёша отмечает, что у него почти 200 соавторов. ^[15] Он был научным руководителем девяти студентов, по одному в Городском университете Нью-Йорка и Университете Рутгерса, когда он работал в Bell Labs, и семи в Калифорнийском университете в Сан-Диего. ^[9]

Заметные темы по математике имени Graham включают проблему Erdős-Грэма на египетских дробей , то теорема Graham-Rothschild в теории Рамсея из параметров слов и числа Грэма производные от него, то теорема Graham-Поллак и pebbling гипотеза Грэма в теории графов , то Алгоритм Коффмана – Грэма для приближенного планирования и рисования графиков, а также алгоритм сканирования Грэма для выпуклых оболочек . Он также начал изучение последовательностей без простых чисел ,Логическая задача Пифагора о троек , самый большой маленький многоугольник и квадратная упаковка в квадрате .

Грэм был одним из авторов публикаций GW Peck , псевдонимного математического сотрудничества, названного по инициалам его членов, с Грэмом как «G». ^[16]

Теория чисел [ править ]

Докторская диссертация Грэма была в теории чисел , на египетских дробей , ^{[7] [9]} , как это проблема Erdős-Graham от того, имеет ли каждый раздел из целых чисел в конечное число классов класс , чье обратными сумма к одному. Доказательство было опубликовано Эрни Крут в 2003 году. ^[17] Еще одна статья Грэма о египетских дробях была опубликована в 2015 году вместе со Стивом Батлером и (почти 20 лет посмертно) Эрдешом; это была последняя из опубликованных работ Эрдёша, в результате чего Батлер стал его 512-м соавтором. ^{[A15] [18]}

В статье 1964 года Грэм начал изучение последовательностей, свободных от простых чисел, с того, что заметил , что существуют последовательности чисел, определяемые тем же рекуррентным соотношением, что и числа Фибоначчи , в которых ни один из элементов последовательности не является простым. ^[A64] Задача построения большего количества таких последовательностей позже была поднята Дональдом Кнутом и другими. ^[19] Книга Грэхема 1980 года, в которой Эрдеш « Старые и новые результаты в комбинаторной теории чисел», представляет собой сборник открытых проблем из широкого круга областей теории чисел. ^[B1]

Теория Рэмси [ править ]

Теорема Грэма – Ротшильда в теории Рамсея была опубликована Грэмом и Брюсом Ротшильдами в 1971 году и применяет теорию Рамсея к комбинаторным кубам в комбинаторике слов . ^[A71a] Грэм привел большое число в качестве верхней границы для примера этой теоремы, теперь известного как число Грэма , которое было занесено в Книгу рекордов Гиннеса как самое большое число, когда-либо использовавшееся в математическом доказательстве, ^[20] хотя оно с тех пор была превзойдена еще большими числами, такими как TREE (3) . ^[21]

Грэм предложил денежную премию за решение булевой пифагорейской проблемы троек , еще одной проблемы в теории Рамсея; приз был востребован в 2016 году. ^[22] Грэм также опубликовал две книги по теории Рамсея. ^{[B2] [B3]}

Теория графов [ править ]

Разбиение ребер полного графа на пять полных двудольных подграфов согласно теореме Грэма – Поллака${\ displaystyle K_ {6}}$

Теорема Грэма – Поллака , которую Грэм опубликовал вместе с Генри О. Поллаком в двух статьях в 1971 и 1972 годах, ^{[A71b] [A72a],} утверждает, что если ребра полного графа -вершины разбиваются на полные двудольные подграфы , то по крайней мере подграфы необходимы. Грэм и Поллак представили простое доказательство, используя линейную алгебру ; несмотря на комбинаторный характер утверждения и многочисленные публикации альтернативных доказательств с момента их работы, все известные доказательства требуют линейной алгебры. ^[23]${\ displaystyle n}$${\ displaystyle n-1}$

Вскоре после того, как исследования квазислучайных графов начались с работы Эндрю Томасона, Грэм опубликовал в 1989 году совместно с Чангом и Р.М. Уилсоном результат , который был назван «фундаментальной теоремой квазислучайных графов», в котором говорится, что существует множество различных определений этих графов. эквивалентны. ^{[A89a] [24]}

Гипотеза Грэхема , появившаяся в статье Чанга 1989 года, касается количества камней в декартовых произведениях графов . По состоянию на 2019 год ^{[Обновить]}он остается нерешенным. ^[25]

Алгоритмы упаковки, планирования и аппроксимации [ править ]

Ранние работы Грэма на планирование работы магазина ^{[A66] [A69]} ввел наихудший коэффициент аппроксимации в изучении алгоритмов аппроксимации , и были заложены основы для последующего развития конкурентного анализа в онлайн - алгоритмов . ^[26] Эта работа была впоследствии признана важной и для теории бен упаковки , ^[27] область, Graham позже работал в более явном виде. ^[A74]

Алгоритм Коффмэны-Грэхэй , который Грэхэй опубликован с Эдвардом Г. Коффманом младшим в 1972 году, ^[A72b] обеспечивает алгоритм оптимального для планирования два машин и гарантированный алгоритм аппроксимации для большего числа машин. Он также был применен в рисовании многоуровневых графиков . ^[28]

В обзорной статье о планировании статей, опубликованной в 1979 году, Грэм и его соавторы ввели трехсимвольную нотацию для классификации теоретических задач планирования в соответствии с системой машин, на которых они должны работать, характеристиками задач и ресурсов, такими как требования к синхронизации. или непрерывность, и показатель производительности должен быть оптимизирован. ^[A79] Эту классификацию иногда называют «нотацией Грэма» или «нотацией Грэма». ^[29]

Дискретная и вычислительная геометрия [ править ]

Сканирование Грэма - это широко используемый и практичный алгоритм для выпуклой оболочки двумерных наборов точек, основанный на сортировке точек с последующей их вставкой в ​​оболочку в отсортированном порядке. ^[30] Грэм опубликовал алгоритм в 1972 году. ^[A72c]

Самая большая проблема с маленьким многоугольником требует многоугольника наибольшей площади для данного диаметра. Удивительно, но, как заметил Грэм, ответ не всегда является правильным многоугольником . ^{[A75a] Гипотеза} Грэма 1975 г. о форме этих многоугольников была окончательно доказана в 2007 г. ^[31]

В другой публикации 1975 года Грэм и Эрдеш отметили, что для упаковки единичных квадратов в больший квадрат с нецелочисленными длинами сторон можно использовать наклонные квадраты, чтобы оставить непокрытую область, которая является сублинейной по длине стороны большего квадрата, в отличие от очевидного упаковка с выровненными по оси квадратами. ^[A75b] Клаус Рот и Боб Воан доказали, что иногда может потребоваться открытая площадь, по крайней мере, пропорциональная квадратному корню из длины стороны; Обеспечение плотного прилегания непокрытой области остается открытой проблемой. ^[32]

Вероятность и статистика [ править ]

В области непараметрической статистики в статье Перси Диакониса и Грэма 1977 года изучались статистические свойства правила стопы Пирсона , меры ранговой корреляции, которая сравнивает две перестановки путем суммирования по каждому элементу расстояния между позициями элемента в двух перестановках. ^[A77] Они сравнили эту меру с другими методами ранговой корреляции, что привело к «неравенствам Диакониса – Грэма».

${\ Displaystyle I + E \ leq D \ leq 2I}$

где - правило Пирсона, - количество инверсий между двумя перестановками (ненормализованная версия коэффициента ранговой корреляции Кендалла ) и - минимальное количество двухэлементных перестановок, необходимых для получения одной перестановки из другой. ^[33]${\ displaystyle D}$${\ displaystyle I}$${\ displaystyle E}$

Случайный процесс Chung-Diaconis-Грэхэм является случайным блужданием по модулю целых чисел нечетное целое число , в котором на каждом шаге один удваивает предыдущий номер , а затем случайным образом добавляет к нулю, , или ( по модулю ). В статье 1987 года Чанг, Диаконис и Грэм изучали время перемешивания этого процесса, мотивированные изучением генераторов псевдослучайных чисел . ^{[A87] [34]}${\ displaystyle p}$${\ displaystyle 1}$${\ displaystyle -1}$${\ displaystyle p}$

Жонглирование [ править ]

Грэм стал способным жонглером с 15 лет и практиковался в жонглировании до шести мячей. ^[4] (Хотя опубликованная фотография показывает, как он жонглирует двенадцатью мячами, ^[5] это сфабрикованное изображение. ^[3] ) Он научил Стива Миллса , неоднократного победителя чемпионатов Международной ассоциации жонглеров, жонглировать, и его работе вместе с Миллсом помогли Миллсу разработать модель жонглирования «Беспорядок Миллса» . Кроме того, Грэм внес значительный вклад в теорию жонглирования, в том числе серию публикаций о заменах сайтов . В 1972 году он был избран президентом Международной ассоциации жонглеров . ^[4]

Награды и награды [ править ]

В 2003 году Грэм выиграл ежегодную премию Лероя П. Стила Американского математического общества за достижения в жизни. Премия отмечена его вкладом в дискретную математику , популяризацией математики посредством его выступлений и письменных работ, его лидерством в Bell Labs и его служением в качестве президента общества. ^[35] Он был одним из пяти инаугурационных победителей Пойа премии в Общества промышленной и прикладной математики , разделяя его с коллегами Ramsey теоретиками Клаус Либом, Брюс Ротшильд , Альфред Hales и Роберт И. Джьюетт. ^[36]Он также был одним из двух инаугурационных победителей Euler медали в Институте комбинаторики и ее применение , другого Клод Берге . ^[37]

Грэм был избран членом Национальной академии наук в 1985 году. ^[38] В 1999 году он был назначен членом ACM «за основополагающий вклад в анализ алгоритмов, в частности, эвристический анализ наихудшего случая, теорию составления расписаний и» вычислительная геометрия ». ^[39] Он стал членом Общества промышленной и прикладной математики в 2009 году; Стипендиат цитирует его «вклад в дискретную математику и ее приложения». ^[40] В 2012 году он стал членом Американского математического общества . ^[41]

Грэм был приглашенным докладчиком на Международном конгрессе математиков 1982 г. (состоявшемся в 1983 г. в Варшаве) ^[13], выступая на тему «Последние достижения в теории Рамсея». ^[A84] Он был дважды Гиббс преподаватель , в 2001 и 2015 годах ^[13] Математическая ассоциация Америки присуждена ему как Карл Allendoerfer премию за бумаги «Штайнер деревья на Checkerboard» с Chung и Мартином Гарднером в математическом журнале ( 1989), ^{[A89b] [42]} и премию Лестера Р. Форда за его статью «Вихревой тур по вычислительной геометрии» сФрэнсис Яо в журнале American Mathematical Monthly (1990). ^{[A90] [43]} Его книга « Магическая математика с Перси Диаконис» ^[B6] получила Книжную премию Эйлера . ^[44]

Труды конференции Integer 2005 были опубликованы как праздничный сборник к 70-летию Рона Грэхема. ^[45] Еще один сборник, основанный на конференции, проведенной в 2015 году в честь 80-летия Грэма, был опубликован в 2018 году как книга « Связи в дискретной математике: чествование работы Рона Грэма» . ^[46]

Избранные публикации [ править ]

Книги [ править ]

Отредактированные тома [ править ]

Статьи [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

• Профиль исследования факультета UCSD Грэма
• Документы Рона Грэма  - исчерпывающий архив статей, написанных Роном Грэмом.
• О Роне Грэхэме  - странице, обобщающей некоторые аспекты жизни и математики Грэма, - часть веб-сайта Фан Чанга.
• «Фонд Саймонса: Рональд Грэм (1935–2020)» . Фонд Саймонса. 11 января 2016 г. - Расширенное видео-интервью.
• «Три математика, которых мы потеряли в 2020 году: Джон Конвей, Рональд Грэм и Фриман Дайсон - все исследовали мир своими мыслями», Рокмор, Дэн. (31 декабря 2020 г.) Житель Нью-Йорка .
• Публикации Рональда Грэма, проиндексированные Google Scholar