Cтраница 1
Граф Кэли, построенный относительно некоторого свободного базиса свободной группы, является деревом, на котором группа действует свободно и без инверсий левыми умножениями на вершинах. Следовательно, G - фундаментальная группа факторграфа и, следовательно, свободна. [1]
Это ясно из рассмотрения стандартного графа Кэли, связанного с базисом этой группы. [2]
Доказательство утверждается 6.2.2. Пусть X - граф Кэли группы относительно порождающего множества S. Тогда существует конечный связный подграф L графа X такой, что граф XL, полученный из X удалением ребер L и всех получившихся изолированных вершин, состоит в точности из п бесконечных компонент. G такой, что gL ] L пусто, и, таким образом, gL лежит целиком внутри некоторой компоненты У из XL. Теперь в точности одна из компонент Y gL бесконечна, и граф LU ( y) - связен, откуда X gL имеет не более двух бесконечных компонент. [3]
Теорема 15.2.1. Все сохраняющие раскраску ребер автоморфизмы графа Кэли для группы получаются как умножения слева на элементы группы. [4]
Рассмотренные идеи приводят к графам, которые известны под названием цветных графов Кэли, или диаграмм. [5]
При построении турнира с группой, изоморфной группе G, мы начнем, как и следовало бы ожидать, с построения объекта Г, который есть не что иное, как цветной граф Кэли группы G ( см. Коксетер и Мозер [ 1, стр. Вершины графа Т соответствуют элементам группы G. Для удобства мы будем обозначать одним и тем же - символом и вершину, и соответствующий ей элемент группы. Отсюда следует, что для каждой вершины и каждой образующей только одна дуга выходит из данной вершины и только одна дуга входит в данную вершину. В графе Т нет петель, так как единичный элемент группы не принадлежит множеству ее образующих. Кроме того, никакие две вершины в графе Т не соединены дугами, ориентированными в противоположных направлениях, так как в противном случае цвета этих дуг соответствовали бы взаимно обратным элементам группы, а таких элементов в множестве образующих нет. [6]
Мы сводим задачу об оценке s ( n) к оценке числа независимых множеств в графе Кэли. F, назовем графом Кэли на множестве У относительно F. Подмножество А вершин графа G называется независимым, если подграф, порожденный множеством А, не содержит ребер. Семейство S § подмножеств вершин графа G назовем покрывающим, если для всякого A ( G) существует В G S § такое, что А С В. [7]
G, 2), натянутый на граф Кэли следующим образом. [8]
Порядок роста функции - у ( г) при г - характеризуется порядком роста графа Г на бесконечности. Мы этот вопрос рассмотрим подробно ниже для графов Кэли конечно порожденных групп. [9]
Любую группу G в алфавите образующих X ( J Х - 1 можно представить геометрически как некоторый граф. Вершинам графа соответствуют элементы группы G. Такое графовое представление группы называется цветным графом Кэли. [10]
Таким образом, каждая вершина является начальной для стольких дуг, сколько элементов содержится в рабочем подмножестве. Каждая дуга окрашивается в свой цвет, соответствующий цвету элемента рабочего подмножества. Заметим, что вершине соответствует петля, если воздействие тождественно. В результате формируется цветной граф Кэли. Таким образом, 4 не формирует группы, определенной вычетами по mod 6 при сложении, так как соответствующий граф не связен. [11]