WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 38 |

[3] Тихоненко Т. В. Конечные группы с максимальными холловыми подгруппами // Известия ГГУ им. Ф. Скорины. 2008. Т. 50, № 5.

C. 198–206.

[4] Монахов В. С. Конечные -разрешимые группы с холловыми максимальными подгруппами // Математические заметки. 2008.

Т. 84, № 3. C. 390–394.

[5] Нерешенные вопросы теории групп. Коуровская тетрадь. 17-е изд. Новосибирск: Новосиб. гос. ун-т, 2010.

[6] Маслова Н. В. Неабелевы композиционные факторы конечной группы, все максимальные подгруппы которой холловы / в сб.

Современные проблемы математики, тезисы 42-й Всероссийской молодежной школы-конференции. С. 221–223. Екатеринбург: ИММ УрО РАН, 2011.

66 Тезисы 43-й молодежной школы-конференции О ВПОЛНЕ РЕГУЛЯРНЫХ ЛОКАЛЬНО GQ(4,6)-ГРАФАХ Махнев А.А., Падучих Д.В., Хамгокова М.М.Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа через i(a) обозначим iокрестность вершины a, то есть подграф, индуцированный на множестве всех вершин, находящихся на расстоянии i от a. Положим (a) = 1(a), a = {a} (a). Если граф зафиксирован, то вместо (a) будем писать [a].

Пусть F некоторый класс графов. Граф назовем локально F-графом, если [a] лежит в F для любой вершины a графа. Если при этом класс F состоит из графов, изоморфных некоторому графу, то граф назовем локально -графом.

Геометрия G ранга 2 это система инцидентности с множеством точек P и множеством блоков B, не имеющая кратных блоков. При этом каждый блок можно отождествить с множеством инцидентных ему точек и инцидентность становится обычным включением. Две точки из P называются коллинеарными, если они лежат в общем блоке. Точечный граф геометрии G это граф на множестве точек P, в котором две точки смежны, если они различны и коллинеарны.

Аналогично определяется блок граф.

Для a P вычетом Ga называется геометрия с множеством точек Pa, коллинеарных с a, и множеством блоков Ba = {B - {a} | a B B}. Если a P, B B и a B, то пара (a, B) называется / антифлагом. Если любые два блока из B пересекаются не более чем по одной точке, то множество блоков называется множеством прямых L, а геометрия (P, L) называется частичным пространством прямых. Частичное пространство прямых имеет порядок (s, t), если каждая прямая содержит ровно s + 1 точку и каждая точка лежит ровно на t + 1 прямой. Частичное пространство прямых порядка (s, t) называется обобщенным четырехугольником и обозначается GQ(s, t), если для любого антифлага (a, L) найдется единственная Работа выполнена при поддержке РФФИ (грант 12-01-00012), программы Отделения математических наук РАН и программ совместных исследований УрО РАН с СО РАН и с НАН Беларуси.

Алгебра прямая M, содержащая a и пересекающая L. Точечный граф геометрии GQ(s, t) сильно регулярен с v = (s + 1)(1 + st), k = s(t + 1), = s - 1, µ = t + 1.

Точка x обобщенного четырехугольника GQ(s, t) называется регулярной, если |({x, y})| = t + 1 для любой точки y x. Для ре/ гулярной точки x обобщенного четырехугольника S = (P, L) порядка (s, s) обобщенный четырехугольник P (S, x) порядка (s - 1, s + 1) имеет множество точек P = P - x и множество прямых L, состоящее из прямых L, не содержащих x, и гиперболических прямых ({x, y}), y x.

/ Задача классификации локально GQ(s, t)-графов является классической и решена для малых s. Например, в [1] завершена классификация локально GQ(3, t)-графов, в [2], [3] классифицированы вполне регулярные локально GQ(4, t)-графы для t = 2, 4 соответственно. В данной работе изучаются вполне регулярные локально GQ(4, 6)-графы.

Теорема. Пусть является связным вполне регулярным локально GQ(4, 6)-графом на v вершинах. Тогда v делится на 3 и выполняется одно из утверждений:

(1) диаметр равен 2, имеет параметры (726, 125, 28, 20) и собственные значения 15 и -7 кратностей 225 и 500;

(2) дистанционно регулярный граф с массивом пересечений {125, 96, 1; 1, 48, 125} на 378 вершинах и спектром 1251, 1125, 542, -20168;

(3) граф диаметра 3 с µ {20, 24, 25, 30, 32, 40}.

Следствие 1. Пусть является связным вполне регулярным локально GQ(4, 6)-графом, в котором окрестность некоторой вершины является известным обобщенным четырехугольником P (W (5), x). Тогда дистанционно регулярный граф с массивом пересечений {125, 96, 1; 1, 48, 125}.

