Как алгебраическая геометрия помогла решить гипотезу из теории графов. О работах Джуна Ха


Джун Ха. Фото Lance Murphey
Джун Ха. Фото Lance Murphey
Ярослав Хроменков
Ярослав Хроменков

Одним из лауреатов Филдсовской премии в 2022 году стал Джун Ха, профессор Принстонского университета. Премия была выдана за решение серии гипотез из комбинаторики методами, основанными на идеях из алгебраической геометрии. Утверждения гипотез имеют элементарные формулировки и в простейшей своей форме могут быть поняты школьником. Тем интереснее, что для доказательства требуются техники из крайне абстрактных и сложных современных разделов математики.

Подобных теорем, конечно, немало в математике. Больше всего этим, пожалуй, славится теория чисел. Самый известный пример — это великая теорема Ферма. Решение школьной по формулировке задачи требует применения крайне сложных методов из алгебры и геометрии, причем эти методы являются частью единой теории, которая связана с самыми разными областями математики. Джеймс Мейнард, другой лауреат Филдсовской премии этого года, также известен доказательством крайне простых по формулировке теорем из теории чисел, которые при этом требуют применения сложных техник из разных областей математики.

В комбинаторике же сложных теорем с простой формулировкой в достатке, но их решения не слишком часто приводят к появлению больших теорий, которые объединяют различные разделы математики. В некотором смысле решения тоже оказываются «элементарными». Работы Ха являются очень ярким исключением. Например, в [1] для решения комбинаторной задачи критичными оказываются теория превратных пучков и теорема о разложении Бейлинсона — Бернштейна — Делиня [2], сложные и глубокие результаты из совершенно отличной от комбинаторики области. Более того, опираясь на результаты из алгебраической геометрии, Ха строит комбинаторную теорию, которая объединяет казавшиеся ранее разнородными методы и крайне интересна для изучения сама по себе.

Творческий путь Джуна Ха был необычен. В школе он получал плохие оценки по математике, а в университете хотел стать журналистом. Но знакомство с математиком Хэйсукэ Хиронакой зародило в Ха интерес к этой науке. Закончив магистратуру Сеульского университета и прослушав всего несколько математических курсов на тот момент, Ха решил поступить в аспирантуру по математике. В большинстве университетов посчитали недостаточным математический опыт Ха, только Иллинойсский университет в Урбане-Шампейне принял Ха в свою аспирантуру. Но из-за нестандартного математического образования у Ха было гораздо меньше стереотипов о границах разделов математики, и можно предположить, что в том числе и поэтому Ха удалось увидеть связь между столь различными областями математики и решить казавшиеся раннее неприступными задачи.

В этой заметке мы расскажем о некоторых результатах Джуна Ха и хотя бы на примерах попытаемся объяснить, как алгебраическая геометрия помогает при доказательстве результатов из комбинаторики.

Неравенства в комбинаторике и раскраски графов

Гипотезы, доказанные Ха, представляют собой комбинаторные неравенства. То есть необходимо доказать, что некоторое комбинаторно определенное число M не превосходит другое комбинаторно определенное число N.

Например, пусть мы выбрали несколько точек на плоскости так, что не все точки лежат на одной прямой. Если M — это количество выбранных точек, а N — количество различных прямых, проходящих через пары выбранных точек, то верно, что M N.

Сформулированное только что неравенство является теоремой де Брёйна — Эрдёша и частным случаем гипотезы Доулинга — Уилсона, которую доказали Ха и Ван в [1]. Впрочем, особенно часто в комбинаторике возникает не просто два изолированных числа, а сразу последовательность чисел. И для таких последовательностей необычайно часто выполняется следующая серия неравенств специального вида.

Определение 1. Последовательность вещественных чисел a0, a1,…, an называется унимодальной, если для некоторого 0 ≤ i ≤ n выполняются неравенства

$$a_0 \le a_1 \le … \le a_i \ge a_{i+1} \ge a_{i+2} … \ge a_{n}.$$

Последовательность вещественных чисел a0, a1,…, an называется лог-вогнутой, если для любого 1 ≤ j ≤ n–1 выполняются неравенства aj-1aj+1 ≤ aj2. Несложно показать, что для последовательностей положительных чисел унимодальность является следствием лог-вогнутости.

Очень большое количество последовательностей в комбинаторике почему-то оказываются унимодальными и даже лог-вогнутыми. Также очень часто эта последовательность обладает симметрией относительно i из определения. Вот некоторое количество примеров.

