Есть одна классная штука: гипотеза Хоггара (Роты-Уэлша-Герона). Элементарно формулируется и доказана несколько лет назад с помощью адского ада. Обычно во всяких популяризаторских сми особенно гремят результаты в теории чисел - там формулировки понятны школьнику, а доказательства - хорошо если специалист за полгода разберется. В комбинаторике подобного добра тоже хватает, но ее меньше жалуют по непонятным мне причинам (вообще, многие не воспринимают комбинаторику всерьез - это они зря). Короче, мне нравится комба, не нравится тч, пишу про комбу.
Хроматические многочлены.
Пусть Г - граф. Рассмотрим функцию P(q), значение которой на натуральном числе q равно числу правильных раскрасок вершин графа Г в q цветов (имеется в виду, что у нас есть q красок, но не обязательно их все использовать). Напомню, что раскраска называется правильной, если концы каждого ребра графа покрашены в различные цвета.
Можно показать (и это хорошее упражнение), что P(q) - многочлен от q. Он называется хроматическим многочленом графа Г.
Пример: сколько способов покрасить путь из 3 вершин в q цветов? Для первой вершины есть q вариантов выбора цвета, для второй: q-1 (т.к. цвет первой вершины уже нельзя использовать), для третьей тоже q-1. В итоге хроматический многочлен = q(q-1)^2.
Для пути из n вершин по тем же причинам получится q(q-1)^{n-1}.
И такой же ответ получается для любого дерева на n вершинах (упражнение).
Пример еще: для полного графа на n вершинах получаем P(q)=q(q-1)(q-2)...(q-n+1), поскольку первую вершину можно покрасить в q цветов, вторую в q-1, третью в q-2 и т.д.
Изначально эту штуку ввели в связи с попыткой доказать тогда-еще-гипотезу четырех красок. Хроматическое число графа, т.е. наименьшее число цветов, в которые можно правильно покрасить вершины графа, очевидным образом извлекается из хроматического многочлена - это просто наименьшее натуральное число, не являющееся его корнем. В те далекие времена было убеждение, что исследуя вместо хроматического числа хроматический многочлен, можно будет как-то воспользоваться матаном для доказательства гипотезы 4-х красок. Программа не выгорела, но хроматический многочлен остался.
У любого многочлена есть коэффициенты: P(q)=a_n q^n+a_{n-1} q^{n-1}+...+a_1q+a_0. Известно (это уже посложнее, называется теоремой Роты), что у коэффициентов хроматического многочлена чередуются знаки: при старшей степени стоит положительный коэффициент (на самом деле a_n=1 всегда), при следующем члене отрицательный, и так далее.
Гипотеза Хоггара утверждает, что, если взять у всех коэффициентов модули, то каждый коэффициент не меньше среднего геометрического своих соседей. По-другому:
(a_i)^2 больше или равно a_{i-1}a_{i+1} для всех i.
Такое свойство последовательности чисел называется логарифмической вогнутостью (ратую за введение термина логнутость).
Вот например, для полного графа получается многочлен q(q-1)...(q-n+1). Его коэффициенты называются числами Стирлинга первого рода. Они логнутостью обладают (хотя даже это не очевидно).
А для дерева получаются биномиальные коэффициенты - они тоже логнутые.
Гипотезу Хоггара недавно доказал американец June Huh. На самом деле он доказал также более общее утверждение - про характеристический многочлен представимого матроида.
(*Не знаю, как правильно читать фамилию этого чувака. Если считать, что он кореец, то она должна читаться как Ха. Знакомый американец называл его Хью, но, кажется, не был до конца уверен, что это правильно)
Матроиды.
Пусть фиксировано конечное множество [m]={1,2,...,m}. Симплициальным комплексом называется любой набор подмножеств множества [m], который вместе с множеством A содержит также и все его подмножества.
Например, на множестве [4]={1,2,3,4} можно рассмотреть такой симплициальный комплекс {пустое множество, {1},{2},{3},{4},{1,2},{1,3},{2,3},{2,4},{3,4},{1,2,3}}. Можно представлять себе симплициальный комплекс геометрически: для каждого одноэлементного подмножества рисуем точку, для каждого двухэлементного {a,b} рисуем отрезок между a и b, для каждого трехэлементного {a,b,c} рисуем треугольник между точками a,b,c, и т.д. Подмножества симплициального комплекса называются симплексами.
Матроид - это симплициальный комплекс K с дополнительным свойством. Это называется свойством обмена: если А, B - два симплекса K, и в B больше элементов, чем в А, то какой-то из элементов B, скажем b, можно перекинуть в А. То есть b не лежит в А, и А вместе с b - это снова симплекс K. На матроидном языке симплексы называются независимыми множествами.
Надои молока.
Я фермер, и я хочу прикупить себе коров. У продавца есть m коров, но всех сразу он не готов продать. Зато у него есть перечень, какие наборы коров он может продать. Допустим, что продавец адекватный: если он готов продать некое множество коров, то он также готов продать и любое его подмножество. Это означает, что у продавца есть симплициальный комплекс, кодирующий, какие совокупности коров он готов продать.
Допустим, известно, сколько литров молока в день дает каждая из коров (в удивительном мире математики это число может быть отрицательным). Моя задача - подобрать себе такое стадо, из числа предлагаемых продавцом, чтобы суммарно оно давало наибольший профит.
Для решения этой задачи я, как человек простой, воспользуюсь жадным алгоритмом. Это означает следующее. Я выберу самую жирную корову, из тех что предлагает продавец. Потом я попрошу у продавца список всех коров, которые он готов дать в довесок к первой, и выберу из них самую жирную. Потом я спрошу, что он готов дать в довесок к двум выбранным ранее, и выберу из них самую жирную. И так далее, пока продавец не пошлет меня к черту.
Понятно, что жадный алгоритм не всегда дает оптимальный ответ (есть в этом какой-то морально-философский смысл). Например, продавец готов продать корову 1 жирности 10 и коров {2,3} в совокупности, каждая жирности 9. По жадному алгоритму я отхвачу одну жирную, и больше мне ничего не светит. А мог бы взять 2-ую и 3-ю и поиметь гораздо больший профит. Увы.
Матроиды - это в точности те симплициальные комплексы, для которых жадный алгоритм дает верный ответ (независимо от предписанных жирностей коров). Свойство обмена как раз гарантирует, что я получу оптимальное стадо.
Откуда брать матроиды - фермерам на заметку.
Пусть есть граф Г с m ребрами (возможны петли и кратные ребра). Рассмотрим симплициальный комплекс, у которого вершины - это ребра Г, а симплексы - это наборы ребер, образующие лес. Упражнение: такой симплициальный комплекс является матроидом. Матроиды, получающиеся таким образом, называются графическими матроидами.
Пусть есть последовательность векторов v1,...,vm в векторном пространстве над произвольным полем F (допускаются нулевые векторы, допускаются повторы). Рассмотрим симплициальный комплекс, у которого вершины - это векторы v1,...,vm, а симплексы - это линейно независимые наборы векторов. Упражнение: такой симплициальный комплекс является матроидом. Матроиды, полученные таким образом, называются представимыми над полем F. Вся матроидная терминология мотивирована этим классом примеров: именно в связи с линейной алгеброй независимые множества матроида называются независимыми множествами, и отсюда же проистекает созвучие слов матроид и матрица.
Упражнение: графический матроид представим над любым полем. Это классное упражнение, поверьте.
Бывают матроиды, непредставимые ни над каким полем. Их вроде даже много, но это - экзотика (типа триангулированных сфер, не представимых как граница выпуклого симплициального многогранника, которых тоже дофига, но они менее интересны, чем многогранники).
Замечание. Классный факт: если смотреть на матроид как на топологическое пространство (т.е. взять геометрическую реализацию его как симплициального комплекса), то он ацикличен во всех размерностях, кроме старшей. Например, можно взять все ненулевые трехмерные векторы над полем из двух элементов и рассмотреть соответствующий представимый матроид. У него 7 вершин, а треугольники натянуты на те вершины, для которых соответствующие векторы образуют базис. Такой комплекс гомотопен букету из 13 двумерных сфер.
Короче говоря, все матроиды являются комплексами Коэна-Маколея.
Характеристический многочлен матроида.
Можно определить такую штуку как характеристический многочлен матроида (отсылаю к https://en.wikipedia.org/wiki/Matroid ибо тут формулы смотрятся погано). Для графических матроидов - это то же, что и хроматический многочлен с точностью до всяких мелочей.
Характеристический многочлен уже никакие раскраски не считает (хотя у меня были соображения, что для некоторых специальных матроидов он таки считает инвариант Бухштабера из нашей науки, правда, так и не опубликованные).
Коэффициенты характеристического многочлена
тоже знакопеременны. И, предположительно, образуют логнутую последовательность. Это гипотеза Роты-Уэлша-Герона, обобщающая гипотезу Хоггара про хроматический многочлен графа. Huh доказал гипотезу для представимых матроидов.
Пермутоэдрическое многообразие и представимые классы.
n-мерный пермутоэдр - это выпуклая оболочка точек, координаты которых - все возможные перестановки чисел 0,1,2,...,n. Это простой многогранник: у него каждая вершина содержится ровно в n гипергранях. Нормальный веер к пермутоэдру совпадает с совокупностью камер Вейля для системы корней A_n. Гладкое проективное торическое многообразие X_n, соответствующее пермутоэдру называется пермутоэдрическим многообразием.
Huh заметил, что любой матроид (в том числе и непредставимый), имеющий n вершин и ранг r+1, задает некий класс 2r-мерных гомологий пермутоэдрического многообразия X_n. Эта конструкция основана на понятии веера Бергмана - штуки из тропической геометрии (грубо говоря, веер Бергмана - это тропикализация линейного подпространства в алгебраическом торе).
Оказалось, что если матроид представимый, то соответствующий ему гомологический класс является фундаментальным классом алгебраического подмногообразия в пермутоэдрическом многообразии. Причем это все имеет смысл над произвольным полем F, только тогда надо рассматривать не обычные (ко)гомологии, а кольца Чжоу вместо когомологий и классы численно эквивалентных циклов вместо гомологий. Имхо, это клево, посколько раньше я не видел никакого особенного профита от торических многообразий над полями конечной характеристики.
Дальше можно заметить, что пермутоэдр можно выродить до симплекса двумя различными способами. Каждый из способов дает бирациональную эквивалентность (последовательность сдутий) из пермутоэдрического многообразия в проективное пространство P^n. Склеив эти два отображения в одно, получим отображение f из пермутоэдрического многообразия в P^n x P^n.
Любой гомологический класс пермутоэдрического многообразия можно индуцированным отображением f_* зашвырнуть в гомологии P^n x P^n. Любой 2r-мерный класс гомологий в P^n x P^n имеет вид
A=a_r[P^r x P^0]+a_{r-1}[P^{r-1} x P^1]+...+a_0[P^0 x P^r]
т.е. определяется последовательностью целых чисел a_i. Оказывается, если пнуть класс матроида из гомологий пермутоэдрического многообразия в гомологии P^n x P^n, то полученная последовательность коэффициентов a_i - это в точности модули коэффициентов характеристического многочлена матроида.
И теперь катарсис. Huh доказал, что если цикл A в H_*(P^n x P^n) представим алгебраическим подмногообразием, то его коэффициенты a_i образуют логнутую последовательность. Это утверждение как-то хитро выводится из выпуклой геометрии: к чему-то (я пока не понял, к чему) применяется конструкция тел Ньютона-Окунькова, и для них используется неравенство Брунна-Минковского.
Для меня эта штука - пока единственное убедительное доказательство реальной пользы от тел Ньютона-Окунькова. Надо разбираться, короче.
Собирая все воедино, получаем то, что надо. Если матроид представимый, то его гомологический класс в пермутоэдрическом многообразии представим алгебраическим подмногообразием, значит, если его отправить в гомологии P^n x P^n, то получится тоже представимый класс, значит коэффициенты последнего, которые суть коэффициенты характеристического многочлена, образуют логнутую последовательность.
Если чуваку, который все это придумал, не дадут Филдса, то это будет совсем печально. Вот его хоумпейдж https://web.math.princeton.edu/~huh/
Комментариев нет:
Отправить комментарий