Хоффман, Алан

Алан Хоффман
англ. Alan Jerome Hoffman
граф Хоффмана — Синглтона, 50 вершин, 175 рёбер
Дата рождения	30 мая 1924(1924-05-30)
Место рождения	Нью-Йорк[1]
Дата смерти	18 января 2021(2021-01-18) (96 лет)
Страна	США
Род деятельности	математик
Научная сфера	комбинаторная оптимизация, теория графов
Место работы	Исследовательский центр Т. Дж. Уотсона[англ.]
Альма-матер	Колумбийский университет
Учёная степень	Доктор философии
Научный руководитель	Edgar Lorch[вд]
Известен как	соавтор графа Хоффмана — Синглтона
Награды и премии	теоретическая премия фон Неймана (1992)

Алан Джером Хоффман (англ. Alan Jerome Hoffman; 30 мая 1924, Нью-Йорк — 18 января 2021^[2]) — американский математик, сотрудник Исследовательского центра Т. Дж. Уотсона^[англ.] компании IBM. Редактор и основатель журнала англ. Linear Algebra and its Applications. Он внес вклад в комбинаторную оптимизацию и теорию собственных значений графов. Хоффман совместно с Робертом Синглтоном построил граф Хоффмана — Синглтона, который является уникальным графом Мура степени 7 и диаметра 2^[3].

Алан Хоффман поступил в Колумбийский университет в 1940 году, получив Пулитцеровскую стипендию в 1940 году в возрасте 16 лет. Вторая мировая война прервала учёбу Хоффмана, он был призван на службу в феврале 1943 года и служил в армии США с 1943 по 1946 год, как в Европе, так и на Тихом океане. Во время базовой подготовки в зенитно-артиллерийской школе он рассматривал возможность разработки аксиом геометрии окружностей^[2].

По возвращении в Колумбию осенью 1946 года он защитил докторскую диссертацию по основам инверсионной геометрии в 1950 году. После этого Хоффман провёл год в Институте перспективных исследований в Принстоне (соседний с ним офис занимал Альберт Эйнштейн)^[2].

Первым местом работы Хоффмана стал Отдел прикладной математики Национального бюро стандартов. В Бюро Хоффман стал лидером в новой области науки — линейном программировании. Хоффман был ключевым организатором влиятельного Второго симпозиума по линейному программированию, состоявшегося в Бюро в январе 1955 года^[2].

В 1956 году Хоффман покинул Бюро и переехал в Англию для работы научным сотрудником по связям в лондонском отделении Бюро военно-морских исследований. Когда год за границей подходил к концу, Хоффману предложили две должности в индустриальных компаниях в Нью-Йорке: одна в крошечной группе математических исследований в зарождающейся исследовательской лаборатории IBM, а другая в штаб-квартире компании General Electric. Хоффман выбрал роль в более авторитетной организации. Руководство разрешило ему заниматься математикой, если это не мешало выполнению возложенных на него обязанностей, и Хоффман продолжил свои математические исследования, совершенно не связанные с его основной работой. В 1961 году он принял приглашение перейти на работу в Исследовательский центр Т. Дж. Уотсона^[англ.] компании IBM^[2].

За свою карьеру в IBM Хоффман опубликовал более 200 научных работ, более трети из них в соавторстве. Его математический диапазон охватывал множество областей математики, от алгебры до исследования операций^[2].

Краткое изложение математических вкладов (из его заметок в Selected Papers of Alan Hoffman)^[4].

Работа Гофмана по геометрии, начиная с его диссертации «Об основаниях инверсионной геометрии», включала в себя доказательства свойств аффинных плоскостей, а также изучение точек соотношения конечных проективных плоскостей, условий на закономерности объединения и пересечения конусов (выведенных во многом из его обобщения его более ранних результатов о ранге вещественных матриц). Он представил альтернативное доказательство, основанное на аксиомах для некоторых абстрактных систем выпуклых множеств, результата (Скарфа и других) о количестве неравенств, необходимых для определения решения задачи целочисленного программирования. Теорема об этой абстрактной системе, по-видимому, тесно связана с антиматроидами (также известными как выпуклые геометрии), хотя связь не была полностью исследована.

Работа Хоффмана по комбинаторике расширила наше понимание нескольких классов графов. Лекция 1956 года Г. Хайоса об интервальных графах привела к характеристике Хоффманом графов сопоставимости, а позже, благодаря сотрудничеству с Полом Гилмором, к теореме GH (также приписываемой А. Гуиа-Ури). Вдохновленный алгоритмом сопоставления Эдмонда, Хоффман сотрудничал с Рэем Фулкерсоном и М. МакЭндрю Хоффманом, чтобы охарактеризовать наборы целых чисел, которые могли бы соответствовать степеням и границам для каждой пары вершин такого графа. Кроме того, они рассмотрели, какие графы в классе всех графов, имеющих заданный набор степеней и границ количества ребер, могут быть преобразованы с помощью определенного набора обменов в любой другой набор в классе. Доказательства тесно связаны с важным понятием базиса Гильберта. Статья о самоортогональных латинских квадратах, написанная совместно с соавторами IBM Доном Копперсмитом и Р. Брайтоном, была вдохновлена просьбой запланировать супругу, избегающую смешанных парных турниров, для местного ракеточного клуба. Она отличается тем, что является единственной статьей, которую Хоффман обсуждал за пределами математического сообщества.

Частично упорядоченные множества были частой темой изучения Хоффмана. В статье 1977 года с Д. Е. Шварцем двойственность линейного программирования используется для обобщения обобщения Грином и Клейтманом 1976 года теоремы Дилуорта о разложении частично упорядоченных множеств, что является еще одним примером объединяющей роли, которую двойственность играет во многих комбинаторных результатах.