Следствие 2. Пусть является дистанционно регулярным графом, в котором окрестность каждой вершины является обобщенным четырехугольником GQ(4, 6). Тогда либо диаметр равен и имеет параметры (726, 125, 28, 20), либо граф с массивом пересечений {125, 96, 1; 1, 48, 125}.

68 Тезисы 43-й молодежной школы-конференции Подмножество точек обобщенного четырехугольника называется гиперовалом, если любая прямая пересекает по 0 или 2 точкам. То есть гиперовал в GQ(s, t) это регулярный подграф без треугольников степени t + 1, имеющий четное число вершин. Хорошо известно, что µ-подграфы в локально GQ(s, t)-графах являются гиперовалами. Для подграфа графа через Xi() обозначим множество всех вершин из -, смежных точно с i вершинами из, и положим xi() = |Xi()|.

Лемма. Пусть обобщенный четырехугольник P (W (5), x) порядка (4, 6) содержит связный гиперовал, Xi = Xi(), xi = |Xi|. Тогда выполняется одно из утверждений:

(1) || = 20, x4 = 105;

(2) || = 24, x0 = 2, x4 = 48, x6 = 48, x8 = 3 и X0 является ребром;

(3) || = 32, x0 = 3, x4 = 9, x6 = 30, x8 = 30, x10 = 18, x12 = 3 и X0 является кокликой;

(4) || = 36, x0 = 2, x2 = 4, x4 = 1, x6 = 10, x8 = 30, x10 = 32, x12 = 8, x14 = 2 и X0 является кокликой;

(5) || = 40, x0 = 5, x8 = 10, x10 = 40, x12 = 30 и X0 является кокликой;

(6) || = 44, x0 = 3, x8 = 1, x10 = 18, x12 = 45, x14 = 14 и Xявляется кокликой;



(7) || = 48 (две орбиты), x0 = 1, x12 = 28, x14 = 48.

Доказательство. Компьютерные вычисления в GAP.

Литература [1] Махнев А.А. Локально GQ(3,5)-графы и геометрии с короткими прямыми // Дискр. математика. 1998. Т. 10, № 2. С. 72-86.

[2] Махнев А.А., Падучих Д.В. Расширения GQ(4, 2), вполне регулярный случай // Дискретная математика. 2001. Т. 13, № 3. С. 91109.

[3] Махнев А.А., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально GQ(4, 4)-графах // Доклады академии наук. 2010.

Т. 434, № 5. С. 583-586.

Алгебра ОБ АВТОМОРФИЗМАХ ДИСТАНЦИОННО РЕГУЛЯРНОГО ГРАФА С МАССИВОМ ПЕРЕСЕЧЕНИЙ {35, 32, 8; 1, 2, 28} Махнев А.А., Циовкина Л.Ю.Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа через i(a) обозначим iокрестность вершины a, то есть подграф, индуцированный на множестве всех вершин, находящихся на расстоянии i от a. Положим [a] = 1(a), a = {a} [a].

Пусть граф, a, b две вершины из, число вершин в [a] [b] обозначается через µ(a, b) (через (a, b)), если a, b находятся на расстоянии 2 (смежны) в. Далее, индуцированный [a] [b] подграф называется µ-подграфом (-подграфом). Если граф диаметра d, то через i,i2,...,it, где ij d для всех j = 1,..., t, обозначается граф с тем же множеством вершин, что и, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии i {i1, i2,..., it} в.

Степенью вершины называется число вершин в ее окрестности.

Граф называется регулярным степени k, если степень любой вершины из равна k. Граф назовем реберно регулярным с параметрами (v, k, ), если он содержит v вершин, регулярен степени k и каждое его ребро лежит в треугольниках. Граф вполне регулярный граф с параметрами (v, k,, µ), если он реберно регулярен c соответствующими параметрами и [a] [b] содержит µ вершин для любых двух вершин a, b, находящихся на расстоянии 2 в. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Если вершины u, w находятся на расстоянии i в, то через bi(u, w) (через ci(u, w)) обозначим число вершин в пересечении i+1(u) (i-1(u)) с [w]. Граф диаметра d называется дистанционно регулярным с массивом пересечений {b0, b1,..., bd-1; c1,..., cd}, если значения bi(u, w) и ci(u, w) не зависят от выбора вершин u, w на расстоянии i в для любого i = 0,..., d. Положим ai = k - bi - ci.

Работа выполнена при поддержке РФФИ (грант 12-01-00012), программы Отделения математических наук РАН и программ совместных исследований УрО РАН с СО РАН и с НАН Беларуси, грантом УрО РАН для молодых ученых за 2012 год.

