WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 38 |

Рассмотрим случай, когда n равно 2w. Любой полностью регулярный код в графе J(2w, w) наследует [5] свойство антиподальности графа: код является либо плюс-антиподальным (т.е. любые две антиподальные вершины являются одновременно либо кодовыми, либо некодовыми), либо минус-антиподальным (в любой паре антиподальных вершин одна вершина является кодовой, а другая нет).

Теорема 1. [4] Пусть D является t - (2w, w, )-схемой, t четно, и D = D. Тогда D является (t + 1) - (2w, w, )-схемой, где = = (w - t)/(2w - t).

Следствие. Пусть C является плюс-антиподальным полностью регулярным кодом в J(2w, w) с = 1. Тогда сила C как блок-схемы является нечетным числом.

Опишем две конструкции Оллтопа. Ниже D обозначает подмножество вершин графа J(2w + 1, w), дополнительное к D.

Теорема 2. [4] Пусть D является t-(2w+1, w, )-схемой, t четно.

Тогда D D является (t + 1) - (2w + 2, w + 1, )-схемой.

Теорема 3. [4] Пусть D является t-(2w+1, w, )-схемой, t нечет2w+но и |D| = /2. Тогда D D является (t + 1) - (2w, w, )w схемой.

76 Тезисы 43-й молодежной школы-конференции Вариант этих утверждений для полностью регулярных кодов принимает следующий вид:

Теорема 4. Пусть C является полностью регулярным кодом с = 1 в J(2w + 1, w). Тогда код C C является полностью регулярным в J(2w + 2, w + 1).

Теорема 5. [4] Пусть C является полностью регулярным кодом с = 1 в J(2w + 1, w), |C| = (2w+1)/2. Тогда код C C является w полностью регулярным в J(2w + 2, w + 1).

В данной работе, используя эти два утверждения и классификацию полностью регулярных кодов в J(9, 4) с радиусом покрытия 1 [6], мы построили полностью регулярные коды в графе J(10, 5) с массивами пересечений {0 = 13, 0 = 12, 1 = 16, 1 = 9} и {0 = 5, 0 = 20, 1 = 8, 1 = 17}. Отметим, что конструкции расширения полностью регулярных кодов применимы к кодам произвольной силы t (в отличие от варианта конструкций для блок-схем).

Литература [1] Delsarte P. An Algebraic Approach to the Association Schemes of Coding Theory // Philips Res. Rep. Suppl. 1973. Vol. 10. Pp. 1–97.

[2] Meyerowitz A. Cycle–balanced partitions in distance–regular graphs // Discr. Math. 2003. Vol. 264. Pp. 149–165.

[3] Martin W. J. Completely Regular Designs // J. Combin. Designs.

1998. Vol. 6, № 4. Pp. 261–273.

[4] Alltop W.O. Extending t-designs // Journal of Combinatorial Theory Ser. A. 1975. Vol. 18, iss. 2. Pp. 177–186.

[5] Avgustinovich S.V., Mogilnykh I.Yu. Perfect 2-colorings of Johnson graphs J(6, 3) and J(7, 3) // LNCS, Springer. 2008. Vol. 5228. Pp.

11–19.

[6] Avgustinovich S.V., Mogilnykh I.Yu. On completely regular codes in Johnson graphs J(2w + 1, w) with covering radius 1 // Proceedings of 12th International workshop on Algebraic Combinatorial Coding Theory (ACCT-2010). Pp. 20–26. Novosibirsk, 2010.

Алгебра КОНЕЧНОСТЬ ЧИСЛА Aut0(d)-СИММЕТРИЧЕСКИХ q-РАСШИРЕНИЙ РЕШЕТКИ d ДЛЯ ПРОСТОГО q Неганова Е.А., Трофимов В.И.Пусть d целое положительное число. Под d-мерной решеткой d далее, как обычно, понимается граф, вершинами которого являются все упорядоченные наборы (a1,...ad) из d целых чисел, и две вершины (a 1,..., a d) и (a 1,...a d) смежны тогда и только тогда, когда выполняется условие |a 1 - a 1| +... + |a d - a d| = 1.

Сдвигом решетки d называется ее автоморфизм, который переводит произвольную вершину (a1,..., ad) в вершину (a1 + k1,..., ad + kd) для некоторых фиксированных целых чисел k1,..., kd. Обозначим через Aut0(d) изоморфную Zd подгруппу группы автоморфизмов решетки d, состоящую из всех ее сдвигов.

