Функция неплотности и обобщенные числа Рамсея тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Полякова, Ольга Павловна

• Полякова, Ольга Павловна
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Полякова, Ольга Павловна

Введение

Глава 1. Функция неплотности графа

1.1. Основные определения 15 1.2 Характеризация графов с помощью функции неплотности 19 1.3. Алгоритм нахождения функции плотности

Глава 2. Различные оценки функции неплотности 27 2.1.0 росте функции неплотности графа

2.2. Оценки функции неплотности

2.3. Поведение функции неплотности при операциях над графами

Глава 3. Оценки обобщенных чисел Рамсея различных классов 65 графов

3.1 Оценки чисел Рамсея рёберных графов

3.2 Оценки чисел Рамсея тотальных графов

3.3 Числа Рамсея графов пересечений геометрических множеств 79 Литература

Введение диссертации (часть автореферата) на тему «Функция неплотности и обобщенные числа Рамсея»

В 1930 году Рамсеем [1] была доказана теорема в области математической логики, которая положила начало теории, названной его именем. В общем виде основное положение этой теории можно сформулировать так:

Если число объектов в совокупности достаточно велико и каждые к объектов связывает одно из набора отношений, то всегда существует подмножество данной совокупности содержащее заданное число объектов, и при этом такое, что в нем все объекты связаны отношением одного типа.

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

Впоследствии теорему Рамсея переоткрыли Эрдёш и Секереш [2] рассмотрев такую геометрическую задачу: если даны п точек.на плоскости в общем положении, то среди них всегда можно найти /г.точек, образующих выпуклый к—угольник.

Значительная часть ранних исследований по теории Рамсея была посвящена множествам точек и линий, но все же во многих из них рассматривались и множества чисел. Б.Л. Ван дер Варден начал решать задачи такого типа еще до того, как Рамсей доказал свою теорему. Теорема Ван дер Вардена [3] впоследствии породила целый ряд направлений в комбинаторике и теории чисел ( см. [4] -[6]).

Первые работы в области рамсеевской теории графов были посвящены методам вычисления некоторых значений классических чисел Рамсея R(m,n), то есть минимального числа N = R(m,n), такого что для каждого графа G с N вершинами либо его плотность (f(G) > m,

Typeset by Дд^-ТеХ либо число независимости е(&) > п. В настоящий момент эта задача решена для малых значений т и п, но из проводимых исследований выросла отдельная самостоятельная дисциплина.

Хватал и Харари [49] предложили рассматривать обобщенные числа Рамсея К{Сг,Н), где Я(С,Н) - это минимальное N такое, что для любой раскраски ребер полного М— вершинного графа К^ в два цвета обязательно существует либо синий подграф, изоморфный (9, либо красный подграф, изоморфный Н. Тогда, очевидно, что Н(Кт,Кп) = Н(т,п). Число ЩО,Н) легко определить, только если один из графов О или Н является разреженным графом. Так, например,

1) 11(Тт,Кп) = (то - 1)(п — 1) + 1, здесь Тт - это дерево на то вершинах;

