автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Функция неплотности и обобщенные числа Рамсея

На правах рукописи

°Г5 ОД

Полякова Ольга Павловна _ ( ;АС

■ - >".Аг ¿иии

Функция неплотности и обобщенные числа

Рамсея.

05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ярославль, 2000 г.

'

Работа выполнена на кафедре математической кибернетики математического факультета Ярославского государственного университета имени П.Г. Демидова.

Научный руководитель — кандидат физико-математических

наук, доцент Дольников В.Л.

Официальные оппоненты —■ доктор физико-математических

наук, профессор Тимофеев Е.А.

Ведущая организация— Российский университет Дружбы

народов

Защита диссертации состоится '¿V " марта 2000 г. в 15_ часов на заседании диссертационного совета К 064.12.04 в Ярославском государственном университете им. П.Г. Демидова по адресу: 150000, г. Ярославль, ул. Советская, д. 14.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им П.Г. Демидова по адресу: 150000, Ярославль, ул. Кирова, 8/10.

Автореферат разослан «.25 » февраля 2000 г.

Ученый секретарь диссертационного

совета, кандидат физико-математических

наук, доцент Пендюр А.Д.

кандидат физико-математических наук, старший научный сотрудник Ломазова И. А.

Общая характеристика работы

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

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

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

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

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

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

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

3Van dor Waerden B.L.Beweis einer Baiidelschen Vermutung. // Nitmw Arch. Wisk., 1927, 15, p. 212-216.

Typeset, by Лд^-ТеХ

направлений в комбинаторике и теории чисел4,5,6.

Первые работы в области рамсеевской теории графов были посвящены методам вычисления некоторых значений классических чисел Рамсея Н(т, п), то есть минимального числа N = П(т, п), такого что для каждого графа О с Лт вершинами либо его плотность у (С?) > т, либо число независимости е(С) > п. В настоящий момент эта задача решена для малых значений т и п, но из проводимых исследований выросла отдельная самостоятельная дисциплина.

Хватал и Харари7 предложили рассматривать обобщенные числа Рамсея Н(С,Н), где И(С,Н) - это минимальное N такое, что для любой раскраски ребер полного Лг— вершинного графа К^ в два цвета обязательно существует либо синий подграф, изоморфный С, либо красный подграф, изоморфный Н . Тогда, очевидно, что ЩК т,Кп) — Д(т,п). Число Л(Сг. Н^ легко определить, только если один из графов (5 или Н является разреженным графом. Так, например,

(1) Д(Тт, Кп) = (т — 1 )(п - 1) 4-1, где Тт - это дерево на т вершинах;5

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

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

5Szemercdi E. On sets of integers containing no k elements in arithmetic progression jj Acta. Arith., 1975, 27, p. 199-245.

"'Nesetril J. , Rodl V. Partition theory and its applications // Surveys in Combinatorics, Cambridge: Cambridge University Press, 1979, p. 9(1-156.

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

feChvatal V. Three-complete graph Ramsey numbers // J. Grapli Theory, 1977, 1, p.93

НИКОВ.9

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

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

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

В работах Дольникова12,13 под влиянием определения Хадвигера- Дебруннера были введены определения {p. q) — свойства для графов и гпперграфов:

Граф G обладает (р, q)—свойством ( G G Lp,q ), если каждый его подграф на р вершинах содержит пустой подграф на q вершинах, конечно р > q и n(G) > р;

а также дано определение функции неплотности, обобщающей понятие полноты графа:

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

Для конечного графа G функция p(q, G) определена при всех q < e(G) и неопределена при q > e(G) (здесь б(С?)

- Burr S.A., Krdös P., Spencer J.II .Ramsey theorems for multiple copies of graphs //Trans.Amer. Math. Soc., 1975, 209, p. 87-99.

10Neset.ril J. Ramsey theory // Handbook of combinatorics, Elsevier Science B.V., 1995, p. 133:5-1403.

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

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

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

- число независимости графа). Очевидно, что p(2,G) = 95(G) + 1 и для пустого графа p(q, G) = q.

Понятие функции неплотности тесно связано с теоремой Рамсея. Легко видеть, что теорему Рамсея можно в этих терминах переформулировать следующим образом Предложение. Для любых натуральных q, $ > 2

sup p(q, G) = N(q. 5, 2) < 00,

GGLs/j

где N(q,s,2)— ■числа Рамсея.

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

В работе Стечкина и Франкля16, исследовались к— графы Gk, обладающие (р, г/)—свойством. В частности было доказано, что если для таких графов р < — 1),

то минимальное число ребер

fn-P + (l\ mmm(G ) = I I.

14 Копылов Г.II. Обобщение теоремы rJ'урана // Математические заметки, 1979, т.20, №4, с. 593-602.

15Tur;m Р. Еду grafelmeleti szelsoertek fcladatrol j/ Mat. Fiz. Larok, 1941, 48, p. 436-452.

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

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

Цель работы. Исследование поведения функции неплотности, се свойств. Алгоритм нахождения этой функции. Получение оценок для обобщенных чисел Рамсея различных классов графов.

Методы исследования. В диссертации использованы методы теории графов, а также различные комбинаторные методы.

Научная новизна. Все основные результаты диссертации являются новыми и состоят в следующем:

1. Доказаны точные формулы для функции неплотности объединения и соединения графов. Получены оценки функции неплотности при других операциях над графами: декартовом произведении, конъюнкции и нормальном произведении.

2. Даны некоторые оценки функции неплотности если известно ее значение в точке.

3. Доказаны оценки функции неплотности через различные характеристики графа.

4. Получены оценки обобщенных чисел Рамсея для классов реберных к обыкновенным графам и муль-тиграфам( в некоторых случаях точные), а также

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

18Варапо» В.П., Стечкин Т5.С. Экстремальные комбинаторные задачи, и их приложения, М.: Наука, 1989, 159 с.

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

для тотальных графов и графов пересечений геометрических множеств.

5. Доказаны теоремы, характеризующие структуру графа, если известно предельное поведение его функции неплотности.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты могут быть полезны специалистам по теории графов и комбинаторной геометрии.

Апробация. Содержащиеся в диссертации результаты докладывались на III М е ж ду нар одной конференции ''Дискретные модели в теории управляющих систем" (МГУ) в 1998 году, на VI Межгосударственном семинаре "Дискретная математика и ее приложения"(МГУ) в 1998 году, на XII Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород) в 1999 году, а также на научных конференциях Ярославского госуниверситета в 97-99 годах.

Публикации. Основные результаты диссертации опубликованы в работах, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения и трех глав, разбитых на 9 параграфов. Текст диссертации изложен на 88 страницах. Список литературы содержит 51 наименование.

Содержание диссертации

Введение. Во введении дается краткий обзор результатов, относящихся к теме диссертации и излагается основное содержание работы.

Первая глава посвящена изучению функции неплотности графа.

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

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

Теорема 1.2.3. Граф G двудолен тогда и только тогда, когда

p(q,G)<2q- 1.

Далее доказывается ряд теорем, характеризующих структуру графа, если известно предельное поведение его функции неплотности.

(

Теорема 1.2.2. Если lim --- < /с для графа G. то

q—> со q

множество его вершин V можно разбить на две такие части V\ и V-2, что | Ух |< ос и f(G2) < к — 1 для подграфа G2 ни множестве \2.

Из теоремы 1.2.2 получаем следующую характериза-шно некоторого класса графов.

Следствие. Множество вершин V графа G можно разбить на две такие части v\ и V2, что V\ - конечное множество, а V2 - независимое множество тогда и только тогда,

— p(q,G) ^

когда lim - < z.

q-¥ со q

Теорема 1.2.4. Вершины V графа G можно разбить на две такие части \\ п V~2, что V*i - конечное множество, а подграф G>, на множестве V2 - двудольный, тогда н только тогда, когда p(q, G) < 2q+k для всех q п некоторого к.

Следующая теорема характеризует графы по поведению функции неплотности в точке.

Теорема 1.2.5. Если p(q -f 1, G) — p(q, G) + к, то множество вершин V графа G можно разбить на две такие части Vi и V2. что | Vi |< оо и <f(G2) < к для подграфа G2 на, множестве Vj.

Третий параграф первой главы описывает алгоритм для нахождения функции плотности графа. Задача нахождения значения функции плотности является NP-полнон, так как, в частности, включает в себя задачу нахождения числа независимости графа. Для этой цели в работе предложено обобщение известного алгоритма Магу. На каждом шаге находится минимальная д.н.ф. для разных булевых функций. Поэтому особое значение приобретает организация вычислений, позволяющая учитывать вычисления на предыдущем ша,ге, а значит как-то уменьшить трудоемкость алгоритма.

Вторая глава посвящена различным оценкам функции неплотности. В первом параграфе второй главы исследуется поведение функции неплотности, если известно ее значение в некоторой точке. Первый результат в этом направлении был получен в работе20.

Сформулируем основной результат этого параграфа.

Теорема 2.1.1.

(1) Если p(q,G) <2q-l, Top(q + t,G) < R(q + t,3,2), где t > 1, q > 2, и R{q + t, 3,2) - число Рамсея.

(2) Если p(q. G) < 2q + k, Top(q + t,G) < R{q + t, 3,2) + 3к + 2, где t > 1, q > 2, 0<k<q-l 11 R(q + t, 3,2) - число Рамсея.

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

При доказательстве теоремы 2.1.1 используется ряд лемм.

Лемма 2.1.2. Если граф G обладает (p,q)— свойством и его подграф Gi на гц вершинах имеет неплотность 1) < к, то подграф Go = G\G 1 обладает {р — п\ ,q — к) — свойством.

Лемма 2.1.3. Если p(q, G\Kn) < Pi, то p(q, (?) < pi + п.

Лемма 2.1.4. Если ^(G) < 4 я в графе G каждые к (к > 2) треугольников имеют общую вершину, то из множества вершин графа можно выкинуть 3 к — 1 та к. что останется граф без треугольников.

В данном параграфе приводятся и некоторые другие, полученные в этом направлении, результаты.

Теорема 2.1.9. Если p{q,G) <2q- 1, то

1) p(q+l,G) <2q + 2, rAe2<q<6;

2) p{q + 1, G) < 3<7 - 4, где q > 7;

3) p(q + 2, G) < max{2q + 7, 3q~ 2}, где q > 2;