70 Тезисы 43-й молодежной школы-конференции Заметим, что для дистанционно регулярного графа b0 это степень графа, c1 = 1. Граф диаметра d называется дистанционно транзитивным, если для любого i {0,..., d} и для любых двух пар вершин (u, w) и (y, z) с d(u, w) = d(y, z) = i найдется автоморфизм g графа такой, что (ug, wg) = (y, z). Для подмножества X автоморфизмов графа через Fix(X) обозначается множество всех вершин графа, неподвижных относительно любого автоморфизма из X. Далее, через pl (x, y) обозначим число вершин в подграфе i(x) j(y) для ij вершин x, y, находящихся на расстоянии l в графе. В дистанционно регулярном графе числа pl (x, y) не зависят от выбора вершин ij x, y, обозначаются pl и называются числами пересечения графа.

ij Для произвольного автоморфизма g графа через j(g) обозначим число вершин x таких, что d(x, xg) = j.

Граф называется реберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер).

В работе [1] найдены массивы пересечений дистанционно регулярных локально циклических графов с числом вершин, не большим 1000.

Предложение. Пусть является дистанционно регулярным графом диаметра, большего 2, на v 1000 вершинах. Если = 2 и µ > 1, то верно одно из утверждений:

(1) примитивный граф с массивом пересечений {15, 12, 6; 1, 2, 10}, {19, 16, 8; 1, 2, 8}, {24, 21, 3; 1, 3, 18}, {35, 32, 8; 1, 2, 28}, {51, 48, 8; 1, 4, 36};

(2) антиподальный граф с µ = 2 и массивом пересечений {2r + 1, 2r - 2, 1; 1, 2, 2r + 1}, r {3, 4,..., 21}\{10, 16} и v = 2r(r + 1);

(3) антиподальный граф с µ 3 и массивом пересечений {15, 12, 1; 1, 4, 15}, {18, 15, 1; 1, 5, 18}, {27, 24, 1; 1, 8, 27}, {35, 32, 1; 1, 4, 35}, {45, 42, 1; 1, 6, 45}, {42, 39, 1; 1, 3, 42}, {75, 72, 1; 1, 12, 75}.

В данной работе изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {35, 32, 8; 1, 2, 28}.

Граф с массивом пересечений {35, 32, 8; 1, 2, 28} имеет v = 1 + 35+ +560 + 160 = 756 вершин и спектр 351, 7270, -1245, -7240, причем сильно регулярный граф с параметрами (756, 160, 40, 32) и спектром 1601, 16245, -8510.

Алгебра Теорема. Пусть дистанционно регулярный граф, имеющий массив пересечений {35, 32, 8; 1, 2, 28}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда (G) {2, 3, 5, 7} и выполняются следующие утверждения:

(1) пустой граф и либо (i) p = 7, 3(g) = 168s, 1(g) = 98l + 42s - 42 и 2(g) = 798-98l - 210s, либо (ii) p = 3, 3(g) = 72s, 1(g) = 42l+18s и 2(g) = 756-42l-90s, либо (iii) p = 2, 3(g) = 48s, 1(g) = 28l + 12s и 2(g) = 756 - 28l-60s;

(2) состоит из вершин, попарно находящихся на расстоянии 3 в и либо (i) p = 5, || = 1, 3(g) = 120s + 40 и 1(g) = 70l + 30s + 5, либо (ii) p = 7, || = 7r, 3(g) = 168s+112/r и 1(g) = 98l+42s-49r, s 2/r, r {1, 2} или || = 21, 3(g) = 0 и 1(g) = 98l + 49, l 6;

(3) p = 2, || = 2t, 3(g) = 48l - 16t, 1(g) = 28s + 12l - 14t и либо (i) для любой вершины a из подграф 3(a) не пересекает и || 36, либо (ii) содержит вершину степени 1 и || 50, либо (iii) степень любой вершины в не меньше 3 и не больше 19, а || 82.





Следствие. Граф с массивом пересечений {35, 32, 8; 1, 2, 28} не является реберно симметричным.

Литература [1] Буриченко В.П., Махнев А.А. О вполне регулярных локально циклических графах / в сб. Современные проблемы математики, тезисы 42-й Всероссийской молодежной конференции. Екатеринбург: ИММ УрО РАН, 2011. С. 181-183.

[2] Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag, 1989.

[3] Cameron P.J. Permutation Groups // London Math. Soc. Student Texts. Vol. 45. Cambridge: Cambridge Univ. Press, 1999.

72 Тезисы 43-й молодежной школы-конференции ТОЧНЫЕ ГРАФЫ ДЕЗА БЕЗ 3-ЛАП Митянина А.В.

Мы рассматриваем неориентированные графы без петель и кратных ребер. Граф называется регулярным, если степени всех его вершин равны. Граф K1,3 называется 3-лапой.

Определение 1. Граф называется графом Деза с параметрами (v, k, b, a), где v > k > b > a, если он является регулярным на v вершинах степени k, в котором любые две различные вершины имеют либо b, либо a общих соседей.

