WWW.DISSERS.RU

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

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


Pages:     | 1 || 3 | 4 |   ...   | 38 |

Работа поддержана грантом РФФИ № 10-01-00509-a и АВЦП Развитие научного потенциала высшей школы № 2.1.1/3023.

12 Тезисы 43-й молодежной школы-конференции КОМБИНАТОРНАЯ СЛОЖНОСТЬ ПЕРЕСТАНОВОК, ПОРОЖДАЕМЫХ НЕПОДВИЖНЫМИ ТОЧКАМИ НЕКОТОРЫХ РАВНОБЛОЧНЫХ БИНАРНЫХ МОРФИЗМОВ Валюженич А.А.

Бесконечное вправо слово над алфавитом это слово вида = 123..., где каждое i. Для слова определим бинарное действительное число R(i) = 0.ii+1... = i+k2-(k+1).

k Отображение h : - называется морфизмом, если h(xy) = = h(x)h(y) для любых слов x, y. Будем говорить, что неподвижная точка морфизма, если () =. Всякий морфизм однозначно определяется образами символов алфавита, которые мы будем называть блоками. Морфизм называется равноблочным, если его блоки имеют одинаковую длину. Морфизм : - называется маркированным, если его блоки имеют вид:

(ai) = bixci, где x произвольное слово, а bi и ci символы алфавита, причем все bi (как и все ci) различны. В дальнейшем мы будем рассматривать только маркированные равноблочные морфизмы с длиной блоков l. Отметим, что для всех неподвижных точек () = рассматриваемых нами морфизмов существует число L такое, что любое подслово слова длины не менее L однозначно разбивается на блоки. Определим функцию : R2 \{(a, a)|a R} {<, >}, которая двум различным действительным числам ставит в соответствие их отношение.

Равноблочный морфизм : {0, 1} - {0, 1} будем называть сравнимым, если его неподвижная точка = () удовлетворяет следующему условию: пусть i = j, где i i (mod l), j j ( mod l) и 0 i, j l - 1, причем i и j фиксированы. Если i = j или если i и j лежат в блоках разного типа в правильном разбиении, то отношение (R(i), R(j)) определено однозначно.

В следующих трех утверждениях мы находим условие, по которому можно определить, является ли маркированный морфизм сравнимым.

Алгебра Утверждение 1. Пусть неподвижная точка маркированного равноблочного морфизма, причем (0) = A, (1) = B. Тогда верны следующие утверждения:

1) если 0u1 является подсловом A или B, причем A = 0u0x, где x некоторое слово, то не является сравнимым морфизмом;

2) если 1u0 является подсловом A или B, причем B = 1u1x, где x некоторое слово, то не является сравнимым морфизмом.

Утверждение 2. Пусть неподвижная точка маркированного равноблочного морфизма, причем (0) = A, (1) = B. Тогда верны следующие утверждения:

1) если 0u является суффиксом A или B, причем A = 0u0x, где x некоторое слово, то не является сравнимым морфизмом;

2) если 1u является суффиксом A или B, причем B = 1u1x, где x некоторое слово, то не является сравнимым морфизмом.

Утверждение 3. Пусть неподвижная точка маркированного равноблочного морфизма, для которого не выполнены условия утверждений 1 и 2. Тогда сравнимый морфизм.

Пусть бесконечное вправо непериодическое слово над алфавитом. Тогда определим бесконечную перестановку, порождаемую словом, как упорядоченную тройку = N, <, <, где < и < линейные порядки на N. При этом < определяется следующим образом: i

Определим комбинаторную сложность (n) = |Perm(n)| перестановки, порождаемой некоторым словом как число различных её подперестановок. Понятие бесконечной перестановки было введено в [1], где, кроме того, исследовались свойства периодичности и низкая комбинаторная сложность перестановок. Понятие перестановки, порожденной бесконечным непериодическим словом, было введено Макаровым в [2]. В работе [3] тот же автор вычислил комбинаторную сложность перестановок, порожденных хорошо известным семейством слов Штурма. В работе [5] Уидмер вычислил комбинаторную сложность перестановки Туэ-Морса. В настоящей работе найдена комбинаторная сложность перестановок, порожденных неподвижными точками сравнимых морфизмов.

14 Тезисы 43-й молодежной школы-конференции Определим функию (n, z): если n = ls|z| + 1 для некоторого натурального s, то (n, z) = 1, иначе (n, z) = 0.