Теорема. 2.1.11. Если p(q,G) < 2q, то

p{q+l,G) <max{2g + 8, 3g - 2, R{q + 1,3,2)}.

где Н(д + 1, 3, 2) - число Рамсея.

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

Теорема 2.2.1. Для любого графа &' порядки п

Р(.Я, G) > V

1

(й) ■ to - 1 + dXl + -~ + d;

г +

\q-2J

+ q- 1, где. dX{ - степень вершины х

Теорема 2.2.2. Пусть С— обыкновенный граф с п вершинами и гп ребрами. Тогда

(1) Если

2т

п <

то

(2)

причем равенство достигается, если каждая компонента связности графа С? является кликой одного и того же размера; если

2т

п >

то

2т

О) > п + 1

(х/у-Т + \ftT-2')2 '

равенство достигается при 3 < с/ < 6, если каждая компонента связности графа С является кликой одного и того же размера.

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

Следующая теорема устанавливает точное значение для функции неплотности объединения и соединения графов.

Теорема 2.3.1.

11 п

(1) = + г=1 г=1

п п

(2) р(9, У СО = шах -«+!}•

Для функции неплотности декартова произведения графов доказана следующая оценка:

Теорема 2.3.2. р{<1, х С2) < (д - 1)(тах{тг(?,<3,1),р(д,С2)} - 1) + 1.

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

Определение. Граф (7 обладает (р, д, п)—свойством, если какие бы п подграфов Ст\ ... С'п таких что —

р ни взять, найдется такой набор независимых множеств V = \ \ ... Уп, что

п

1^1 > Ч, V, С Сп и К- П V, = 0.

Суммарной функцией неплотности р(д,гг,Ст) называется минимальное р такое, что граф Ст обладает (р, q^n)— свойством.

Теорема 2.3.3.

р^, С х Кп) = п, С).

