Комбинаторные структуры в топологии
       Спецкурс в МК НМУ, осень 1998
     
                С.В.Дужин
              duzhin@botik.ru

                 Лекция 1

Три определения графа (три ступени абстракции)
1. (Детское) Граф -- это набор точек (вершин) и соединяющих их линий (ребер).
2. (Обычное) Граф -- это конечное множество $V$ (вершины) и выделенное 
   симметричное подмножество декартова квадрата $V\times V$ (ребра).
3. (М.Концевич). Граф --- это множество со свободной инволюцией и отношением 
   эквивалентности.

Определение. Графом Мура называется регулярный граф степени $k$,
порядка $k^2+1$ и диаметра 2.

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

Теорема. Графы Мура существуют для $k=1,2,3,7$ и, быть может, 57.

Пояснение. Это значит, что для значений $k$, кроме перечисленных, 
графов Мура не существует.
Графы Мура степени 1, 2, 3 и 7 существуют и хорошо известны.
До сих пор неизвестно, существует ли граф Мура степени 57.

Схема доказательства.

1. Граф степени k и порядка k^2+1 является графом Мура тогда и только тогда,
когда он не содержит циклов длины 3 и 4.

2. Если A -- матрица смежности графа Мура, то она удовлетворяет
уравнению 
$$
  A^3 - (k-1)A^2 - (2k-1)A + k(k+1) = 0.
$$

3. Собственные значения $\lambda_{1,2}$ матрицы $A$, отличные от 1,
и их кратности $m_{1,2}$ удовлатворяют системе уравнений
\begin{eqnarray*}
   m_1 + m_2      &=& k^2,\cr
   \l_1 m_1+\l_2 m_2 = -k,\cr
   \l_1+\l_2 = -1.
\end{eqnarray*}

4. Если $k\ne2$, то $m_1\ne m_2$ и, следовательно, числа $\l_1$ и 
$\l_2$ рациональны. На самом деле $\l_i = (-1\pm t)/2$, где
где $t$ --- целое число, удовлетворяющее уравнению
$$
  t^4 - 2t^2 - 16(m_1-m_2)t - 15 = 0.
$$
Отсюда вытекает, что $t=1$, 3, 5 или 15.

Граф Мура степени 1 --- это $K_2$ (полный граф с 2 вершинами),
степени 2 --- пятиугольник $C_5$. 
Графы Мура степеней 3 и 7 тоже существуют и единственны
с точностью до изоморфизма. Это граф Петерсена $P_{10}$
и граф Хоффмана--Синглтона $HS_{50}$. 

Граф Петерсена состоит из двух пятиугольников $C_5$,
вершины которых соединены между собой еще пятью ребрами
по правилу $x \mapsto 2x$ по модулю 5 (если вершины каждого цикла
$C_5$ нумеровать вычетами по модулю 5).

Граф Хоффмана--Синглтона можно построить так.
Возьмем граф $K_{5,5}$ (полный двудольный граф с 5+5 вершинами, 
т.е. граф "5 домиков и 5 колодцев", которые будем представлять себе
расположенными в виде двух горизонтальных рядов). 
Каждую вершину этого графа заменим на цикл $C_5$, а каждое
ребро --- на пятерку ребер, осуществляющих взаимно-однозначное
соответствие между вершинами этих циклов по тому же пригципу, что
и в графе Петерсена. Точнее, из вершины $x$ $i$-го "домика"
проведем ребро в вершину $j$-го колодца с номером $2x+ij \mod 5$.

Определение.
Отображение графов --- это отображение множеств вершин,
которое сохраняет отношение смежности и, таким образом, индуцирует
вполне определенное отображение на множестве ребер.

Определение.
Граф $H$ является $m$-листным (комбинаторным) накрытием графа $G$, если
существует отображение графов $p:H\to G$ такое, что прообраз любой вершины
$v\in V(G)$ состоит из $m$ вершин, не соединенных ребрами,
а прообраз любого ребра состоит из $m$ ребер, не имеющих общих
концов.

Замечание. Всякое комбинаторное накрытие является также
топологическим накрытием. Обратное неверно.

Группа монодромии накрытия над точкой базы $v\in V(G)$ --- это группа 
перестановок слоя $p^{-1}(v)$, порожденная поднятиями всех замкнутых 
путей в графе $G$, начинающихся и заканчивающихся в точке $V$.

Наблюдение.
Если из графа Мура выбросить какую-то вершину и все смежные с ней
вершины, то останется граф, который является $k-1$-листным накрытием 
полного графа $K_k$. Монодромия этого накрытия не имеет неподвижных точек 
над циклами в базе длины 3 и 4.

Задачи

1. Проверить, что описанная выше конструкция графа Хоффмана-Синглтона
действительно приводит к графу диаметра 2.

2. Доказать несуществование графа Мура степени 4 путем подсчета
   числа циклов длины 5, проходящих через фиксированную его вершину.

3. Построить граф Хоффмана--Синглтона через 6-листное накрытие над
$K_7$, монодромия которого над циклами длины 3 и 4 не имеет 
неподвижных точек.

4. Классифицировать накрытия:
   a. двулистные над $C_3$.
   б. двулистные над $K_4$.
   в. трехлистные над $C_3$.

Проблема. 
Выяснить, существует ли граф Мура степени 57.