Содержание к диссертации
Введение
1 Конструкции совершенных 2-раскрасок графов Джонсона 28
2 Необходимые условия существования совершенных 2-раскрасок графов Джонсона 40
2.1 Спектр белых вершин совершенной 2-раскраски относи-\ тельно дистанционно-регулярного расслоения 41
2.2 Пространства собственных векторов и свойство к-регулярности совершенных раскрасок 44
2.2.1 Собственные значения и собственные векторы графов 45
2.2.2 Собственные значения совершенных 2-раскрасок графа Джонсона и свойство k-регулярности 47
2.3 Нижняя оценка параметра a,2i совершенной 2-раскраски графа Джонсона 55
2.4 Несуществование некоторых совершенных 2-раскрасок графов Джонсона 62
3 Совершенные 2-раскраски графов J(n,w), п < 8 70
3.1 Совершенные 2-раскраски графа J(6,3) 71
3.2 Совершенные 2-раскраски графа J(7,3) 75
3.3 Совершенные 2-раскраски графа J(8,3) 76
3.4 Совершенные 2-раскраски графа J(8,4) 81
4 Слабые изометрии кодов Препараты 85
4.1 Слабые изометрии выколотых кодов Препараты 85
4.2 Слабые изометрии кодов Препараты 92
5 Приложение 94
Литература 99
- Спектр белых вершин совершенной 2-раскраски относи-\ тельно дистанционно-регулярного расслоения
- Собственные значения и собственные векторы графов
- Несуществование некоторых совершенных 2-раскрасок графов Джонсона
- Слабые изометрии кодов Препараты
Введение к работе
Актуальность темы. В настоящей диссертации исследуются проблемы существования и перечисления объектов, находящихся на стыке алгебраической комбинаторики, теории кодов, исправляющих ошибки в канале связи с шумами и теории графов. Предметом исследования данной работы являются совершенные 2-раск-раски графов Джонсона, тесно связанные с равновесными совершенными кодами и блок-схемами.
Под совершенной раскраской в т цветов (совершенной т-раскраской) графа G с матрицей A = {aij}i,j=i,...,m понимается раскраска вершин графа G в множество цветов {1,..., т} такая, что число вершин цвета j, смежных с фиксированной вершиной цвета г, однозначно определено цветом последней вершины и равно a,ij. Матрица А называется матрицей параметров совершенной раскраски. Разбиение вершин графа G по цвету, естественно ассоциируемое с совершенной раскраской этого графа, в англоязычной литературе обычно называется equitable partition. Если такое разбиение получено дистанционным образом относительно некоторой совокупности С вершин графа, то множество С называют полностью регулярным кодом в графе G (по Ньюмайеру [27]). Отметим, что такое определение полностью регулярного кода совпадает с исходным, введенным Ф. Дельсартом в [11], если граф G является дистанционно-регулярным. Непосредственно из приведенных определений следует, что совершенные 2-раскраски есть суть полностью регулярные (в том числе и 1-совершенные) коды по Ньюмайеру с радиусом покрытия 1. В случае совершенных раскрасок в два цвета цвет номер 1 будем называть белым, а цвет номер 2 -черным.
Граф Джонсона J(n, w) (названный так в честь первого из исследователей одноименной схемы ассоциативности [22]) определяется как граф, вершинами которого являются всевозможные двоичные векторы длины new единичными координатами, пара векторов соединяется ребром, если они различаются ровно в двух координатах.
Одной из основных проблем теории кодирования и дискретной математики является проблема существования объектов с определенными свойствами. Вопросы существования таких структур как
совершенные, полностью регулярные и равномерно упакованные коды, блок-схемы и совершенные раскраски различных графов уже на протяжении многих лет притягивают внимание многих выдающихся математиков. При этом одним из ключевых моментов доказательств обычно является установление некоторых свойств этих объектов, влекущих сильные необходимые условия на существование подобных объектов.
Первая бесконечная серия совершенных блоковых кодов была построена Р. Хэммингом в 1950 году [19]. Спустя более чем 20 лет В. А. Зиновьев и В. К. Леонтьев [4], [5], и независимо Э. Титвайнен в [33], доказали что кодов с параметрами, отличными от параметров кода Хэмминга, за исключением двоичного и троичного кодов Голея над полями Галуа не существует.
Ф. Дельсарт в [11] ввел понятие полностью регулярных кодов в дистанционно-регулярных графах, класса кодов, включающего в себя совершенные коды и обладающих многими схожими с ними свойствами. Проблема существования полностью регулярных кодов в n-кубе является нерешенной, то есть известны не все параметры, для которых существуют полностью регулярные коды. Известно, что класс полностью регулярных кодов в n-кубе содержит равномерно упакованные коды в узком смысле, введенные Н. В. Семаковым, В. А. Зиновьевым и Г. В. Зайцевым в [6]. Эти коды включают совершенные и укороченные совершенные коды, выколотые коды Препараты, некоторые классы кодов БЧХ и выколотых кодов Рида-Маллера. Полное описание всех равномерно упакованных кодов было сделано X. К. А. ван Тилборгом в [34]. Упомянутая выше связь совершенных раскрасок и полностью регулярных кодов объясняет актуальность исследований равномерно упакованных кодов (в частности кодов Препараты) в рамках темы настоящей диссертации.
Проблема существования совершенных кодов в схеме Джонсона оказалась сложнее, чем аналогичная проблема в схеме Хэмминга. В работе [11], Дельсарт выдвинул гипотезу, что совершенных кодов в графе Джонсона не существует. Усилия целого ряда авторов так и не привели ни к ее доказательству, ни к ее опровержению. Один из лучших на сегодняшний день результатов был получен Д. Гордоном в 2006 году в работе [18]. Используя компьютер, он доказал, что не существует 1-совершенных кодов в графах Джонсона
J(n,w) при n < 2250.
Как отмечалось ранее, совершенные 2-раскраски являются обобщением 1-совершенных кодов. Заметим, что гипотеза Дельсарта не может быть обобщена на совершенные 2-раскраски графов Джонсона. У. Мартин в работе [24] заметил, что совершенную 2-раскрас-ку J(n, w) можно получить, покрасив блоки (w — l) — (n, w, А)-схемы (при этом подразумевается что все блоки схемы различны) в один цвет, а оставшиеся вершины J(n, w) в другой цвет. Проблема существования таких схем при w = 3 была решена М. Дегоном в 1983 в работе [10]; при w = 4 для А = 1 (системы четверок Штейнера) X. Ханани в работе [20], для А = 2 А. Хартманом и К. Т. Фелпсом в [21], для А = 3 К. Т. Фелпсом, Д. Р. Стинсоном и С. А. Ван-стоуном в работе [28], для A = 0(mod 3), где А=НОД(-и — 3,12)) доказана Л. Теирлинком в [31], для всех А, если п = Ъ 2т Т. Этци-оном и А. Хартманом в [12]. Проблема существования таких схем при w = 4 и А отличных от вышеперечисленных, за исключением нескольких спорадических случаев, является открытой. Для w = 4, 3-(25,4,4)-схема является схемой с наименьшим п, для которой вопрос существования открыт. Еще меньше результатов известно для w > 5. При А = 1 получено несколько спорадических примеров для w = 5, 6 и не найдено ни одной такой схемы для w > 7. При А > 1 и w > 5 можно особо выделить работу Л. Теирлинка [32], в которой установлено, что для любого w существуют (w — 1) — (п, w, А)-схемы при всех п = w — l(modA), где A = (w)l2w~l.
В данной диссертации впервые предпринято систематическое исследование проблемы существования совершенных 2-раскрасок графов Джонсона, включающей в себя вопросы существования (w— 1) — (n,w, А)-схем и совершенных равновесных кодов.
Цель данной работы состоит в исследовании необходимых условий существования совершенных 2-раскрасок графов Джонсона, в построении таких раскрасок и изучении их свойств.
Методика исследований. В диссертации используются традиционные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа, теории графов и теории блок-схем.
Научная новизна.
Все результаты, представленные в диссертации, являются новыми. В диссертации получено несколько конструкций совершенных 2-раскрасок графов Джонсона. Используя разработанные в диссертации алгебро-комбинаторные подходы, установлено несколько необходимых условий существования совершенных 2-раскрасок графов Джонсона.
Получен ряд конструкций совершенных 2-раскрасок графов Джонсона J(2w, w), J(2k, 3) для произвольных w, к, а также найдены спорадические конструкции совершенных 2-раскрасок графов J(6, 3), J(8, 3), J(8, 4). Найдены параметры всех выше перечисленных совершенных раскрасок.
Из работы А. Ньюмайера [27] следует, что число вершин белого цвета совершенной 2-раскраски дистанционно-регулярного графа, находящихся на расстоянии і от вершины х, зависит только от цвета вершины х и параметров совершенной раскраски. В диссертации получено обобщение этого результата - доказано, что количество вершин белого цвета совершенной 2-раскраски дистанционно-регулярного графа, находящихся на расстоянии і от произвольного полностью регулярного кода С, определяется однозначно массивом пересечений кода С, количеством белых вершин в С и параметрами совершенной 2-раскраски. Для доказательства использовалась система линейных алгебраических уравнений, схожая с системой уравнений, возникшей в работе Г. С. Шапиро и Г. Л. Злотника [30] при доказательстве дистанционной инвариантности совершенных кодов. Найденные в диссертации массивы пересечений некоторых полностью регулярных кодов в графах Джонсона позволили использовать данный результат для решения вопросов существования совершенных 2-раскрасок графов Джонсона.
Доказано, что совокупность белых вершин совершенной 2-раскраски графа J(n, w) является t — (п, w, А)-схемой, найдены явные выражения для параметров t и А. Полученное свойство является обобщением свойства /^-регулярности совершенных равновесных кодов, установленного Т. Этционом и М. Шварцем в [13]. Оно позволило использовать необходимые условия существования t-схем для решения вопросов существования совершенных 2-раскрасок графов Джонсона.
Анализируя графы, индуцированные сферами радиуса 1 и 2 в
графах Джонсона, получена нижняя оценка параметра й2\ совершенной 2-раскраски графа Джонсона с матрицей параметров А2х2, доказано несуществование ряда совершенных 2-раскрасок графов Джонсона .7(11,3), J(12,5), J(13,4), J(9,3).
С помощью полученных конструкций и разработанных необходимых условий существования перечислены (теоретически, без использования компьютера) параметры всех совершенных 2-раскрасок графов Джонсона J(n, w) для п < 8. С помощью компьютера доказано несуществование ряда совершенных раскрасок некоторых графов Джонсона J(n, w) для п, больших 8.
В данной диссертации доказано, что всякая слабая изомет-рия двух выколотых кодов Препараты является изометрией. С учетом установленной С. В. Августиновичем и Ф. И. Соловьевой в [2] метрической жесткости выколотых кодов Препарата отсюда вытекает, что слабоизометричные выколотые коды Препараты длины п > 210 — 1 являются эквивалентными, а группа автоморфизмов любого такого кода изоморфна группе автоморфизмов его графа минимальных расстояний. Аналогичные результаты доказаны для кодов Препараты длины, не меньшей 212.
Практическая и теоретическая ценность. Работа носит теоретический характер. Методы, разработанные в диссертации, могут быть применены для исследования вопросов существования полностью регулярных кодов и совершенных раскрасок различных графов, а также в теории блок-схем. Дальнейшее развитие этих методов может дать продвижения в доказательстве гипотезы Дель-сарта о несуществования совершенных равновесных кодов.
Апробация работы. Результаты работы прошли апробацию на следующих международных конференциях: на конференции по алгебраической и комбинаторной теории кодирования АССТ-Х (Звенигород, 2006); на международных симпозиумах по проблемам избыточности в информационных системах PRICS XI (Санкт-Петербург, 2007 г.) и PRICS XII (Санкт-Петербург, 2009 г.); Втором международном симпозиуме по проблемам теории кодирования и приложениям, 2ICMCTA (Медина дель Кампо, Испания, 2008 г.); Международной конференции по совершенным кодам и смежным вопросам, (Стокгольм, Швеция, 2009 г.). Результаты диссертации
докладывались на семинаре "Теория кодирования" и семинара лаборатории "Теория Графов" НГУ и Института математики СО РАН. Кроме того, некоторые результаты диссертации докладывались на семинаре группы "Отдела инженерии, информатики и связи" Независимого Университета г. Барселоны, Испания, и на семинаре Дискретного отдела Королевского Технологического Института г. Стокгольма, Швеция.
Результаты диссертации отмечены дипломами Международной Студенческой Научной Конференции (МНСК-2006, МНСК-2007), грантом "Академическая мобильность" фонда Культурных Инициатив Михаила Прохорова в 2009 году, стипендией Сибирского Математического Журнала для аспирантов в 2010 году.
Основные результаты диссертации.
Получен ряд (как бесконечных, так и спорадических) конструкций совершенных 2-раскрасок графов Джонсона.
Установлены следующие свойства совершенных 2-раскрасок:
Доказано, что спектр множества белых вершин совершенной 2-раскраски графа G относительно полностью регулярного кода С однозначно определяется количеством белых вершин, принадлежащих множеству С, массивом пересечений полностью регулярного кода С и параметрами рассматриваемой совершенной 2-раскраски.
Доказано, что множество вершин фиксированного цвета всякой совершенной 2-раскраски графа J(n, w) с матрицей параметров А образует t — (п, w, Л)-схему, где t и Л однозначно определяются числами n,w и матрицей А.
Получена нижняя оценка параметра й2\ совершенной 2-раскраски графа Джонсона с матрицей параметров А.
Перечислены параметры совершенных 2-раскрасок графов Джонсона J(n, w) для п < 8.
Доказано, что слабая изометрия двух выколотых кодов Препараты является изометрией. Аналогичный результат получен для кодов Препараты.
На защиту выносятся новые конструкции совершенных 2-раскрасок графов Джонсона, необходимые условия существования совершенных 2-раскрасок графов Джонсона.
Объем и структура диссертации. Диссертация состоит из введения, четвірех глав, приложения и списка литературві (61 наименование). Объем диссертации 105 страниц, включая 14 таблиц.
Спектр белых вершин совершенной 2-раскраски относи-\ тельно дистанционно-регулярного расслоения
У. Мартином в [41] доказаны некоторые необходимые условия существования полностью регулярных схем. Им доказано, что для всякой полностью регулярной схемы в J(n, w) с минимальным расстоянием 5 имеет место неравенство 5 (2w+1)/3. Более того, если минимальное расстояние такой схемы не меньше чем 2а, то такая схема является a—{n,w, Ла) , п[а/2\ -,Iа/21 -,а/21 схемой, где Ла CTl_w , а число блоков схемы не меньше Ci, C _WJ. С помощью полученных необходимых условий существования У. Мартином перечислены все полностью регулярные системы Штейнера силы 2 и все симметричные полностью регулярные схемы. Другие результаты о полностью регулярных кодах в графах Джонсона получены А. Мейеровицем. В [42] он доказал , что схема D является схемой силы 0 тогда и только тогда, когда D — {Ь Є J(n, w) : b С L] или D = {b Є J(n,w) : b Э L}, где L - некоторое подмножество множества {1,...,77,}. Другими словами, полностью регулярная схема силы 0 является орбитой стабилизатора некоторых из п координат на множестве векторов длины п веса w в группе перестановок Sn. У. Мартин в работе [40] предложил конструкцию полностью регулярной схемы, именуемой groupwise complete схемой. Пусть п — qpviw — sp, гДер 2 и q 2s. Пусть {Х\,... ,Xq} - разбиение множества {1,...,тг} на q подмножеств ХІ, каждое мощности р. Пусть блоки D это С подмножеств вида b — Uje/X;, где і" пробегает все подмножества множества {1,...,д} мощности s. У. Мартин показал, что такая схема является полностью регулярной тогда и только тогда, когда выполнено одно из следующих трех условий: p=w, n=2w или р=2 или р=3, s=l. Несложно видеть, что описанные выше схемы (именуемые groupwise complete схемы) имеют силу 1 и минимальное расстояние р. В работе [40] У. Мартин доказал, что всякая полностью регулярная схема силы 1 с минимальным расстоянием большим или равным 2 является groupwise complete схемой. Несмотря на ряд приведенных выше утверждений, множество вопросов, касающихся полностью регулярных равновесных кодов, остается открытым. Прежде всего не найдено эффективных критериев проверки, является ли данный код полностью регулярным или нет. Как следствие, не исследовано большое множество кодов, которые могли бы быть полностью регулярными. С другой строны, многие исследованные классы полностью регулярных кодов очень узки и поэтому соответствующие результаты носят частичный характер.
Также недостаточно изучены наиболее интересные случаи (в контексте данной диссертации )- схемы большой силы с минимальным расстоянием 5 = 1 и покрывающим радиусом р = 1 (по сути дела, совершенные 2-раскраски). Совершенные раскраски в два цвета произвольного радиуса бесконечной прямоугольной решетки исследовались М. Аксенович в работе [17]. В данном случае под совершенной раскраской радиуса г понимается раскраска вершин графа в множество цветов, при которой количество вершин цвета j, находящихся на расстоянии, не больше г от вершины х цвета г, не зависит от выбора вершины х. М. Аксенович была описана часть совершенных 2-раскрасок, установлено, что необходимым условием существования остальных раскрасок является выполнение условия \ац — 221 + 1 4. Также ею были перечислены параметры всех совершенных 2-раскрасок радиуса 1. Совершенные раскраски бесконечной прямоугольной решетки были предметом кандидатской диссертации [10] С.А. Пузыниной. Ею доказано, что если существует совершенная раскраска радиуса 1 бесконечной прямоугольной решетки с матрицей параметров А, то существует также периодическая совершенная раскраска, чья матрица параметров совпадает с А. Приведем краткое описание результатов настоящей диссертации. В первой главе приводится описание орбитного метода - классического способа построения таких комбинаторных объектов, как i-схемы, совершенные раскраски различных графов. С использованием орбитного метода в этой главе получена серия как бесконечных, так и спорадиче ских конструкций совершенных 2-раскрасок графов Джонсона, найдены параметры этих раскрасок. Напомним, что автоморфизмом произвольного графа G называется подстановка на множестве вершин графа, сохраняющая отношение смежности между вершинами. Совокупность таких преобразований относительно операции суперпозиции образует группу, обозначаемую Aut{G). Очевидно, что такая группа является подгруппой группы Sv, где v - число вершин графа G. Пусть Н является некоторой подгруппой группы автоморфизмов графа G. Действие группы Н разбивает множество вершин графа G на непересекающиеся орбиты.
Поставив орбитам в соответствие различные цвета, получим орбитную раскраску вершин графа G, соответствующую подгруппе Н группы автоморфизмов графа G. В [15] доказано, что всякая орбитная раскраска является совершенной. В общем случае число цветов в орбитной раскраске может оказаться достаточно большим. В отдельных случаях число цветов в такой раскраске можно уменьшить. Лемма 1. (Об объединении цветов) [9] Пусть существует совершенная раскраска в т цветов с матрицей параметров Атхт. Раскраска, получаемая из исходной объединением цветов в г групп Li, . . . , Lr: Lt- Г) Lj = Ui=i г Li — {І)---; тп] будет совершенной тогда и только тогда, когда для любых г, j Є {1,..., т}, і j и для любых p s Є Ьг выполнено условие Под орбигпиым методом в данной диссертации понимается метод построения совершенных 2-раскрасок n-вершинного графа, при котором множество вершин фиксированного цвета получается объединением некоторых орбит под действием некоторой подгруппы группы Sn. С использованием описанного выше метода в параграфе 1.1 получены
Собственные значения и собственные векторы графов
Большое количество результатов, посвященных исследованию собственных пространств и собственных значений графов, можно найти в монографии [15] Д. Цветковича, М. Дуба и X. Захса. Теория матриц активно использовалась Дельсартом в [24] для изучения схем отношений, возникающих в теории кодирования. Многие результаты, полученные в [15], имеют прямое отношение к вопросам исследования собственных пространств таких графов, как граф n-куба и граф Джонсона, а также различных структур в них (полностью регулярных, в том числе и совершенных кодов и совершенных раскрасок). Отметим, что так как матрица смежности М неориентированного графа G является веществениозначной симметрической матрицей, то пространства всех собственных векторов матрицы М, отвечающих различным собственным значениям ортогональны и существует базис пространства F0V(G \, состоящий из собственных векторов матрицы М. Далее под собственными векторами и собственными значениями графа G будем понимать собственные значения и собственные векторы матрицы смежности этого графа. Теперь рассмотрим совершенную раскраску графа G в произвольное число цветов. Собственным значением и собственным вектором совершенной раскраски с матрицей параметров Атхт графа G назовем собственные значения и собственный вектор Матрицы А-тУ.т.- ПуСТЬ V является собственным вектором этой совершенной раскраски, соответствующим собственному значению Л. Присвоим значение V{ всем вершинам цвета г в графе G. Полученный вектор обозначим через v, его компонента vx (подразумевается, что нумерация компонент вектора vx совпадает с нумерацией вершин графа G, выбранной при определении матрицы смежности графа G) равна Vi, если х является вершиной цвета г. Несложно доказать, что вектор v будет собственным вектором графа G: Теорема 4. [15] Пусть v - собственный вектор совершенной раскраски, соответствующий собственному значению А. Тогда вектор v является собственным вектором графа G, соответствующим собственному значению А. Из этой теоремы вытекает Следствие 2. Всякое собственное значение совершенной раскраски графа G является собственным, значением G. Рассмотрим граф Джонсона J(n, w). Собственные значения этого графа были найдены Ф. Дельсартом при исследовании схем отношений Джонсона.
Теорема 5. [24] Собственные значения графа Джонсона J(n,w) исчерпываются следующими числами: Собственное значение, равное (w — j){n — w — j) — j, будем далее называть j-м собственным значением графа J(n, w). Приведем описание собственных пространств графов Джонсона, данное в [34]. Пусть S является подмножеством множества вершин графа J(n,w). Через х(3) обозначим вектор из нулей и единиц, координаты которого занумерованы вершинами J(n,w), такой что координата x(S%, соответствующая вершине х графа J(n,w), равна единице в том и только том случае, если вершина х принадлежит множеству S. Пусть у является вектором Еп веса і,і w. Рассмотрим подмножество Ьц(у) вершин графа J(n,w). Другими словами, х( о{у)) является вектором из нулей и единиц, таким что координата х( о{у))х, соответствующая вектору х веса w, равна единице в том и только том случае, если вектор у предшествует вектору х. Обозначим через С/г- линейную оболочку векторов x{Lo(y)), соответствующих всем векторам у веса г. Укажем некоторые простые свойства пространства /г-. Размерность этого пространства равна Сгп. Пространство Щ является подпространством Uj, если і j. Каждое из таких подпространств является инвариантным относительно преобразования, задаваемого матрицей смежности графа Джонсона. Используя введенные выше обозначения, пространство собственных векторов графов Джонсона можно описать следующим образом. Теорема 6. (См. [24j, [34]) Пространство UiHU i является пространством всех собственных векторов графа J(n,w), соответствующих г-му собственному значению. Здесь и далее под UL\ понимается пространство, ортогональное Ui-\. Сначала докажем следующее вспомогательное "Утверждение 4.
Пусть существует совершенная 2-раскраска регулярного связного графа G степени t с матрицей параметров А = {tty}ij=i,2- Тогда оба числа ац — а,2\ и t являются собственными значениями совершенной раскраски и собственными значениями графа G, причем ац — a,2i не равно t. Доказательство. Прямым подсчетом легко убедиться, что числа ац — СІ2І и t являются характеристическими числами матрицы Л = {aij}i,j=i,2-Отметим, что ац — а2і не равно t, так как иначе a,2i = 0, то есть внешние степени цветов равны 0 и вершины графа можно разбить на две компоненты связности в соответствии с их цветом. Применение Следствия 2 завершает доказательство. Очевидно, что собственное значение ац — а \ всегда меньше степени і графа. По этой причине, далее число ац — а2і будем называть младшим собственным значением совершенной 2-раскраски регулярного графа G с матрицей параметров А = {a ij}i,j=i,2 Используя описания пространств собственных значений графов Джонсона, данных в Теореме 6 а также Утверждение 4, докажем, что множество вершин всякой совершенной 2-раскраски фиксированного цвета образует схему, параметры которой можно найти, используя матрицу параметров этой совершенной раскраски. Это свойство является обобщением свойства /с-регулярпости совершенных равновесных кодов, установленного Т. Этционом и М. Шварцем в [27]. Отметим, что доказательство этого факта может быть проведено без использования описания пространств собственных векторов графов Джонсона и понятия собственного значения графа как такового. В этом случае доказательство будет аналогично доказательству свойства /с-регулярности совершенных равновесных кодов в [27]. Зафиксируем совершенную 2-раскраску графа J(n,w) с матрицей параметров А. Через к обозначим число Очевидно, что к зависит от п, w и матрицы параметров рассматриваемой совершенной 2-раскраски, но для краткости их далее будем опускать. Теорема 7. Пусть W является миоэюеетвом белых вершин совершенной 2-раскраски графа J(n,w) с матрицей параметров А — {ay}2.j=i,2; Тогда 1. младшее собственное значение ац — a2i является собственным значением графа J(n,w) с номером к + 1, где к 0. 2. множество белых вершин этой совершенной раскраски W является к — (n,w, — г—С ) -схемой. 3. множество W не является (к + 1) — (n, w, X)-схемой. Доказательство. Согласно Утверждению 4, младшее собственное значение ац — а,21 совершенной раскраски является некоторым собственным значением графа J(n,w) (например j-м, 1 j in). Воспользовавшись
Несуществование некоторых совершенных 2-раскрасок графов Джонсона
В этом параграфе докажем несуществование некоторых совершенных 2-раскрасок графов Джонсона с небольшими значениями параметра агі, удовлетворяющих необходимым условиям существования совершенных 2-раскрасок, описанным в Следствиях 1, 3 и Теореме 11. Через х обозначим произвольную вершину белого цвета графа Джонсона J(n,w). Аналогично предыдущему параграфу, вершины подграфа, порожденного Li (ж), будем представлять как клетки прямоугольника Hwx(n-w)i с отношением смежности, заданным принадлежностью одной строке и одному столбцу. При этом клетки прямоугольника покрашены в цвета соответствующих им вершин из Li(x). Введем одно дополнительное определение. Минором порядка 2 в прямоугольнике Пшх(„_ш) будем называть совокупность клеток, находящихся на пересечении двух различных строк и двух различных столбцов этого прямоугольника. Утверждение 8. Пусть у є L- x), тогда клетки nwx(n_?J)), отвечающие совокупности всех вершин из Ь\(х), которые смежны с у, образуют минор порядка 2 в прямоугольнике Пмх(п_№). Доказательство. Очевидно, что у = (supp(x)\{s,t})U{m, 1} для некоторых {s,i} Є supp(x), {m, 1} Є {1,..., n} \ supp(x). Тогда вершины (supp(x) \ t) U га, (supp(x) \ t) U /, (supp(x) \ s) U m и (supp(x) \ s) U I являются совокупностью всех вершин из Li(x), смежных с у. Согласно соответствию между клетками nwx(„_№) и вершинами Li(x), получаем, что клетки, отвечающие этим вершинам, образуют минор порядка 2 в прямоугольнике Пшх(п-ш) Принимая во внимание Утверждение 8, вершины из - (ж) будем интерпретировать как миноры порядка 2 в прямоугольнике Hwx(n-w)- При этом пара вершин в L-2,(x) смежна в том и только в том случае, когда соответствующие им миноры имеют ровно две общие клетки. Доказательство всех следующих лемм этой главы проводится от противного. Лемма 5. Не существует совершенной раскраски J (11, 3) с матрицей /8 1б\ \4 20 J Доказательство. Покажем, что множество всех белых клеток в ПзХ8 является совокупностью всех клеток некоторой строки. Предположим, что это не так. Тогда любая строка ЩХ8 содержит не более трех белых клеток (иначе существует черная вершина из L\(x), смежная с пятью белыми клетками из х U L\(x), что противоречит тому, что параметр tt2i рассматриваемой совершенной раскраски равен 4). Более того, так как белых клеток в ПзХ8 всего восемь, а у прямоугольника ЩХ8 три строки, то в Пзх8 Две строки содержат по три белых клетки и одна строка (скажем, первая) содержит две белых. Заметим, что существует три столбца, которым принадлежат все белые клетки из строк с тремя белыми клетками.
В противном случае, три столбца, содержащих три белых клетки второй строки, содержат черную клетку из третьей строки. Так как вершина, соответствующая этой черной клетке смежна с пятью белыми клетками из х U Ь\(х), получаем противоречие. Тогда в строке, которая содержит две белые клетки, найдется черная клетка, принадлежащая этим трем столбцам. Вершина, соответствующая этой клетке, смежна с пятью белыми вершинами из x\JL\(x), что противоречит тому, что параметр а \ рассматриваемой совершенной раскраски равен 4. Итак, все белые клетки ПзХ8 состоят из клеток Пзх8; принадлежащих одной строке. Исходя из соответствия между смежностью, заданной в прямоугольнике Пзх8 и смежностью в графе, порожденном Li(x), совокупность белых вершин L\(x) и вершина х образуют клику размера 9. Так как ац = 8, то других белых вершин, смежных с этой кликой, нет и множество белых вершин графа J(11,3) разбивается на независимые клики размера 9. Следовательно, число белых вершин в графе «7(11, 3) кратно 9. Однако, согласно Утверждению 2, имеем \W\ = 33. Получаем противоречие. Доказательство. Пусть существует совершенная раскраска с матрицей (2.15). Тогда, так как a2i = 2, то любая черная клетка прямоугольника Щх8 смежна не более чем с одной белой клеткой. Очевидно, что это возможно только тогда, когда все белые клетки прямоугольника Щх8 заполняют все клетки некоторого столбца прямоугольника ЩХ8- Отсюда следует, что белые вершины разбиваются на независимые клики размера 5. Следовательно \W\ делится на 5, что противоречит Утверждению 2, согласно которому имеем \W\ = 31. Пусть существует совершенная раскраска графа J(12, 4) с матрицей параметров (2.16). Покажем, что в прямоугольникеЩХ8 существует два столбца и одна строка, состоящие из белых клеток и других белых клеток в ЩХ8 нет. Пусть не существует строки, целиком состоящей из белых клеток. По принципу Дирихле существует строка, в которой не менее [ 1] = 4 белых клеток и хотя бы одна черная клетка. Вершина, соответствующая любой черной клетке из этой строки смежна с 5 белыми вершинами из U Li(x), что противоречит тому, что параметр i2i рассматриваемой совершенной раскраски равен 4. Следовательно, в прямоугольнике ЩХ8 существует строка (скажем с номером 1), целиком состоящая из белых клеток. Так как а \ — 4, то среди строк с номерами 2, 3 и 4 нет строки, содержащей более двух белых клеток и, следовательно, каждая из этих строк содержит ровно по две белых клетки из шести оставшихся. Более того, все белые клетки строк 2, 3 и 4 содержатся в двух столбцах. В противном случае два столбца, содержащих две белые клетки второй строки, содержат черную клетку из третьей или четвертой строк.
Так как вершина, соответствующая этой черной клетке, смежна с пятью белыми клетками изжиі/і, получаем противоречие. Следовательно, в прямоугольнике ГЦхв существует два столбца (первый и второй без ограничения общности) и одна строка, целиком состоящие из белых клеток и других белых клеток нет. Тогда всякая черная вершина из Li (ж) смежна с 4 белыми вершинами из ж U L\{x). Следовательно, так как а \ = 4, то никакая черная вершина из L\{x) не смежна ни с одной белой из L,2(x). Рассмотрим белую клетку v прямоугольника Щхв, принадлежащую его 1-й строке (состоящей целиком из белых вершин), но не принадлежащую первым двум столбцам (которыми покрываются все белые клетки, не принадлежащие первой строке). Вершина, соответствующая г;, смежна с 8 белыми вершинами из Li(x)Ux, следовательно, существует вершина у белого цвета из 1/2(ж), смежная с z. По утверждению 8 совокупность всех клеток из Li (ж), смежных с у, в прямоугольнике Г±4х8 образует минор порядка 2. Поэтому в одном столбце с клеткой v найдется клетка, отличная от нее, которой соответствует вершина, смежная с у. Из доказанного выше следует, что эта вершина имеет черный цвет и смежна с пятью белыми вершинами из х U L\{x) U г(ж). Противоречие.
Слабые изометрии кодов Препараты
Проводя похожие рассуждения, можно получить аналогичные результаты для кодов Препараты. Приведем аналоги вспомогательных лемм 10-13, опустив их доказательства. Лемма 14. (См. [12]) Пусть Рп - произвольный приведенный код Препараты. Тогда множество кодовых слов веса 6 кода Рп образует 3-(п, 6, (п 4)/3)-схему. Лемма 15. Пусть х - кодовое слово произвольного кода Препараты Рп, wt(x) = г. Тогда любой вектор из Di -2(x) (Оц- {х) и Di)i-Q(x) соответственно) имеет ровно 4 (5 и 6 соответственно) нулевые координаты из supp{x) и ровно 2 (1 и 0 соответственно) единичные координаты из {1,... ,n}\supp(x). Лемма 16. Пусть х Є Рп, m,l,k Є supp(x), а векторы u,v - произвольные два кодовых слова Рп, находящиеся на расстоянии 6 от вектора х с единицами в координатах т, I, к. Тогда u,v не имеют общих нулевых координат, принадлежащих множеству supp{x) \ {т, I, к} и не имеют общих единичных координат, принадлежащих мнооїсеству {1,... ,n}\supp(x). Лемма 17. Пусть х - произвольное кодовое слово веса г, принадлежащее коду Препараты. Тогда выполняется: Cf(i - 4) 4 A, _2(aOI + 20Diti-A(x)\ + 60А -6(я) Cf{i - 3). (4.6) С учетом 14-17, проводя рассуждения, аналогичные рассуждениям Теоремы 17, имеем следующую Теорема 20. Пусть J : Р" —» Р% является слабой изометрией двух кодов Препараты Р и Р2П длины п. Тогда J является изометрией. Следствие 11. Пусть п 212. Два кода Препараты длинып являются слабоизометричными тогда и только тогда, когда они эквивалентны. Используя терминологию графов минимальных расстояний имеем: Теорема 21. Два кода Препараты изометричны тогда и только тогда когда их графы минимальных расстояний изоморфны. Следствие 12. Пусть п 212. Два кода Препараты длины п эквивалентны тогда и только тогда, когда графы минимальных расстояний этих кодов изоморфны. Следствие 13.
Группа автоморфизмов кода Препараты длинып, п 212 изоморфна группе автоморфизмов графа минимальных расстояний этого кода. В данном Приложении приводятся результаты проверки необходимых условий существования совершенных 2-раскрасок графов Джонсона, изложенных в Главе 2. Необходимые условия существования совершенных 2-раскрасок графов Джонсона с заданной матрицей параметров включают в себя Следствия 1, 3, Теорему 11 и результаты параграфа 2.4 о несуществовании совершенных 2-раскрасок (Теорема 12). Наиболее эффективный способ перечисления матриц, которые гипотетически могут быть матрицами параметров совершенных 2-раскрасок графа J(n,w) был ранее описан в Главе 3. Он заключается в перечислении всех матриц с неотрицательными целочисленными коэффициентами, сумма элементов каждой строки которых равна w(n — w), а разность двух различных элементов, принадлежащих одному столбцу (младшее собственное значение) равна (w — к)(п — w — к) — к, для некоторого 2 к w. Полученные таким образом матрицы будут содержать матрицы всех совершенных 2-раскрасок с собственным значением, отличным от первого. Вопрос существования совершенных раскрасок при к — 1 решен, см. Теорему 8, поэтому мы его не рассматриваем. С каждым графом Джонсона J(n, w) свяжем таблицу, строкам которой предписано значение Л, равное (w — к)(п — w — к) — к (собственное значение), 2 к w, а столбцам - значение г. Каждой клетке этой таблицы соответствует квадратная матрица
А порядка 2 с неотрицательными целочисленными элементами, чье младшее собственное значение равно Л, а компонента «12 равна г. Неизвестные элементы этой матрицы однозначно восстанавливаются из Л и ai2, используя следующие соотношения: Пусть А - матрица, соответствующая некоторой клетке. Если заключение Следствия 3 (необходимого условия, основанного на свойстве к-регулярности) не выполнено, то совершенной раскраски с матрицей А не существует и в эту клетку ставится - . Если заключение Следствия 3 выполнено, но не выполнено Следствие 1, то в клетке стоит = . Если заключения этих следствий выполнены, но не выполнена нижняя оценка Теоремы 11, то в клетке стоит , если совершенная раскраска совпадает с одной из раскрасок, несуществование которых показано в Теореме 12, то в клетке стоит = . Во всех перечисленных выше случаях совершенной раскраски с матрицей А не существует. Если совершенная раскраска с матрицей А существует, то в клетке стоит номер конструкции (в нумерации настоящей диссертации) с помощью которой она получена. Если совершенная раскраска получена с помощью конструкции, описание которой не вошло в данную диссертацию, то в клетке стоит О . В клетке стоит X , если несуществование совершенной раскраски показано методами, отличными от перечисленных в данной диссертации. Знак означает что вопрос существования совершенной раскраски с данными параметрами остается открытым.
