WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 |
Московский государственный университет им. М.В. Ломоносова – механико-математический факультет

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

УДК 519.174.7+519.175.4 Нагаева Светлана Вячеславовна ЭКСТРЕМАЛЬНЫЕ ХАРАКТЕРИСТИКИ ВЛОЖЕНИЙ СЛУЧАЙНЫХ ГРАФОВ В ГЕОМЕТРИЧЕСКИЕ ГРАФЫ 01.01.05 теория вероятностей и математическая статистика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Москва 2009

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

Научный консультант: доктор физико-математических наук, Андрей Михайлович Райгородский

Официальные оппоненты: доктор физико-математических наук, профессор Александр Антонович Сапоженко кандидат физико-математических наук, Роман Григорьевич Степанов

Ведущая организация: Центральный ЭкономикоМатематический Институт

Защита диссертации состоится 29 мая 2009 г. в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при Московском государственном университете им. М.В. Ломоносова по адресу 119991, ГСП1, Москва, Ленинские горы, МГУ, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 28 апреля 2009 г.

Ученый секретарь диссертационного совета Д 501.001.85 при МГУ доктор физико-математических наук, профессор И.Н. Сергеев

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

Актуальность темы.

Настоящая работа посвящена решению ряда задач вероятностной теории случайных графов.

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

По существу, теория случайных графов оформилась в самостоятельную и многоплановую дисциплину на рубеже 50ых и 60ых годов XX века с трудами П. Эрдеша и А. Реньи123. Однако естественная идея вероятностной трактовки науки о графах возникла намного раньше.

Сразу после возникновения теории случайных графов стало ясно, что она имеет не только огромную теоретическую ценность, но также и массу практических приложений. Здесь стоит упомянуть, например, проблематику построения вероятностных алгоритмов на графах и статистический анализ данных в различных "реальных" сетях – социальных, биологических и пр.Сейчас роль вероятности в теории графов несомненна. Достаточно процитировать классические монографии таких выдающихся специалистов в области, как Б. Боллобаш5, Н. Алон и Дж. Спенсер6, С. Янсон, Т. Лучак, А. Ручиньски7, В.Ф. Колчин8 и др.

Одной из важных задач вероятностной теории графов является проблема отыскания в случайном графе подграфов, каждый из которых P. Erds, A.‘Rnyi, On random graphs I, Publ. Math. Debrecen, 6 (1959), 290 - 297.

P. Erds, A. Rnyi, On the evolution of random graphs, Publ. Math. Inst. Hungar.

Acad. Sci., 5 (1960), 17 - 61.

P. Erds, A. Rnyi, On the evolution of random graphs, Bull. Inst. Int. Statist. Tokyo, 38 (1961), 343 - 347.

А.М. Райгородский, Экстремальные задачи теории графов и анализ данных, НИЦ "Регулярная и хаотическая динамика 2009.

B. Bollobs, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

Н. Алон, Дж. Спенсер, Вероятностный метод, Бином: Лаборатория знаний, Москва, 2007.

S. Janson, T. Luczak, A. Rucinski, Random Graphs, Wiley, New York, 2000.

В.Ф. Колчин, Случайные графы, Москва, Физматлит, 2002.

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

Изучение графов расстояний и их хроматических чисел глубоко мотивировано исследованиями в рамках классической проблемы Нелсона – Эрдеша – Хадвигера в комбинаторной геометрии. Эта проблема состоит в отыскании минимального количества цветов, в которые можно так покрасить все точки данного метрического пространства, чтобы между точками одного цвета не было расстояния из фиксированного заранее множества различных положительных вещественных чисел. Такое количество цветов принято называть хроматическим числом метрического пространства с данным множеством запрещенных расстояний.

Проблема Нелсона – Эрдеша – Хадвигера играет заглавную роль в области геометрической комбинаторики. В разное время ею занимались такие крупные специалисты, как Г. Хадвигер9, Д. Ларман и К.А.

Роджерс10, П. Франкл и Р.М. Уилсон11 и др. Эта проблема допускает естественную теоретико-графовую интерпретацию, и потому к ней применяются методы вероятностной теории графов. В самом деле, как показали П. Эрдеш и Н.Г. де Брёйн12, хроматическое число любого метрического пространства совпадает с хроматическим числом некоторого конечного графа расстояний с вершинами в этом пространстве.