Определение 2. Граф является сильно регулярным с параметрами (v, k,, µ), если он является регулярным степени k, и для любых различных вершин u и v имеем |[u] [w]| =, если u w, и |[u] [w]| = µ в противном случае.

Определение 3. Точным графом Деза называется граф Деза, не являющийся сильно регулярным и имеющий диаметр 2.

В статье [1] приводится полный список графов Деза с числом вершин, не превышающим 13, а также дается несколько способов построения графов Деза из разностных множеств, композиций и произведений графов и из сильно регулярных графов.

В статье [2] авторы находят все графы Деза на 14, 15 и 16 вершинах и описывают конструкции для построения каждого из графов.

В данной работе доказана следующая теорема.

Теорема. Если граф является точным графом Деза с параметрами (v, k, b, a) и удовлетворяет следующим условиям:

1) не содержит 3-лап;

2) содержит 3-коклику;

3) является объединением окрестностей некоторых двух несмежных вершин, тогда он имеет параметры (9, 4, 2, 1) или (12, 6, 3, 2).

Алгебра В доказательстве теоремы используются следующие леммы.

Лемма 1. Если граф удовлетворяет условию теоремы, то k {2b, 2b + 1, 2b + 2}.

Лемма 2. Если граф удовлетворяет условию теоремы, то он не содержит 4-коклик.

В ходе доказательства теоремы строятся возможные конфигурации графа в зависимости от расположения вершин из некоторой 3коклики в замкнутых окрестностях вершин A и B, где = A B.

Литература [1] Erickson M., Fernando S., Haemers W.H., Hardy D., Hemmeter J.

Deza Graphs: A Generalization of Strongly Regular Graphs // J. Combin. Designs. 1999. Vol. 7. Pp. 395-405.

[2] Горяинов С.В., Шалагинов Л.В. О графах Деза на 14, 15 и вершинах // в сб. Современные проблемы математики, тезисы 42-й Всероссийской молодежной школа-конференции. С. 56–59.

Екатеринбург: ИММ УрО РАН, 2011.

74 Тезисы 43-й молодежной школы-конференции ПОЛНОСТЬЮ РЕГУЛЯРНЫЕ КОДЫ В ГРАФАХ ДЖОНСОНА И БЛОК-СХЕМЫ Могильных И.Ю.Рассмотрим регулярный граф G. Для всякого кода (т.е. подмножества вершин) C в графе G определим дистанционное разбиение множества вершин V этого графа относительно C: V = Ci, i=0,..., где := max{d(x, C) : x C} называется радиусом покрытия кода C. Код C в G называется полностью регулярным, если любая вершина из слоя Cj имеет j, j и j соседей соответственно из слоев Cj-1, Cj и Cj+1. Набор чисел {j, j, j : j = 0,..., } называется массивом пересечения кода C.

Вершинами графа Джонсона J(n, w) являются все w-элементные подмножества n-элементного множества; две вершины смежны, если их пересечение имеет мощность w - 1.

Совокупность w-элементных подмножеств n-элементного множества, именуемых блоками, называется t - (n, w, )-схемой, если любое t-элементное подмножество содержится в точности в блоках. В дальнейшем мы будем рассматривать лишь схемы, все блоки которой различны. Блоки такой схемы можно рассматривать как вершины графа Джонсона. Силой схемы называется максимальное t, для которого она является t - (n, w, )-схемой.

В работе Дельсарта [1] установлено, что всякий полностью регулярный код в графе Джонсона является t - (n, w, )-схемой. Более того, в случае = 1 числа t, однозначно определяются массивом пересечений полностью регулярного кода: t определяется из соотношения:

(w - (t + 1))(n - w - t - 1) - t - 1 = 0 - 1, 0 t w, а равняется 1 n-t /(1 + 1).

k-t Итак, полностью регулярные коды в графах Джонсона можно рассматривать как подкласс t-схем со специальными комбинаторными свойствами.

В работе [2] получено конструктивное описание всех полностью регулярных кодов силы 0 в графах Джонсона. В [3] показано, что Работа поддержана грантом МК-1700.2011.1 и грантами РФФИ № 09-0100244, 12-01-00551-а и 10-01-00616-a.

Алгебра всякая блок-схема силы w - 1 и с размером блока w является полностью регулярным кодом в графе J(n, w). Эти схемы включают в себя широко известные системы троек и четверок Штейнера.

В данной работе мы рассматриваем классические конструкции Оллтопа [4] расширения блок-схем из существующих и показываем, что их применение к полностью регулярным кодам дает новые полностью регулярные коды. В качестве исходных блок-схем для этих конструкций берутся блок-схемы с размером блока, равным половине от числа точек.

Пусть D является t - (n, w, )-схемой. Введем следующие обозначения D = { (n + 1) : D}, D = {{1,..., n} \ : D}.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 38 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.