Классификация и хроматическая определяемость элементов малой высоты в решётках полных многодольных графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

УДК 519.174

Сеньчонок Татьяна Александровна

КЛАССИФИКАЦИЯ И ХРОМАТИЧЕСКАЯ ОПРЕДЕЛЯЕМОСТЬ ЭЛЕМЕНТОВ МАЛОЙ ВЫСОТЫ В РЕШЁТКАХ ПОЛНЫХ МНОГОДОЛЬНЫХ ГРАФОВ

01.01.06 - Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

3 МАП ¿012

Екатеринбург - 2012

005019104

005019104

Работа выполнена на кафедре алгебры и дискретной математики Института математики и компьютерных наук ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина».

Научный руководитель: доктор физико-математических наук,

профессор В.А. Баранский

Официальные оппоненты: доктор физико-математических наук,

профессор В.В. Кабанов

кандидат физико-математических наук, доцент Е.А. Перминов

Ведущая организация: ФГБОУ ВПО «Омский

государственный университет им. Ф.М. Достоевского»

Защита состоится « 22 » мая 2012 года в 14°° на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан « 18 » апреля 2012 года

Учёный секретарь диссертационного совета, кандидат физ.-мат. наук

И.Н. Белоусов

Общая характеристика работы

Актуальность темы

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

Для нас важно отметить, что в 1912 году попытки решить проблему четырёх красок привели Биркгофа [1] к понятию хроматического многочлена карты. Это понятие в 1932 году было обобщено Уитни [2] на произвольный граф. Им же было найдено несколько фундаментальных свойств хроматических многочленов графов. В 1968 году Рид [3] ввёл понятие хроматически эквивалентных графов, т. е. графов, имеющих одинаковые хроматические многочлены, и сформулировал задачу о необходимых и достаточных условиях хроматической эквивалентности графов. В 1978 году Чао и Уайтхед [4] ввели понятие хроматически определяемого графа, т. е. графа, который определяется своим хроматическим многочленом с точностью до изоморфизма. Они же нашли некоторые семейства хроматически определяемых графов. Хотя Биркгоф и не смог решить проблему четырёх красок с помощью хроматических многочленов, его исследования породили в теории раскрасок графов множество работ других авторов по хроматической эквивалентности и хроматической определяемое™ графов. Данное направление активно развивается и в настоящее время. Состояние дел в этой области достаточно полно изложено в обзорных статьях [5-8] и монографиях [9, 10].

Особое место в исследовании хроматической определяемости графов занимает изучение полных многодольных графов, так как любая раскраска графа — это вложение этого графа в некоторый полный многодольный граф. То есть любой граф, раскрашиваемый в £ цветов, можно получить из полного ¿-дольного графа удалением некоторого множества рёбер. Поэтому, опираясь на хроматические свойства полных многодольных графов, можно исследовать хроматическую опре-деляемость любых других классов графов. Полные ¿-дольные графы будем обозначать через К^щ, щ,..., щ), где щ, пг,..., щ — размеры

всех £ долей этого графа. Рассматривая полные ¿-дольные графы будем всегда предполагать, что щ > п^ > ••• > щ.

В 1990 году Ли и Лью [11] доказали, что граф К{гч,... 1,1) является хроматически определяемым тогда и только тогда, когда 2 > > ... > Щ-1 > 1. В силу этого в дальнейшем нас будет интересовать хроматическая определяемость полных многодольных графов только с неодноэлементными долями.

Задача о хроматической определяемости полных многодольных графов привлекала внимание значительного числа исследователей, при этом особым интересом пользовались случаи двух- и трёхдольных графов. Хроматической определяемости двудольных гафов было посвящено множество работ, и, наконец, в 1990 году Кох и Тео [12] доказали, что любой полный двудольный граф хроматически определяем, если его доли неодноэлементны. После этого задачи для двудольных графов фокусируются вокруг удаления из них определённых наборов рёбер и доказательства хроматической определяемости получившихся графов (см., например, [13]). Что же касается полных трёхдольных графов, то их хроматическая определяемость до сих пор не доказана в общем случае, т.е. когда доли графа неодноэлементны. В настоящее время продолжается исследование хроматической определяемости некоторых классов полных трёхдольных графов (см., например, [14]).

Многие же исследования направлены на произвольные полные ¿-дольные графы. В них можно выделить два основных направления исследований. Часть исследований, по аналогии с трёхдольными графами, касается доказательства хроматической определяемости полных ¿-дольных графов определённого вида. Доказано, что хроматически определяемы следующие многодольные графы.

1. К{р,р,...,р,р-к) при к>2,Ь> 4 и р > к + 2 (Цао, 2005 [10]).

2. К(р,р,... ,р,р — 1 ,р — к) при к > 2, ¿>4ир>Н2 (Ксю, 2008 [15]).

(Лау и Пенг, 2009 [16]).

В этих случаях авторы брали классы полных трёхдольных графов, хроматическая определяемость которых уже была доказана, и

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

Другая часть исследований обращена к обобщению утверждения Чао и Новацки [17], которые в 1982 году доказали, что для любого t > 2 полный i-дольный граф K(ni,n2,... ,nt) хроматически определяем, если |п,- — rij| < 1 для всех i,j = 1,2,..., t. В этом направлении следует отметить результат Цао [10], он доказал, что если —rij\ < 2 И fil > П2 > ... > nt > t + 1, ТО К(щ,П2, ■ . . ,nt) хроматически определяем при t > 2. Если обобщить задачу для произвольного значения |п,- — Tij| < k (i,j = 1,2,...,£), то ответ на этот вопрос дали Цао, Ли, Лью и Йе [18], они показали, что если |п< — < к и Щ > > ... > nt > tk2/A + 1 для некоторого натурального числа к, то К(щ, П2,..., nt) хроматически определяем. В этих исследованиях доказана хроматическая определяемость полных многодольных графов с серьёзным ограничением на размеры долей этих графов (щ достаточно велико).

Учитывая исследования различных авторов можно сформулировать следующую гипотезу: любой полный многодольный граф К(т, П2, . . . , щ) является хроматически определяемым при П\>П2> ... >nt> 2.

