Блок-схемы, комбинаторно симметричные графы и их автоморфизмы

• Автор: Гаврилюк, Александр Львович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Екатеринбург
• Количество страниц: 77 с.

Вполне регулярные графы и блок-схемы

Автоморфизмы дистанционно регулярного графа с массивом пересечений {60,45, 8,1,12, 50}

Графы Крейна без треугольников

Список литературы

В комбинаторном анализе проблемой общего характера является задача размещения элементов в заданном числе множеств таким образом, чтобы г-ЫЙ элемент ПОЯВЛЯЛСЯ Ті раз во всей совокупности этих множеств, чтобы І-ос множество содержало точно к^ элементов и, наконец, чтобы пары, тройки и тому подобные наборы элементов появлялись определенное число раз. Такое размещение может быть названо системой инцидентности. В частности, в прикладной математике (статистика, теория планирования экспериментов) чаще используется понятие уравновешенной неполной блок-схемы, в которой всякий набор элементов (блок) состоит точно из к элементов (точек), каждая точка принадлежит точно г блокам, и каждая пара различных точек появляется вместе точно в Л блоках [8].
Блок-схема является частным случаем 1-схем (с параметрами (и,к,Х)), которые определяются как пара (Х,В), где X — множество точек, В — множество блоков, каждый из которых содержит точно к точек, и любые і точек принадлежат вместе точно Л блокам. Таким образом, блок-схема является 2-схемой с подходящими параметрами.
Взаимосвязь блок-схем с другими объектами комбинаторного анализа — кодами, исправляющими ошибки, графами, хорошо известна и исследовалась ранее (см. [19]).
Далее мы рассматриваем неориентированные графы без петель и кратных ребер. В таком случае граф можно определить как пару, состоящую из множества вершин и множества ребер, то есть неупорядоченных двухэлементных подмножеств множества вершин. Заметим, что любой регулярный граф (то есть граф, в котором каждая вершина смежна с одним и тем же числом вершин) является 1-схемой, а полный граф (клика) является 2-схемой (схемой пар или полной схемой).

Использование более сильных условий регулярности для графа позволяет ввести понятие сильно регулярного графа с параметрами (у, к, Л, р). который определяется как граф на V вершинах, регулярный степени к, в котором пересечение окрестностей любой пары различных вершин содержит точно Л или р вершин в зависимости от того, смежны эти вершины или нет. Впервые понятие сильно регулярного графа было введено Боузом [12] при изучении частичных геометрий и уравновешенных неполных блок-схем. Так, например, хорошо известно [12], что блок-граф 2 — (и, к, 1) схемы, в котором два блока смежны тогда и только тогда, когда они имеют непустое пересечение, является сильно регулярным графом. Этот факт был обобщен Боузом, Геталсом и Зейделем для блок-графов квазисимметричных схем [19]. Таким образом, блок-схемы позволяют получить примеры сильно регулярных графов. Однако изучение этих графов не дает дополнительной информации о схемах. Напротив, изучение схем, возникающих в сильно регулярных графах, позволяет в ряде случаев установить некоторые структурные особенности графа, в том числе, доказать его несуществование.
Вместе с тем, к понятию сильно регулярного графа можно прийти и другим путем, рассматривая действие некоторой группы перестановок Є па конечном множестве V. Будем говорить, что Є имеет подстановочный ранг 3, если С? транзитивно действует на V и имеет точно 3 орбиты на V х V: диагональ {(р,р) | р Є V} и еще'две другие орбиты-О-О'-г Если группа ранга 3-имест четный порядок, то она содержит инволюцию, переставляющую, скажем, точки р ид. Таким образом, орбита, содержащая р ид, симметрична. Образуем граф Г, вершинами которого являются элементы V, а ребрами — неупорядоченные пары, соответствующие упорядоченным парам из О. Тогда группа С вкладывается в группу автоморфизмов графа Г, а граф Г является сильно регулярным. Теория групп ранга 3 была развита в работах Д. Хигмана ([24]—[30]).

ним, что для любой вершины с из Г2(а) П £1 подграф Ф содержит 3 вершины из [с], и по 4 вершины из Г2(с) и из Ес. Если Ф П [с] содержит 2 вершины из Фо и вершину е из Ф5, то 4 вершины из Ф Г) Ес не попадают в ех. Противоречие с тем, что Ф П Ес содержит быть может вершину ИЗ Фо и не более 2 вершин ИЗ Ф5 — ех. Если Ф П [с] содержит вершину ИЗ Фо и 2 вершины е, / из Фд, то Ф П Ес содержит 2 вершины из Фо и 2 из Фд — (ех и /х), и в этом случае ех П Ф5 = /х П Фд. Положим {е',/'} = Ф5 — ех. Тогда (е')х-П Фд = (/0х П Фд и каждая вершина из Фд — {е, /, е', /'} смежна со всеми вершинами из {е, /, е', /'}, в частности, Фд — {е, /, е', /'} является объединением двух изолированных ребер {р, д} и {р д'}. Теперь [е]П[р содержит /, д и вершину с' из Г2(а) П £2. Противоречие с строением Ф П Ес’.
Если Ф П [с] содержит 3 вершины е, /, д из Ф5, то Ф П Ес содержит не более 3 вершин из Фо и вершину И из Ф5 — (ех и /х и дх). Противоречие с тем, что Фд(/і) содержит не более 4 вершин.
Итак, ФП[с] содержит 3 вершины из Фо для любой вершины с 6 £2ПГ2(а). Для Ь Є £2(а) подграф Е П Еь содержит не более 5 вершин из Фд. Теперь для е Є Фд П Г2(6) подграф [6] П [е] содержит не менее двух вершин из £1 П Г2(о), противоречие.
Пусть |Фд| = 10 и Ф0 = {и}. Если с Є Г2(а) П £2 П Г2(и), то для {е, /, д} — Ф П [с] получим ех П Фд = /х П Ф5 = дх П Ф5 и Ф П Ес содержит 4 вершины из Фд — ех. Положим Ф' = Фд(е) — {/, д}. Тогда каждая вершина из Ф' смежна не более чем с 2 вершинами из Фд П Ес и число ребер между Ф' и Ф5 П Ес не больше 6. С другой стороны, каждая вершина из Фд П Ес смежна по крайней мере с 2 вершинами из Ф' и указанное число ребер не меньше 8, противоречие.
Пусть ірі —■ число вершин е из Фд таких, что |£2 П [е] П [ш]| = г. Тогда
+ Р7 + ^12 = Ю. Далее, для с £ П П [є] П [и] подграф Ес П Ф5 совпадает’ с Фд — ех. Теперь для различных вершин х,у из Ф5 — ех подграф Е1 П Еу содержит £2П[е]П[а], поэтому р-? = — 0. Отсюда, в частности, |£2(н)|