Для функции неплотности декартова произведения произвольног о графа на полный доказаны следующие оценки:

Теорема 2.3.4.

1 )p(q, G X Kn) < np(q, G) - n -f 1;

2)p(q, G x Kn) < np(q, G) - 2n + 1, earn G) > q + 1;

3)p(q, G X Kn) = n{q - 1) + 1, если ,\'(G) < n.

Для функции неплотности конъюнкции двух графов получен следующий результат.

Теорема 2.3.5.

p(g,Gi&G2) < (g- l)(min{p(fLGa),p(g,G,)} - 1) + 1.

Следующее неравенство дает оценку функции неплотности нормального произведения графов.

Теорема 2.3.6.

pO?,GbG2) < (p(q,Gi) - 1 )(p(q,G2) - 1) + 1.

В качестве примера для функции неплотности нормального произведения произвольного графа G на полный граф Кп приведена следующая оценка:

Теорема 2.3.7.

p{qiG.Kn)=n{p(q, G)-l) + l.

Третья глава посвящена изучению обобщенных чисел Рамсея различных классов графов: реберных и тотальных к обыкновенным графам и мультиграфам, графов пересечений геометрических множеств.

В первом параграфе третьей главы приведены оценки чисел Рамсея для класса реберных графов. Наиболее сильные результаты получены для класса реберных к обыкновенным графам.