Графы, хроматическую определяемость которых мы будем исследовать, характеризуются своим положением в некоторой решётке полных i-дольных графов. Использовать решёточный порядок для доказательства хроматической определяемое™ полных многодольных графов предложили Баранский и Королёва [19] в 2007 году. Хроматическая определяемость наименьшего элемента этих решёток была доказана Чао и Новацки [17]. В работе [20] установлена хроматическая определяемость атомов этих решёток при nt > 2. Элементы высоты 2 и 3 этих решёток при t = 3 рассмотрены в работах [21-23], там же доказана хроматическая определяемость полных трёхдольных графов, имеющих высоту 2 и 3 в решётках полных трёхдольных графов.

Цели работы состоят в следующем:

1. Дать классификацию элементов высоты < 3 в решётках полных ¿-дольных графов при t > 4.

2. Доказать хроматическую определяемость полных многодольных

графов с неодноэлементными долями, имеющих высоту < 3 в этих решётках.

Основные методы исследования

Доказательство хроматической определяемое™ полных многодольных графов проводится с помощью свойств некоторых хроматических инвариантов и взаимосвязи этих свойств с решёточными порядками на множествах полных многодольных графов.

Научная новизна

Все результаты являются новыми.

Теоретическая и практическая ценность

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

Апробация работы

Результаты диссертации были представлены на 42-й Всероссийской молодёжной школе-конференции (Екатеринбург, 2011), XIV Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2011), на первом русско-финском симпозиуме по дискретной математике (Санкт-Петербург, 2011), Международной (43-й Всероссийской) молодёжной школе-конференции (Екатеринбург, 2012). Автор выступал с докладами по теме диссертации на семинаре "Алгебраические системы" (УрФУ, рук. JI.H. Шеврин, 2012) и на алгебраическом семинаре института математики и механики УрО РАН (рук. A.A. Махнёв, 2012).

Публикации

Материалы диссертации опубликованы в 8 печатных работах [2734], из них 3 статьи в рецензируемых журналах [27-29] и 5 тезисов докладов [30-34]. 5 работ ([27], [29], [31-33]) опубликовано совместно с В;А. Баранским, однако доказательства основных результатов принадлежат автору.

Структура и объём диссертации

Диссертация состоит из введения, двух глав и списка литературы. Объём диссертации составляет 125 страниц. Библиографический список содержит 63 наименования.

Содержание работы

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

В данной работе мы рассматриваем только обыкновенные графы, т. е. графы без петель и кратных рёбер. Обозначения и терминологию для графов будем использовать в соответствии с [24].

Пусть С? — произвольный (п, тп, А;)-граф, т. е. граф, имеющий п вершин, т рёбер и к компонент связности. Раскраской или Ь-раскраской графа Є называется отображение <р из множества вершин V графа д в множество натуральных чисел {1,2,..., £} такое, что для любых двух различных смежных вершин и и и графа Є выполняется </?(гг) ф <р(у), т.е. любые две различные смежные вершины имеют разный "цвет". Граф называется Ь-раскрашиваемым, если он обладает і-раскраской и — Ь-хроматическим, если он ¿-раскрашиваемый, но не является (і — 1)-раскрашиваемым; в этом случае число Ь называют хроматическим числом графа С и обозначают через

Для натурального числа х через Р(Є, х) обозначим число всевозможных раскрасок графа Є в х заданных цветов, причём не предполагается, что в раскраске должны быть использованы все х цветов. Хорошо известно, (см., например, [3] или [24]), что функция Р(С,х) является многочленом степени п от переменной х, который называют хроматическим многочленом графа С. Два графа называются хроматически эквивалентными, если они имеют одинаковые хроматические многочлены.

Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвариантами являются, например, число вершин, число рёбер и число компонент связности графа [3]. Число рёбер графа Є будем обозначать через /г(С). Отметим, что число вершин графа Є можно было бы обозначать через /і(С). Ещё одним хроматическим инвариантом является /з(<?) — число треугольников в графе Є [25].

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

щих из попарно несмежных вершин графа Є. По теореме Зыкова [26] хроматический многочлен можно представить в виде

п

где через х^ обозначается факториалъная степень переменной х, т. е. х^ = х(х — 1) (х — 2)... (х — і + 1), а через х ~ хроматическое число графа С?. В силу этой теоремы числа р£((?, г) при X < і < п являются хроматическими инвариантами. Нас особенно будут интересовать инварианты х) и X + !)•

Граф является хроматически определяемым, если он изоморфен любому хроматически эквивалентному ему графу.

Граф Є называют Ь-дольным графом, если множество его вершин можно разбить на £ непустых подмножеств (долей) так, что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина из одной доли соединена с каждой вершиной из других долей, то Є называют полным і-дольньш. графом и обозначают через К(пі, пг, -.., щ), где п\,П2, ■ ■ ■, пг — последовательность чисел элементов для всех Ь долей этого графа. Рассматривая полные ¿-дольные графы будем всегда предполагать, что гаї > пг > ••• > Щ-

Разбиением натурального числа п называется невозрастающая последовательность целых неотрицательных чисел и = (щ, щ,...) такая, что щ > щ > ..., причём и содержит лишь конечное число ненулевых компонент и п = щ + иг + .... Число I такое, что I > 1, щ > О и щ+1 = щ+2 = ... = 0, назовём длиной разбиения и, в этом случае будем писать и — (щ,... ,щ).

Разбиение натурального числа удобно изображать в виде так называемой диаграммы Ферре, которую можно представить в виде вертикальной стенки, сложенной из кубических блоков одинакового размера. Вот пример такой диаграммы.

Рис. 1 8

На Рис. 1 представлено разбиение 20 = 6 + 4 + 4 + 3 + 1 + 1 + 1 числа 20 на 7 слагаемых. Здесь 7 — длина разбиения (6,4,4,3,1,1,1).

Через ЛГР£(п, £) обозначим множество всех разбиений длины £ натурального числа п, где 1 < £ < п. Определим понятие элементарного преобразования разбиения и = («1,^2,..., щ) числа п [19]. Пусть натуральные числа ¿и; таковы, что

1) 1 < г < з < Ъ

2) щ — 1 > щ+1 и > щ + 1;

3) щ = и} + 6, где 8 > 2.

