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

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

Первые результаты, посвященные асимптотическим оценкам количества n-вершинных графов в наследственных классах, появились несколько десятилетий назад. Первоначально изучались классы с одним запрещенным подграфом, а позднее и общий случай наследственных классов. Например, П. Эр-дёш (P. Erdos), Д.Дж. Клейтман (D.J. Kleitman) и B.JI. Ротшильд (B.L. Rothschild) [31] и Ф. Г. Колайтис (Ph.G. Kolaitis), Х. Ю. Промел (H.J. Promel) и Б. Л. Ротшильд [39] исследовали наследственные классы, не содержащие больших полных подграфов, П. Эрдёш, П. Франкл (P. Frankl) и В. Редль (V. Rodl) [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.

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

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

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

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

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

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

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

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

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

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

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

12. Allen P. Forbidden induced bipartite graphs //J. Graph Theory. 2009. -Vol. 60, — P. 219−241.

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

14. Alon N. The structure of almost all graphs in a hereditary property / Alon N., Balogh J., Bollobas В., Morris R. // J. Combin. Theory Ser. B. 2011. — Vol. 101. — P. 85−110.

15. Balogh J. The speed of hereditary properties of graphs / Balogh J., Bollobas В., Weinreich D. // J. Combin. Theory Ser. B. 2000. — Vol. 79. — P. 131−156.

16. Balogh J. A jump to the Bell number for hereditary graph properties / Balogh J., Bollobas В., Weinreich D. // J. Combin. Theory Ser. B. 2005. — Vol. 95. — P. 29−48.

17. Bandelt H. J. Distance-hereditary graphs / Bandelt H. J., Mulder H. M. // J. Combin. Theory Ser. B. 1986. — Vol. 41. — P. 182−208.

18. Bollobas B. Extremal graph theory. London: Acad. Press, 1978.

19. Bollobas B. Projections of bodies and hereditary properties of hypergraphs / Bollobas B., Thomason A. // Bull. London Math. Soc. 1995. — Vol. 27. P. 417−424.

20. 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.

21. 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.

22. Cayley A. A theorem on trees // Quart. J. Math. 1889. — Vol. 23. — P. 376−378.

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

24. Courcelle B. Handle-rewriting hypergraphs grammars / Courcelle B., Engelfriet J., Rozenberg G. // J. Comput. System Sci. 1993. — Vol. 46. P. 218−270.

25. Courcelle B. Upper bounds to the clique width of graphs / Courcelle B., Olariu S. // Discrete Appl. Math. 2000. — Vol. 101. — P. 77−114.

26. Damaschke P. Induced subgraphs and well-quasi-ordering //J. Graph Theory- 1990. Vol. 14. — P. 427−435.

27. Ding G. Subgraphs and Well-Quasi-Ordering //J. Graph Theory 1992. -Vol. 16. — P. 489−502.

28. 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.

29. 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.

30. 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.

31. 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.

32. Higman G. Ordering by divisibility of abstract algebras // Proc. London Math. Soc. 1952. — Vol. 2. — P. 326−336.

33. 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.

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

35. 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.

36. Kloks T. Ki^-iiee and W4-free graphs // Information Processing Letters -1996. Vol. 60. — P. 221−223.

37. Kloks T. Treewidth of chordal bipartite graphs / Kloks T., Kratsch D. // J. Algorithms 1995. — Vol. 19. — P. 266−281.

38. 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.

39. Kuhn D. Induced subdivisions in KSiS-free graphs of large average degree / Kuhn D., Osthus D. // Combinatorica. 2004. — Vol. 24(2). — P. 287−304.

40. 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.

41. 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).

42. 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.

43. Lozin V. V. Chordal bipartite graphs of bounded treeand clique-width / Lozin V. V., Rautenbach D. // Discrete Mathematics. 2004. — Vol. 283. -P. 151−158.

44. Promel H. J. Excluding induced subgraphs: quadrilaterals / Promel H. J., Steger A. // Random Structures Algorithms. 1991. — Vol. 2. — P. 55−71.

45. Promel H. J. Excluding induced subgraphs III: a general asymptotic / Promel H. J., Steger A. // Random Structures Algorithms. 1992. — Vol. 3. — P. 19−31.

46. Promel H. J. Excluding induced subgraphs II: extremal graphs / Promel H. J., Steger A. // Discrete Appl. Math. 1993. — Vol. 44. — P. 283−294.

47. Robertson N. Graph Minors. XX. Wagner’s conjecture / Robertson N., Seymour P. D. // J. Combin. Theory Ser. B. 2004. — Vol. 92. — P. 325−357.

48. 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.

49. Spinrad J. Bipartite permutation graphs / Spinrad J., Brandstadt A., Stewart L. // Discrete Appl. Math. 1987. — Vol. 18. — P. 279−292.

50. Spinrad J. P. Nonredundant l’s in T-Free Matrice // SIAM Journal on Discrete Mathematics. 1995. — Vol. 8(2). — P. 251−257.

51. 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.

52. 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.