Прочитал тут про еще одно красивое приложение эквивариантной топологии в теоретической информатике. Кому не терпится до сути, то вот прошу, а я напишу, каким боком там топология в меру своего понимания. Довольно длинно получилось, но будем надеяться, что все, кого это смущает, от меня отписались.
Пусть есть некоторое конечное множество M. Свойством подмножеств в M будем называть произвольную булеву функцию f из множества подмножеств 2^M множества M в {0,1}. Если f(I)=1 для подмножества I, то говорим, что I обладает свойством f. Понятно, что свойство f можно отождествить с подмножеством K булева куба - совокупностью всех подмножеств, обладающих свойством f.
Назовем свойство f монотонным (вниз), если из условия, что I обладает свойством f следует, что любое подмножество множества I тоже обладает свойством f. По определению, это означает, что соответствующая совокупность K элементов булева куба является симплициальным комплексом. Поэтому монотонные вниз свойства - это то же самое, что симплициальные комплексы.
Теперь рассмотрим такую задачу. У Алисы есть симплициальный комплекс K. Борис загадывает какое-то подмножество I вершин симплициального комплекса, а задача Алисы - угадать, является ли загаданное множество симплексом комплекса K (т.е. обладает ли загаданное подмножество I нужным Алисе монотонным свойством). Для этого Алиса может задавать Борису вопросы вида "верно ли, что i лежит в I?" для какой-то вершины i из множества M. Более формально, у Алисы должно быть разрешающее бинарное дерево, в узлах которого задаются вопросы вида "iϵI?", а на листьях дается ответ "I - симплекс K" или "I - не симплекс K".
Цель Алисы: задать как можно меньше вопросов, чтобы точно определить, принадлежит ли борисово множество ее симплициальному комплексу. Понятно, что всегда можно задать m=|M| вопросов: попросту побитово выяснить, какое подмножество загадал Борис. Однако иногда можно задать мЕньшее число вопросов. Назовем симплициальный комплекс K простым, если Алиса может гарантированно решить задачу принадлежности, задав меньше чем m=|M| вопросов, т.е. представив разрешающее дерево высоты меньше m.
Пример простого комплекса на картинке. В случае объединения двух треугольников по общему ребру {2,3}, Алиса спрашивает Бориса: верно ли, что 1ϵI? Если нет, то Алиса сразу говорит, что IϵK. Если да, то Алиса спрашивает, верно ли, что 4ϵI? Если нет, то Алиса делает вывод, что IϵK. Если да, то получается, что обе вершины 1 и 4 принадлежат I, а значит I не может быть симплексом K. В итоге Алиса обходится всего двумя вопросами вместо четырех возможных.
Какие комплексы просты?
Пусть K - простой, тогда у Алисы есть разрешающее дерево высоты меньше m. Пусть "jϵI?" - первый вопрос в этом дереве. Если получен ответ "да", то соответствующее поддерево будет разрешающим деревом для комплекса link_K{j}, линка вершины j. Если получен ответ "нет", то соответствующее дерево будет разрешающим для комплекса K\{j} - полного подкомплекса на всех вершинах кроме j-й. И высота поддерева в обоих случаях меньше чем m-1, т.е. меньше чем число вершин в соответствующих комплексах. А это значит, что оба комплекса link_K{j} и K\{j} тоже являются простыми. Ну и, наконец, любой полный симплекс является простым комплексом: в этом случае Алиса говорит, что IϵK независимо от того, что за множество загадал Борис, Алисе вообще ни одного вопроса не надо задавать.
Получаем индуктивное определение простого комплекса:
(1) Полный симплекс - простой,
(2) Если прицепить к простому комплексу (то, что называлось K\{j}) конус вдоль простого подкомплекса (т.е. конус над link_K{j}), то получится простой комплекс.
Все простые комплексы получаются такой процедурой. Тут замята под ковер какая-то техническая возня с призрачными вершинами, но она из под ковра вынимается при желании.
А из такого определения легко доказать по индукции, что:
Любой простой комплекс - стягиваемый.
Ну действительно, любой симплекс стягиваем. Если прицепить к чему-то стягиваемому конус над чем-то стягиваемым, то получится что-то стягиваемое. На самом деле, можно доказать, что любой простой комплекс монотонно сдавливается до точки, и более того, этим же свойством обладает комплекс, комбинаторно двойственный к нему по Александеру. Если в этом покопаться, то получится, что класс простых комплексов строго меньше чем класс стягиваемых комплексов, но этот зазор не особо существенный как будто.
Получается, что если у комплекса есть нетривиальные топологические фичи, то он точно не может быть простым, а значит Алиса не может гарантированно угадать соответствующее свойство за менее чем m вопросов.
Абстрактные комплексы - это прекрасно, но давайте рассмотрим пример поконкретнее.
Рассмотрим все простые графы на 6 вершинах, и рассмотрим свойство планарности таких графов. Очевидно, что это свойство - монотонное вниз: если граф планарен, то и любой его подграф планарен. Граф задается множеством своих ребер, а потому в этом примере M состоит из 15 элементов - это все возможные пары из 6 вершин: каждая такая пара может либо быть ребром графа, либо не быть. В итоге свойство планарности кодируется некоторым симплициальным комплексом K(6,0) на 15 вершинах (6 означает, что мы взяли 6 вершин, 0 - это род 2-мерной сферы).
Что мы можем сказать про комплекс K(6,0)? Можно заметить, что его максимальные по включению симплексы соответствуют планарным графам, в которые невозможно добавить дополнительное ребро, не потеряв планарности. Т.е. макс. симплексы - это триангуляции 2-сферы (если бы была нетреугольная грань, в ней можно было бы провести диагональ). С помощью формулы Эйлера легко посчитать, что в триангуляции сферы на 6 вершинах должно быть ровно 12 ребер. Доказали, что комплекс K(6,0) чистый и имеет размерность 12-1=11.
Возьмем какую-нибудь триангуляцию 2-сферы, и выделим в ней одно ребро e. По этому ребру можно сделать флип: соединить два соседних с e треугольника в 4-угольник, и провести в нем другую диагональ. Получится новая триангуляция сферы, у которой все ребра те же самые, кроме одного. Это означает, что для любого максимального симплекса IϵK(6,0) и любой его гиперграни J существует ровно один другой максимальный симплекс с гипергранью J.
А значит K(6,0) является псевдомногообразием.
А значит у K(6,0) есть фундаментальный класс - сумма всех максимальных симплексов.
А значит, у K(6,0) есть нетривиальная 11-мерная гомология над полем GF(2).
А значит K(6,0) не является простым.
А значит невозможно определить, является ли граф на 6 вершинах планарным, не проверив все его ребра.
*Внимательный читатель заметит, что в рассуждении про флип есть лажа: иногда сделать флип нельзя, потому что добавляемое ребро уже есть в триангуляции. Но эта лажа отлаживается, - над этим приятно подумать самостоятельно.
Ну и очевидно, что это рассуждение обобщается. Рассмотрим свойство простого графа на n вершинах быть вложимым в сферу с g ручками. Это свойство кодируется симплициальным комплексом K(n,g). Комплекс имеет m=n(n-1)/2 вершин (вершины комплекса соответствуют возможным ребрам графа). Будем считать, что свойство нетривиально: т.е. что полный граф на n вершинах НЕ вкладывается в сферу с g ручками. Это условие дается конкретным неравенством между g и n, оценкой Юнгермана-Рингеля, но она сейчас не важна. Если комплекс K(n,g) нетривиален, то те же рассуждения, что и выше, показывают, что K(n,g) - псевдомногообразие, а значит не может быть простым: Алиса не может проверить условие вложимости графа в поверхность, не проверив все ребра графа.
Псевдомногообразия K(n,g) возникли с какой-то чисто утилитарной целью. Но фактически получился прелюбопытный объект: что-то вроде пространства всевозможных триангуляций поверхности рода g с n вершинами. Я не верю, что эти комплексы никто не придумал и не изучал, подходя с точки зрения пространств модулей и всякой подобной науки. Какие-нибудь там канонические классы определить и всё такое. Но конкретных ссылок дать увы не могу.
вотэтазадача 71: верно ли, что K(n,g) - ориентируемое псевдомногообразие?
Дальше можно сосредоточиться на свойствах графов. Когда говорим о монотонных свойствах графов на множестве вершин V - имеются в виду симплициальные комплексы K на множестве M={V \choose 2} всех двухэлементных подмножеств в V. Назовем свойство инвариантным, если оно не зависит от нумерации вершин графа. Более формально, пусть S(V) - группа перестановок множества V. Стандартное действие S(V) на V индуцирует действие S(V) на M. Комплекс K инвариантен, если сохраняется действием S(V) на M.
Вот, например, свойства планарности или вложимости в сферу с g ручками - очевидно не зависят от нумерации вершин, поэтому инвариантны. В частности, это означает что на наших псевдомногообразиях K(n,g) имеется действие группы перестановок S_n.
А вот открытая гипотеза Аандераа-Карпа-Розенберга: любое простое инвариантное монотонное свойство графов - тривиально (т.е. либо все графы обладают этим свойством, либо все - не обладают). Иными словами, любое нетривиальное инвариантное монотонное свойство графа можно проверить, лишь перебрав все ребра графа. Весьма удивительно!
Гипотеза доказана Каном, Саксом и Стертевантом (Kahn, Saks, Sturtevant. A topological approach to evasiveness) в случае, когда число n вершин графа - степень простого числа. Идея топологическая. В группе S(V) можно взять подгруппу G аффинных преобразований поля из n элементов. Группа G действует на множестве M двухэлементных подмножеств транзитивно. С другой стороны, G в некотором смысле достаточно маленькая: для нее выполнен аналог теоремы Брауэра. А именно, раз мы предположили, что свойство K простое (т.е. проверяется менее чем за |M| вопросов), то K - стягиваем. Доказывается, что у действия G на геометрической реализации K есть неподвижная точка. Неподвижная точка лежит внутри некоторого симплекса J. Но раз действие транзитивно на множестве всех вершин, то J обязан совпадать со всем множеством M. Т.е. свойство K - это полный симплекс, все графы обладают этим свойством.
Вообще мне кажется довольно занятным посмотреть на разные естественные свойства графов, и понять, почему соответствующие комплексы непростые. Идея про алгоритмическую непростоту планарности взята из Lenstra, Best, Boas, A sharpened version of the Aanderaa-Rosenberg conjecture, только у них ничего про топологию не говорится. Их результат можно топологически сформулировать так: раз мы знаем, что любой простой комплекс монотонно сдавливается в точку, значит у него есть максимальный симплекс со свободной гипергранью (это тот симплекс, который мы вдавим первым шагом). А значит, если свободных симплексов нет, то комплекс не простой. Этого соображения достаточно, чтобы доказать непростоту комплекса K(n,g), используя трюк с флипами ребер в графе. Фундаментальный цикл - штука прикольная, но она там не особо нужна.
И этого же соображения достаточно, чтобы доказать сложность свойства ацикличности графа. Это свойство довольно любопытное: соответствующий симплициальный комплекс Aс(n) - это комплекс независимых множеств графического матроида полного графа. Известно, что независимые комплексы матроидов гомотопны букетам сфер одной размерности.
В статье Ленстры-Беста-Боаса также оставлено в виде упражнения - доказать, что свойство несвязности графа является сложным. Из их теоремы мне, впрочем, это как-то увидеть не удалось: в соответствующем комплексе DC(n) вполне себе бывают сдавливаемые симплексы. Однако тут можно заметить, что DC(n) гомотопен геометрической реализации решетки разбиений множества [n] (из которой выкинули наименьшее и наибольшее разбиение). Из матроидной теории опять же следует, что геометрическая решетка гомотопна букету сфер. Количество сфер равно значению функции Мебиуса mu(0,1) чума. Конкретно в нашем случае - имеем (n-1)! сфер.
Короче, всякие свойства графов весьма забавны с топологической точки зрения.
Комментариев нет:
Отправить комментарий