Теорема 1. Пусть неподвижная точка сравнимого морфизма. Тогда комбинаторная сложность перестановки, порожденной nar, вычисляется следующим образом: (n) = [Ca (n)(ma + a1A1 bad wide +na ) + (Ca (n) + Ca (n))(ma + 2na )] + Ca (n)ma 1 1 1 a2A2 2 1 - [Sz(n - 1)(kz + tz + rz)(1 - (n, z)) + (kz + rz)(n, z)] для zZ n L.

Все функции, входящие в условие теоремы, определяются в работе [4].

Литература [1] Fon-Der-Flaass D.-G., Frid A.E. On periodicity and low complexity of infinite permutations // European J. Combin. 2007. Vol. 28, № 8.

Pp. 2106-2114.

[2] Makarov M.A. On permutations generated by infinite binary words // Sib. Elektron. Mat. Izv. 2006. Vol. 3. Pp. 304-311.

[3] Makarov M.A On the permutations generated by the Sturmian words // Sib. Math. J. 2009. Vol. 50, № 3. Pp. 674-680.

[4] Valyuzhenich A. Permutation complexity of the fixed points of some uniform binary morphisms // EPTCS 63 (2011), Proceedings of WORDS 2011. Pp. 257-264.

[5] Widmer S. Permutation complexity of the Thue-Morse word // Adv.

in Appl. Math. 2010.

Алгебра О СИЛЬНО РЕГУЛЯРНЫХ СИСТЕМАХ ТРОЕК Воробьёв К.В.Граф G = (V, E) называется сильно регулярным с параметрами (v, k,, µ), если |V | = v, граф G является связным регулярным степени k, любая смежная пара вершин имеет общих соседей, и любая пара несмежных вершин имеет µ общих соседей [1].

Д.Г. Фон-Дер-Флаассом было введено определение сильно регулярной системы троек. Пусть V – конечное множество, пусть T – подмножество множества трёхэлементных подмножеств V. T называется сильно регулярной системой троек с параметрами = (0, 1, 2, 3) и M = (µ0, µ1, µ2, µ3), если для любых трех различных вершин u, v, w верно следующее:



1. Если {u, v, w} T, то (a) |{x V \ {u, v, w}|{x, v, w}, {u, x, w}, {u, v, x} T }| = 0;

/ (b) |{x V \ {u, v, w}|{x, v, w}, {u, x, w}, T, {u, v, x} T }| = / = 1;

(c) |{x V \ {u, v, w}|{x, v, w} T, {u, v, x}, {u, x, w} T }| = / = 2;

(d) |{x V \ {u, v, w}|{x, v, w}, {u, x, w}, {u, v, x} T }| = 3.

2. Если {u, v, w} T, то / (a) |{x V \ {u, v, w}|{x, v, w}, {u, x, w}, {u, v, x} T }| = µ0;

/ (b) |{x V \ {u, v, w}|{x, v, w}, {u, x, w}, T, {u, v, x} T }| = / = µ1;

(c) |{x V \ {u, v, w}|{x, v, w} T, {u, v, x}, {u, x, w} T }| = / = µ2;

(d) |{x V \ {u, v, w}|{x, v, w}, {u, x, w}, {u, v, x} T }| = µ3.

Работа поддержана грантом Президента Российской Федерации для молодых ученых (МК-1700.2011.1).

16 Тезисы 43-й молодежной школы-конференции Для любой системы троек T и любой ее вершины u определен граф G на V \{u}: его ребрами являются те пары {v, w}, для которых {u, v, w} T. Будем говорить, что граф G индуцирован системой T и вершиной u. Несложно доказать, что индуцированные графы сильно регулярной системы троек являются сильно регулярными, при этом относительно любой вершины системы троек индуцируется сильно регулярный граф с одинаковым набором параметров (v, k,, µ).

Cильно регулярная система троек T называется сильно регулярным расширением графа G, если в результате этой операции относительно любой вершины системы троек получается граф, изоморфный G. В работе исследуется существование сильно регулярных расширений сильно регулярных графов на небольшом количестве вершин. Основным результатом работы является Теорема. Существуют сильно регулярные расширения графа Петерсена с параметрами = (2, 2, 0, 0) и M = (2, 1, 1, 0) и графа решетки 33 с параметрами = (0, 2, 0, 1) и M = (1, 0, 2, 0). Не существует сильно регулярных расширений графов Шрикхандэ, Пэли порядка 13 и L(K6).

Литература [1] Брауэр А.Е., Ван Линт И.X. Сильно регулярные графы и частичные геометрии / в Киберн. сб. № 24. С. 186–229. М.: Наука, 1987.