Пусть q целое положительное число. Связный граф называется Aut0(d)-симметрическим q-расширением решетки d, если существуют такая вершинно-транзитивная группа G автоморфизмов графа и такая система импримитивности группы G на V () с блоками порядка q, что для некоторого изоморфизма графа / на решетку d справедливо G-1 = Aut0(d).

Aut0(d)-симметрические q-расширения решеток d для d 1 и q > 1 представляют интерес (см. [1]) в связи с кристаллографией частиц с внутренней структурой и теорией струн.

В общем случае открытым является вопрос о конечности множества Aut0(d)-симметрических q-расширений решетки d для произвольных целых положительных чисел d и q (см. вопрос 3 из [1]).

Нами получен следующий результат.

Теорема. Для произвольного целого положительного числа d и для произвольного целого простого числа q имеется лишь конечное множество Aut0(d)-симметрических q-расширений решетки d.

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

78 Тезисы 43-й молодежной школы-конференции Литература [1] Trofimov V.I. Symmetrical extensions of graphs and some other topics in graph theory related with group theory // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 185–189.

Алгебра О СТРУКТУРЕ НЕРАЗРЕШИМЫХ SM2-ГРУПП Поляков С.В.

Наша цель описать структуру конечных неразрешимых групп, у которых квадрат любого неприводимого представления разлагается в сумму неприводимых представлений с малыми кратностями.

Определение 1. Конечную группу G назовем SMm-группой1, если тензорный квадрат любого ее неприводимого представления разлагается в сумму неприводимых представлений группы G с кратностями, не превосходящими m.

Интерес к рассматриваемым группам вызван недавно полученными результатами для конечных SR и ASR групп. Было доказано (см. работы [2] и [3]), что эти группы являются разрешимыми. Этого уже нельзя сказать про SM2-группу A5.



Для доказательства основных результатов была использована теорема Классификации конечных простых неабелевых групп. В ряде случаев необходимые вычисления велись в системе GAP([7]).

Свойства SMm-групп Перечислим здесь свойства, вытекающие непосредственно из определения конечных SMm-групп:

Утверждение 1. Пусть G конечная SMm-группа, ее неприводимый характер, а k(G) число классов сопряженных элементов в G. Тогда 1) (1) mk(G);

2) |G| m2k(G)3;

3) 2(1) m |G|k(G);

4) (1) mk(G) - m, если G неразрешимая группа.

Используя эти свойства для m = 2, удалось значительно сократить список простых и почти простых неабелевых SM2-групп. После дополнительной проверки при помощи GAP, а также таблиц характеров была доказана от Square multiplicity 80 Тезисы 43-й молодежной школы-конференции Теорема 1. Пусть G конечная почти простая SM2-группа. То гда G P GL2(q).

= В ходе доказательства также были получены утверждения, касающиеся ряда простых групп, в частности, групп L2(q), L3(q) и U3(q):

1. Группа L2(q), для нечетных q, за исключением группы L2(5) A5, не является SM2-группой.

= 2. Группы P GL2(q) являются SM2-группами для любого q > 3.

3. Если L2(q) < G Aut(L2(q)), q > 3, и G = P GL2(q), то G не SM2-группа.

4. В группе L3(q) найдутся неприводимые характеры, степеней (q + 1)(q2 + q + 1) и (q - 1)2(q + 1) соответственно такие, что [2, ] = (q - 1, n) · (q + 3).

5. В группе U3(q), для подходящего q, найдутся неприводимые характеры, степеней степеней q3 + 1 и (q + 1)2(q - 1) такие, что [2, ] = q + 2.

Неразрешимые SM2-группы Опытным путем для неразрешимых SM2-групп небольшого порядка было установлено, что все их неабелевы композиционные факторы изоморфны L2(q). Будем считать, что G неразрешимая SM2группа наименьшего порядка, в которой существуют неабелевы композиционные факторы, отличные от L2(q). В этом случае оказывается верна:

Теорема 2. Пусть N минимальная нормальная подгруппа группы G. Тогда:

1) G/N разрешимая группа, а N цоколь группы G;

2) N L1 · · ·Lk, где Li изоморфны простой неабелевой группе = L;

3) G подгруппа сплетения Aut(L) S, где S Sk подгруппа симметрической группы степени k, действующая транзитивно на множестве минимальных нормальных подгрупп группы N.