2) Я(п * К3,п * А'з) = 5п для п > 2, здесь п * объединение не пересекающихся по вершинам п треугольников.

Наиболее полный обзор результатов, полученных в данном направлении, дан Я. Нешетрилем [7].

Следующим этапом в развитии обсуждаемой проблематики можно считать работу Хадвигера и Дебруннера [8]. В этой работе для семейств выпуклых множеств было дано определение (р,д) — свойства:

Будем говорить, что семейство множеств, состоящее из р или более множеств, обладает (р, д)—свойством, где р > д, если в каждом его подсемействе из р множеств содержится д множеств с непустым пересечением.

В работах Дольникова [9], [10] под влиянием определения Хадвигера - Дебруннера были введены определения (р, д)—свойства для графов и гиперграфов:

Граф £ обладает (р, д)—свойством ( О £ ), если каждый его подграф на р вершинах содержит пустой подграф на q вершинах, конечно р > q и n(G) > р\ а также дано определение функции неплотности, обобщающей понятие полноты графа:

Пусть p(q,G) - наименьшее из таких чисел р, что граф G € Lp^q (q > 2). Функцию p(q,G) назовем функцией неплотности графа G.

Для конечного графа G функция p(q,G) определена при всех q < б(G) и неопределена при q > t(G) (здесь e(G) - число независимости графа). Очевидно, чтор(2,(?) = <p(G) + l, где cp(G)— плотность графа, и для пустого графа p(q, G) = q.

Понятие функции неплотности тесно связано с теоремой Рамсея. Легко видеть, что теорему Рамсея можно в этих терминах переформулировать следующим образом Предложение. Для любых натуральных q, s > 2 sup p(q, G) = N(q, s, 2) < oo, где N(q, 5, 2) — числа Рамсея. GeLSi2

В работе Копылова [11], где рассматривался следующий вопрос: какое максимальное число ребер может иметь п—вершинный граф, обладающий (р, д)—свойством. В случае q = 2 (p,q)— свойство эквивалентно тому, что граф не содержит полного подграфа с р вершинами. В этом случае максимальное число ребер было определено Тураном [12]. В статье результат Турана обобщается на случай произвольного q. Также были получены оценки максимального числа ребер для п—вершинного графа с заданной функцией неплотности.

В работе Стечкина и Франкля [13] исследовались А;-графы Gk, обладающие (р, q) — свойством. В частности было доказано, что если для таких графов р < — 1), то минимальное число ребер п — р (¡\ тшт(СА) = ( у ).

Функция неплотности является мало исследованной характеристикой графов несмотря на то, что определение (р, д)—свойства приведено уже во многих книгах ( см., например, [14] - [16]). Эта величина обобщает число независимости и тесно связана с теоремой Рамсея. Основная цель настоящей работы дальнейшее изучение функции неплотности графов, ее свойств, а также получение оценок для обобщенных чисел Рамсея различных классов графов.

Диссертация состоит из введения и трех глав, разбитых на 9 параграфов.

Список литературы диссертационного исследования кандидат физико-математических наук Полякова, Ольга Павловна, 2000 год

1. Ramsey F.P. On a problem for formal logic // Proc. London Math. Soc. - 1930. - 30. - p. 264-286.

2. Erdos P., Szekeres D. A combinatorial problem in geometry // Compos. Math.- 1935. 2. - p. 463-470.

3. Van der Waerden B.L.Beweis einer Baudetschen Vermutung. // Nieuw Arch. Wisk. 1927. - 15. - p. 212-216.

4. Hales A.W., Jewett R.I. Regularity and positional games // Trans. Amer. Math. Soc. 1963. - 106. - p. 222-229.

5. Szemeredi E. On sets of integers containing no к elements in arithmetic progression // Acta. Arith. 1975. - 27. - p. 199-245.

6. Nesetril J. , Rodl V. Partition theory and its applications // Surveys in Combinatorics. Cambridge: Cambridge University Press. -1979. - p. 96-156.

7. Nesetril J. Ramsey theory // Handbook of combinatorics. Elsevier Science. - 1995. - p. 1333-1403

8. Хадвигер Г., Дебруннер Г. Комбинаторная геометрия на плоскости М.: Наука, 1965. - 171 с.

9. Дольников В.Л. Об одной задаче окрашивания // Сиб. матем. ж. 1972. - XIII, №6. - с. 1272 - 1283.

10. Дольников В.Л. Об одном обобщении теоремы Рамсея // ДАН СССР. 1977. - 232, №6. - с. 1241 - 1244.

11. Копылов Г.Н. Обобщение теоремы Турана // Математические заметки. 1979. - т.26, №4. - с. 593-602.

12. Turan P. Еду grafelmeleti szelsoertek feladatrol // Mat. Fiz. Larok. 1941. - 48. - p. 436-452.

13. Стечкин B.C., Франкл П. Локалъно-турановское свойство дляк— графов // Математические заметки. 1981. - т.29, №1. -с. 83-94.

14. Комбинаторный анализ задачи и упражнения / Под редакцией К.А. Рыбникова. - М.: Наука, 1976. - 368 с.

15. Баранов В.П., Стечкин B.C. Экстремальные комбинаторные задачи и их приложения М.: Наука, 1989. - 159 с.

16. Зыков A.A. Основы теории графов М.: Наука, 1987. - 381 с.

17. Ecknoff J. Helly, Radon and Caratheodory Type Theorems. //Handbook of convex geometry / Gruber P.M., Wills J.M. Ed. Elsevier Science Publishers B.V. - 1993. - p. 389 - 448.

18. Alón N., Kleitman D.J. Piercing convex sets and Hadviger- Debrun-ner (p, q) — problem //Bull. Amer. Math. Soc. 1992. - 27, №2. - p. 252 - 256.

19. Харари Ф. Теория графов M.: Мир, 1973. - 300 с.

20. Емеличев Е.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. - 385 с.

21. Дольников B.JL, Полякова О.П. Функция неплотности графа и числа Рамсея различных классов графов // Дискретный анализ и исследование операций. 1997. - №4. - с. 102 - 103.

22. Грэхем Р. Начала теории Рамсея М.: Мир, 1984. - 97 с.

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

24. Maghout К. Applications de Г Algebre de Boole a la Theorie des Graphes// Cahiers du Centre d'Etudes de Recherche Opérationnelle. Bruxelles 5. - 1963. - №1-2. - p. 21.

25. Васильев Ю.Л., Ветухновский Ф.Я., Глаголев В.В., Журавлев Ю.И., Левенштейн В.П., Яблонский C.B. Дискретная математика и математические вопросы кибернетики, т.1 М.: Наука, 1974. - 311 с.

26. Кофман А. Введение в прикладную комбинаторику М.: Наука, 1975. - 479 с.

27. Erdôs P., Hajnal A. Problem 3, р. 362, Theory of graphs // Proceed-igs of the Colloquium held at Tihany, Hungary, September 1966, /edited by Erdôs P. and Katona G. Budapest : Akademial Kiado, 1968.

28. Дольников B.JI., Полякова О.П. О росте функции неплотности графа //Труды III международной конференции "Дискретные модели в теории управляющих систем" (22-27 июня 1998). М.: Диалог -МГУ, 1998. - с. 29-31.

29. Полякова О.П. Характеризация графов с помощью функции неплотности // Современные проблемы математики и информатики. Ярославль : Изд. Яросл.гос.ун-та, 1997. - с.6-13.

30. Ope О. Теория графов М.: Наука, 1980. - 336 с.

31. Дольников В.Л., Полякова О.П. Функция неплотности и обобщенные числа Рамсея // Дискретная математика. 1998. -том 10, вып.З. - с.84-99.

32. Полякова О.П. Поведение функции неплотности при операциях над графами //Современные проблемы математики и информатики. Вып. 2. Сборник научных трудов молодых ученых,аспирантов и студентов. Ярославль : Изд. Яросл.гос.ун-та, 1999. - с. 24-30.

33. Berge. С. Graphs and Hypergraphes North-Holland Publ. Co., 1973. - 528 p.

34. Дольников B.JI., Полякова О.П. Оценки чисел Рамсел для некоторых классов графов // Современные проблемы естествознания. Математика. Информатика. Ярославль : Изд. Яросл. гос. ун-та, 1997. - с.5-8.

35. Дольников В.Л., Полякова О.П. Функция неплотности и обобщенные числа Рамсея // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов", Выпуск II. М.: Изд. МГУ, 1998. - с.95-97.

36. Полякова О.П. Оценки чисел Рамсея рёберных графов // Современные проблемы естествознания. Математика: сборник тезисов областной научной конференции студентов, аспирантов и молодых ученых. Ярославль: Изд. Яросл.гос.ун-та, 1999. -с. 16-17.

37. Косточка A.B. Одно применение веера Визинга //Комбинаторный анализ. 1983. - Вып.6. - с. 68-69.

38. Тараканов В.Е. О реберном числе независимости и числе покрытия для регулярных графов //Дискретная математика. -1990. том 2, вып.1. - с.16-25.

39. Bosak J. Chromatic index of finite and infinite graphs // Czechosl. Mat. J. 1972. - №2, 22. - p. 272-290.

40. Визинг В.Г. Хроматический класс мулътиграфа // Кибернетика. 1965. - №3. - с.29-39.

41. Chetwynd A.G., Hilton A.G., Zhao Cheng N. The total chromaticnumber of graphs of high minimum degree j J J. London Math. Soc. 1991. -44, №. - p. 193 - 202.

42. Vijayditya N. On total chromatic number of a graph // J.London Math.Soc. 1971. - 3, №3. - p. 405-408.

43. Визинг В.Г .Оценка числа внешней устойчивости гра фа // ДАН СССР. 1965. - 164, №4. - с. 729 - 731.

44. Косточка А.В. Точная верхняя оценка тотального хроматического числа мулътиграфов// "24 Int. Wiss. Kolloq., Ilmenau, 22 okt. 26 okt., 1979, Helf 5 Vortragsreine B2, B3", Ilmenau, s.a. -33-36. №2. - p. 161-162.

45. Kostochka A.V. The total chromatic number of any multigraph with maximum degree five is at most seven //Discrete Mathematics. -1996. 162, №1-3. - p. 199-214.

46. Fon-Der-Flaas D.G., Kostochka A.V. Covering boxes by points // Discrete Mathematics. 1993. - 120. - p. 269 - 275.

47. Дольников В.JI. О разбиении семейств выпуклых тел // Сиб. матем. ж. 1971. - XII, №3. - с. 664 - 667.

48. Chvatal V., Harary F. Generalized Ramsey theory for graphs III: Small off-diagonal numbers // Pacific J. Math. 1972. - 41. - p. 335 -345.

49. Chvatal V. Three-complete graph Ramsey numbers //J. Graph Theory. 1977. - 1. - p.93.

50. Burr S.A., Erdos P., Spencer 3.В.Ramsey theorems for multiple copies of graphs //Trans.Amer. Math. Soc. 1975. - 209. -p. 87-99.