Исследование факториального яруса решетки наследственных классов графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Замараев, Виктор Андреевич

• Замараев, Виктор Андреевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Замараев, Виктор Андреевич

Оглавление

Введение

I. Условия факториальности наследственных классов

1.1. Лемма о локально ограниченных покрытиях

1.2. Достаточные условия

II. Подклассы двудольных графов

2.1. Двудольные графы без С4

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. Факториальные вполне квазиупорядоченные классы

Литература

Список обозначений

С = (У,Е) граф с множеством вершин 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 посвящена изучению связи между полной квазиупорядоченностью наследственных классов графов отношением быть порожденным подграфом и скоростью роста числа п-вершинных графов в этих классах. Частично упорядоченное множество графов называется вполне квазиупорядоченным, если оно не содержит бесконечных антицепочек, то есть бесконечного множества попарно несравнимых графов, и любое его непустое подмножество имеет минимальный элемент. Высказывается гипотеза 6.0.11 о том, что если наследственный класс графов вполне квазиупорядочен отношением быть порожденным подграфом, то он не более чем факториальный. В разделе 6.1 доказывается полная квазиупорядоченность любого наследственного класса X, для которого |ХП| < п^+^К В разделе 6.2 упомянутая выше гипотеза 6.0.11 проверяется для некоторых семейств наследственных классов. Результаты шестой главы опубликованы в [11].