Алгебра Из теоремы 2, с учетом свойств SM2-группы, доказывается, что цоколь N представляет собой прямое произведение групп, изоморфных L2(q). Таким образом, доказана Теорема 3. Пусть G неразрешимая SM2-группа. Тогда ее неабелевы композиционные факторы изоморфны группе L2(q).

В заключении отметим, что в рассмотренных примерах SM2групп количество факторов, изоморфных L2(q), не превосходит двух.

Литература [1] Белоногов В.А. Представления и характеры в теории конечных групп. Свердловск: УрО АН СССР, 1990.

[2] Казарин Л.С., Янишевский В.В. О конечных просто приводимых группах // Алгебра и анализ. 2007. Т. 19, № 6. С. 86-116.

[3] Казарин Л.С., Чанков Е.И. Конечные просто приводимые группы разрешимы // Математический сборник. 2010. Т. 201, № 5. С.

27-40.

[4] Conway J.H., Curtis R.T., Norton S.P., Parker R.A., Wilson R.A. Atlas of Finite Groups. Oxford: Clarendon Press, 1985.

http://brauer.maths.qmul.ac.uk/Atlas/v3/ [5] Isaacs I.M. Character theory of finite groups. N.Y.: Acad. Press, 1976.

[6] Simpson W.A., Frame W.A. The character tables for SL(3, q), SU(3, q), P SL(3, q), P SU(3, q) // Can. J. Math. 1973. Vol. XXV, № 3. Pp. 486–494.

[7] The GAP Group, GAP Groups, Algorithms and Programming, Version 4.4.10, Aachen, St. Andrews, 2008;

http://www.gap-system.org [8] Wigner E.P. On representations of finite groups // Amer. J. Math.

1941. Vol. 63. Pp. 57-63.

82 Тезисы 43-й молодежной школы-конференции ГРУППЫ, НАСЫЩЕННЫЕ ПРЯМЫМИ ПРОИЗВЕДЕНИЯМИ КОНЕЧНЫХ ПРОСТЫХ НЕАБЕЛЕВЫХ ГРУПП Сабодах И.В., Шлепкин А.А.

Понятие насыщенности группы заданным множеством групп появилось в 1993 году в работе А.К. Шлепкина [1].

Группа G насыщена группами из множества групп M, если любая конечная подгруппа из G содержится в подгруппе, изоморфной некоторой группе из M.

В настоящее время сложилась следующая терминология и обозначения, связанные с условием насыщенности. Насыщающее множество – это множество M из определения насыщенности. Группа G насыщена группой M – это случай, когда насыщающее множество M = {M} состоит из одной группы.

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

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

Нами продолжено изучение групп, насыщенных прямым произведением различных групп. Пусть множество M = {M} состоит из одной группы M, являющейся прямым произведением групп из i i {L (pn )|i = 1, 2,..., m}, где через L(pn) обозначается группа L3(pn), 3 i если = +, и группа U3(pn), если = -.

Доказан следующий результат.

Теорема. Пусть группа Шункова G насыщена группой M. Тогда G обладает периодической частью T (G) M.

Алгебра Литература [1] Шлепкин А.К. Сопряженно бипримитивно конечные группы, содержащие конечные неразрешимые подгруппы / Труды III международной конференции по алгебре. С. 363. Красноярск, 1993.





[2] Сабодах И.В., Шлепкин А.А. Группы, насыщенные прямыми произведениями конечных простых неабелевых групп / в сб.

Студент и научно-технический прогресс: Математика, материалы XLIX Международной научной студенческой конференции.

С. 21. Новосибирск, 2011.

[3] Сабодах И.В., Шлепкин А.А. Группы, насыщенные прямыми произведениями линейных групп размерности 2 / в сб. Современные проблемы математики, тезисы 42-й Всероссийской молодежной школы-конференции. С. 240. Екатеринбург, 2011.

84 Тезисы 43-й молодежной школы-конференции О СВОЙСТВАХ ХРОМАТИЧЕСКОГО ИНВАРИАНТА P T (G, + 1) Сеньчонок Т.А.

Пусть G произвольный (n, m, k)–граф, т.е. граф, имеющий n вершин, m рёбер и k компонент связности. Раскраской, или tраскраской, графа G называется отображение из множества вершин V в множество натуральных чисел{1, 2,..., t}такое, что для любых двух различных смежных вершин u и v графа G выполняется (u) = (v), т.е. любые две различные смежные вершины имеют раз ный цвет. Граф называется t-раскрашиваемым, если он обладает t-раскраской, и t-хроматическим, если он t-раскрашиваемый, но не является (t - 1)-раскрашиваемым; в этом случае число t называют хроматическим числом графа G и обозначают через (G).