Конкретная задача, решаемая в диссертации, основана на идеях П.

H. Hadwiger, Unelste Probleme N 40, Elemente der Math., 16 (1961), 103 - 104.

D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981), 357 - 368.

N.G. de Bruijn, P. Erds, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), N5, 371 - 373.

Эрдеша13 и поставлена в работе А.М. Райгородского14. Интересующая нас вероятностная характеристика – это величина t(d, n, p, ), равная максимальному k, при котором в модели случайного графа G(n, p), предложенной еще Эрдешем и Реньи, с большой вероятностью случайный граф содержит такой индуцированный подграф на k вершинах, что у него хроматическое число не меньше и он изоморфен какомулибо графу расстояний в Rd. Если при всех k вероятность описанного события мала, то величина t(d, n, p, ) полагается равной нулю.

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

Цель работы и основные задачи. Цель исследования в разработке вероятностных методов теории случайных графов и в получении с помощью этих методов достаточно точных оценок величины t(d, n, p, ) при различных соотношениях и зависимостях между параметрами.

Научная новизна.

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

1. При различных соотношениях между аргументами d, n, p, установлено равенство нулю величины t(d, n, p, ) (параграф 1.4).

2. В весьма широкой общности, то есть при практически произвольных значениях аргументов d, n, p, получены новые нетривиальные верхние оценки для величины t(d, n, p, ) (теорема 3).

3. Доказаны новые нижние оценки для величины t(d, n, p, ) в условиях, когда d не зависит от n (теорема 4).

P. Erds, Unsolved Problems, Congress Numerantium XV - Proceedings of the 5th British Comb. Conf. 1975, (1976), 681.

А.М. Райгородский, Проблема Нелсона – Эрдеша – Хадвигера и вложения случайных графов в геометрические, Доклады РАН, 403 (2005), N2, 169 - 171.

4. Показано, что в широком классе ситуаций (например, при постоянных d и p) верхние и нижние оценки из пунктов 2 и 3 совпадают по порядку величины и, стало быть, в указанном классе задача отыскания порядка роста функции t(d, n, p, ) решена полностью (параграф 1.4).

Все результаты диссертации получены соискателем самостоятельно.

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

Теоретическая и практическая значимость полученных результатов. Диссертация носит теоретический характер. Разрабатываемая в ней вероятностная техника может быть полезной при исследовании различных свойств случайных графов, в том числе и тех свойств, которые в конечном итоге важны и для практических приложений (например, речь может идти об оценках сложности тех или иных вероятностных алгоритмов на графах). Кроме того, результаты диссертации могут быть использованы при чтении различных курсов по теории случайных и геометрических графов.

Апробация результатов. Результаты диссертации докладывались на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупанова (Москва, 2007 г.), на Ломоносовских чтениях в Московском государственном университете (2006 г.), а также на кафедральном семинаре кафедры математической статистики и случайных процессов механикоматематического факультета МГУ, на семинаре професора Б.М. Гуревича в МГУ (2008 г.), на семинаре профессора С.В. Конягина в МГУ (2008 г.), неоднократно на семинарах доктора физико-математических наук А.М. Райгородского в МГУ (2005-2009 гг.), на семинаре доктора физико-математических наук А.М. Райгородского на факультете инноваций и высоких технологий Московского физико-технического института (2009 г.), на семинаре профессора А.А. Сапоженко на факультете Вычислительной математики и кибернетики МГУ (2009 г.) и семинаре в Центральном Экономико-Математическом Институте (2009 г.).

Публикации. Результаты диссертации опубликованы в четырех работах. Список этих работ приведен в конце автореферата.

Структура и объем диссертации В диссертации имеется введение, общая характеристика работы, три главы, список литературы.

Полный объем 64 страницы, из них 5 страниц занимает список литературы (40 наименований).

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