Пример 1. Для фиксированного n последовательность биномиальных коэффициентов

$$a_k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$

является унимодальной, лог-вогнутой и симметричной.

Пример 2. Для фиксированных n и q > 0 последовательность q–биномиальных коэффициентов

$$a_k = \binom{n}{k}_{q} = \frac{(1-q^n)(1-q^{n-1})…(1-q^{n-k+1})}{(1-q)(1-q^2)…(1-q^k)}$$

является унимодальной, лог-вогнутой и симметричной.

Первые два примера — это простые упражнения, унимодальность и лог-вогнутость можно вывести алгебраически из приведенных формул. В первом примере ak равно количеству k–элементных подмножеств {1, 2, …, n}, поэтому интересной головоломкой является задача привести комбинаторные доказательства унимодальности и лог-вогнутости, т. е. не использующие явную алгебраическую формулу. Решение можно подсмотреть в [3].

Пример 3. Для фиксированных n и k можно показать, что q–биномиальный коэффициент является многочленом от q

$$\binom{n}{k}_{q} = a_0 + a_1q + a_2q^2 +… + a_nq^{n(n-k)}.$$

Последовательность коэффициентов ak является унимодальной и симметричной (но не обязательно лог-вогнутой).

Третий пример уже совершенно нетривиален. Унимодальность приведенной последовательности была сформулирована как гипотеза Кэли в 1856 году, а впервые доказана Сильвестром в 1878-м в [12]. Одно из более современных доказательств (и ссылки на несколько других) есть в [7].

Для последнего примера нам понадобится определение хроматического многочлена графа.

Определение 2. Правильной раскраской графа G в t цветов называется сопоставление каждой вершине графа G одного из t цветов так, что если две вершины соединены ребром, то им сопоставлены разные цвета. Количество правильных раскрасок G в t цветов будем обозначать χG(t).

Функция χG(t) называется хроматическим многочленом графа G. Тот факт, что это действительно многочлен от t, является несложной теоремой. Также несложно заметить, что свободный член χG(t) равен нулю.

Давайте посчитаем хроматический многочлен в нескольких простых примерах. Пусть в графе G четыре вершины. Первая соединена со второй, вторая с третьей, а третья с четвертой.

У нас есть t способов покрасить первую вершину. После выбора цвета для первой вершины у нас останется t–1 вариантов цвета для второй вершины, так как первая и вторая вершины должны быть покрашены в разные цвета. После выбора цвета для первых двух вершин у нас будет снова t–1 вариантов для цвета третьей вершины, так как третья вершина должна быть покрашена в цвет, отличный от цвета второй (но при этом может быть того же цвета, что и первая, поэтому вариантов t–1, а не t–2). Аналогично у нас останется t–1 вариантов для цвета четвертой вершины. Получаем, что в данном случае

$$\chi_G(t) = t(t-1)(t-1)(t-1) = -t + 3t^2 – 3t^3 + t^4$$

Но что, если теперь первая вершина соединена с четвертой?

В таком случае нам запрещено красить первую и четвертую вершину в один цвет. Так что из полученного раннего ответа нужно вычесть количество раскрасок, в которых для первой и четвертой вершины выбран один цвет. Несложно проверить, что таких раскрасок всего t(t–1)(t–2). Получаем, что

$$\chi_G(t) = t(t-1)(t-1)(t-1) – t(t-1)(t-2) = -3t + 6t^2 – 4t^3 + t^4$$

На самом деле мы здесь, по сути, применили формулу удаления — стягивания

$$\chi_G(t) = \chi_{G \setminus uv}(t) – \chi_{G/uv}(t)$$

где Guv — это граф, получающийся из G выкидыванием ребра uv, а G/uv — это граф, в котором ребро uv стянули.

Пример 4 (Гипотеза Рида). Рассмотрим для графа G хроматический многочлен

$$\chi_G(t) = a_1t + a_2t^2 + … + a_nt^n.$$

Коэффициенты ak образуют лог-вогнутую последовательность (но не обязательно симметричную). В данном случае знаки ai чередуются, поэтому унимодальной является последовательность абсолютных значений |ak|.

Унимодальность последовательности абсолютных значений коэффициентов хроматического многочлена была сформулирована как гипотеза Ридом в 1968 году, а доказательство впервые было получено Ха во время обучения в аспирантуре в [5]. Основываясь на этой работе Ха, Кац и Адипрасито положили начало комбинаторной теории Ходжа в [6] и доказали более общую гипотезу Херона — Роты — Уэлша, в которой вместо графа рассматривается произвольный матроид.

