Исследование факториального яруса решетки наследственных классов графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Замараев, Виктор Андреевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Нижний Новгород
МЕСТО ЗАЩИТЫ
|
||||
|
2012
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
005019578
Замараев Виктор Андреевич
Исследование факториального яруса решетки наследственных классов графов
01.01.09 - «дискретная математика и математическая кибернетика:
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
1 9 АПР 2012
Нижний Новгород - 2012
005019578
Работа выполнена на кафедре математической логики и высшей алгебры факультета вычислительной математики и кибернетик^ Нижегородского государственного университета им. Н. И^Лобачевского.
Научный руководитель:
Доктор физико-математических наук, профессор Алексеев Владимир Евгеньевич
Официальные оппоненты:
Иорданский Михаил Анатольевич,
доктор физико-математических наук, профессор, заведующий кафедрой информатики и информационных технологий Нижегородского государственного педагогического университета им. Козьмы Минина
Шевченко Владимир Иванович,
кандидат физико-математических наук, доцент, старший научный сотрудник кафедры геометрии и высшей алгебры механико-математического факультета Нижегородского государственного университета им. Н. И. Лобачевского
Ведущая организация:
факультет вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова
Защита состоится 10 мая 2012 года в 14 часов 40 минут на заседании диссертационного совета Д.212.166.06 при Нижегородском государственном университете им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, корп. 2, конференц зал.
С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета им. Н. И. Лобачевского.
С текстом автореферата можно ознакомиться на официальном сайте Нижегородского государственного университета им. Н. И. Лобачевского www.unn.ru.
Автореферат разослан
2012 г.
Ученый секретарь диссертационного совета Д.212.166.06
В.И. Лукьянов
Общая характеристика работы
Актуальность работы. В работе исследуются количественные характеристики наследственных классов графов, то есть множеств графов, которые замкнуты относительно изоморфизма и удаления вершины. В частности, изучаются классы, в которых гасло п-вершинных графов растет как функция факториального типа.
Первые результаты, посвященные асимптотическим оценкам числа п-вершшшых графов в наследственных классах, появились несколько десятилетий назад. Первоначально изучались классы с одним запрещенным подграфом, а позднее и общий случай наследственных классов. Например, П. Эрдёш, Д.Дж. Клейтман и Б.Л. Ротшильд1 и 1>.Г. Колайтис, Х.Ю. Промел и В.Л. Ротшильд2 исследовали наследственные классы, не содержащие больших полных подграфов, П. Эрдёш, П. Франкл и В. Редль3 изучали классы с одним запрещенным подграфом (необязательно порожденным), Х.Ю. Промел и А. Стегер получили ряд результатов4'0'6 для классов, заданных одним запрещенным порожденным подграфом. В ходе дальнейших исследований в этом направлении был получен фундаментальный результат, который говорит, что для любого бесконечного наследственного класса X обыкновенных графов, отличного от класса всех графов, справедливо следующее соотношение:
1,111 —лл— = 1 ~ ТТтп'
П-+00 У к(К)
где Х„ - количество п-вершинных графов из X, а £(Х) - натуральное число, называемое индексом класса X. Для определения последнего понятия обозначим через Еу класс всех графов, у которых множество вершин можно разбить на 1->г ] подмножеств так, что г из них порождают полные, а } - пустые подграфы. Например, Ео,2 совпадает с классом двудольных графов, а Е^х - с классом расщепляемых графов. Индексом наследственного класса X называется наибольшее число /с(Х), при котором в X содержится хотя бы один из классов Еу с гЧ= к(Х). Впервые этот результат был получен В.Е. Алексеевым7, а позднее свое доказательство этого факта предложили Б. Болобаш и А. Томасон8'9. Сейчас в литературе этот результат можно встретить под названием
1 Erdos P., Kleitman D. J., Rothschild В. L. Asymptotic enumeration of Kn-free graphs // Colloquio Internazionale sulle Teorie Combinatorie (Home). - 1973. - P. 19-27
2 Kolaitis Ph. G., Promel H. J., Rothschild B. L., iw+i-free graphs: asymptotic structure and a 0-1 law // Trans. Amer. Math. Soc. - 1987. - V. 303. - P. 637-671
3 Erdos P., Frankl P., Rodl V. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent // Graphs and Combin. - 1986. - V. 2. - P. 113-121
4 Promel H. J., Steger A. Excluding induced subgraphs: quadrilaterals // Random Structures Algorithms. - 1991. - V. 2. - P. 55-71
5 Promel H. J., Steger A. Excluding induced subgraphs II: extremal graphs // Discrete Appl. Math. - 1993. - V. 44. - P. 283-294
6 Promel H. J., Steger A. Excluding induced subgraphs III: a general asymptotic // Random Structures Algorithms. - 1992. - V. 3. - P. 19-31
7 Алексеев В. E. Область значений энтропии наследственных классов графов // Дискретная Математика. - 1992. - В. 4(2) - С. 148-157
8 Bollobas В., Thomason A. Projections of bodies and hereditary properties of hypergraphs // Bull. London Math. Soc. - 1995. - V. 27. - P. 417-424
9 Bollobas В., Thomason A. Hereditary and monotone properties of graphs // «The mathematics of Paul Erdos, II> (R.L. Graham and J. Nesetril, Editors), Alg. and Combin. - 1997. - V. 14. - P. 70-78
теорема Алексеева-Болобаша-Томасона (Alekseev-Bollobas-Thomason Theorem)10.
Указанный выше результат В.Е. Алексеев получил, изучая вопрос кодирования наследственных классов графов. Неформально, кодированием графа называется представление его словом в конечном алфавите. Как известно, любой обыкновенный граф можно представить симметричной матрицей смежностей, у которой на главной диагонали стоят нули. Выписывая элементы этой матрицы, расположенные выше главной диагонали, в одну строчку, получим двоичное слово длины п(п — 1)/2, которое однозначно определяет исходный граф и называется каноническим кодом этого графа11. Если нам заранее ничего не известно об исходном графе, то (2) будет минимальным количеством двоичных символов, необходимым для его кодирования, то есть в этом случае канонический код будет неизбыточным. Если же мы имеем дело с графами из некоторого класса X, то, вообще говоря, используя эту информацию, графы могут быть закодированы с использованием меньшего числа двоичных символов. С другой стороны, очевидно, что log2 |Х„| - это минимальное количество бит, необходимое для кодирования п-вершинных графов из X. Если В* - множество всех слов в алфавите В = {0,1}, то кодированием для класса графов X называется семейство взаимно однозначных отображений Ф = {фп\п = 1, 2,...}, где фп : Х„ —» В*. Кодирование называют асимптотически оптимальным, если
Отношение логарифма числа п-вершинных графов в классе X к длине канонического кода - /г„(Х) = |Х„|/(2), можно рассматривать как максимально возможный «коэффициент сжатия» при кодировании графов из Хп. Если последовательность Ь„(Х) сходится, то её предел, обозначаемый через Л(Х), называется энтропией класса X. В.Е. Алексеев показал, что любой бесконечный наследственный класс имеет энтропию, а для классов с энтропией, отличной от нуля, предложил эффективный алгоритм кодирования графов, который дает асимптотически оптимальные коды11. Кроме того, В.Е. Алексеев полностью решил вопрос о возможных значениях энтропии для бесконечных наследственных классов. Как видно из (1), эту область составляют только числа вида 1 — 1 ¡к, то есть решетка наследственных классов графов разбивается на счетное множество слоев, каждый из которых состоит из классов с определенным значением энтропии. Для каждого слоя В.Е. Алексеев описал все минимальные элементы. Для к-то слоя, который состоит из классов с энтропией, равной 1 — 1 /к, минимальными элементами являются определенные выше классы Е;^-*, г = 0,1,..., к, и только они.
Перепишем (1) в следующем виде
Видно, что данное соотношение не дает асимптотической оценки функции log2 |Х„| для классов из унитарного слоя, то есть слоя с индексом, равным 1. Вместе с тем, этому слою принадлежат многие важные с практической и теоретической точек зрения
10 Alón N., Balogh J., Bollobás В., Morris R. The structure of almost all graphs in a hereditary property // J. Combin. Theory Ser. В. - 2011. - V. 101. - P. 85-110
11 Алексеев В. E. Наследственные классы и кодирование графов // В сб. Проблемы кибернетики. Под ред. C.B. Яблонского. - 1982. - В. 39. - Р. 151-164
max{|0n(G)|}
n^oo log2 |ХП|
(2)
классы, например, леса, планарные графы, реберные графы, интервальные графы, ко-графы, хордальные двудольные графы и др.
Для исследования асимптотического поведения функции log2 |Х„| для классов из унитарного слоя В.Е. Алексеев ввел понятие равновеликости. Множества графов X и У называются равновеликими, если существуют положительные константы с1,с2,По такие, что |У„|С1 < |Xn| < \Yn\C2 для всех п > п0. Из определения следует, что если Iog2 \Хп\ = ©(/(п)) и множества X и У равновелики, то log2 |У„| = 0(/(п)). Множество графов X, для которого log2 \Хп\ совпадает по порядку с 1, log2 п, п, п log2 п, называется константным, полиномиальным, экспоненциальным и факториальным соответственно. Сверхфакториальным называют множество графов X такое, что для любых положительных с и п0 существует п > п0 такое, что log2 |Х„| > cnlog2ri. Нетрудно видеть, что равновеликость является отношением эквивалентности. Классы эквивалентности по отношению равновеликости па множестве наследственных классов графов называются ярусами.
Все конечные наследственные классы образуют один ярус. Как видно из (2), все наследственные классы с индексом, большим 1, также составляют один ярус - для этих классов log2 |Х„| по порядку совпадает с п2. В свою очередь семейство наследственных классов с индексом, равным 1, - унитарный слой, разбивается на бесконечное множество ярусов. Действительно, рассмотрим класс Zp всех двудольных графов, не содержащих Крр в качестве подграфа. Из известных результатов12 о максимальном числе ребер в графах из Zp следуют оценки
Cjn^A" < log2 |Z£| < c2712"p log2n,
где Ci и с2 не зависят от п. Отсюда видно, что V и Z2p не равновелики.
Э. Шайнерман и Дж. Зито выделили четыре самых нижних яруса унитарного
i ^
слоя :
1) константный ярус состоит из классов X, для которых log2 |Х„| = 9(1),
2) полиномиальный ярус состоит из классов X, для которых log2 |Х„| = 0(logn),
3) экспоненциальный ярус состоит из классов X, для которых log2 |Х„| = 0(п),
4) факториалъныи ярус состоит из классов X, для которых log2 |Х„| = ©(nlogn).
Эти же авторы показали, что никаких промежуточных типов поведения не существует. Независимо, такой же результат был получен В.Е. Алексеевым14. Более того, для первых трех ярусов В.Е. Алексеев получил структурные описания и в каждом из четырех нашел все минимальные элементы, то есть такие классы, всякий наследственный собственный подкласс которых принадлежит нижележащему ярусу, и каждый наследственный класс из некоторого яруса содержит в себе по крайней мере один минимальный класс данного яруса. Позже аналогичные результаты были получены Дж. Балогхом, Б. Бoлoбáшeм и Д. Вайнрайхом15.
12 Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике - М.: Мир, 1976
13 Scheinerman Е. R., Zito J. On the size of hereditary classes of graphs // J. Combin. Theory Ser. В. - 1994. - V. 61. - P. 16-39
14 Алексеев В. E. О нижних ярусах решётки наследственных классов графов // Дискрет, анализ и исслед. операций. - 1997. - В. 4. - С. 3-12
15 Balogh J., Bollobás В., Weinreich D. The speed of hereditary properties of graphs // J. Combin. Theory Ser. В. - 2000. - V. 79. - P. 131-156
Факториальный ярус существенно богаче предыдущих трех, а классы из этого яруса имеют более разнообразную структуру. Значимость факториального яруса заключается в том, что он содержит многие классы, представляющие большой интерес с теоретической и практической точек зрения. Например, он содержит все упомянутые выше классы из унитарного слоя, за исключением класса хордальных двудольных графов. Несмотря на это, факториальный ярус не имеет какой-либо полной структурной характеризации. В диссертации представлены несколько подходов к исследованию факториального яруса и результаты, полученные на этом пути.
Цель работы. Целью работы является исследование свойств факториального яруса. Рассматриваемые вопросы включают:
1) исследование факториальных классов в некоторых семействах наследственных классов;
2) проверку справедливости гипотезы Лозина для отдельных семейств наследственных классов;
3) исследование множества хордальных двудольных графов как сверхфакториально-го класса, подозрительного на минимальность;
4) исследование связи между полной квазиупорядоченностью наследственного класса графа отношением быть порожденным подграфом и скоростью роста числа п-вершинных графов в этом классе.
Методы исследования. В работе использованы методы комбинаторного анализа и теории графов.
Результаты работы и научная новизна. Все полученные в диссертации результаты являются новыми. Основными результатами, выносимыми на защиту, являются
1. Доказана факториальность некоторых семейств подклассов класса двудольных графов. Описаны все факториальные классы, у которых запрещенные графы содержат не более 4 вершин. Для подклассов класса квазиреберных графов доказана гипотеза Лозина.
2. Охарактеризованы все подклассы класса хордальных двудольных графов с ограниченной древесной шириной.
3. Найден собственный сверхфакториальный подкласс класса хордальных двудольных графов, и тем самым показано, что последний не является минимальным сверхфакториальным. Кроме того, выявлены новые факториальные подклассы класса хордальных двудольных графов.
4. Доказано, что субфакториальные классы, а также классы из «нижней части» факториального яруса вполне квазиупорядочены отношением быть порожденным подграфом. Для определенного семейства подклассов класса двудольных графов доказана гипотеза о том, что если наследственный класс графов вполне квазиу-порядочен отношением быть порожденным подграфом, то он не более чем факториальный.
Теоретическая и практическая значимость. Работа носит теоретический характер. Полученные в диссертации результаты могут применяться для количественного анализа наследственных классов, а также могут служить ориентиром при разработке алгоритмов кодирования графов из классов с нулевой энтропией. Критерий ограниченности древесной ширины для подклассов класса хордальных двудольных графов может быть полезен при выявлении новых классов, для которых существуют полиномиальные алгоритмы решения задач определенного типа. Результаты работы могут быть использованы при разработке и чтении спецкурсов по теории графов.
Апробация работы. Основные результаты диссертации докладывались на:
• X международном семинаре «Дискретная математика и её приложения» (Москва, 2010);
• XV и XVI Нижегородских сессиях молодых ученых - математические науки (Красный плес, 2010, 2011);
• XVI международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 2011);
• VIII молодежной научной школе по дискретной математике и её приложениям (Москва, 2011);
• семинаре ВМиК МГУ «Дискретный анализ» (руководители А. А. Сапоженко, Т. В. Андреева);
• общегородских семинарах г. Н. Новгорода по дискретной математике (руководитель В.Н. Шевченко).
Публикации. По теме диссертации опубликовано 11 работ, список которых приводится в конце автореферата. Среди них 4 статьи в изданиях, рекомендованных ВАК РФ для публикации диссертаций («Вестник Нижегородского государственного университета», «Дискретная математика», «The Electronic Journal of Combinatorics», «European Journal of Combinatorics»), а также одна работа в рецензируемом журнале «Moscow Journal of Combinatorics and Number Theory», остальные в прочих изданиях.
Личный вклад автора. Общее направление исследований, а также подход к изучению факториалыюго яруса, основанный на рассмотрении конечноопределенных классов, были предложены научным руководителем.
Все основные результаты работы, выносимые на защиту, принадлежат лично соискателю.
Многие результаты были получены в ходе совместных исследований с В. В. Ло-зиным. Формулировка и доказательство леммы о локально ограниченных покрытиях принадлежат В. В. Лозину. Остальные результаты первой главы диссертации получены соискателем лично.
Доказательство теоремы 2.2.2 принадлежит К. Мэйхилу, доказательства теорем 3.2.4, 3.2.5, 3.2.8 и 3.2.24 принадлежат В. В. Лозину. Доказательства остальных результатов второй, третьей и четвертой глав работы принадлежат автору.
Доказательства теорем 5.1.5 и 5.1.8 получены В. В. Лозиным, а доказательства остальных теорем пятой главы диссертации получены соискателем.
Формулировка задачи, исследуемой в шестой главе, и гипотезы 6.0.11, а также доказательство леммы 6.1.4 принадлежат В. В. Лозину, в то время как доказательства остальных результатов последней главы работы получены автором.
Структура и объем диссертации. Диссертация состоит из введения, шести глав и списка литературы, включающего 53 наименования. Общий объем диссертации составляет 94 страниц. Нумерация всех теорем и лемм ведется независимо внутри каждой главы.
Содержание работы
Во введении обосновывается актуальность темы исследований, кратко излагаются основные результаты диссертации, а также приводятся используемые базовые определения и общепринятые обозначения.
В первой главе формулируются и доказываются условия факториальности наследственных классов графов, которые используются в последующих главах для исследования факториального яруса.
Будем говорить, что множество графов X является не более чем факториальным, если 1о§2 \Хп\ = 0(п\о&п), и не менее чем факториальным, если либо X факториально, то есть 1о§2 \Хп\ = в(пк^тг), либо 1о§2 £ 0(п\о£п). Объединением двух графов вх = (УиЕх) и <32 = {У2,Е2) будем называть граф Я = (V1 и и Е2). Пусть б -
некоторый граф. Множество графов {Нь ..., Н^}, объединение которых совпадает с (3, будем называть покрытием графа (?. Наибольшее число графов покрытия, которым одновременно принадлежит некоторая вершина покрываемого графа, назовем толщиной покрытия.
В первом разделе главы 1 доказывается следующее достаточное условие факториальности множества графов.
Лемма 1 (1.1.1) (О локально ограниченных покрытиях) Пусть X не менее чем факториальное множество графов и т & N некоторая константа. Если всякий граф € X может быть покрыт графами из не более чем факториального множества У так, что толщина покрытия не превосходит то, то X - факториальное множество.
Эта достаточно простая лемма оказалась мощным инструментом при выявлении факто-риальных наследственных классов. В частности, при исследовании конкретного класса она позволяет ограничиться рассмотрением только связных графов из данного класса.
Следствие 2 (1.1.3) Пусть X - множество графов, а X' - множество связных графов из X. Если X' не более чем факториальное, то X также не более чем факториальное.
Во втором разделе главы 1 формулируется ряд достаточных условий факториальности наследственных классов. Среди них наиболее значимыми являются следующие два.
Лемма 3 (1.2.1) Пусть X - не менее чем факториальный наследственный класс, V -не более чем факториальный наследственный класс и к & N - некоторая константа. Если для всякого графа б 6 X существует такое разбиение множества его вершин = VI и • • • и V», что:
1) для любых г,_/ е {1,... и V,-] е У,
2) для любого г 6 {1,..., в} и любой вершины V € V;, V имеет соседей в не более чем к множествах разбиения, отличных от VI,
то X - факториалъный класс.
Лемма 4 (1.2.2) Пусть X - не менее чем факториалъный класс графов, Y - не более чем факториалъный класс и <1 & N - некоторая константа. Если для любого графа (7 € X существует такое непустое множество А С У(С), что:
1) <3[Л] е У,
2) для любой вершины а € А либо ¡./^(а)! < й, либо |Л/в(а)| > п — щ — (1, где В = \ А, |У(С)| = п и \А\ = щ,
то X - факториалъный класс.
Результаты первой главы опубликованы в работе [4].
Во второй главе изучаются наследственные подклассы класса двудольных графов, интерес к которым вызван гипотезой Лозина. Обозначим через В, В в в класс двудольных, дополнительных к двудольным (кодвудольных) и расщепляемых графов соответственно.
Гипотеза 5 (2.0.7) [3] (гипотеза Лозина16) Наследственный класс X является фак-ториалъным тогда и только тогда, когда по крайней мере один из классов ХПВ, ХПВ или X П Б является факториальным и каждый из этих классов не более чем факториалъный.
Истинность этой гипотезы и знание всех факториальных подклассов двудольных, кодвудольных и расщепляемых графов может оказать существенную помощь при ответе на вопрос, является ли заданный наследственный класс X факториальным.
Напомним, что класс X - наследственный тогда и только тогда, когда он может быть задан множеством запрещенных порожденных подграфов М. При этом принято писать X = Ргее(М).
В первом разделе второй главы изучается семейство подклассов класса двудольных графов, не содержащих порожденного четырехвершинного цикла - С4. Доказывается, что для любого леса Р класс двудольных графов, не содержащих порожденных подграфов Р и С4, является не более чем факториальным.
Теорема 6 (2.1.2) Для любого леса Р класс Free(C4,F) П В является не более чем факториальным.
Подклассы класса хордальных двудольных графов исследуются во втором разделе. Доказывается, что для любого леса F класс хордальных двудольных графов, не содержащих порожденного леса Р, является не более чем факториальным.
Теорема 7 (2.2.2) Для любого леса Р класс Ргее(Р) П СВ является не более чем факториальным.
16 Эта гипотеза была предложена В.В. Лозиным более 10 лет назад, хотя и опубликована совсем недавно.
Также в этом разделе доказывается факториалыюсть класса хордальных двудольных графов, не содержащих фиксированного полного двудольного графа.
Теорема 8 (2.2.3) Для любых натуральных р, д > 2 класс Егее{КРЛ) ПСВ - фактори-алъный.
Последняя теорема является следствием другого важного результата данной главы. Древесная ширина - графовый параметр, представляющий интерес в связи с тем, что многие задачи, являющиеся А^Р-трудными в классе всех графов, могут быть решены за полиномиальное время на графах с ограниченной древесной шириной. Результат, о котором идет речь, описывает все подклассы хордальных двудольных графов с ограниченной древесной шириной. А именно справедлива следующая теорема.
Теорема 9 (2.2.8) Пусть X = Ргее(7^)ПСВ - подкласс класса хордальных двудольных графов. X имеет ограниченную древесную ширину тогда и только тогда, когда Крч 6 7?. для некоторых р, д е N.
В третьем разделе второй главы рассматриваются два семейства подклассов класса двудольных графов без Доказывается, что классы из этих семейств являются не более чем факториальными. Эти результаты обобщают некоторые утверждения из предыдущих двух разделов, однако, были получены независимо от последних.
Теорема 10 (2.3.2) Для любого леса Р и любого з € N класс Ргее(К,^, Р)ПВ является не более чем факториалъным.
Теорема 11 (2.3.4) Класс Ргее(К3)1, С2к, С2к+2, С2к+ь,.. .) ПВ является не более чем факториалъным для любых натуральных к > 2 и в > 2.
Результаты второй главы опубликованы в [7, 10 ].
В третьей главе исследуются конечноопределенные классы графов, то есть классы, определяемые конечным множеством запрещенных порожденных подграфов.
В первом разделе данной главы приводятся все факториальные классы, определяемые одним запрещенным подграфом.
Теорема 12 (3.1.1) Класс Ггее(С) факториален тогда и только тогда, когда (3 £
Наследственные классы с двумя запрещенными подграфами изучаются во втором разделе главы. Здесь формулируется необходимое условие факториалыюсти таких классов, описывающее структуру их запрещенных подграфов. Обозначим через -граф, получающийся из двух звезд и соединением их центральных вершин ребром. Граф Фр>д получается из 5р,д одиночным подразбиением ребра, соединяющего центральные вершины. Через Т1ь2,з обозначим граф, получаемый из звезды К13 одиночным подразбиением одного из её ребер и двойным подразбиением другого её ребра.
Утверждение 13 (3.2.2) Пусть X = 5Уее(С,#) - не более чем факториальный класс аС,Я^ВпВП8. Либо графы б, Н, либо их дополнения удовлетворяют одному из следующих условий:
1) один из запрещенных графов является С4, а другой - порожденным подграфом графа + Ог, для некоторых натуральных
2) один из запрещенных графов является порожденным подграфом одного из графов Ті>2,з,Фр,д + К\ или Р7 и при этом отличен от Сц, а другой - порожденным подграфом одного из двух графов 5рд + Оі или К\ф + Оя.
Для классов, у которых одни из запрещенных графов является полным, доказывается следующий результат.
Теорема 14 (3.2.4) Класс X = Ргее{Кг, Н), г > 3, не более чем факториалъный тогда и только тогда, когда Ргее(Н) П В не более чем факториалъный.
ііз этой теоремы следует справедливость гипотезы Лозина для классов указанного типа, а также описание почти всех факториальных классов с двумя запрещенными подграфами, одним из которых является полный граф.
Теорема 15 (3.2.5) Если Н не является порожденным подграфом какого-либо из графов 7^2,3, Фр,? + К і или Р7, то класс Ргее(Кг, Н), г > 3 - сверхфакториалъный. Если Н = Ті^.з или Н = Фр,? + К і для любых натуральных р, д, то Ргее{КТ,Н),г > 3 -факториалъный.
Единственным открытым здесь вопросом остается случай Ргее(Кг, Р7) при г > 3.
Далее в этом разделе для ряда семейств классов с двумя запрещенными подграфами доказывается их факториальность. Наиболее общими результатами здесь являются следующие теоремы.
Теорема 16 (3.2.23) Класс Ргее(К^р + 0\, + 0\) является факториалъным для любых натуральных р > 3 и д > 3.
Теорема 17 (3.2.24) Класс Ргее(КііР+Оя, Кг—е) является факториалъным для любых натуральных р >2, q>\ и г > 4.
Ещё одним важным результатом текущего раздела является доказательство фактори-альности класса Ргее(К\ ъ,Сц).
Теорема 18 (3.2.22) Класс Ргее(К13,Сі) факториалеп.
Некоторое время этот класс был единственным классом с двумя запрещенными четырехвершшшыми подграфами, для которого вопрос о его факториалыюсти был открыт. Ответ на этот вопрос позволил описать все факториальные классы, у которых запрещенные графы содержат не более четырех вершин. А именно, в третьем разделе текущей главы доказана следующая теорема.
Теорема 19 (3.3.2) Пусть М. - множество графов с числом вершин не более четырех такое, что Ргее(М) не менее чем факториалъный класс. Ргее(М) факториалеп тогда и только тогда, когда ни одно из следующих множеств не пусто: МГЇВ, Л4ПВ, Л^ПЭ, М П Ргее(К3, Сі), М П Ртее{КІ,СІ).
Результаты третьей главы опубликованы в работах [1-3, 5,6,8].
Сложная структура класса Free(Л'lIз, С4) обусловлена тем, что он содержит в себе подкласс класса квазиреберных графов без порожденных подграфов С4. Граф называется квазиреберным, если окрестность каждой его вершины можно разбить на две клики или, что то же самое, окрестность каждой вершины порождает кодвудольный граф. Несмотря на простое определение, структура квазиреберных графов весьма непростая.
Доказательство факториалыюсти класса Ргее(К\^, С4) можно разбить на два этапа:
1) сведение задачи к подклассу Free(Ct¡) HQ С Free(Kí¡3, С4), где Q - класс квазиреберных графов;
2) доказательство факториалыюсти класса Free(C4) П Q.
Основная трудность заключалась в реализации второго этапа, осуществление которого натолкнуло автора на рассмотрение следующего вопроса.
Для каких графов G класс Free(G) П Q факториален? (3)
Исследованию этого вопроса посвящена четвертая глава диссертации, основным результатом которой является следующее утверждение.
Теорема 20 (4.0.3) Пусть М. - множество графов. Free(M)OQ - не более чем фак-ториальный класс тогда и только тогда, когда Free(j\4) ПБ - не более чем фактори-алъный.
Из этой теоремы, в частности, следует справедливость гипотезы Лозина для подклассов класса квазиреберных графов. Кроме того, теорема 20 позволяет ответить на вопрос ( 3^ почти для всех графов G. Единственным исключением является граф P?, для которого вопрос остается открытым.
Теорема 21 (4.0.4) Если G не является порожденным подграфом какого-либо из графов 71,2,3, Фр,? + К i или Р7, то класс Free(G) flQ - сверхфакториалъиый. Если G = или G = ФPig + Ki, для любых натуральных р, q, то Free(G) П Q - факториальный.
Результаты четвертой главы опубликованы в [9,'11 ].
В пятой главе рассматривается ещё один подход к изучению факториального яруса, который заключается в исследовании минимальных сверхфакториальных классов. Если бы мы знали все минимальные классы яруса, следующего за факториальным, то могли бы либо доказать, либо опровергнуть гипотезу Лозипа. Однако, па сегодняшний день даже неизвестно, существует ли такой ярус. Например, может оказаться, что за факториальным ярусом следует бесконечная последовательность ярусов, «сходящаяся» к факториальному.
Если допустить, что ярус, следующий за факториальным, существует, то вполне естественно задаться вопросом, каким может быть этот ярус. При исследовании этого вопроса имеет смысл изучать «наименьшие» из известных сверхфакториальных классов. Известны классы17,18, для которых логарифм от числа n-вершинных графов по порядку совпадает с п log2 п. Это самые «близкие» к факториальному ярусу из известных на сегодняшний день сферхфакториальных классов. Единственным среди таких классов, для которого известно описание через запрещенные порожденные подграфы, является класс хордальных двудольных графов СВ = Free(C3, С5, С6, С7,...). Все известные из литературы наследственные подклассы класса хордальных двудольных графов являются факториальными. Это наталкивает на вполне естественный вопрос: является ли класс хордальных двудольных графов минимальным свсрхфакториальиым? В первом разделе пятой главы доказывается теорема 22 , которая дает отрицательный
17 Scheinerman Е. R., Zita J. On the size of hereditary classes of graphs //J. Combin. Theory Ser. В. - 1994. - V. 61. - P. 16-39.
18 Spinrad J. P. Nonredundant l's in Г-Free Matrice // SIAM Journal on Discrete Mathematics. -1995. - V. 8 (2). - P. 251-257.
ответ на этот вопрос. Обозначим через 2С4 граф, состоящий из двух вершинио-нспс-ресекающихся графов С4, а через 2С4 + е - граф, получающийся из 2С4 добавлением ровно одного ребра, соединяющего вершины различных С4.
Теорема 22 (5.1.3) Логарифм числа п-вершинных графов в наследственном классе Free(2Ci, 2С4 + е)ПСВ совпадает по порядку с n\og2n, то есть класс Free(2C4,2C4 + е) П СВ является сверхфакториальпым.
Теорема 7 говорит, что если в классе хордальных двудольных графов запретить произвольный порожденный лес (то есть граф без циклов), то мы получим факториальный класс. С другой стороны, согласно теореме 22 , если в классе хордальных двудольных графов запретить порожденный подграф, содержащий 2С4, то мы получим сверхфак-ториальный класс. По этой причине имеет смысл исследовать подклассы класса хордальных двудольных графов, которые получаются запретом порожденного подграфа с одним циклом. Такие классы рассматриваются во втором разделе данной главы. Все классы, для которых удалось получить конкретные результаты, оказались факториаль-ными.
Теорема 23 (5.1.5) Класс Free(Q) П СВ факториален. Теорема 24 (5.1.8) Класс Free(A) П СВ факториален.
Я А
Рис. 1. Графы <5 и А
Теорема 25 (5.1.10) Для любого натурального р > 2 класс Ргее(Крф + К{) П СВ -факториальный.
Последняя теорема является обобщением факториальности класса ^гее(С4 + Л"1)ПСВ. Результаты пятой главы опубликованы в [7, 10 ].
Шестая глава посвящена изучению связи между полной квазиупорядочепиостыо наследственного класса графа отношением быть порожденным подграфом и скоростью роста числа п-вершшшых графов в этом классе. Частично упорядоченное множество графов называется вполне квазиупорядоченным, если оно не содержит бесконечных антицепочек, то есть бесконечного множества попарно несравнимых графов, и любое его непустое подмножество имеет минимальный элемент. В данной главе высказывается следующее предположение.
Гипотеза 26 (6.0.11) Любой наследственный класс графов, вполне квазиупорядочен-ный отношением быть порожденным подграфом, является не более чем факториаль-ным.
Эта гипотеза доказывается для двух семейств наследственных классов.
Теорема 27 (6.2.1) Любой наследственный подкласс класса хордальных двудольных графов, вполне квазиупорядоченный отношением быть порожденным подграфом, является не более чем факториалытм.
Теорема 28 (6.2.2) Любой наследственный класс X С Ргее(К,:в)ПВ, где веМ, вполне квазиупорядоченный отношением быть порожденным подграфом, является не более чем факториальным.
Ещё одним важным результатом пятой главы является доказательство полной квазиу-порядоченпости любого наследственного класса X, для которого |Х„| <
Теорема 29 (6.1.5) Если X - наследственный класс и |Х„| < п'1"1"0'1^™, то X вполне квазиупорядочен отношением быть порожденным подграфом.
Результаты шестой главы опубликованы в [10].
Публикации по теме диссертации
В изданиях, включенных в перечень ВАК РФ:
[1] Алексеев В. Е. Некоторые результаты о наследственных классах графов / Алексеев
B. Е., Замараев В. А., Захарова Д. В., Малышев Д. С., Мокеев Д. Б. // Вестник Нижегородского университета им. H.H. Лобачевского. - 2011. - Т. 6. - С. 169-173.
[2] Замараев В. А. Оценка числа графов в некоторых наследственных классах // Дискретная Математика. - 2011. - Т. 23(3). - С. 57-62.
[3] Lozin V. V. A note on the speed of hereditary graph properties / Lozin V. V., Mayhill
C., Zamaracv V. // The Electronic Journal of Combinatorics. - 2011. - Vol. 18(1).
[4] Lozin V. V. Locally bounded coverings and factorial properties of graphs / Lozin V. V., Mayhill C., Zamaraev V. // European Journal of Combinatorics. - 2012. - Vol. 33(4).
- P" 534-543.
В прочих изданиях:
[5] Алексеев В. Е. Некоторые факториальные классы графов, определяемые двумя запрещёнными графами / Алексеев В. Е., Замараев В. А., Лозин В. В., Мэйхил К. // Тезисы докладов XV Нижегородской сессии молодых ученых - математические науки. Красный плес: 25-28 мая 2010. - С. 16-17.
[G] Замараев В. А. Оценка числа графов в некоторых наследственных классах // Материалы X Международного семинара «Дискретная математика и её приложения». Москва: 1-6 февраля 2010. - С. 301-303.
[7] Замараев В. А. Подклассы хордальных двудольных графов с ограниченной древесной шириной // Доклады Одесского семинара по дискретной математике (вып. 12). Одесса: 12-16 сентября 2011. - С. 28-31.
[8] Замараев В. А. Оценка числа графов в наследственных классах с запрещенными графами маленького порядка // Материалы XVI Международной конференции «Проблемы теоретической кибернетики». Нижний Новгород: 20-25 июня 2011. -С. 173-175.
[9] Замараев В. А. Факториальные подклассы квазиреберных графов, определяемые одним запрещенным подграфом // Тезисы докладов XVI Нижегородской сессии молодых ученых - математические науки. Нижний Новгород: 23-26 мая 2011. - С. 26-27.
[10] Замараев В. А. Оценка числа графов в некоторых подклассах двудольных графов // Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям. Москва: 24-29 октября 2011. - С. 29-33.
[11] Zamaraev V. Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph // Moscow Journal of Combinatorics and Number Theory. - 2011.
- Vol. 1(3). - P. 277-286.
Подписано в печать 30.03.2012. Формат 60><84 1/16. Бумага офсетная. Печать офсетная. Гарнитура Тайме. Усл. печ. л. 1. Заказ № 186. Тираж 100.
Отпечатано в типографии Нижегородского госуниверситета им. Н.И. Лобачевского 603000, г. Нижний Новгород, ул. Б. Покровская, 37
61 12-1/1041
ФГБОУ ВПО «Нижегородский государственный университет им. Н.И. Лобачевского» факультет вычислительной математики и кибернетики
На правах рукописи
Замараев Виктор Андреевич
Исследование факториального яруса решетки наследственных классов графов
01.01.09 - «дискретная математика и математическая кибернетика»
Диссертация на соискание ученой степени кандидата физико-математических наук
Научный руководитель: д. ф.-м. н., профессор Алексеев Владимир Евгеньевич
Нижний Новгород - 2012
Оглавление
Введение ......................................................................4
I. Условия факториальности наследственных классов .... 14
1.1. Лемма о локально ограниченных покрытиях...........14
1.2. Достаточные условия........................16
II. Подклассы двудольных графов..................21
2.1. Двудольные графы без С4 .....................25
2.2. Хордальные двудольные графы..................26
2.3. Двудольные графы, не содержащие больших полных двудольных подграфов ............................36
III. Конечноопределенные классы..................38
3.1. Один запрещенный подграф....................39
3.2. Два запрещенных подграфа....................40
3.3. Запрещенные графы с не более чем 4 вершинами........62
IV. Подклассы квазиреберных графов...............65
V. Сверхфакториальные классы...................68
5.1. Хордальные двудольные графы..................68
5.1.1. Собственный сверхфакториальный подкласс ......69
5.1.2. Новые факториальные подклассы.............71
VI. Вполне квазиупорядоченные классы..............82
6.1. Полная квазиупорядоченность субфакториальных классов и классов из нижней части факториального яруса.........84
6.2. Факториальные вполне квазиупорядоченные классы......87
Литература..................................89
Список обозначений
С = (У,Е) граф с множеством вершин V и множеством ребер Е
У (С) множество вершин графа С
Е{0) множество ребер графа б
С = (Л, В, Е) двудольный граф с долями Л, В и множеством ребер
С [Л] подграф графа (3, порожденный множеством Л С V (С)
С [Л, В] двудольный подграф с множеством вершин А и В (Л, В С
Л П В = 0), ребрами которого являются те и только те ребра графа С, у которых один конец лежит в Л, а другой в В
ЛГ(г>) множество вершин, смежных с вершиной v
Лмножество вершин из множества Л, смежных с вершиной у
Хп подмножество графов из множества X, в которых вершины помечены
числами 1,2,... }п
Сп п-вершинный простой цикл
]¥п (га + 1)-вершинный граф, получающийся из цикла Сп добавлением
вершины, смежной со всеми вершинами цикла
г(р, д) число Рамсея с параметрами р, д, то есть такое наименьшее число,
что всякий граф с числом вершин не менее г(р, q) содержит либо Кр, либо 0„ в качестве порожденного подграфа
Введение
В работе исследуются количественные характеристики наследственных классов графов, то есть множеств графов, которые замкнуты относительно изоморфизма и удаления вершины. В частности, изучаются классы, в которых число n-вершинных графов растет как функция факториального типа.
Первые результаты, посвященные асимптотическим оценкам количества n-вершинных графов в наследственных классах, появились несколько десятилетий назад. Первоначально изучались классы с одним запрещенным подграфом, а позднее и общий случай наследственных классов. Например, П. Эр-дёш (P. Erdos), Д.Дж. Клейтман (D.J. Kleitman) и B.JI. Ротшильд (B.L. Rothschild) [31] и Ф.Г. Колайтис (Ph.G. Kolaitis), Х.Ю. Промел (H.J. Prömel) и Б.Л. Ротшильд [39] исследовали наследственные классы, не содержащие больших полных подграфов, П. Эрдёш, П. Франкл (P. Frankl) и В. Редль (V. Rödl) [30] изучали классы с одним запрещенных подграфом (необязательно порожденным), Х.Ю. Промел и А. Стегер (А. Steger) получили ряд результатов [45-47] для классов, заданных одним запрещенным порожденным подграфом. В ходе дальнейших исследований в этом направлении был получен фундаментальный результат, который говорит, что для любого бесконечного наследственного класса X обыкновенных графов, отличного от класса всех графов, справедливо следующее соотношение:
log2|Xn| 1 m
llm —лл— = 1 ~ TTvv П-» оо Q к(Х)
где Хп - количество n-вершинных графов из X, а /с(Х) - натуральное число, называемое индексом класса X. Для определения последнего понятия обозначим через Е¿j класс всех графов, у которых множество вершин можно разбить на г + j подмножеств так, что г из них порождают полные, a j -пустые подграфы. Например, Ео,2 совпадает с классом двудольных графов, а Ехд - с классом расщепляемых графов. Индексом наследственного класса X называется наибольшее число &(Х), при котором в X содержится хотя бы один из классов E^j с г + j = k(K). Впервые этот результат был получен
В.Е. Алексеевым [2], а позднее свое доказательство этого факта предложили Б. Болобаш (В. Bollobas) и А. Томасон (A. Thomason) [20, 21]. Сейчас в литературе этот результат можно встретить под названием теорема Алексеева-Болобаша-Томасона (Alekseev-Bollobas-Thomason Theorem) (см., например,
[15])-
Указанный выше результат В.Е. Алексеев получил, изучая вопрос кодирования наследственных классов графов. Неформально, кодированием графа называется представление его словом в конечном алфавите. Как известно, любой обыкновенный граф можно представить симметричной матрицей смежностей, у которой на главной диагонали стоят нули. Выписывая элементы этой матрицы, расположенные выше главной диагонали, в одну строчку, получим двоичное слово длины п(п — 1)/2, которое однозначно определяет исходный граф и называется каноническим кодом этого графа [1]. Если нам заранее ничего не известно об исходном графе, то Q) будет минимальным количеством двоичных символов, необходимым для его кодирования, то есть в этом случае канонический код будет неизбыточным. Если же мы имеем дело с графами из некоторого класса X, то, вообще говоря, используя эту информацию, графы могут быть закодированы с использованием меньшего числа двоичных символов. С другой стороны, очевидно, что log2 |ХП| - это минимальное количество бит, необходимое для кодирования n-вершинных графов из X. Если В* - множество всех слов в алфавите В = {0,1}, то кодированием для класса графов X называется семейство взаимно однозначных отображений Ф = {фп\п = 1,2,...}, где фп : Хп —»• В*. Кодирование называют асимптотически оптимальным, если
max{|0n(G)|}
lim п _2.
п-» оо log2 (Хп|
Отношение логарифма числа n-вершинных графов в классе X к длине канонического кода - hn(K) = log2 |ХП|/Q), можно рассматривать как максимально возможный «коэффициент сжатия» при кодировании графов изХп. Если последовательность hn(X) сходится, то её предел, обозначаемый через /г(Х), называется энтропией класса X. В [1] В.Е. Алексеев показал, что лю-
бой бесконечный наследственный класс имеет энтропию, а для классов с энтропией, отличной от нуля, предложил эффективный алгоритм кодирования графов, который дает асимптотически оптимальные коды. В [2] В.Е. Алексеев полностью решил вопрос о возможных значениях энтропии для бесконечных наследственных классов. Как видно из (1), эту область составляют только числа вида 1 — 1/к, то есть решетка наследственных классов графов разбивается на счетное множество слоев, каждый из которых состоит из классов с определенным значением энтропии. Кроме того, в [2] были описаны минимальные элементы каждого слоя. Для к-то слоя, который состоит из классов с энтропией, равной 1 — 1/к, минимальными элементами являются определенные выше классы г = 0,1,..., к, и только они.
Перепишем (1) в следующем виде
Видно, что данное соотношение не дает асимптотической оценки функции |ХП| для классов из унитарного слоя, то есть слоя с индексом, равным 1. Вместе с тем, этому слою принадлежат многие важные с практической и теоретической точек зрения классы, например, леса, планарные графы, реберные графы, интервальные графы, кографы, хордальные двудольные графы
Для исследования асимптотического поведения функции |ХП| для классов из унитарного слоя В.Е. Алексеев ввел понятие равновеликости [3]. Множества графов X и У называются равновеликими, если существуют положительные константы С1,С2,по такие, что < \Хп\ < \Уп\°2 для всех п > щ. Из определения следует, что если |ХП| = Q(f(n)) и множества X и У равновелики, то \Уп\ = ©(/(п)). Множество графов X, для которого 1о§2 \Хп\ совпадает по порядку с 1,к^2п, п, пк^2п, называется константным, полиномиальным, экспоненциальным и факториальным соответственно. Сверхфакториальным называют множество графов X такое, что для любых положительных сищ существует п > щ такое, что \Хп\ > сп п. Нетрудно видеть, что равновеликость является отношением эквивалентно-
и др.
сти. Классы эквивалентности по отношению равновеликости на множестве наследственных классов графов называются ярусами.
Все конечные наследственные классы образуют один ярус. Как видно из (2), все наследственные классы с индексом, большим 1, также составляют один ярус - для этих классов log2 |ХП| по порядку совпадает с п2. В свою очередь семейство наследственных классов с индексом, равным 1, - унитарный слой, разбивается на бесконечное множество ярусов. Действительно, рассмотрим класс Zp всех двудольных графов, не содержащих KPjP в качестве подграфа [3]. Из известных результатов о максимальном числе ребер в графах из TP (см., например [12] или [19]) следуют оценки
Cin2_^+i < log2 \7Pn\ < С2П2~р log2 га,
где с\ и с2 не зависят от п. Отсюда видно, что Zp и 7?р не равновелики.
В [49] Э. Шайнерман (E.R. Scheinerman) и Дж. Зито (J. Zito) выделили четыре самых нижних яруса унитарного слоя:
1. константный ярус состоит из классов X, для которых log2 |Хп| = в(1),
2. полиномиальный ярус состоит из классов X, для которых log2 |Хп| = 9 (log га),
3. экспоненциальный ярус состоит из классов X, для которых log2 |Хп| =
е(п),
4. факториальный ярус состоит из классов X, для которых log2 |Хп| = O(ralogra).
Авторы [49] также показали, что никаких промежуточных типов поведения не существует. Независимо, такой же результат был получен В.Е. Алексеевым [3]. Более того, для первых трех ярусов В.Е. Алексеев получил структурные описания и в каждом из четырех нашел все минимальные элементы, то есть такие классы, всякий наследственный собственный подкласс которых принадлежит нижележащему ярусу, и каждый наследственный класс из некоторого
яруса содержит в себе по крайней мере один минимальный класс данного яруса. Позже аналогичные результаты были получены Дж. Балогхом (Л. Вак^И), Б. Болобашем и Д. Вайнрайхом (Б. \¥ешге1сЬ) [16].
Факториальный ярус существенно богаче предыдущих трех, а классы из этого яруса имеют более разнообразную структуру. Значимость факто-риального яруса заключается в том, что он содержит многие классы, представляющие большой интерес с теоретической и практической точек зрения. Например, он содержит все упомянутые выше классы из унитарного слоя, за исключением класса хордальных двудольных графов. Несмотря на это, факториальный ярус не имеет какой-либо полной структурной характеризации. В данной работе представлены несколько подходов к исследованию фактори-ального яруса и результаты, полученные на этом пути.
Диссертация состоит из введения, шести глав и списка литературы. Основные результаты излагаются в главах 2, 3, 4, 5 и 6.
В главе I формулируются и доказываются условия факториальности наследственных классов графов, которые используются в последующих главах для исследования факториального яруса. Результаты данной главы опубликованы в работе [43].
В следующих трех главах изучаются различные семейства наследственных классов графов. В рассматриваемых семействах исследуются фактори-альные классы с целью выявления для них общих структурных закономерностей, что может оказаться полезным для получения структурного описания факториального яруса. Так, в главе II изучаются наследственные подклассы двудольных графов, интерес к которым вызван гипотезой Лозина о том, что наследственный класс является не более чем факториальным тогда и только тогда, когда подклассы двудольных, кодвудольных и расщепляемых графов из этого класса не более чем факториальные. Здесь приводятся почти все факториальные подклассы двудольных графов, определяемые одним запрещенным подграфом [13]. Единственным исключением является класс двудольных графов, не содержащих порожденного пути на 7 вершинах -Р7. Для данного класса вопрос о его факториальности до сих пор остается от-
крытым. В разделе 2.1 изучается семейство подклассов двудольных графов, не содержащих порожденного четырехвершинного цикла -С4. Доказывается, что для любого леса Г, класс двудольных графов, не содержащих порожденных подграфов ^ и С4, является не более чем факториальным. Подклассы хордальных двудольных графов исследуются в разделе 2.2. Здесь доказывается, что для любого леса Г, класс хордальных двудольных графов, не содержащих порожденного леса является не более чем факториальным. Также в этом разделе описываются все подклассы хордальных двудольных графов с ограниченной древесной шириной. Последний результат позволяет доказать факториальность класса хордальных двудольных графов, не содержащих К3:3 для некоторого фиксированного натурального я. В разделе 2.3 рассматриваются два семейства подклассов класса двудольных графов без К8 3. Доказывается, что классы из этих семейств являются не более чем фак-ториальными. Результаты второй главы опубликованы в [7, 11].
В главе III исследуются факториальные конечноопределенные классы графов, то есть классы, определяемые конечным множеством запрещенных порожденных подграфов. В разделе 3.1 приводятся все факториальные классы, определяемые одним запрещенным подграфом. Наследственные классы с двумя запрещенными графами изучаются в разделе 3.2. Здесь формулируется необходимое условие факториальности таких классов, описывающее структуру их запрещенных подграфов. Кроме того, для ряда семейств классов с двумя запрещенными графами доказывается их факториальность. Для классов, у которых один из запрещенных графов является полным, доказывается гипотеза Лозина. В разделе 3.3 описываются все факториальные классы, у которых запрещенные графы содержат не более четырех вершин. В частности, в данной главе доказывается, что класс Ггее(К\^, С4) является факториальным. Некоторое время этот класс был единственным классом с двумя запрещенными четырехвершинными подграфами, для которого вопрос о его факториальности был открыт. Сложная структура указанного класса обусловлена тем, что он содержит в себе подкласс квазиреберных графов без порожденных подграфов С4. Граф называется квазиреберным, если окрест-
ность каждой его вершины можно разбить на две клики или, что то же самое, окрестность каждой вершины порождает кодвудольный граф. Несмотря на простое определение, структура квазиреберных графов, описанная недавно в [24], весьма непростая. Результаты, полученные в третьей главе, опубликованы в работах [4-6, 8, 9, 42].
Семейство наследственных подклассов квазиреберных графов изучается в главе IV. Из определения видно, что класс квазиреберных графов содержит в себе класс кодвудольных графов. Доказывается, что любой наследственный подкласс квазиреберных графов не более чем факториальный тогда и только тогда, когда подкласс, состоящий из кодвудольных графов этого класса, является не более чем факториальным. Из этого, в частности, следует справедливость гипотезы Лозина для подклассов квазиреберных графов и описание почти всех факториальных подклассов квазиреберных графов, определяемых одним запрещенным подграфом. Эти результаты опубликованы в [10, 53].
В главе V в качестве одного из подходов к изучению факториального яруса предлагается исследовать «наименьшие» из известных сверхфакториаль-ных классов. Одним из таких классов является класс хордальных двудольных графов, рассматриваемый в разделе 5.1. Двудольный граф называется хор-дальным двудольным, если всякий его порожденный цикл есть В разделе 5.1.1 выявляется собственный сверхфакториальный подкласс класса хордальных двудольных графов и тем самым доказывается, что класс хордальных двудольных графов не является минимальным сверхфакториальным. Этим подклассом является подкласс хордальных двудольных графов, не содержащих порожденных подграфов 2С4 и + Первый из этих графов есть объединение двух вершинно-непересекающихся циклов С4, а второй получается из первого добавлением ребра, соединяющего вершины из разных С4. Отсюда видно, что если в классе хордальных двудольных графов запретить граф, содержащий порожденный подграф 2С4, то мы получим сверхфакториальный подкласс. С другой стороны, согласно одному из результатов второй главы, если в классе хордальных двудольных графов запретить произвольный порожденный лес (то есть граф без циклов), то мы получим факториальный
класс. Поэтому в разделе 5.1.2 рассматриваются подклассы класса хордаль-иых двудольных графов, не содержащие порожденных подграфов ровно с одним циклом. Доказывается факториальность каждого из рассматриваемых подклассов. Эти результаты позволяют думать, что класс хордальных двудольных графов без порожденных 2С4 и 2С4 + е может быть минимальным сверхфакториальным. Полученные в данной главе результаты опубликованы в [7, 11].
Глава VI пос
