Исследование факториального яруса решетки наследственных классов графов

• Автор: Замараев, Виктор Андреевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Нижний Новгород
• Количество страниц: 94 с. : ил.

Оглавление
Введение
I. Условия факториальности наследственных классов
1.1. Лемма о локально ограниченных покрытиях
1.2. Достаточные условия
II. Подклассы двудольных графов
2.1. Двудольные графы без Сф
2.2. Хордальные двудольные графы
2.3. Двудольные графы, не содержащие больших полных двудольных подграфов
III. Конечноопределенные классы
3.1. Один запрещенный подграф
3.2. Два запрещенных подграфа
3.3. Запрещенные графы с не более чем 4 вершинами
IV. Подклассы квазиреберных графов
V. Сверхфакториальные классы
5.1. Хордальные двудольные графы
5.1.1. Собственный сверхфакториальный подкласс
5.1.2. Новые факториальные подклассы
VI. Вполне квазиупорядоченные классы
6.1. Полная квазиупорядоченность субфакториальных классов и
классов из нижней части факториального яруса
6.2. Факториальные вполне квазиупорядоченные классы
Литература

Список обозначений
(7 = (С, Е) граф с множеством вершин V и множеством ребер Е
V(Є) множество вершин графа (7
Е(Є) множество ребер графа б
(7 = (А, В, Е) двудольный граф с долями А, В и множеством ребер Е (7[Л] подграф графа (7, порожденный множеством А С У(С)
С [А, В] двудольный подграф с множеством вершин А и В (А, В С С(<7),
А Г) В = 0), ребрами которого являются те и только те ребра графа (7, у которых один конец лежит в А, а другой в В N (у) множество вершин, смежных с вершиной V
Ма{у) множество вершин из множества А, смежных с вершиной у
Хп подмножество графов из множества X, в которых вершины помечены
числами 1,2 Сп гг-вершинный простой цикл
Шп (п + 1)-вершинный граф, получающийся из цикла Сп добавлением
вершины, смежной со всеми вершинами цикла
г(р, <7) число Рамсея с параметрами р, то есть такое наименьшее число,
что всякий граф с числом вершин не менее г(р, д) содержит либо Кр, либо Оя в качестве порожденного подграфа
Введение
В работе исследуются количественные характеристики наследственных классов графов, то есть множеств графов, которые замкнуты относительно изоморфизма и удаления вершины. В частности, изучаются классы, в которых число n-вершинных графов растет как функция факториального типа.
Первые результаты, посвященные асимптотическим оценкам количества n-вершинных графов в наследственных классах, появились несколько десятилетий назад. Первоначально изучались классы с одним запрещенным подграфом, а позднее и общий случай наследственных классов. Например, П. Эрдёш (P. Erdos), Д.Дж. Клейтман (D.J. Kleitman) и Б.Л. Ротшильд (B.L. Rothschild) [31] и Ф.Г. Колайтис (Ph.G. Kolaitis), Х.Ю. Промел (H.J. Prömel) и Б.Л. Ротшильд [39] исследовали наследственные классы, не содержащие больших полных подграфов, П. Эрдёш, П. Франкл (Р. Frankl) и В. Редль (V. Rödl) [30] изучали классы с одним запрещенных подграфом (необязательно порожденным), Х.Ю. Промел и А. Стегер (A. Steger) получили ряд результатов [45-47] для классов, заданных одним запрещенным порожденным подграфом. В ходе дальнейших исследований в этом направлении был получен фундаментальный результат, который говорит, что для любого бесконечного наследственного класса X обыкновенных графов, отличного от класса всех графов, справедливо следующее соотношение:
r l°g2 Хп
™ Ц) *(Х)
где Хп - количество n-вершинных графов из X, а к(Х) - натуральное число, называемое индексом класса X. Для определения последнего понятия обозначим через Еij класс всех графов, у которых множество вершин можно разбить на i + j подмножеств так, что г из них порождают полные, a j -пустые подграфы. Например, Еод совпадает с классом двудольных графов, а Ец 1 - с классом расщепляемых графов. Индексом наследственного класса X называется наибольшее число fc(X), при котором в X содержится хотя бы один из классов Еу с г + j = k(X). Впервые этот результат был получен
Из (2.3) следует, что для любых i = 1
а. Существует ] такое, что Аг. е Ск- и для любого г = 1,5, Вц ф. Ск~ 1- В этом случае положим С(Мк) = Ак Это не нарушает условия допустимости, так как ни одно из множеств Д. не принадлежит Ск Кроме того, Ак < АГ] | < р, поскольку А/; С уЦ
ЭГз. е С*_1-
б. Существует г такое, что Д4 6 Д_1 и для любого j = 1Д, УЦ Ск-ъ В этом случае положим С(Мк) = Вк Как и в предыдущем случае, это не нарушает условия допустимости, так как ни одно из множеств АГ] не принадлежит Д,. | Д | < Вц < р, так как Вк С Д. и В], е Ск-ъ
в. Для любых i = 1,в, j = 1Д, Ац 6 Ск-1 и ВГ] е Ск-ъ В этом случае в качестве С(Мк) возьмем то из множеств Ак я Вк, которое имеет меньшую мощность. Это не может нарушить условия допустимости, поскольку НИ ОДНО ИЗ множеств УЦ, Д. не принадлежит Д. При этом ттЦДД |Д-|} < р.
По построению С = Ст удовлетворяет условиям леммы.
Лемма 2.2.14. Древесная ширина графа С 6 КР:Р П СВ не превосходит 2р-3.
Доказательство. Пусть С - допустимое множество графа С, построенное согласно доказательству леммы 2.2.13, то есть для каждого С е С, С < р. По теореме 2.2.11 С является подграфом хордального графа Не, полученного из С добавлением всевозможных ребер между вершинами множества С для каждого С € С. Из теоремы 2.2.12 следует, что максимальный размер клики в Не не превосходит 2р — 2. Наконец, из (2.2) следует, что древесная ширина С не превосходит 2р — 3.