Матроиды — это комбинаторный объект, который обобщает идею независимости конечных наборов векторов. Матроид состоит из конечного множества E и некоторого множества подмножеств E, которые называются независимыми и должны удовлетворять ряду аксиом. По графу можно построить матроид на множестве его ребер. Набор ребер графа объявляется независимым, если он не содержит циклов.

Матроиды, например, интересны тем, что для них жадные алгоритмы дают оптимальный ответ. В случае матроидов, построенных по графам, мы получаем, что остовное дерево минимального веса для графа можно строить, выбирая на каждом шаге алгоритма минимальное по весу ребро, не создающее цикла. Для матроидов можно определить аналог хроматического многочлена. Гипотеза Херона — Роты — Уэлша утверждает, что коэффициенты хроматического многочлена матроида образуют лог-вогнутую последовательность.

Также следует упомянуть сильную гипотезу Мейсона, которая недавно была доказана различными методами в [11] и [10].

Пример 5. (Cильная гипотеза Мейсона). Для матроида M на множестве из n элементов определим Ik как количество независимых множеств из k элементов. Последовательность Ik является унимодальной и лог-вогнутой (но не симметричной). В данном случае также выполняются более сильные неравенства

$$I_{j-1}I_{j+1}(1 + \frac{1}{j})(1 + \frac{1}{n-j}) \le I_j^2.$$

Множество классических примеров унимодальных и лог-вогнутых последовательностей в комбинаторике приводит Стэнли в обзоре [7]. До некоторой степени удивительно, что столь многие последовательности в комбинаторике являются лог-вогнутыми. Оказывается, это не совпадение, большое количество неравенств в комбинаторике могут быть объяснены в рамках одной теории, которая основывается на неравенствах из алгебраической геометрии.

Унимодальность и лог-вогнутость в геометрии

Если мы хотим доказать, что некоторая симметричная последовательность в комбинаторике унимодальна (что слабее, чем лог-вогнутость), то можно обойтись лишь частью идей, которые использовал Ха в своих доказательствах. Такие применения были известны уже в конце XX века (см. [7]). Оказывается, симметричные унимодальные последовательности возникают в алгебраической геометрии — на первый взгляд, очень далеком от комбинаторики разделе математики.

Грубо говоря, алгебраическая геометрия занимается изучением форм, заданных системой алгебраических уравнений. Такие объекты называются алгебраическими многообразиями. Например, множество решений x2 + y2 + z2 = 1 (вещественные решения образуют сферу), а также квадрики из курса линейной алгебры. Возможно, читатель слышал об эллиптических кривых — они также являются алгебраическими многообразиями и изучаются в рамках алгебраической геометрии.

Каждому алгебраическому многообразию X можно сопоставить последовательность чисел Бетти

$$\beta_0(X), \beta_1(X), …, \beta_m(X).$$

Определение чисел Бетти для более общего класса геометрических объектов принадлежит топологии, еще одной современной области математики. Если X — алгебраическое многообразие, удовлетворяющее ряду геометрических свойств, то оно называется гладким проективным многообразием. В таком случае верно, что последовательности чисел Бетти

$$\beta_0(X), \beta_2(X), \beta_4(X), …, \beta_{2n}(X)$$

$$\beta_1(X), \beta_3(X), …, \beta_{2n-1}(X)$$

являются симметричными и унимодальными!

Симметричность является следствием двойственности Пуанкаре. Унимодальность же следует из сложной теоремы Лефшеца. Двойственность Пуанкаре и сложная теорема Лефшеца — это фундаментальные теоремы о том, как геометрически устроены гладкие проективные многообразия.

Поэтому теперь естественно возникает идея доказательства, что некоторая последовательность a0, a1,…, an является симметричной и унимодальной. Для этого достаточно построить такое гладкое проективное многообразие X, что β2i(X) = ai. Уже этой идеи достаточно, чтобы показать множество интересных теорем из комбинаторики (см. [7]). Разумеется, построить — совершенно не тривиальная задача, мы должны каким-то образом закодировать комбинаторную информацию в геометрии. Но так, например, можно доказать неочевидный пример с q-биномиальными коэффициентами. В данном случае в качестве геометрического объекта нужно взять многообразие Грассманна. Используя похожую идею в особенно сложном случае (и с использованием теории Горески — Макферсона), Стэнли доказал ряд гипотез о многогранниках (см. [7]).