Будем говорить, что разбиение V = (щ,... ,щ — 1,... + 1,... ,щ) получено элементарным преобразованием (или перекидыванием блока) разбиения и = (щ,... .. .., щ). Отметим, что V отличается от и точно на двух компонентах с номерами г и Для диаграммы Ферре такое преобразование означает перемещение верхнего блока г-го столбца вправо в j-ый столбец. Условия 2) и 3) гарантируют, что после такого перемещения снова получится диаграмма Ферре.

Рассмотрим отношение > на множестве ИРЬ{п, £), полагая и > V для и, V б NPL(n, £), если V можно получить из и с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований. Отметим, что ЛГРЬ(п,£) является решёткой относительно > [19].

Элементарное преобразование разбиения будем называть падением блока, если j = i-^-\ и 6 > 2 (см. Рис. 2(а)), и — сдвигом блока, если г + 1 < з, щ — щ+1 + 1, щ+1 = щ+г = ... = и щ-1 = щ + 1 (см. Рис. 2(6)), или если ;'=1+1и(5=2 (см. Рис. 2(в)).

и1 ==т-,

МИ1 мммм и и 11

(а) (б) (в)

Рис. 2

Рассмотрим отношение => на МРЬ(п, £), полагая и => V, если разбиение V получается из разбиения и падением или сдвигом блока. Отметим, что отношение => совпадает с отношением покрытия в решётке ЛГР£(п,£) [19].

Пусть п = £ • д + г, где д — натуральное число и г — неотрицательное целое число такие, что 0 < г < Нетрудно заметить, что

-1

(в)

разбиение (q + 1,..., q + 1, q,..., q), где число 1 повторяется г раз, а число q повторяется t — г раз, является наименьшим элементом решётки NPL(n,t).

