Комбинаторные структуры в топологии Спецкурс в МК НМУ, осень 1998 С.В.Дужин duzhin@botik.ru Лекция 2 Конструкция Зайделя Пусть $P$ --- множество точек трехмерного проективного пространства над полем $\Z_2$, а $L$ --- множество прямых в нем же. Положим $V=P\cup L$. Это множество мощности 50, которое мы примем за множество вершин графа. Ребра определяются так: 1. между $p_1,p_2\in P$ ребер нет. 2. $p\in P$ соединяется ребром с $l\in L$, если точка $p$ принадлежит прямой $l$. 3. для того, чтобы определить смежность между прямыми $l_1,l_2\in L$, построим вначале взаимно-однозначное соответствие между $L$ и множеством всех троек точек некоторого вспомогательного множества $M$, при котором две прямые $l_1$ и $l_2$ пересекаются в проективном пространстве тогда и только тогда, когда две соответствующие тройки имеют ровно одну общую точку. Тогда прямые $l_1$ и $l_2$ соединяются ребром в том и только том случае, когда соответствующие тройки не имеют оющих точек. Описание некоторых простых комбинаторных объектов, возможно, связанных с графом Хоффмана-Синглтона, 1. Проективная плоскость из 7 точек -- набор семи троек, составленных из данных семи точек так, что каждая пара точек принадлежит ровно одной тройке, а каждые две тройки имеют ровно одну общую точку. 2. Семицветная карта на торе -- регулярный паркет из правильных шестиугольников на плоскости можно раскрасить в 7 цветов так, что получится дважды периодический узор. Таким образом, каждый их 7 цветов определяет некоторый циклический порядок в множестве остальных 6 цветов. 3. Полиэдр Часара -- многогранник в трехмерном пространстве, имеющий 7 вершин, 21 ребро и 14 треугольных граней и гомеоморфный тору. С комбинаторной точки зрения, речь идет о наборе 14 троек из данных 7 точек, который обладает некоторыми специальными свойствами. Прямое произведение. Прямым произведением графов $G$ и $H$ называется граф с множеством вершин $V(G)\times V(H)$, в котором вершины $(u_1,v_1)$ и $(u_2,v_2)$ соединяются ребром, если либо $u_1=u_2$, а $(v_1,v_2)$ --- ребро в $H$, либо $v_1=v_2$, а $(u_1,u_2)$ --- ребро в $G$. Пример. Если $K_2$ --- отрезок, то $K_2\times K_2=C_4$ --- квадрат. Ребра в прямом произведении условно можно разделить на вертикальные и горизонтальные. Если разрешить, чтобы горизонтальные ребра были не строго горизонтальны, а слегка подкручены, то мы придем к понятию расслоения, или косого произведения. Определение. Отображение графов $p:E\to B$ называется расслоением со слоем $F$, если прообраз любой вершины базы есть граф, изоморфный $F$, а прообраз любого ребра $(v_1,v_2)$ состоит из одного и того же числа ребер, соединяющих вершины графов $p^{-1}(v_1)$ и $p^{-1}(v_2)$ так, что получается взаимно-однознаяное соответствие между этими двумя множествами. Если полный прообраз любого подграфа $K_2\subset B$ (ребра с двумя концами) представляет собой один и тот же граф $C$, с точностью до изоморфизма, то говорят, что речь идет о расслоении типа $C$. Важный пример: расслоение Петерсена --- это расслоение типа $P_{10}$ со слоем $C_5$, т.е. расслоение, в котором над каждой точкой базы висит пятиугольник, а разные пятиугольники соединяются между собой скручиванием Петерсена (отображением вида $x\mapsto\pm2x+a$ в смысле поля вычетов $\Z_5$). К этому классу относятся графы Петерсена и Хоффмана-Синглтона. Замечание. В отличие от понятия накрытия, расслоения графов, определенные комбинаторным образом, не имеют ничего общего с понятием расслоения в топологии, так как размерность пространства расслоения равна сумме размерностей базы и слоя. Правильным аналогом размерности для регулярных графов является валентность. Некоторые классические многообразия имеют вполне очевидные аналоги в категории графов, например, $K_n$ --- $n$-мерная сфера, $K_2^n$ --- $n$-мерный тор, $C_n$ --- замкнутая ориентируемая поверхность рода $n-3$. Предложение. Спектр прямого произведения графов равен сумме спектров сомножителей. Теорема о спектре расслоения Петерсена. Спектр любого расслоения Петерсена над графом $B$ состоит из собственных чисел графа $D$, сдвинутых на 2, и, кроме того, некоторого набора собственных значений, который можно разбить на пары так, что сумма чисел в каждой паре равна $-1$. Задачи. 1. Проверить, что конструкция Зайделя дает граф диаметра 2. 2. Пользуясь материалами предыдущей лекции, найти спектры графов Мура $P_{10}$ и $HS_{50}$ и проверить для них выполнение теоремы о спектре расслоения Петерсена. 3. Если бы граф Мура степени 57 существовал и представлялся как расслоение Петерсена, то что можно сказать о спектре базы этого расслоения? 4. Классифицировать расслоения: а. над $C_n$ со слоем $K_2$, б. над $K_4$ со слоем $K_2$, в. над $K_2$ со слоем $C_n$. Проблема. Найти естественную конструкцию графа Хоффмана-Синглтона, связанную с перечисленными выше "простыми комбинаторными объектами". В частности, эта конструкция должна объяснять, откуда берется взаимно-однозначное соответствие между неупорядоченными парами чисел 1..6 и перестановками, состоящими из 3 транспозиций, которое приводит к замечательному 6-листному накрытию графа K_7, описанному в лекции 1: 12 216543 13 341265 14 465132 15 532614 16 654321 23 564312 24 351624 25 645231 26 432165 34 632541 35 456123 36 215634 45 214365 46 546213 56 361542 Проблема. Можно ли построить содержательную теорию гомологий или гомотопий в категории регулярных графов, в которой аналогом размерности была бы степень (валентность) графа? Хочется, чтобы $n$-я группа гомологий сферы была нетривиальной, и при этом существовал бы некий аналог точной последовательности расслоения.