Cтраница 1
Два-граф, являющийся также и 2-схемой, называется регулярным два-графом. [1]
Теорема 6.2. Два-граф регулярен тогда и только тогда, когда ( 0 -, - -) - матрица смежности некоторого ( а, стало быть, и каждого) графа в переключательном классе имеет ровно два собственных значения. [2]
Если Д - два-граф, у которого Д ( ро) Г для некоторой вершины р0, то легко видеть, что перестановка, переставляющая ро и р и действующая, как h на Г ( р) и / 12 на Г ( р), есть автоморфизм на А. [3]
В процессе доказательства единственности регулярного два-графа на 276 вершинах Геталс и Сейдел обнаружили в его переключательном классе граф, содержащий индуцированный подграф, изоморфный П з ( объединение 11 непересекающихся треугольников), такой, что каждая из оставшихся вершин смежна ровно с одной вершиной в каждом треугольнике. B ( vii), мы заключаем что для графа на оставшихся 243 вершинах собственные значения ( - 1, 1, 0) - матрицы смежности суть 4922, 221, ( - 5) 220, поэтому это и есть требуемый граф. [4]
В процессе доказательства единственности регулярного два-графа на 276 вершинах Геталс и Сейдел обнаружили в его переключательном классе граф, содержащий индуцированный подграф, изоморфный 11 Кз ( объединение 11 непересекающихся треугольников), такой, что каждая из оставшихся вершин смежна ровно с одной вершиной в каждом треугольнике. B ( vii), мы заключаем что для графа на оставшихся 243 вершинах собственные значения ( - 1, 4 - 1, 0) - матрицы смежности суть 4922, 221, ( - 5) 220, поэтому это и есть требуемый граф. [5]
Мыслимо существование другого srg в переключательном классе рассматриваемого регулярного два-графа. [6]
Два-граф, являющийся также и 2-схемой, называется регулярным два-графом. [7]
А ( но не его дополнение) удовлетворят (), то методы-используемые для два-графов, перестают работать; но структура Д достаточно ограничена, чтобы некоторый прогресс б ыл возможен. [8]
Если мы рассмотрим граф на множестве блоков и добавим изолированную точку, то получим граф, который содержится в переключательном классе некоторого регулярного два-графа. Соответствующая матрица Адамара является симметрической с постоянной диагональю, однако не регулярна ( как утверждается в [ 72, стр. [9]
Поскольку полностью подходящая когомология тривиальна, то это, таким образом, есть кограница 1-коцепи, а последнее, будучи функцией пар в Z2, являет собой граф; тройки два-графа являются носителями нечетного числа ребер этого графа. Две 1-коцепи имеют одну и ту же кограницу тогда и только тогда, когда они отличаются на 1-коцикл, то есть кограницу 0-коцепи ( функцию из точечного множества в Z2); это означает существование разбиения точечного множества Х [) Y и двух графов, согласованных внутри X и внутри У и являющихся дополнительными между этими множествами. В терминологии Зейделя эти графы являются связанными по переключению относительно разбиения XJY. Таким образом, два-граф эквивалентен переключательному классу графов. Пустой два-граф соответствует переключательному классу полных двудольных графов, а полный два-граф - двум полным графам. Эти случаи исключаются из дальнейшего рассмотрения. [10]
Единственная известная схема с k 3, удовлетворяющая аксиоме ( 2) из теоремы 6.5, - это 2 - ( 16 6, 2) - схема, которую мы уже встречали в предыдущем разделе; для этой схемы Д является регулярным два-графом. Полная характеризация этой схемы посредством этой аксиомы представляется трудной задачей; отметим более слабую характеризацию. [11]
Определим граф на этих 276 вершинах таким образом, что X является кокликой, точка соединена с блоками, содержащими ее, а два блока соединены, если они пересекаются по одной точке. Полученный таким образом граф содержится в переключательном классе некоторого регулярного два-графа на 276 точках. [12]
Предположим, что имеется система Штейнера 8 ( 2, К. Если мы рассмотрим граф на множестве блоков и добавим изолированную точку, то получим граф, который содержится в переключательном классе некоторого регулярного два-графа. Соответствующая матрица Адамара является симметрической с постоянной диагональю, однако не регулярна ( как утверждается в [ 72, стр. [13]
Поскольку полностью подходящая когомология тривиальна, то это, таким образом, есть кограница 1-коцепи, а последнее, будучи функцией пар в Z2, являет собой граф; тройки два-графа являются носителями нечетного числа ребер этого графа. Две 1-коцепи имеют одну и ту же кограницу тогда и только тогда, когда они отличаются на 1-коцикл, то есть кограницу 0-коцепи ( функцию из точечного множества в Z2); это означает существование разбиения точечного множества Х [) Y и двух графов, согласованных внутри X и внутри У и являющихся дополнительными между этими множествами. В терминологии Зейделя эти графы являются связанными по переключению относительно разбиения XJY. Таким образом, два-граф эквивалентен переключательному классу графов. Пустой два-граф соответствует переключательному классу полных двудольных графов, а полный два-граф - двум полным графам. Эти случаи исключаются из дальнейшего рассмотрения. [14]
При q 5 такой граф был построен Геталсом ( см. разд. Для больших q такие графы неизвестны. Отметим, что при q 32л 1 дважды транзитивное представление на q3 1 точках имеют группы Ри. Это представление приводит к регулярному два-графу с теми же параметрами, что и два-граф, связанный с группой РГЩЗ, q2) и обсуждавшийся выше. [15]