Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Ярмухаметов, Андрей Ринатович
01.01.05
Кандидатская
2012
Москва
63 с. : ил.
Стоимость:
499 руб.
Оглавление
Введение
1 История и формулировки результатов
1.1 Основные определения и история задачи
1.2 Постановка основной задачи
1.3 Формулировки результатов
2 О связности случайного дистанционного графа
2.1 Доказательство пункта б) теоремы
2.2 Схема доказательства пункта а) теоремы
2.3 Доказательства утверждений 2.2, 2.3, 2.4, 2
2.3.1 Доказательство утверждения
2.3.2 Доказательство утверждения
2.3.3 Доказательство утверждения
2.3.4 Доказательство утверждения
2.3.5 Доказательство утверждения
3 О распределении количества древесных компонент в случайном дистанционном графе
3.1 Вспомогательные утверждения и леммы
3.1.1 Формулировки вспомогательных утверждений
3.1.2 Доказательство утверждения
3.1.3 Доказательство утверждения
3.1.4 Формулировка и доказательство леммы
3.1.5 Формулировка и доказательство леммы
3.1.6 Доказательство утверждения
3.1.7 Доказательство утверждения
3.1.8 Доказательство утверждения
3.2 Доказательство теоремы
3.2.1 Доказательство пункта 1
3.2.2 Доказательства пунктов 2 и
3.2.3 Доказательство пункта 3
3.2.4 Доказательство пункта
4 О гигантской компоненте в случайном дистанционном графе
4.1 Вспомогательные утверждения и леммы
4.1.1 Формулировки вспомогательных утверждений и лемм
4.1.2 Доказательство утверждения
4.1.3 Доказательство утверждения
4.1.4 Доказательство утверждения
4.1.5 Доказательство утверждения
4.1.6 Доказательство утверждения
4.2 Завершение доказательства пункта б) теоремы
4.3 Доказательство пункта а) теоремы
4.3.1 Ветвящиеся процессы
4.3.2 Завершение доказательства пункта а) теоремы
4.4 О предельной вероятности связности внутри фазового перехода
4.4.1 Доказательство теоремы
Введение
Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике.
Одним из тех, кто первым применил данный метод к задачам экстремальной комбинаторики, был венгерский математик Т. Селе. С помощью вероятностных соображений он доказал, что существует турнир на п вершинах, который содержит не менее п!/2"-1 гамильтоновых путей (1943, [1]). Селе не построил явную конструкцию такого турнира, но показал, что множество турниров, удовлетворяющих данному требованию, не пусто. Это является характерной чертой такого способа доказательств. Именно поэтому этот метод также называется неконструктивным.
Широкое применение метода к теории чисел привело к появлению вероятностной теории чисел ([2] — [3]). Одним из первых применений неконструктивного метода к данной отрасли математики было новое, более простое доказательство теоремы Г. Харди и С. Рамануджана (1917, [4]), принадлежащее П. Турану (1934, [5]).
Примечательно, что примерно в это же время в вычислительной математике стремительно развивается применение статистических методов испытаний, более известных под названием “Метод Монте-Карло” (1949, [6]). Статистические методы вычислений использовались еще в XVIII - XIX вв. Самым широкоизвестным таким методом, в том или ином виде входящем во многие университетские учебники по теории вероятностей, является метод определения числа 7Г с помощью бросания иглы Бюффона (например, [7]).
Наибольшее применение вероятностный метод получил в экстремальной теории множеств, а также в теории графов и гиперграфов. Одним из первых результатов в этих областях была теорема П. Эрдеша, Ч. Ко и Р. Радо (1938, [8]) об экстремальных свойствах совокупностей подмножеств конечного множества. Именно выдающийся венгерский математик Эрдеш считается
3.1.7 Доказательство утверждения
Имеем
М(к,г,М)= 1 = Мі-М2,
1 < (1) < <](т) <Ткіп
V 1 < и < V < г : У(т(к,,?(«))) П У(т(/г,(г;)))
м, = 1,
1<7'(1 )<-<]{г)<Тк
Очевидно, что
1<](1)<...<](г)<Тк,„
З 1 < и < и < г : У(т(к, ]{и))) П V" (т(/с, 37 (г?)))
Мг — (Тк,м)г ~ {Тк,мУ ,
м2< £ £ !-
1<и<и<Г 1 < ;(1) < ... < ](т) < Тк,н
У(т(к,](и))) ПУ(тЦ,;(»))) # В
Если при некоторых 1 и 12 имеем 1 < 1 < 12 < и И(т(£Д1)) П
У(т(к,12)) 0, то очевидно, что
У(т(к,11))иУ(т(к,12))<2к-1.
Следовательно,
. Г2 ( .г-2 лг2/г-1 2 Гт у (А;!)2 Л*"1
м2 < СГ (Д,лг) '/V = Сг'(Д|ЛГ) —2
Т1, ~4 ТУ2“2
ж*)* _ 0(Мі),
/с2/с-4 ’ 2/21п 2/ АУ2/г
Таким образом, утверждение 3.4 доказано.
3.1.8 Доказательство утверждения
Из утверждения 3.3 следует, что
Е (Хм,кУ = £ 1) А"дг (г))
1 <Д1) < ... <Дг) <тк,„
V 1 < и < 1/ < г : У(т(А:,<;(и))) П У(т(к, ,?(и)))
(3.13)
Название работы | Автор | Дата защиты |
---|---|---|
Последовательные методы проверки статистических гипотез и обнаружения разладки | Житлухин, Михаил Валентинович | 2013 |
Предельные распределения чисел конфигураций, удовлетворяющих линейным соотношениям | Круглов, Василий Игоревич | 2009 |
Теоретико-вероятностные и комбинаторные задачи теории кодирования ДНК-последовательностей | Воронина, Анна Никитична | 2010 |