Функция неплотности и обобщенные числа Рамсея Полякова Ольга Павловна

Введение к работе

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

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

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

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

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

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

³Van dor Waerden B.L. Bcweis einer Baudelschen Vermutung. // Nieuw Arch. Wisk., 1927, 15. p. 212-216.

Typeset by Лд^-ТеХ

направлений в комбинаторике и теории чисел⁴,⁵,⁶.

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

Хватал и Харари⁷ предложили рассматривать обобщенные числа Рамсея R(G,H), где R(G,H) - это минимальное N такое, что для любой раскраски ребер полного А^г— вершинного графа К^ в два цвета обязательно существует либо синий подграф, изоморфный G, либо красный подграф, изоморфный Н . Тогда, очевидно, что R(K_m,K_n) = R(m,n). Число R{G₁H) легко определить, только если один из графов G или Н является разреженным графом. Так, например,

1. R(T_m, К_п) = (т - 1)(п - 1) 4-1, где Т_т - это дерево на m вершинах;⁵¹

2. R(n * А'з, п + Kz) = Ъп для п > 2, где п * К₃ объединение не пересекающихся по вершинам п треуголь-

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

⁵Szemercdi E. On sets of integers containing no k elements in arithmetic progression /j 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. 9fi-156.

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

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

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

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

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

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

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

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

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

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

"Burr S.A., Krdos P., Spencer J Лі. Ramsey theorems for multiple copies of graphs //Trans.Amer. Math. Soc, 1975, 209, p. 87-99.

¹⁰Ncsctril J. Ramsey theory // Handbook of combinatorics, Elsevier Science B.V., 1995, p. 1333-1-103.

¹' Ха.двигер I^і., Дебрупнер Г. Комбинаторная геометрия, на плоскости — М.: Наука. 1905, 171 с.

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

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

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

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

sup p(q,G) = N{q,s,2) <оо,

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

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

В работе Стечкина и Франкля¹⁶, исследовались к— графы G^k, обладающие (р, г/)—свойством. В частности было доказано, что если для таких графов р < тАг(

ґґ*к\ fn-p + q

mmm(G ) = (

¹⁴ Копылов Г.II. Обобщение теоремы Турана, // Математические заметки, 1979, т.20, JVM, с. 593-602.

^1,>Turaii Р. Еду grafelmeleti szelsoertek feladatrol // Mat. Fiz. Larok, 1941, 48, p. 436-452.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие диссертации на Функция неплотности и обобщенные числа Рамсея

Разработка и реализация алгоритмов для работы с FLINSPACE конструктивными вещественными числами и алгоритмическими функциями над нимиЯхонтов Сергей Викторович

Проблема суммирования арифметических функций по числам, свободным от k-ых степенейОрлова Светлана Викторовна

Винеровские интегралы в пространстве непрерывньк функций бесконечного числа переменных и иx применениеБилущак, Галина Ивановна

Приближение функций многих переменных комбинациями функций меньшего числа переменныхБабаев, Мелик-Бахыш Али Икрам оглы

О приближении операторами Баскакова функций, имеющих конечное число точек разрыва производныхШерстюк, Татьяна Юрьевна

Нахождение, оценка и сравнение числа бесповторных булевых функций в различных базисахЗубков Олег Владимирович

Синтез алгоритмов цифровой обработки сигналов радио- и оптического диапазонов на основе атомарных функций и теории чиселГоршков, Алексей Станиславович

Неопубликованные материалы Эйлера по аналитической теории чисел : Элементы теории дзета - функции в его записных книжкахГорлова, Виктория Дмитриевна

Применение спектральной теории автоморфных функций к некоторым задачам аналитической теории чисел Быковский Виктор Алексеевич

Представление целых функций рядами экспонент с показателями на конечном числе лучей Иванов Михаил Степанович