В работе используются следующие общепринятые обозначения. Граф с множеством вершин V и множеством ребер Е обозначается через (7 = (V, Е). Через Ы{у) обозначается окрестность вершины у, то есть множество вершин, смежных с v. Если II С V, то через -/%(г>) обозначается множество вершин из и, смежных с у, через обозначается подграф графа (7, порождаемый множеством II, а через С \ и обозначается граф \ 17]. Если А и В - непересекающиеся подмножества множества вершин графа С, то В] обозначает двудольный граф с множеством вершин А и В, ребрами которого являются все ребра графа у которых один конец лежит в А, другой -в В, и только они. (7 обозначает граф, дополнительный к С. Кп, Сп, Рп -соответственно полный граф, простой цикл и простой путь с п вершинами,

Кп,т _ полный двудольный граф. Объединение двух вершинно-непересекаю-щихся графов и Я будем обозначать через С + Я. Если X и У - множества графов, то X + У = {С + Я|С Е Х,Н £ У}. Две вершины графа называются подобными, если не существует третьей вершины, которая смежна только с одной из них. Легко видеть, что подобие - отношение эквивалентности и каждый класс эквивалентности порождает полный или пустой подграф.

Будем рассматривать обыкновенные графы, вершины которых помечены натуральными числами. Если X - множество графов, то через Хп обозначается подмножество графов из X с множеством вершин {1,2,..., п}. Множество графов, замкнутое относительно изоморфизма, называется классом графов. Для того, чтобы подчеркнуть, что некоторое множество графов X является классом, мы будем выделять его жирным шрифтом. Класс X называется монотонным, если всякий граф, изоморфный некоторому подграфу графа из X, принадлежит X. Класс X называется наследственным, если каждый граф, изоморфный порожденному подграфу графа из X, принадлежит X. Наследственные классы графов допускают описание через множество запрещенных порожденных подграфов. Пусть .М - множество графов, тогда через Ргее(Л4) принято обозначать множество всех графов, не содержащих порожденных подграфов, изоморфных графам изЛ4. Известно (см., например, [1]), что множество графов X является наследственным классом тогда и только тогда, когда X = Ргее{М) для некоторого Л4. Для простоты договоримся опускать фигурные скобки в записи Ргее(Л4), когда вместо Л4 указывается конкретное множество графов. Например, вместо Ргее({К1^}) будем писать Ргее(К\Нетрудно показать, что X = Free(Л4) С У = Ргее{М) тогда и только тогда, когда для каждого графа Н Е N существует граф С Е Л4 такой, что С является порожденным подграфом Н. Наследственный класс X = Ргее(М.) называется конечноопределенным, если множество М, - конечно. Если X и У - наследственные классы, то, очевидно, X и У и X П У - тоже наследственные классы. Наследственным классом является и множество X, состоящее из всех графов, дополнительных к графам из X. Такой класс называется инверсным к X. Если X = Ргее(М), Y = ^гее(Л/*), то

= Free(Л/í и Л/"), X = Ргее(М), где М - множество графов, дополнительных к графам из Л4. Пусть X - произвольное множество двудольных графов. Сопряженным к X называется множество графов у которых множество вершин можно разбить на два подмножества Ух и Уч такие, что С[У\] - пустой, граф Сг^] - полный, а граф 1, У%\ принадлежит множеству X. Сопряженное к X множество будем обозначать через X.

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

I. Условия факториальности наследственных классов

Будем говорить, что множество графов X является не более чем факто-риальным, если \Хп\ = 0(n\ogn), и не менее чем факториальным, если либо X - факториальное, то есть \Хп\ = Q(nlogn), либо \Хп\ ф 0(n\ogn). Наследственный класс будем называть субфакториалъным, если он принадлежит одному из трех ярусов: константному, полиномиальному или экспоненциальному.

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

1.1. Лемма о локально ограниченных покрытиях

Объединением двух графов Са = (Уь Е\) и = (У2, Е2) будем называть граф Н = (У\ и ¥2, и Е2). Пусть некоторый граф. Множество графов {#1,..., Нь}, объединение которых совпадает с С, будем называть покрытием графа С. Наибольшее число графов покрытия, которым одновременно принадлежит некоторая вершина покрываемого графа, назовем толщиной покрытия.

Лемма 1.1.1. (О локально ограниченных покрытиях) Пусть X не менее чем факториальное множество графов и т £ N некоторая константа. Если всякий граф С Е X может быть покрыт графами из не более чем факториального множества У так, что толщина покрытия не превосходит т, то X - факториальное множество.

Доказательство. Пусть ..., Нк\ СУ - покрытие графа С € X, толщина которого не превосходит т. Если щ = \У(Нг)\,п = |У(С)|, то

к

Очевидно, что всякий п-вершинный граф С из X может быть однозначно задан парой наборов:

1) набором графов Н\,..., Нь ¡Е У, покрывающих С,

2) набором инъективных отображений ф^ : —У {1 ,...,п}, г = 1,..., к, каждое из которых определяет вложение графа Щ в граф С.

Поэтому \Хп\ не превосходит количества различных пар наборов. Так как У не более чем факториальное, то существует с > 0 такое, что \Уп\ < псп. Отсюда следует, что

то есть log2 \Хп\ = O(nlogn). Учитывая условие леммы, заключаем, что X

Следствие 1.1.2. Пусть X - не менее чем факториальное множество графов. X является факториальным тогда и только тогда, когда существуют такие константа т Е N и не более чем факториальное множество У, что для любого графа С 6 X существует покрытие {Яь ..., Я^} С У, толщина которого не превосходит т.

Доказательство. Для доказательства необходимости заметим, что если X факториальное, то любой граф из этого множества может быть покрыт самим собой, то есть в качестве У достаточно взять X, а т положить равным 1. Достаточность следует из леммы 1.1.1. ■

Следствие 1.1.3. Пусть X - множество графов, а X' - множество связных графов из X. Если X' не более чем факториальное, то X также не более чем факториальное.

(1.1)

k к ш < Дп-п- < n(c+1)£ni <

г=1

факториальное множество.

1.2. Достаточные условия

Лемма 1.2.1. Пусть X - не менее чем факториалъный наследственный класс, У - не более чем факториалъный наследственный класс и к Е N -некоторая константа. Если для всякого графа С 6 X существует такое разбиение множества его вершин = У\ и • • • и У8, что:

1) для любых i,jE{l,..., и V}] Е У,

2) для любого г Е {1,..., 5} и любой вершины у Е Уг, у имеет соседей в не более чем к множествах разбиения, отличных от

то X - факториалъный класс.

Доказательство. Рассмотрим произвольный граф С из класса X, и пусть 1/(С) = У\ и • • • и У3 - разбиение, удовлетворяющее условиям леммы. Покажем, что С может быть покрыт графами из класса У так, что толщина покрытия не превосходит к + 1. По лемме 1.1.1 это будет означать, что X факториальный.

Обозначим через Н^ подграф графа порожденный вершинами

из множества У{, которые смежны хотя бы с одной вершиной из множества^-, и вершинами из множества У^, которые смежны хотя бы с одной вершиной из множества Ц,. Нетрудно видеть, что множество {(^[Ух],..., и {Н^\г =

1, з, = 1,5, г < является покрытием графа Кроме того, в силу наследственности, каждый из этих графов принадлежит У. Рассмотрим произвольную вершину V Е У (С) и обозначим через £ номер множества в разбиении, которому принадлежит у. По очевидным причинам у может покрываться только графами Н2,и • • •, Щг+и • • • > На самом же деле

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

Лемма 1.2.2. Пусть X - не менее чем факториалъный класс графов, У -не более чем факториалъный класс и (1 Е N - некоторая константа. Если

для любого графа С Е X существует такое непустое множество А С что:

1. в\А] е Y,

2. для любой вершины а £ А либо |А^(а)| < (I, либо | АГв(а) | > га — щ — 4, где В = У (С) \ А, |У(<3)| = га и \А\ = щ,

то X - факториальный класс.

Доказательство. Так как X не менее чем факториальный, то нам остается доказать только верхнюю факториальную оценку числа п-вершинных графов в классе X. Обозначим это число через /(га) и докажем, что /(га) < пНп для всех га, при некотором /г > 0. Доказательство проведем индукцией по га. Очевидно, что /(1) < 1. Пусть га > 2 и /л(га) - число графов из Хп, для которых фиксированное множество А удовлетворяет условиям леммы. Так как У не более чем факториальный, то существуете > 0 такое, что \Уп\ < псп для всех га > 0. Поэтому величину /д(га) можно оценить следующим образом:

где га^"1 - оценка количества различных графов, порождаемых множеством А, /(га — п\) - количество различных графов, порождаемых множеством В, и С1!"1)) ~ оценка числа различных расположений ребер между

множествами А и В.

/а(га) < пСП1(2{(1+ 1)га°г)П1/(п - щ) = га(с+^)п1ап1/(га - щ), где а = 2(4 + 1). Для га > 2, ащ = пП11оёпа < га&П1, где Ь = а, поэтому

/А(п) < га^+с+^П1/(п - щ) = га^Дга - ты), (1.2)

где Ь — Ь + с +

По предположению индукции для щ > 0, /(п — щ) < (п — П1)1г^п~п1\ Для завершения доказательства нам необходимо показать, что /(п) < пНп. Не уменьшая общности, будем считать, что Н > £ + 2. Учитывая (1.2):

п / \ п п /(п) < (п )пЫ1{п - п1)Кп~п1) < < ]г пЫ~щ <пЫ-

Список литературы диссертационного исследования кандидат физико-математических наук Замараев, Виктор Андреевич, 2012 год

Литература

[1] Алексеев В. Е. Наследственные классы и кодирование графов // В сб. Проблемы кибернетики. Под ред. C.B. Яблонского. - 1982. - Т. 39. - С. 151-164.

[2] Алексеев В. Е. Область значений энтропии наследственных классов графов // Дискретная Математика. - 1992. - Т. 4(2). - С. 148-157

[3] Алексеев В. Е. О нижних ярусах решётки наследственных классов графов // Дискрет, анализ и исслед. операций. - 1997. - Т. 4. - С. 3-12.

[4] Алексеев В. Е. Некоторые результаты о наследственных классах графов / Алексеев В. Е., Замараев В. А., Захарова Д. В., Малышев Д. С., Мокеев Д. Б. // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2011. - Т. 6. - С. 169-173.

[5] Алексеев В. Е. Некоторые факториальные классы графов, определяемые двумя запрещёнными графами / Алексеев В. Е., Замараев В. А., Лозин В. В., Мэйхил К. // Тезисы докладов XV Нижегородской сессии молодых ученых - математические науки. Красный плес: 25-28 мая 2010. - С. 16-17.

[6] Замараев В. А. Оценка числа графов в некоторых наследственных классах // Материалы X Международного семинара «Дискретная математика и её приложения». Москва: 1-6 февраля 2010. - С. 301-303.

[7] Замараев В. А. Подклассы хордальных двудольных графов с ограниченной древесной шириной // Доклады Одесского семинара по дискретной математике (вып. 12). Одесса: 12-16 сентября 2011. - С. 28-31.

[8] Замараев В. А. Оценка числа графов в наследственных классах с запрещенными графами маленького порядка // Материалы XVI Международной конференции «Проблемы теоретической кибернетики». Нижний Новгород: 20-25 июня 2011. - С. 173-175.

[9] Замараев В. А. Оценка числа графов в некоторых наследственных классах // Дискретная Математика. - 2011. - Т. 23(3). - С. 57-62.

[10] Замараев В. А. Факториальные подклассы квазиреберных графов, определяемые одним запрещенным подграфом // Тезисы докладов XVI Нижегородской сессии молодых ученых - математические науки. Нижний Новгород: 23-26 мая 2011. - С. 26-27.

[11] Замараев В. А. Оценка числа графов в некоторых подклассах двудольных графов // Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям. Москва: 24-29 октября 2011. -С. 29-33.

[12] Эрдёш П. Вероятностные методы в комбинаторике / Эрдёш П., Спенсер Дж. / Москва: Мир, 1976

[13] Allen P. Forbidden induced bipartite graphs //J. Graph Theory. - 2009. -Vol. 60, - P. 219-241

[14] Allen P. Clique-width and the speed of hereditary properties / Allen P., Lozin V., Rao M. // Electronic Journal of Combinatorics. - 2009. - Vol. 16.

[15] Alon N. The structure of almost all graphs in a hereditary property / Alon N., Balogh J., Bollobâs В., Morris R. // J. Combin. Theory Ser. B. - 2011. - Vol. 101. - P. 85-110.

[16] Balogh J. The speed of hereditary properties of graphs / Balogh J., Bollobâs В., Weinreich D. // J. Combin. Theory Ser. B. - 2000. - Vol. 79. - P. 131-156

[17] Balogh J. A jump to the Bell number for hereditary graph properties / Balogh J., Bollobâs В., Weinreich D. // J. Combin. Theory Ser. B. - 2005. - Vol. 95. - P. 29-48

[18] Bandelt H. J. Distance-hereditary graphs / Bandelt H. J., Mulder H. M. // J. Combin. Theory Ser. B. - 1986. - Vol. 41. - P. 182-208.

[19] Bollobas B. Extremal graph theory. London: Acad. Press, 1978

[20] Bollobas B. Projections of bodies and hereditary properties of hypergraphs / Bollobas B., Thomason A. // Bull. London Math. Soc. - 1995. - Vol. 27.

- P. 417-424.

[21] Bollobas B. Hereditary and monotone properties of graphs / Bollobas B., Thomason A. // "The mathematics of Paul Erdos, II" (R.L. Graham and J. Nesetril, Editors), Alg. and Combin. - 1997. - Vol. 14. - P. 70-78.

[22] Brandstadt A. Clique-Width for 4-Vertex Forbidden Subgraphs / Brandstadt A., Engelfriet J., Le H.-O., Lozin V. V. // Theory of Computing Systems. -2006. - Vol. 34. - P. 561-590.

[23] Cayley A. A theorem on trees // Quart. J. Math. - 1889. - Vol. 23. - P. 376-378

[24] Chudnovsky M. The structure of claw-free graphs / Chudnovsky M., Seymour P. // London. Math. Soc. Lecture Note Series - 2005. - Vol. 327. - P. 153-171

[25] Courcelle B. Handle-rewriting hypergraphs grammars / Courcelle B., Engelfriet J., Rozenberg G. // J. Comput. System Sci. - 1993. - Vol. 46.

- P. 218-270.

[26] Courcelle B. Upper bounds to the clique width of graphs / Courcelle B., Olariu S. // Discrete Appl. Math. - 2000. - Vol. 101. - P. 77-114.

[27] Damaschke P. Induced subgraphs and well-quasi-ordering //J. Graph Theory

- 1990. - Vol. 14. - P. 427-435.

[28] Ding G. Subgraphs and Well-Quasi-Ordering //J. Graph Theory - 1992. -Vol. 16. - P. 489-502.

[29] Eisenbrand F. The stable set polytope of quasi-line graphs / Eisenbrand F., Oriolo G., Stauffer G., Ventura P. // Combinatorica - 2008. - Vol. 28. - P. 45-67.

[30] Erdos P. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent / Erdos P., Frankl P., Rodl V. // Graphs and Combin. - 1986. - Vol. 2. - P. 113-121

[31] Erdos P. Asymptotic enumeration of Kn-iiee graphs / Erdos P., Kleitman D. J., Rothschild B. L. // Colloquio Internazionale sulle Teorie Combinatorie. Rome: 1973. - P. 19-27.

[32] Golumbic M. C. On the clique-width of some perfect graph classes / Golumbic M. C., Rotics U. // International J. Foundations of Computer Science. - 2000.

- Vol. 11. - P. 423-443.

[33] Higman G. Ordering by divisibility of abstract algebras // Proc. London Math. Soc. - 1952. - Vol. 2. - P. 326-336.

[34] Hoffman A. J. Totally-balanced and greedy matrices / Hoffman A. J., Kolen A. W., Sakarovitch M. // SIAM J. Algebr. Discrete Meth. - 1985. - Vol. 6.

- P. 721-730.

[35] Kierstead H. A. Radius two trees specify %-bounded classes / Kierstead H. A., Penrice S. G. // J. Graph Theory - 1994. - Vol. 18. - P. 119-129.

[36] Kierstead H. A. Radius three trees in graphs with large chromatic number / Kierstead H. A., Xhu Y.-X. // SIAM J. Discrete Mathematics - 2004. - Vol. 17. - P. 571-581.

[37] Kloks T. Ki^-iiee and W4-free graphs // Information Processing Letters -1996. - Vol. 60. - P. 221-223.

[38] Kloks T. Treewidth of chordal bipartite graphs / Kloks T., Kratsch D. // J. Algorithms - 1995. - Vol. 19. - P. 266-281.

[39] Kolaitis Ph. G. K/+i-free graphs: asymptotic structure and a 0-1 law / Kolaitis Ph. G., Promel H. J., Rothschild B. L. // Trans. Amer. Math. Soc.

- 1987. - Vol. 303. - P. 637-671.

[40] Kühn D. Induced subdivisions in KSiS-free graphs of large average degree / Kühn D., Osthus D. // Combinatorica. - 2004. - Vol. 24(2). - P. 287-304.

[41] Lazebnik F. Explicit construction of graphs with an arbitrary large girth and of large size / Lazebnik F., Ustimenko V. A. // Discrete Applied Mathematics. - 1995. - Vol. 60. - P. 275-284.

[42] Lozin V. V. A note on the speed of hereditary graph properties / Lozin V. V., Mayhill C., Zamaraev V. // The Electronic Journal of Combinatorics. -2011. - Vol. 18(1).

[43] 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.

[44] Lozin V. V. Chordal bipartite graphs of bounded tree- and clique-width / Lozin V. V., Rautenbach D. // Discrete Mathematics. - 2004. - Vol. 283. -P. 151-158.

[45] Prömel H. J. Excluding induced subgraphs: quadrilaterals / Prömel H. J., Steger A. // Random Structures Algorithms. - 1991. - Vol. 2. - P. 55-71.

[46] Prömel H. J. Excluding induced subgraphs III: a general asymptotic / Prömel H. J., Steger A. // Random Structures Algorithms. - 1992. - Vol. 3. - P. 19-31.

[47] Prömel H. J. Excluding induced subgraphs II: extremal graphs / Prömel H. J., Steger A. // Discrete Appl. Math. - 1993. - Vol. 44. - P. 283-294.

[48] Robertson N. Graph Minors. XX. Wagner's conjecture / Robertson N., Seymour P. D. // J. Combin. Theory Ser. B. - 2004. - Vol. 92. - P. 325-357.

[49] Scheinerman E. R. On the size of hereditary classes of graphs / Scheinerman E. R., Zito J. // J. Combin. Theory Ser. B. - 1994. - Vol. 61. - P. 16-39.

[50] Spinrad J. Bipartite permutation graphs / Spinrad J., Brandstadt A., Stewart L. // Discrete Appl. Math. - 1987. - Vol. 18. - P. 279-292.

[51] Spinrad J. P. Nonredundant l's in T-Free Matrice // SIAM Journal on Discrete Mathematics. - 1995. - Vol. 8(2). - P. 251-257.

[52] Wagon S. A bound on the chromatic number of graphs without certain induced subgraphs //J. Combin. Theory Ser. B. - 1980. - Vol. 29. - P. 345-346.

[53] 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.