Алгебра О НЕИЗОМОРФНЫХ СОВЕРШЕННЫХ 2-РАСКРАСКАХ ГРАФА ДЖОНСОНА J(10, 3) Гаврилюк А.Л., Горяинов С.В., Могильных И.Ю.Графом Джонсона J(v, k) называется граф, вершинами которого являются все k-элементные подмножества некоторого v-элементного множества; два подмножества смежны, если они имеют точно k - общих элементов. Графы J(v, k) и J(v, v - k) изоморфны, поэтому далее считаем, что k v/2. Граф Джонсона является дистанционнорегулярным, см. [1], имеет диаметр k и k + 1 различных собственных значений: i = (k - i)(v - k - i) - i, i = 0,..., k.

Совершенной раскраской графа в t цветов (далее, для краткости t-раскраской) называется разбиение множества вершин на t классов (цветов) C1,..., Ct такое, что для любых i, j {1,..., t} любая вершина из класса Ci смежна с одним и тем же числом вершин, а именно, cij, из класса Cj. Матрица C = (cij)i,j=1,...,t называется матрицей параметров t-раскраски. Мы не различаем раскраски, полученные переименованием цветов.

Хорошо известно [2], что собственные значения матрицы параметров совершенной раскраски являются собственными значениями графа. В частности, если C матрица параметров совершенной 2раскраски графа Джонсона J(v, k), то она имеет два собственных значения: 0 = k(v - k) валентность графа J(v, k) и i, i > 0.

Изучение совершенных 2-раскрасок графов Джонсона связано с гипотезой Дельсарта о несуществовании совершенных кодов в этих графах и более общей задачей изучения полностью регулярных кодов, см. [3]. Из работ [4] и [2] следует описание 2-раскрасок J(v, k), матрицы параметров которых имеют собственные значения 1 или k. В серии работ [3], [5], [6] были описаны совершенные 2-раскраски графов Джонсона J(v, k) при v 8 и J(v, 2). В частности, в работе [3] был поставлен вопрос о существовании 2-раскраски графа J(9, 3) 10 с матрицей параметров, отрицательный ответ на кото8 Работа поддержана грантом РФФИ № 12-01-00551-а, программой совместных исследований УрО РАН с СО РАН, программой поддержки молодых ученых УрО РАН, третий автор поддержан грантами МК-1700.2011.1, РФФИ № 09-0100244 и РФФИ 10-01-00616-a.

18 Тезисы 43-й молодежной школы-конференции рый дает одна из следующих двух теорем из [7].

Теорема 1. При нечетных v граф J(v, 3) не допускает совершенных 2-раскрасок, матрица параметров которых имеет собственное значение 2.

Теорема 2. Если v четно и A симметричная матрица параметров совершенной 2-раскраски графа J(v, 3), имеющая собствен2v - 8 v - ное значение 2, то v 2 (mod 4), A = и либо v - 1 2v - v = 6 или 10, либо v > 22.

Пример раскраски из теоремы 2 при v = 6 был построен в работе [6], а при v = 10 в работе [3].

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

Известно лишь, что системы троек и четверок Штейнера и кратные совершенные коды в J(6, 3) (в некотором смысле, тривиальные конструкции) дают примеры неизоморфных раскрасок с одинаковыми матрицами параметров.

В данной работе показано, что граф J(10, 3) имеет две неизоморфные совершенные 2-раскраски с матрицей параметров 12.

9 Как отмечалось выше, одна из них построена в [3]. Новая, найденная в данной работе, может быть описана с помощью орбит некоторой подгруппы группы автоморфизмов графа J(10, 3). Рассмотрим граф, состоящий из двух изолированных 5-циклов. Занумеруем его вершины некоторым образом и сопоставим естественным образом каждой тройке вершин графа некоторую вершину графа J(10, 3).





Группа автоморфизмов графа действует транзитивно на следующих множествах троек вершин из (и, значит, соответствующих множествах вершин J(10, 3)):

• тройки вершин из, образующих 2-пути в обоих циклах (всего 10 таких троек);

• тройки вершин из, две вершины из которых смежны в одном Алгебра из циклов, а оставшаяся вершина принадлежит другому циклу (имеется 50 таких троек);

• тройки вершин из, все три вершины которых лежат в одном цикле и состоят из пары смежных вершин и одной изолированной от них вершины (всего 10 таких троек);

• тройки вершин из, пара вершин которых принадлежит одному циклу и несмежна, а оставшаяся вершина принадлежит другому циклу (имеется 50 таких троек).