Но гипотезу Херона — Роты — Уэлша так доказать не получится. Действительно, соответствующие последовательности даже не симметричны, а потому не могут быть буквально числами Бетти некоторого гладкого проективного многообразия. Также такой метод даже в случае симметричной последовательности позволяет доказывать лишь унимодальность, а не лог-вогнутость.

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

Соотношения Ходжа — Римана — это ряд неравенств на аналоги количеств точек пересечения геометрических фигур с определенными свойствами. Вместе с двойственностью Пуанкаре и сложной теоремой Лефшеца они образуют набор утверждений, называемый набором Кэлера. В [4] Ха и Кац используют неравенство Хованского — Теиссиера, которое является следствием соотношений Ходжа — Римана, чтобы доказать гипотезу Херона — Роты — Уэлша для представимых матроидов. Для этого им, в частности, необходимо было для каждого графа G построить такое гладкое проективное многообразие, что из его геометрии извлекается хроматический многочлен G.

Комбинаторная теория Ходжа

Для непредставимых матроидов гипотезу Херона — Роты — Уэлша доказали Ха, Кац и Адипрасито позднее в [6]. Основной проблемой в случае непредставимых матроидов является то, что не получается построить алгебраическое многообразие с нужными свойствами, к которому можно применить всю мощь существующих в алгебраической геометрии утверждений из набора Кэлера.

Но оказывается, что можно развить теорию, которая вдохновляется геометрическими результатами, но не использует их прямым образом. Для матроидов тоже существует набор утверждений, являющийся аналогом набора Кэлера в геометрии. Построенная теория называется комбинаторной теорией Ходжа для матроидов и формально независима от теории Ходжа для многообразий. Следует пояснить, что даже правильная формулировка аналогов соотношений Ходжа — Римана не тривиальна, в данном случае изначально геометрическая теория удивительным образом находит отражение в комбинаторике.

Сейчас идут активные исследования в комбинаторной теории Ходжа. Оказывается, что многие интересные эффекты в комбинаторике, которые казались очень разнородными, находят единое объяснение в рамках комбинаторной теории Ходжа. Также теория достаточно богата, чтобы в ней каждый день появлялись новые конструкции и определения (которые сразу же находят конкретные комбинаторные применения). Например, в [8] строится модуль когомологий пересечения для матроидов, а в [9] изучаются тавтологические классы матроидов. Похоже, что благодаря работам Ха появилась новая область математики, работа в которой пока далека от завершения.

Ярослав Хроменков,
аспирант Северо-Западного университета (штат Иллинойс, США)

1. Huh J., and Wang B. Enumeration of points, lines, planes, etc. // Acta Mathematica 218.2 (2017): 297–317.

2. Deligne P., Beilinson A., and Bernstein J. Faisceaux pervers. Astérisque 100 (1983).

3. Sagan B. E. Inductive and injective proofs of log concavity results // Discrete mathematics 68.2–3 (1988): 281–292.

4. Huh J., and Katz E. Log-concavity of characteristic polynomials and the Bergman fan of matroids // Mathematische Annalen 354.3 (2012): 1103–1116.

5. Huh J. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs // J. Amer. Math. Soc.

6. Adiprasito K., Huh J., and Katz E. Hodge theory for combinatorial geometries // Annals of Mathematics 188.2 (2018): 381–452.

7. Stanley R. P. Log-concave and unimodal sequences in algebra, combinatorics, and geometry // Ann. New York Acad. Sci 576.1 (1989): 500–535.

8. Braden T., Huh J., Matherne J. P., Proudfoot N., and Wang B. Singular Hodge theory for combinatorial geometries. arXiv preprint arXiv:2010.06088 (2020).

9. Berget A., Eur C., Spink H., and Tseng D. Tautological classes of matroids. arXiv preprint arXiv:2103.08021 (2021).

10. Anari N., Liu K., Gharan S. O., and Vinzant C. Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids. arXiv preprint arXiv: 1811.01600 (2018).

11. Brändén P., and Huh J. Lorentzian polynomials // Annals of Mathematics 192.3 (2020): 821–891.

12. Sylvester J. J. XXV. Proof of the hitherto undemonstrated fundamental theorem of invariants // The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 5.30 (1878): 178–188.

Подписаться
Уведомление о
guest

0 Комментария(-ев)
Встроенные отзывы
Посмотреть все комментарии
Оценить: 
Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (2 оценок, среднее: 4,50 из 5)
Загрузка...