Для натурального числа x через P (G, x) обозначим число всевозможных раскрасок графа G в x заданных цветов, причем не предполагается, что в раскраске должны быть использованы все x цветов.

Хорошо известно (см. [1]), что функция P (G, x) является многочленом степени n от x, который называют хроматическим многочленом графа G. Два графа называются хроматически эквивалентными или -эквивалентными, если они имеют одинаковые хроматические многочлены.

Граф является хроматически определяемым или -определяемым, если он изоморфен любому хроматически эквивалентному ему графу. Это понятие ввели Chao C.Y. и E.G. Whitehead Jr. [2].

Различными авторами были проведены многочисленные исследования по изучению хроматической эквивалентности и хроматической определяемости для графов. Большое место в них уделено изучению хроматической определяемости полных многодольных графов.

Граф G называют t-дольным графом, если множество его вершин можно разбить на t непустых подмножеств (долей) так, что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина из одной доли соединена с каждой вершиной из других долей, то G называют полным t-дольным графом и обозначают через K(n1, n2,..., nt), где n1, n2,..., nt числа элементов в долях этого графа.

Алгебра В 1990 г. Koh K.M. и Teo K.L. [3] доказали, что полный двудольный граф K(n1, n2) хроматически определяем при n1 n2 2.

Тогда же Li N.Z. и Liu R.Y. [4] доказали, что граф K(1, n2,..., nt) -определяем тогда и только тогда, когда max{n2,..., nt} 2.

Известны многочисленные работы китайских авторов на эту тему. Они рассматривали графы для различных конкретных наборов (n1, n2,..., nt) и доказывали их хроматическую определяемость при достаточно большом количестве вершин в долях.

В ходе исследований различных авторов возникла следующая гипотеза: любой полный многодольный граф K(n1, n2,..., nt) является хроматически определяемым при t 3 и n1 n2... nt 2.

Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвариантами являются числа вершин, рёбер и компонент связности графа [5]. Число рёбер графа G будем обозначать через I2(G). Отметим, что число его вершин можно было бы обозначить через I1(G). Ещё одним хроматическим инвариантом является I3(G) число треугольников в графе G (см. [6] или [7]).

Далее через pt(G, i) мы будем обозначать число разбиений множества вершин графа G на i непустых коклик, т.е. подмножеств, состоящих из попарно несмежных вершин графа G. По теореме Зыкова (см. [8]), n P (G, x) = pt(G, i)x(i), i= где через x(i) обозначается факториальная степень переменной x, т. е. x(i) = x(x-1)(x-2)... (x-i+1), а через хроматическое число графа G. В силу указанной теоремы числа pt(G, i) при i n являются хроматическими инвариантами. Нас особенно будет интересовать инвариант pt(G, + 1).

Вычислим значение инварианта pt(G, + 1) для полного tдольного графа G = K(n1, n2,..., nt), где n1 n2... nt 1.

Здесь = t и раскраска графа в t цветов даёт единственное разбиение множества его вершин на t коклик долей этого графа. Разбиение на t + 1 непустых коклик получается из предыдущего разбиения разбиением одной из долей на два непустых подмножества. Следо1-t-вательно, pt(K(n1, n2,..., nt), t + 1) = 2n - 1 +... + 2n - 1 = 86 Тезисы 43-й молодежной школы-конференции 1-t-= 2n +... + 2n - t.

Любой граф G с хроматическим числом = t может быть представлен в виде G = K -E, где K = K(n1, n2,..., nt) это некоторый полный t-дольный граф, а E множество отбрасываемых рёбер.

Основным нашим результатом является следующая Теорема. Если |E| = k, то k pt(K, + 1) - pt(G, + 1) 2k - 1.

Полученная оценка для изменения инварианта pt(G, +1) может быть эффективно использована для доказательства хроматической определяемости графов.

Литература [1] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ Регулярная и хаотическая динамика, 2001.

[2] Chao C.Y., E.G. Whitehead Jr. On chromatic equivalence of graphs // Theory and applications of graphs. 1978. Vol. 642. Pp. 121–131.

[3] Koh K.M., Teo K.L. The search for chromatically unique graphs // Graphs Combin. 1990. Vol. 6. Pp. 259–285.

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 38 |










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

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