В параграфе 1.1 вводится модель Эрдеша – Реньи случайного графа, которую принято обозначать G(n, p). Говоря кратко, G(n, p) = (n, Bn, Pn)это (конечное) вероятностное пространство, в котором элементарные события суть все возможные графы на n вершинах без петель, кратных ребер и ориентации, алгебра событий представляет собой совокупность всех наборов графов из n, а вероятность отдельного графа G = (V, E) ищется по формуле n Pn(G) = p|E|(1 - p)C -|E|.

Иными словами, каждое ребро из потенциальных Cn ребер, которые могли бы возникнуть на данных n вершинах (то есть на множестве V ), принадлежит случайному графу с вероятностью p независимо от остальных ребер.

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

Наконец, формулируется пример классического утверждения о вложении фиксированного графа в случайный граф.

В параграфе 1.2 речь идет об истории проблемы Нелсона – Эрдеша – Хадвигера в комбинаторной геометрии, а также дается теоретикографовая интерпретация этой проблемы. В частности, определяется хроматическое число (Rd), равное минимальному количеству цветов, в которые можно так покрасить все точки пространства, чтобы между одноцветными точками не было расстояния 1. Приводятся оценки хроматического числа пространств Rd при d 4 и при d.

В параграфе 1.3, по существу, дается мотивировка всей дальнейшей деятельности и, собственно, формулируются основные результаты работы. Так, в пункте 1.3.1 определяется основная вероятностная характеристика, изучаемая в диссертации, – величина t(d, n, p, ). А именно сперва вводится событие Qk, k = 1,..., n, на пространстве G(n, p), состоящее в том, что в случайном графе G = (V, E) существует такой индуцированный подграф H = (U, F ), у которого |U| = k, (H) и H изоморфен некоторому конечному графу расстояний в Rd (здесь (H) – хроматическое число графа H, то есть минимальное количество цветов, в которые можно так покрасить вершины H, чтобы вершины, соединенные ребром, были разноцветными). И уже затем полагается t(d, n, p,, ) = 0, если {k {1,.., n} : Pn(Qk) }} = ;

= max{k {1,.., n} : Pn(Qk) }, иначе.

В конечном итоге рассматривается t(d, n, p, ) = t(d, n, p,, 0.5). Замена произвольного на конкретное 0.5 существа дела не меняет.

В том же параграфе 1.3 детально обсуждается смысл и значимость указанного определения. В пункте 1.3.2 последовательно перечисляются старые и новые результаты относительно поведения величины t(d, n, p, ).

Из числа старых теорем следует привести теоремы А.М. Райгородского.

Теорема 1. Пусть l = l(n, p) – это любая функция, с которой имеет l l место асимптотическое выражение Cn(1 - p)C 0, n. Тогда t(d, n, p, ) l(Rd).

Теорема 2. Пусть m = m(n) – это некоторая целочисленная функция, удовлетворяющая условиям m {1,..., n}, m при n.

k0 kДля каждого m определим k0 = k0(m) из неравенств Cm 2-C < 1 < k0-k0-Cm 2-C и положим k1 = k0 - 4. Допустим, что для любого m(1+) m = (n) = o(1) выполнено Cn e- 4k 0 при n и что k1(m) d+2 = d(n)+2. Тогда t d, n,, d m, где d – самая лучшая известная на сегодняшний день нижняя оценка величины (Rd) Однако основными теоремами являются теоремы 3 и 4, принадлежащие соискателю:

Теорема 3. Пусть при n выполнено: d(n) = const или d(n).

Тогда для любого > 0 существует N, такое, что при всех n > N и 3·0,99 либо при любых, d и p <, либо при любых, d 10 и p 16 имеем: если 1 d-d (2(d + 2)!) p <, d (1 + )(d + 2)8+ ln n то 1 d+d 2(d + 2)! t(d, n, p, ) ;

(d + 2)4 p если же 1 d-d (2(d + 2)!) p, d (1 + )(d + 2)8+ ln n то (d + 2)8 ln n t(d, n, p, ) (1 + ).

pТеорема 4. Пусть функция вероятности ребра p такова, что pn и (1 - p)n для любого фиксированного > 0. Тогда, каковы бы ни были заданные наперед d, (Rd) и, найдется n0, начиная с ln n которого при всех n выполнена оценка t(d, n, p, ) 2(1 - ).

Pages:     || 2 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»