На протяжении всей своей карьеры Хоффман искал простые и элегантные альтернативные доказательства установленных теорем. Эти альтернативные доказательства часто приводили к обобщениям и расширениям. В конце 1990-х он сотрудничал с Цао, Хваталом и Винсом, чтобы разработать альтернативное доказательство, используя элементарные методы, а не линейную алгебру или теорему Райзера о квадратных матрицах 0-1.

Работа Хоффмана о матричных неравенствах и собственных значениях является основой любого курса по теории матриц. Особое очарование, в соответствии с его любовью к унификации подходов, представляет его статья 1975 года о линейных G-функциях. Хотя доказательство указанной вариации Гершгорина длиннее и сложнее других, оно охватывает все вариации Островского и многие дополнительные вариации как частные случаи.

Хоффман был воодушевляющим старейшиной, но не принимал активного участия в разработке IBM ряда продуктов для линейного и целочисленного программирования. Однако он продолжал исследования комбинаторных и алгебраических аспектов линейного программирования и линейных неравенств, включая восхитительную абстракцию двойственности линейного программирования (1963). Он также продолжал использовать свойства линейных неравенств для доказательства (или более элегантного повторного доказательства) результатов о выпуклости.

В сотрудничестве с Шмуэлем Виноградом, также сотрудником IBM в отделе математики, был разработан эффективный алгоритм для нахождения всех кратчайших расстояний в направленной сети с использованием псевдоумножения матриц. Серия статей о решетчатых многогранниках (некоторые с Доном Швартсом) ввела понятие решетчатых многогранников, что привело к еще одному примеру комбинаторной двойственности.

После сотрудничества с Рэем Фулкерсоном и Розой Оппенгейм над сбалансированными матрицами Хоффман обобщил результат Форда-Фалкерсона о максимальном потоке — минимальном разрезе на другие случаи (поток в узлах, ненаправленные дуги и т. д.), предоставив доказательство того, что все ранее известные случаи были Особые случаи. В этой статье также введена концепция (но опять же, не название) полной двойственной целочисленности, идея, стоящая за большинством применений линейного программирования для доказательства экстремальных комбинаторных теорем.

На протяжении своей карьеры Хоффман изучал класс задач целочисленного программирования, которые можно было решить, последовательно максимизируя переменные в некотором порядке. Одним из таких примеров является полная транспортная задача в случае, когда коэффициент стоимости демонстрирует особое свойство, открытое более века назад французским математиком Гаспаром Монжем. Этот подход, названный в статье Хоффмана просто «простым», позднее Эдмондс и Фулкерсон сочли «жадным». Свойство Монжа порождает антиматроид, и благодаря использованию этого антиматроида результат Хоффмана легко распространяется на случай неполных транспортных задач. Хоффман повторно использовал термин «жадный» для описания подкласса матриц 0-1, для которых двойственная линейная программа может быть решена жадным алгоритмом для всех правых частей и всех целевых функций с убывающими (по переменному индексу) коэффициентами. . Вместе с Коленом и Сакаровичем он показал, что для этих матриц соответствующая целочисленная программа имеет целочисленное оптимальное решение для целочисленных данных. Элегантная и краткая статья 1992 года дает характеристику матриц 0-1, для которых задачи упаковки и покрытия могут быть решены с помощью жадного подхода. Он обеспечивает унификацию результатов для задач поиска кратчайшего пути и минимального остовного дерева. Его заключительная статья на эту тему «О жадных алгоритмах, частично упорядоченных множествах и субмодулярных функциях», написанная в соавторстве с Дитрихом, появилась в 2003 году.

Хоффман совместно с Робертом Синглтоном построил граф Хоффмана — Синглтона^[5], который является уникальным графом Мура степени 7 и диаметра 2^[3]. В 1963 году он построил Граф Хоффмана, который хотя и коспектрален графу четырёхмерного гиперкуба Q₄^[6], но радиус которого равен 3 (есть такие вершины, кратчайший путь из которых в любую другую вершину графа состоит из не более чем трёх рёбер), в то время как радиус графа гиперкуба Q₄ равен 4^[7].

Хоффман был избран в Национальную академию наук в 1982 году^[1], в Американскую академию искусств и наук в 1987 году^[1] и в первый состав членов Института исследования операций и наук управления (INFORMS)^[англ.] в 2002 году^[8]. В 1992 году вместе с Филиппом Вулфом (тоже из IBM) он был награжден теоретической премией Джона фон Неймана^[1]. Почётный доктор наук Техниона (Израильского технологического института) с 1986 года.

За свою долгую карьеру Хоффман входил в редакцию одиннадцати журналов и был редактором и основателем журнала англ. Linear Algebra and its Applications^[1]. В биографии, опубликованной в выпуске, посвященном 65-и летию Хоффмана, Уриэль Ротблюм^[англ.] написал, что «Помимо его научных и профессиональных достижений, Хоффман обладает беспрецедентной способностью получать удовольствие от всего, что он делает. Он любит петь, играть в пинг-понг, каламбуры, остроумные истории и, возможно, больше всего на свете — заниматься математикой»^[2].

• Hoffman A. J., Jacobs W. Smooth patterns of production (англ.) // Management Science. — 1954. — Vol. 1, iss. 1. — P. 86–91.
• Hoffman, A. J., Singleton, R. R. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вып. 4. — С. 497–504. — doi:10.1147/rd.45.0497.
• Hoffman A. J. On the Polynomial of a Graph (англ.) // Amer. Math. Monthly. — 1963. — Vol. 70. — P. 30—36.
• Hoffman A. J., Wolfe P. History of Traveling Salesman problem // The Traveling Salesman Problem (англ.) / Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., & Shmoys D. B., eds. — John Wiley, 1985.

Полный список публикаций приведён на персональной странице^[1].