Рассмотрим произвольный полный i-дольный граф К (ni, п2,..., nt). Пусть n = ni + пг + ... + п( — разбиение числа п, где щ > n-i > ... > nt > 1. Очевидно, с точностью до изоморфизма существует взаимно однозначное соответствие между полными i-дольными графами на п вершинах и элементами решётки NPL(n,t). Поэтому мы можем отождествлять полный многодольный граф на п вершинах с соответствующим ему разбиением числа п. Конечно, порядок > на NPL(n, t) можно рассматривать как порядок на множестве полных f-дольных графов на п вершинах.

Первая глава диссертации посвящена классификации элементов высоты < 3 в решётках разбиений натуральных чисел заданной длины t > 4.

В первом параграфе первой главы даны основные определения и сведения об объектах, используемых в тексте диссертации. Приведены леммы об изменении значений хроматических инвариантов Iz{G) Hpt(G,x + l) при выполнении элементарных преобразований.

Во втором параграфе первой главы получена классификация элементов высоты < 3 в решётках NPL(n,t) при t > 4. Результаты этой классификации сформулированы в виде Теоремы 1. В этой теореме представлена таблица, в которой перечислены все элементы высоты < 3 и условия их существования, а также некоторые их числовые характеристики. В частности, в колонке "Высота" указана высота этих элементов в решётке NPL(n,t), т.е. длина кратчайшего пути в решётке от наименьшего элемента до представленного. В колонке "Уровень" мы указали разницу в количестве рёбер между наименьшим элементом и рассматриваемым. Отметим, что в тексте диссертации вместо Теоремы 1 представлено более общее утверждение — Теорема 1.1, которая нам необходима при доказательстве второго нашего основного результата.

Теорема 1. Следующая таблица дает, классификацию элементов высоты < 3 в решётках NPL(n, t) при t > 4.

Таблица 1. Элементы малой высоты в решётках ЛгРЬ(п,4) при £ > 4

Элемент Условие существования Высота Уровень

61 = (о + 1,...,9 + 1,9,-, 9) г £—г о < г < г - 1 0 0

Ь2 = (9 + 2,9 + 1,..., 9 + 1,9,..., г—2 «-Г+1 2<г<г-1 1 1

¿з = (9 + 1.-. 9 + 1> <?'•••' 9 - 1) г+1 г-2 0 < г < 4 - 2 1 1

Ь4 = (9 + 2,9 + 2,9+ 1,...,9+1,9,...,^ г—4 «-г+2 4<г<е-1 2 2

Ъъ = (9 + 2,9 + 1ч9,-.,д;,9- 1) г-1 £-г-1 1 < Г < 4 - 1 2 2

Ь6 = (?+ 1,-.9 + 1Ч9,-,Я.9- 1.9-1) г+2 «-Г-4 0 < г < Ь - 4 2 2

¿7 = (9+ 3,9 + 1,...,9+1,9,..., 9) г—3 £—г+2 3 = г < £ — 1 2 3

4 < г <1 3 3

68 = (з + 2,...,9 + 2,9+ 1,...,9+ 1,3,-, <?) 3 г-6 £-г+3 6 < г < « _ 1 3 3

69 = (д + 2,9 + 2, 9 + 1,..., 9 + 1, д,..., ц, 9 - 1) г-з г-г 3<r<t-l 3 3

¿ю = (9+ 2,9 + 1,..., 9 + 1,^,-.^ 9~ 1,9-1) г £—т—3 0<г<¿-3 3 3

¿и = (9+ 1..--.9+ 1ч9.-.?.%9- !>■••, 9- 1) г+З £—г—6 3 0<Г<£_6 3 3

¿12 = (? + 1>-,9+ 1ч9,->?,9-2) г+2 ¿-г-3 0 < г = £ — 3 2 3

0 < г < 4 - 4 3 3

¿14 = (9 + 3,9+ 1,...,9+ 1чд,...,9^,9- 1) г-2 г-г 2 = г < £ — 1 3 4

3 = г < £ — 1 3 4

¿17 = (9+2,9+2, <7+1,...,9+1^9,...,<£, 9 — 1,9—1) г—2 е-г-2 2 = г < £ = 4 3 4

¿19 = (9 + 2-9 + 1,-. 9 + 1| <?>•••» 9У, 9-2) 1<г=г-2 3 4

г е-г-2 0 < г = £ — 3 3 4

В третьем параграфе первой главы указаны основные виды частично упорядоченных множеств, представляющих нижние этажи решёток NPL(n, t) для различных значений nut. Вид решётки NPL(n, t) будет существенным образом зависеть от значений и соотношения параметров rat. При достаточно больших значениях г и t (в некотором наиболее общем случае) элементы высоты <3 имеют в решётке NPL(n,t) уровень <3. Это происходит при условии 6 < г < t — 6, и в этом случае нижние этажи решётки NPL(n, t) выглядят как показано на Рис. 3. Отметим, что на Рис. 3 над символами покрытий представлены числа, на которые изменяется инвариант pt(G,t+ 1).

Ьт = (9 + 3,9+ 1,..., 9+1, q,..., q)

i—3 t-r+2

= (q + 2,.», q + 2,9 + 1,~.,9 + 1, <?,..., q)

3 r-6 t-r+3

b4 = («7 + 2,9 + 2,9+ 1,..., g+ 1, ?,..., q)

-4 l-r+2

bj = (q + 2, q + 1,..., q + 1,9,..., q) b8 = (q + 2, q + 2, q + 1,..., q + 1,9,..., q, q - 1)

,_2 l-r+K

T?^

I—3 t-r

bt = (9 + 1,. ,9+ 1,9,-,9) b5 = (9 + 2,9 + 1,. ,9+ 1,9,...,9,9- 1)

:<><4

1 t-r-l

bj = (9 + 1,...,9 + 1,9,...,9,9 - 1) b10 = (9 + 2,9+ 1,—, 9+ 1,9,...,9,9 - 1,9-1)

be = (9 + l,...,9+l,9,..., 9,9 - 1,9 - 1)

Ьц = (9+ !,■■■,9 + 1.9.--.9.9- 1.-.9- 1)

r+3 t-r-6 3

bia = (9 + l,^.,9+l,9,-.9.? - 2)

r+2 t—1—3

Рис. 3

В некоторых частных случаях элементы высоты 3 в решётках ЫРЬ{п, £) могут иметь уровень 4. Например, при условии 3 = г < ¿—8 нижние 4 этажа решётки МРЬ(п, I) будут выглядеть следующим образом (Рис. 4).

Рис. 4

При условии 8 < г = t — 3 получаем симметричный предыдущему вид нижних четырёх уровней решётки NPL(n,t) (Рис. 5).

bis = (17 + 3,4 + 2,5 + 1.....9+1,9.....g)

Ьт = (Я +

Ь< =(9 + 2,q + 2,g+ 1,..., 5 +

(9+2.....9+2,9+1,.. „9+1.9.....9.9-1)

3 1—5 t-r+l

Ьз = (9+2,9+ 1,..., 9+ 1,9,..., 9) Ь» = (9 + 2,9 + 2,9+ 1.....g + 1,9,..., 9, 9 - Ч

r-3 t-r+l

г-З t-r

b! = (g +1,--, g + 1,g,.--,g) fas = (g + 2,9+ 1,...,9 + l,g,...,9,9 - 1) bir - (9+2,9+2, 9+1,...,9+1, 9,...,9,9-1,9-1)

r t-r r-1 t-r-1 r-2 t-r-2

4\ -V«'

Ьз = (g 4-g- 1) Ью Д (g + 2, g + 1,...,g 1, g, g - 1, g ~ 1)

r+l i-r-2 r e-r-3

* = bia = (g + l,.-,g + l,g.-,g.g- 2)

r+3 t-r-3

Рис. 5

Для всех остальных значений параметров г и t нижние этажи соответствующей решётки NPL{n, t) будут вкладываться естественным

образом как частично упорядоченное множество в одну из трёх приведённых выше решёток. Полученные изображения нижних этажей решёток ЫРЬ{п, ¿) будут полезны нам в дальнейшем при доказательстве хроматической определяемости элементов этих решёток.

Вторая глава диссертации посвящена доказательству хроматической определяемости полных многодольных графов, имеющих высоту 2 и 3 в решётках

В первом параграфе второй главы приведена схема доказательства хроматической определяемости интересующих нас полных многодольных графов. При выполнении элементарного преобразования инвариант /2 (число рёбер в соответствующем графе) увеличивается. Для доказательства хроматической определяемости графа С7 = К(пх, П2,..., щ) рассматривается соответствующее ему разбиение и = (щ,п2,... ,тц) в решётке ЫРЫпуЬ), при этом граф С? можно обозначить через К{и). Пусть граф Н хроматически эквивалентен графу К(и). Если Н = то элементы и и V находятся на одном уровне

решётки 7УРЬ(п,^), так как /2(<?) = 1ъ{Н). Если же Н — К(и) - Е для некоторого множества рёбер Е графа К(ь), то элемент V будет находиться к уровнями ниже и в решётке МРЬ(п,Ь), где к = |.Е|. Таким образом, для доказательства хроматической определяемости некоторого полного многодольного графа достаточно показать, что он хроматически не эквивалентен ни одному графу, находящемуся с ним на одном уровне в решётке МРЬ(п,Ь), и что, удаляя ребра из элементов меньшего уровня в решётке, нельзя получить граф, хроматически эквивалентный данному. Хроматическую неэквивалентность графов мы часто показываем, сравнивая значения инвариантов х + 1)

соответствующих графов. Для этого нами получена оценка изменения этого инварианта при удалении рёбер из графа, а именно, к < р^Н, х + 1) — р£(<2, X + 1) < — 1. Отметим, что наибольшую сложность при доказательствах вызывает случай п( = 2. Причина этой сложности заключается в том, что при малых значениях некоторых из чисел щ,п2,... разность р£(#,х + 1) — + вычисляется

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

Во втором и третьем параграфах второй главы доказывается хроматическая определяемость полных многодольных графов, имеющих в решётке ЫРЬ(п, {) высоту 2 и 3, соответственно. Результатом

этой главы является следующая Теорема 2, которая является вторым основным результатом диссертации.

Теорема 2. Пусть nut — натуральные числа такие, что t < п. Тогда любой полный t-долъный тг-граф с неодноэлементными долями, гшеющий высоту < 3 в решётке NPL{n, t), является хроматически определяемым.

Если соотнести результаты, полученные нами, с результатами предшествующих исследований, то получим следующее.

В работах [10], [15] и [16] рассмотрен элемент 612, элемент ¿>5 при условии г — t — 1 и элемент big при условии г = t — 2.

Что касается результата Цао, Ли, Лью и Йе [18], в случае элементов высоты 2 и 3 мы улучшили оценку nt > tk2/4 + 1 до оптимальной оценки nt > 2.

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

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

[1] Birkhoff, G.D. A determinant formula for the number of ways of coloring a map // Annal. Math. 2nd Ser. 1912-1913. Vol. 14. P. 42-46.

[2] Whitney, H. The coloring of graphs // Annal. Math. 1932. Vol. 33. P. 688-718.

[3] Read, R.C. An introduction to chromatic polynomials //J. Comb. Theory. 1968. Vol. 4. P. 52-71.

[4] Chao, C.Y., Whitehead Jr., E.G. On chromatic equivalence of graphs // Theory and Appl. of Graphs. 1978. Vol. 642. P. 121-131.

[5] Read, R.C., Tutte, W.T. Chromatic polynomials // Selected Topics in Graph Theory III. Academic Press. 1988. P. 15-42.

[6] Koh, K.M., Teo, K.L. The search for chromatically unique graphs II U Discrete Math. 1997. Vol. 172. P. 59-78.

[7] Chia, G.L. Some problems on chromatic polynomials // Discrete Math. 1997. Vol. 172. P. 39-44.

[8] Liu, R.Y. Adjoint polynomials and chromatically unique graphs // Discrete Math. 1997. Vol. 172. P. 85-92.

[9] Dong, F.M., Koh, K.M., Teo, K.L. Chromatic polynomials and chromaticity of graphs. Monograph, Preprint, 2004. 356 p.

[10] Zhao, H. Chromaticity and adjoint polynomials of graphs. Zutphen: Wöhrmann Print Service, 2005. 169 p.

[11] Li, N.Z., Liu, R.Y. The chromaticity of the complete i-partite graph K{l-,p2;..;pt) // Xinjiang Univ. Natur. Sei. 1990. Vol. 7, № 3. P. 95-96.

[12] Koh, K.M., Teo, K.L. The search for chromatically unique graphs // Graphs Combin. 1990. Vol. 6. P. 259-285.

[13] Rolsan, H., Peng, Y.H. Chromatic uniqueness of complete bipartite graphs with certain edges deleted // Ars Combin. 2011. Vol. 98. P. 203-213.

[14] Su, K.Y., Chen, Х.Б. A note on chromatic uniqueness of completely tripartite graphs //J. Math. Res. Exposition 2010. Vol. 30, № 2. P. 233-240.

[15] Xu, L.M. Chromatic uniqueness of complete i-partite graphs K{n — k,n,...,n) (Chinese) // J. Univ. Sei. Technol. China 2010. Vol. 38, № 9. P. 1036-1041.

[16] Lau, G.C., Peng, Y.H. Chromatic uniqueness of certain complete i-partite graphs // Ars Combin. 2009. Vol. 92. P. 353-376.

[17] Chao, C.Y., Novacky Jr., G.A. On maximally saturated graphs // Discrete Math. 1982. Vol. 41. P. 139-143.

[18] Zhao, H.X., Li, X.L., Liu, R.Y., Ye, C.F. The chromaticity of certain complete multipartite graphs // Graphs and Combin. 2004. Vol. 20. P. 423-434.

[19] Баранский, В.А., Королева, Т.А. Решетка разбиений натурального числа // Доклады Академии Наук. 2008. Том 418, № 4. С. 439-442.

[20] Баранский, В.А., Королева, Т.А. Хроматическая определя-емость атомов в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2007. Т. 13, № 3. С. 22-29.

[21] Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов. I // Тр. Ин-та математики и механики УрО РАН. 2007. Т. 13, № 3. С. 65-83.

[22] Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов. II // Изв. Урал. гос. ун-та. 2010. № 74. С. 39-56.

[23] Баранский, В.А., Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов // Изв. Урал. гос. ун-та. 2010. № 74. С. 5-26.

[24] Асанов, М.О., Баранский, В.А., Расин, В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб.: "Лань", 2010. 368 с.

[25] Farrell, E.J. On chromatic coefficients // Discrete Math. 1980. Vol. 29. P. 257-264.

[26] Зыков, A.A. Основы теории графов. М.: "Вузовская книга", 2004. 664 с.

Работы автора по теме диссертации

[27] Сеньчонок, Т.А., Баранский, В.А. Классификация элементов малой высоты в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 2. С. 159-173.

[28] Сеньчонок, Т.А. Хроматическая определяемость элементов высоты 2 в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 3. С. 271-281.

[29] Баранский, В.А., Сеньчонок, Т.А. Хроматическая определяемость элементов высоты <3 в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 3-18.

[30] Сеньчонок, Т.А. О хроматической определяемое™ элементов высоты 2 в решётках полных многодольных графов // Тезисы 42-й Всероссийской молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН. 2011. С. 241-243.

[31] Баранский, В.А., Сеньчонок, Т.А. О хроматической определяемое™ элементов малой высоты в решетках полных многодольных графов // XIV Всероссийская конференция Математическое программирование и приложения (тезисы докладов). Екатеринбург: УрО РАН. 2011. С. 150-151.

[32] Баранский, В.А., Сеньчонок, Т.А. Хроматическая определя-емость элементов высоты <3 в решетках полных многодольных графов // Тезисы Международной конференции по алгебре и геометрии, посвящённой 80-летию со дня рождения А.И.Старостина. Екатеринбург: Изд-во "УМЦ-УПИ". 2011. С. 16-17.

[33] Baransky, V.A., Senchonok, Т.А. Chromatic uniqueness of elements of height <3 in lattices of complete multipartite graphs // First Russian-Finnish Symposium on Discrete Mathematics. Abstracts. St.Petersburg. 2011. P. 13-14.

[34] Сеньчонок, Т.А. О свойствах хроматического инварианта pt(G,x + 1) // Тезисы Международной (43-й Всероссийской) молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН. 2012. С. 84-86.

Подписано в печать 11.04.2012. Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 1,1 Тираж 100 экз. Заказ № 700

Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4

61 12-1/872

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Уральский федеральный университет имени первого Президента России Б.Н.Ельцина"

На правах рукописи

АЛ(

Сеньчонок Татьяна Александровна

КЛАССИФИКАЦИЯ И ХРОМАТИЧЕСКАЯ ОПРЕДЕЛЯЕМОСТЬ ЭЛЕМЕНТОВ МАЛОЙ ВЫСОТЫ В РЕШЁТКАХ ПОЛНЫХ МНОГОДОЛЬНЫХ ГРАФОВ

01.01.06 - математическая логика, алгебра и теория чисел

Диссертация

на соискание учёной степени кандидата физико-математических наук

Научный руководитель

доктор физико-математических наук

профессор В.А. Баранский

Екатеринбург - 2012

Содержание

Введение ......................................................................3

Глава 1. Описание элементов высоты < 3 в решётках ЫРЬ(п,1) 21

1.1. Решётки КРЬ(п,Ь) и хроматические инварианты.........21

1.2. Классификация элементов высоты 2 и 3 в решётках ИРЬ(п,1) . 27

1.3. Нижние этажи решёток МРЬ(п^).................51

Глава 2. Хроматическая определяемость элементов высоты < 3 в решётках NРЪ(п,1)..........................68

2.1. Раскраски графов и свойства хроматических инвариантов ... 68

2.2. Хроматическая определяемость элементов высоты 2 в решётках ИРЦп^).............................78

2.3. Хроматическая определяемость элементов высоты 3 в решётках ЫРЦп^).............................90

Литература.......................................119

Введение

Изучение раскрасок графов началось с задачи о четырёх красках. В 1852 году Гутри предложил выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. В терминах графов эта задача звучит так: показать, что хроматическое число плоского графа (карты) не превосходит четырёх. При попытках доказательства этого факта в 1912 году Биркгоф [1] ввёл понятие хроматического многочлена карты.

Понятие хроматического многочлена в 1932 году было обобщено Уитни [2] на произвольный граф. Им же было найдено несколько фундаментальных свойств таких многочленов. В 1968 году Рид [3] ввёл понятие хроматически эквивалентных графов, т. е. графов, имеющих одинаковые хроматические многочлены, и сформулировал задачу о необходимых и достаточных условиях хроматической эквивалентности графов. В 1978 году Чао и Уайтхед [4] ввели понятие хроматически определяемого графа, т. е. графа, который определяется своим хроматическим многочленом с точностью до изоморфизма. Они же нашли некоторые семейства хроматически определяемых графов [5-7]. Хотя Биркгоф и не смог решить проблему четырёх красок с помощью хроматических многочленов, его исследования породили в теории раскрасок графов множество работ других авторов по хроматической эквивалентности и хроматической определяемости графов. Данное направление активно развивается и в настоящее время.

Теория раскрасок графов имеет огромное практическое значение. Она используется для задач теории расписаний, задач распараллеливания численных методов, задач экономии памяти, задач распределения ресурсов, технологий цифровых водяных знаков и многих других задач (см. [8-17]). Что

же касается исследований, связанных с хроматическими многочленами, то они стали весьма разнообразными и обширными. Состояние дел в этой области достаточно полно изложено в обзорных статьях [18-22] и монографиях [23, 24].

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

В данной работе мы рассматриваем только обыкновенные графы, т. е. графы без петель и кратных рёбер. Обозначения и терминологию для графов будем использовать в соответствии с [25].

Пусть — произвольный (п, т, А;)-граф, т. е. граф, имеющий п вершин, т рёбер и к компонент связности. Раскраской или 1-раскраской графа С? называется отображение ф из множества вершин V графа С в множество натуральных чисел {1, 2,... ,¿1 такое, что для любых двух различных смежных вершин и и v графа С выполняется ф(и) ф Ф(у), т.е. любые две различные смежные вершины имеют разный "цвет". Граф в.дзът&етсяЬ-раскрашиваемым, если он обладает ¿-раскраской и — Ахроматическим, если он ¿-раскрашиваемый, но не является (£— 1)-раскрашиваемым; в этом случае числом называют хроматическим числом графа (9 и обозначают через

Для натурального числа х через х) обозначим число всевозможных раскрасок графа С в х заданных цветов, причём не предполагается, что в раскраске должны быть использованы все х цветов. Хорошо известно, (см., например, [3] или [25]), что функция Р(С, х) является многочленом степени п от х, который называют хроматическим многочленом графа С. Два графа называются хроматически эквивалентными или х-э?бивалентными, если они имеют одинаковые хроматические многочлены.

Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвари-

антами являются число вершин, число рёбер и число компонент связности графа [3]. Число рёбер графа С будем обозначать через /2(С). Отметим, что число вершин графа С можно было бы обозначать через 1\{0). Ещё одним хроматическим инвариантом является /з(С?) — число треугольников в графе С (см. [26] или [27]).

Далее через pt(G, г) мы будем обозначать число разбиений множества вершин графа (У на г непустых коклик, т. е. подмножеств, состоящих из попарно несмежных вершин графа По теореме Зыкова (см. [28] или [29])

п г=Х

где через х^ обозначается факториальная степень переменной х, т. е. х^ = х(х — 1)(х — 2)... (х — г + 1), а через х ~ хроматическое число графа (7. В силу этой теоремы числа г) при % < г < п являются хроматическими инвариантами. Нас особенно будут интересовать инварианты х) и

рКС,Х + !)•

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

Граф С называют Ь-дольпым графом, если множество его вершин можно разбить на £ непустых подмножеств (долей) так, что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина из одной доли соединена с каждой вершиной из других долей, то называют полным 1-дольным графом и обозначают через К(п1, П2,..., щ), где П1,П2,... — последовательность чисел элементов для всех£ долей этого графа. Рассматривая полные ¿-дольные графы будем всегда предполагать,

ЧТО П1 > П2 > ... > Щ.

Все полные графы Кп хроматически определяемы (только их хроматические многочлены имеют вид х^). Возникает естественный вопрос: если из Кп начать удалять рёбра, останутся ли полученные графы хроматически определяемыми? В частности, какие из полных ¿-дольных графов К(п\,п2,... ,щ) будут х-определяемы? Лоренц и Уайтхед в 1981 году [30] изучали класс графов, полученных из Кп удалением множества из к (0 < 2к < п) независимых рёбер, т. е. паросочетания из к рёбер. Они показали, что все такие графы хроматически определяемы. Ясно, что каждый их этих графов изоморфен некоторому графу К{пъп2,..., щ), где ¿>2и1<Пг<2 для всех г = 1, 2,..., Более общий результат относительно таких графов получили Чао и Новацкий в 1982 году [31]. Они доказали, что для любого £ > 2 граф К{п1,П2, хроматически определяем, если \щ — < 1 для всех г,= 1,2,... , Отметим, что этот результат легко вытекает из теоремы Турана (см. Бонди и Мурти [32]), так как рассматриваемый граф — это граф, имеющий максимальный размер (по числу рёбер) среди всех графов на п = щ + щ Н-----Ь щ

вершинах, имеющих хроматическое число равное

Задача о хроматической определяемости полных многодольных графов привлекала внимание значительного числа исследователей, при этом особым интересом пользовался случай двух- и трёхдольных графов. Хроматической определяемости двудольных гафов были посвящены работы [33, 34], ив 1990 году Кох и Тео [19] доказали, что полный двудольный граф К(п1,П2) хроматически определяем при щ > щ > 2. После этого задачи для двудольных графов фокусируются вокруг удаления из них определённых наборов рёбер и доказательства хроматической определяемости получившихся графов [35-38]. Что же касается полных трёхдольных графов К(п\, п2, Пз), то их хроматическая определяемость до сих пор не доказана в общем случае при Щ > П2 > щ > 2. В настоящее время продолжается исследование хромати-

ческой определяемости для некоторых классов полных трёхдольных графов [39-44].

Многие же исследования направлены на произвольные полные t-дольные графы. Часть исследований, по аналогии с трёхдольными графами, касается доказательства хроматической определяемости полных t-дольных графов определённого вида. Доказано, что хроматически определяемы следующие многодольные графы.

1. К(р,р,... ,р,р - к) при к > 2, t > 4 и р > к + 2 (Цао, 2005 [24]).

2. К(р,р,... ,р,р - 1,р - к) при к > 2, t > 4 и р > к + 2 (Ксю, 2008 [45]).

t-d-2 d+1 Пенг, 2009 [46]).

Другая часть исследований обращена к обобщению утверждения Чао и Новацки [31]. В связи с этим Кох и Тео поставили задачу: будет ли граф K(m,n2,..., щ) хроматически определяем, если \щ — rij\ <2 для всех i,j = 1,2, и число nt достаточно велико, где щ > щ > ... > щ! В 1985 году Гьюдичи и Лопез [47] доказали, что полные t-дольные графы K(q 41, q,..., g, q — 1) хроматически определяемы при t > 2 и q > 3. Более общий ответ на поставленный вопрос получил Цао [24], он доказал, что если |щ — rij\ < 2 и ni > Щ > ... > щ > t + 1, то K(ni,ri2,... ,nt) хроматически определяем при t > 2. Если обобщить задачу для произвольного значения \щ — rij| < к (г, j — 1, 2,..., t), то ответ на этот вопрос дали Цао, Ли, Лью и Йе [48], они показали, что если \щ — щ\ < к и щ > П2 > ... > щ > tk2/4 -Ь 1 для некоторого натурального числа к, то K(ni,ri2,... ,щ) хроматически определяем. Отметим, что Цао ранее получил аналогичный результат [24], но с оценкой для щ, которая хуже указанной здесь.

к) при p>k + 2>4w.t>d + 3>3 (Лау и

В 1990 г. Ли и Лью [49] доказали, что граф К(п\,... 1) является ^-определяемым тогда и только тогда, когда 2 > п\ > ... > \ > 1.

В ходе исследований различных авторов возникла следующая гипотеза: любой полный многодольный граф ■ ■ ■ является хрома-

тически определяемым при щ > п2 > ... > щ > 2.

Графы, хроматическую определяемость которых мы будем доказывать, характеризуются своим положением в некоторой решётке разбиений натуральных чисел. Основы теории разбиений чисел были заложены Эйлером ещё в XVIII веке. В монографии [50] приведены сведения по истории этой теории и многочисленным её достижениям.

Разбиением натурального числа п называется невозрастающая последовательность целых неотрицательных чисел и = {щ^щ, ■ ■ ■) такая, что щ > щ > ..., причём и содержит лишь конечное число ненулевых компонент и п = Щ. Число I такое, что / > 1, щ > 0 и щ+х = щ+2 = ... = 0, назовём длиной разбиения и и обозначим через 1{и). Мы будем писать п = пит(и) и для удобства записывать разбиение и в одном из следующих видов

и = (щ,и2,...) = (иъ...,щ).

Разбиение натурального числа удобно изображать в виде так называемой диаграммы Ферре, которую можно представить в виде вертикальной стенки, сложенной из кубических блоков одинакового размера. Вот пример такой диаграммы.

Рис. 1

На Рис. 1 представлено разбиение 20 = 6 + 4 + 4 + 3 + 1 + 1 + 1 числа 20 на 7 слагаемых. Здесь 7 — длина разбиения (6, 4,4, 3,1,1,1).

Через ЫРЬ{п, ¿) обозначим множество всех разбиений длины £ натурального числа п, где 1 < £ < п. Определим понятие элементарного преобразования разбиения и = (-¿¿х, гл2,. •. ,щ) числа п — пит(и) [51]. Пусть натуральные числа г и у таковы, что

1) 1 < г < з < Ц

2) щ — 1 > щ+1 и щ-г + 1;

3) щ = г^- + (), где 5 >2.

Будем говорить, что разбиение г> = (^1,..., щ — 1,..., щ + 1,..., щ) получено элементарным преобразованием (или перекидыванием блока) разбиения и = (щ,... щ), и будем писать в этом случае и -> V. Отметим,

что г; отличается от и точно на двух компонентах с номерами гну. Для диаграммы Ферре такое преобразование означает перемещение верхнего блока г-го столбца вправо в ^'-ый столбец. Условия 2) и 3) гарантируют, что после такого перемещения снова получится диаграмма Ферре.

Рассмотрим отношение > на множестве АГРЬ(п, £) [51], полагая и > V для и,у £ ИРЬ(п, £), если и можно получить из и с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований. Ясно, что отношение > на множестве МРЬ(п, ¿) является отношением частичного порядка. Отметим, что выполняется

тогда и только тогда, когда щ + .. .+щ > г>1 + .. .+Vi для любого г = 1,2,..., Отметим, что МРЬ(п, £) является решёткой относительно > [51].

Элементарное преобразование разбиения будем называть падением блока, если ; = г + 1 и 5 > 2 (см. Рис. 2(а)), и — сдвигом блока, если i + 1 < ^ щ — щ+1 + 1, г/г-+1 = = ... = и = % 1 (см. Рис. 2(6)), или если ;=г + 1и5 = 2 (см. Рис. 2(в)).

1

-1

(а)

(б) Рис. 2

(в)

Рассмотрим отношение => на ЫРЬ{п, ¿), полагая и V, если разбиение V получается из разбиения и падением или сдвигом блока. Отметим, что отношение совпадает с отношением покрытия в решётке МРЬ(п, ¿) [51].

Пусть п = £ • q + г, где д — натуральное число и г — неотрицательное целое число такие, что 0 < г < ¿. Нетрудно заметить, что разбиение (д + 1,..., д-Ь 1, д,..., д), где число д +1 повторяется г раз, а число д повторяется £ — г раз, является наименьшим элементом решётки ЛГР£(п,£).

Рассмотрим произвольный полный ¿-дольный граф К{п\, П2, ■ • •, щ)-Пусть п — щ + П2 + ... 4- щ — разбиение числа п, где щ > П2 > ... > щ > 1. Очевидно, с точностью до изоморфизма существует взаимно однозначное соответствие между полными ¿-дольными графами на п вершинах и элементами решётки АТРЬ(п,£). Поэтому мы можем отождествлять полный многодольный граф на п вершинах с соответствующим ему разбиением числа п. Конечно, порядок > на АТРЬ{п^) можно рассматривать как порядок на множестве полных ¿-дольных графов на п вершинах.

Как уже говорилось, в работе [31] доказано, что хроматически определяемы полные ¿-дольные графы вида К{д + 1,..., д + 1, д,..., д). Иными словами, хроматически определяемы полные многодольные графы, являющиеся наименьшими элементами в решётках ЛГР£(п, ¿). В работе [52] установлена хроматическая определяемость атомов в решётках ЫРЬ{п^ ¿) при щ > 2. Элементы высоты 2 и 3 этих решёток при ¿ = 3 рассмотрены в работах [53-55], там же доказана хроматическая определяемость полных трёхдольных графов, имеющих высоту 2 и 3 в решётках АТРЬ(п, 3) при щ > 2.

Цели данной работы состоят в следующем.

1. Дать классификацию элементов высоты < 3 в решётках АТРЬ(п, £) разбиений натуральных чисел п заданной длины I при £ > 4.

2. Исследовать хроматическую определяемость полных многодольных графов с неодноэлементными долями, имеющих высоту < 3 в этих решётках.

Перейдём теперь к изложению основных результатов диссертации. Текст диссертации, следующий за введением, разделён на две главы. Основные результаты работы названы теоремами, их две, по одной в каждой главе.

Первая глава посвящена классификации элементов высоты < 3 в решётках разбиений натуральных чисел заданной длины Ь > 4.

В первом параграфе первой главы даны основные определения и сведения об объектах, используемых в тексте диссертации. Сформулированы и доказаны леммы об изменении значений хроматических инвариантов/2(С), /3(С) и х + 1) при выполнении элементарных преобразований.

Во втором параграфе первой главы получена классификация элементов высоты < 3 в решётках А/"РЬ(п, при £ > 4. Результаты этой классификации сформулированы в виде Теоремы 1. В этой теореме представлена таблица, в которой перечислены все элементы высоты < 3 и условия их существования, а также некоторые их числовые характеристики. В частности, в колонке "Высота" указана высота этих элементов в решётке МРЬ(п,£), т.е. длина кратчайшего пути в решётке от наименьшего элемента до представленного. В колонке "Уровень" мы указали разницу в количестве рёбер между наименьшим элементом и рассматриваемым. Отметим, что далее в тексте диссертации вместо Теоремы 1 представлено более общее утверждение — Теорема 1.1, которая нам понадобится при доказательстве второго нашего основного результата.

Теорема 1. Следующая таблица дает классификацию элементов высоты < 3 в решётках ЛТРЬ(п, £) при £ > 4.

Таблица 1. Элементы малой высоты в решётках ЫРЬ(п,1) при г > 4

Элемент Условие существования Высота Уровень

Ь\ = ($ + 1,...,д + 1,^,...,^) г Ь—г о < г < г - 1 0 0

Ь2 = (д + 2чд + 1,...,д + 1—2 ¿-г+1 2 < г < £ — 1 1 1

63 = (д + 1,-..,д+ 1чд,...,д^,д- 1) г+1 г-г-2 0 < г < £ — 2 1 1

64 = (д + 2,д + 2чд + 1,...,д + 1чд,...,ду) г-4 £-г+2 4 < г<1 2 2

65 = (д + 2чд + 1,...,д+1чд,...,д^,д-1) г—1 г—1 1 < г < £ - 1 2 2

Ь6 = + 1,...,д + 1чд,...,д^,д- 1,д - 1) г+2 ¿-г-4 0 < г < £ — 4 2 2

Ь7 = (д + Зчд-1- 1,...,д + 1чд,...,ду) г-З £-г+2 3 = г < £ — 1 2 3

4 < г < £ - 1 3 3

Ь8 = (д + 2,...,д + 2чд + 1,...,д+ 1,чд,...,дЗ 3 т—б ¿-г+З 6 < г < £ - 1 3 3

69 = (д + 2,д + 2чд + 1,...,д + 1чд,...,д/д- 1) г-З ¿-г 3 < г <г-1 3 3

Ью = (д + 2чд + 1,-., д + 1, % д - 1, д - 1) г Ь—г—3 0<г<£-3 3 3

6ц = (чд + 1,...,д + 1чд,...,д^чд- 1,...,д- 1) г+З ¿-г-6 3 0 < г <6 3 3

Продолжение на следующей странице

Элемент Условие существования Высота Уровень

Ь\2 = (# + + 1, 2) г+2 г-г-ъ о < г = г - з 2 3

о < г < г - 4 3 3

Ьы = (д + + + 1, 1) г—2 ¿-г 2=г<г-\ 3 4

з = г < Ь - 1 3 4

&17 = (д + 2,д + 2чд + 1,...,д + 1,д- 1) г—2 ¿-г-2 2 = г < £ = 4 3 4

&19 = (д + + 1,..., д + 1,^,..., д-2) г Ь-г-2