Теорема 3.1.1.

(1) М(д,з,2-,Ь1)<з(г1-1) + 1]

(2) ЛГ(д,5,2;2а)>5($-1)-г + 1, з = 2* + 1, * > 1, д = Ы + 1 + г, гё2и0<г<4-1, в частности, Лг(<?, з, 2; ¿1) — й(«7 — 1) + 1 при г = 0;

(3) N(<7,з,2;¿1) > 5(^-1)-г - +1, з = 2<, I > 1, д = Ы + г + 1, г, г € 2 и 0 < г < < - 1;

(4) = + д< ;

(5) ЛГ(9,3,2;Х,)=[|(9-1)]+1.

Для чисел Рамсея класса реберных к мультиграфам доказаны следующие оценки:

Теорема 3.1.3.

(1) тУ((/.з,2;Ь2) < ([§(* - 1)] - 1)(9- 1) + 1, з > 5

(2) 2; ¿2) > (з - 1)(д - 1) + <-Ч(«-г-1) + в = 21-1. Ь>2. д = 2к + 1 + г, г, к <Е 2 и 0 < г < 1;

(3) ДГ(д,з,2; Ь2) > (з - 1)(з - 1) + ('-Ы'-г-Ъ + 1, 5 = 2£, ^ > 1, д = 2к + г + 1, г, к ЕЪ п [) <г < 1;

(4) Л^,4,2;1,2)<4д-3;

(5) Д%3,2;Ь2)= [|(д-1)] + 1.

Теорема 3.3.4. Для класса реберных к двудольным мультиграфам Ь'2

Во втором параграфе получены следующие оценки для чисел Рамсея тотальных графов.

Теорема 3.2.1.

(1) з, 2; Ьт) < - 1 + 2 ] - 1) + 1;

(2) ЛГ(д,з,2-,ЬТ) > з(ч - 1) + 1, з = 21 + М > 2, у =

+ г + М, гб2п0<г<1- 1;

(3) ЩьзЛЬт) > (з-1)(д-1)-§(г-[^±1])+г+1, з = 2*, < > 2, д = + г + 1, I, г£%иО<г<г - 1;

(4) ^(д,5,2;Хг) = 5д-4;

(5) Аг(д. 4, 2; ¿г) < 4д — 3, в частности, Лт(у, 4,2; £г) = 4д - 3, при д = 2* + 1.

Для чисел: Рамсея класса Ьтм тотальных к мульти-графам даны следующие оценки:

Теорема 3.2.2.

(1) Ьтм) < [§5 - 3] (д - 1) + 1, > 6;

(2) Щ^з,2]1тм)>з(д-1)+1, з> 5;

Третий параграф этой главы посвящен получению оценок для чисел Рамсея графов пересечений геометрических множеств.

Обозначим через Ь]1 - класс графов пересечения семейств кубов в К", через Ь™ - семейств равных кубов в К." и через 1з - класс графов пересечения семейств параллелотопов в Кп. Во всех семействах кубы и параллелотопы с соответственно параллельными ребрами.

Теорема 3.3.1.

(1) Щд, з, 2; < 2"(з - 2)(д - 2) + з + д - 2 ;

(2) Дг(д, з, 2; Ц) < 2п~: (з - 2)(д - 2) + з + д - 2 ;

(3) Щз, д, 2; Ц) < ((з - 1) 1о§Г> - 1) + п-

-0.5(3-1)1оёГ1Й-1)Н9-1) + 1-

Теорема 3.3.2. Аг(д, з, 2; Ь\) = (з - 1)(д - 1) + 1.

Теорема 3.3.3. Для класса Ь\ графов пересечении дуг на окружности

N(</,3,2;^) < (з-1)д и К(д, 3,2; Ь\) < 2д.

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

Публикации автора по теме диссертации

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

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

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

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

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

-МГУ, 199S. - с. 29-31. ( Дольниковым В.Л. была поставлена задачи., а все результаты этой работы получены Поляковой О.П. самостоятельно. )

G. Дольников B.JL, Полякова О.П. Функция неплотности и обобщенные числа Рамсея // Дискретная математика. - 1998. - том 10, вып.З. - с.84-99. (Поляковой О.П. принадлежат теоремы 3; 4, 6-8).

7. Полякова О.П. Поведение функции неплотности при операциях над графами // Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 17-22 мая 1999 г.). Часть II. /Под редакцией О.Б. Лупа-нова. - М.: Изд. мех.-мат. факультета МГУ, 1999. -с. 188.

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

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

Введение

Глава 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 параграфов.

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.