Теперь два подграфа графа J(10, 3), индуцированные объединением двух первых множеств и двух последних множеств соответственно, задают совершенную 2-раскраску J(10, 3) с указанной матрицей параметров. Легко проверить, что она не изоморфна 2-раскраске, описанной в [3].

Литература [1] Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin, New-York, Heidelberg: Springer-Verlag, 1989.

[2] Martin W.J. Completely regular designs of strength one // J. Algebr.

Comb. 1994. Vol. 3. Pp. 170–185.

[3] Августинович С.В., Могильных И.Ю. Совершенные раскраски графов Джонсона J(8, 3) и J(8, 4) в два цвета // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 2. С. 3–19.

[4] Meyerowitz A.D. Cycle-balanced partitions in distance-regular graphs // J. Combin. Inform. System Sci. 1992. Vol. 17. Pp. 39–42.

[5] Могильных И.Ю. О несуществовании некоторых совершенных 2раскрасок графов Джонсона // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 5. С. 52–68.

[6] Mogilnykh I.Yu., Avgustinovich S.V. Perfect 2-colorings of Johnson graphs J(6, 3) and J(7, 3) // Lect. Notes Comp. Sci. Vol. 2008. 5228.

Pp. 11–19.

[7] Gavrilyuk A.L., Goryainov S.V. On perfect 2-colorings of Johnson graphs J(v, 3) / Тез. докл. Межд. конф. Мальцевские чтения.

С. 64–65. Новосибирск, 2011.

20 Тезисы 43-й молодежной школы-конференции ГРАФЫ ДЕЗА С 4-МЯ РАЗЛИЧНЫМИ СОБСТВЕННЫМИ ЗНАЧЕНИЯМИ Гаврилюк А.Л., Шалагинов Л.В.Для вершины x графа через 1(x) обозначим множество соседей вершины x. Сильно регулярным графом с параметрами (v, k,, µ) называется граф такой, что для любых его вершин x, y множество 1(x)1(y) содержит k вершин, если x = y, вершин, если вершины x, y смежны, и µ вершин, если x, y не смежны.

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

Матрицей смежности графа на v вершинах называется (0, 1)матрица A размера v v, строки и столбцы которой проиндексированы вершинами, и для вершин x, y графа имеем Ax,y = 1, если x и y смежны, и Ax,y = 0 в противном случае. Спектром (собственным значением) графа называется спектр (собственное значение) его матрицы смежности.

Хорошо известно, что регулярный граф (в котором каждая вершина имеет одно и то же число соседей), имеющий точно 3 различных собственных значения, сильно регулярен. Более того, эти собственные значения могут быть вычислены из параметров v, k,, µ.

Для графов Деза подобная характеризация не известна авторам.

Спектр графов Деза не определяется из параметров v, k, b, a по крайней мере, с точностью до кратностей собственных значений.

Теперь понятно, что граф Деза имеет по крайней мере 4 различных собственных значения. В докладе речь пойдет об этом экстремальном случае. В частности, в работе вычислены спектры некоторых конструкций графов Деза из [1] и показано, что многие из Работа поддержана программой совместных исследований УрО РАН с СО РАН, программой поддержки молодых ученых УрО РАН, грантом МК938.2011.2.

Алгебра них имеют точно 4 различных собственных значения. В статье [2] показано, что еще одна конструкция графов Деза (являющихся подграфами определенного вида в симплектических сильно регулярных графах) дает графы точно с 4 различными собственными значениями. Построенные в статье [3] графы Деза имеют 5 различных собственных значений. Среди всех графов Деза с не более чем 16 вершинами (их описание см. в [4]) имеется граф с параметрами (16, 5, 2, 1), спектр которого имеет 7 различных собственных значений. С другой стороны, не сложно получить следующий результат.

Утверждение 1. Для любого натурального s существует граф Деза, имеющий не менее s различных собственных значений.

Пример такого графа обеспечивает конструкция прямого произведения двух графов Деза с параметрами b = 2, a = 0. Заметим, что графы Деза с условием a = 0 могут иметь диаметр больше 2.

Предложение 1. Граф Деза с параметрами (v, k, b, 0) и точно 4мя различными собственными значениями имеет диаметр 2.

В связи с утверждением 1 интересно, существуют ли константы A > 0 или 0 < M < 1 такие, что любой граф Деза на v вершинах имеет не более чем v - A или vM различных собственных значений.

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

Pages:     | 1 || 3 | 4 |   ...   | 38 |










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

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