Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Числа Рамсея
СообщениеДобавлено: 25 окт 2017, 23:12 
Не в сети
Начинающий
Зарегистрирован:
03 окт 2017, 16:19
Сообщений: 32
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Условие. Полным графом на n вершинах называется (обозначается Kn) граф без петель и кратных ребер, любая пара вершин которого соединена ребром. Числом Рамсея R(k,l) (здесь k,l - произвольные натуральные числа) называется такое наименьшее натуральное число n, что при раскраске ребер полного графа Kn в синий и красный цвета в нем найдется либо подграф Kk, все ребра которого красные, либо подграф Kl, все ребра которого синие.


Есть R(3,4),вероятность покраски ребра в красный цвет равна 1/3 в синий соответственно 2/3. Какое наибольшее n (в таком решении) можно гарантировать, при котором R(3,4)≥n?

-----------------------------
Например доказательство для R(10,10)>95 выглядит так:

Применим схему C(95,2) испытаний Бернулли с вероятностью успеха 1/2. Если в i-ом испытании произошел успех, то включаем в строящийся случайный подграф графа K95 i-ое ребро, иначе -- не включаем. Для произвольного 10-элементного множества R вершин графа K95 обозначим A(R) событие, заключающееся в том, что все его ребра покрашены в один и тот же цвет. Очевидно, P(A(R))=(1/2)^(C(10,2)−1). Тогда вероятность того, что для некоторого R событие A(R) произойдет, не превосходит

C(95,10)/((1/2)^44)<(95^10)/((2^44)*10!)<1

Следовательно, с положительной вероятностью не произойдет ни одного из событий A(R), т.е. найдется такая раскраска, что в графе K95 не будет существовать ни синего K10, ни красного K10.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Возведение комплексного числа в степень + корни комп. числа

в форуме Комплексный анализ и Операционное исчисление

pe3a4ok

1

539

04 ноя 2013, 15:56

Взаимно простые числа, фракталы и числа Фибоначчи

в форуме Теория чисел

xcont

4

860

19 авг 2013, 23:32

Комплексные числа, найти корни к-го числа

в форуме Комплексный анализ и Операционное исчисление

bellkross

4

102

04 окт 2016, 17:43

Два числа

в форуме Алгебра

DeD

4

86

18 фев 2017, 11:58

Числа

в форуме Алгебра

den111

9

383

29 май 2013, 02:40

Ряд от числа

в форуме Ряды

DeusEx

4

206

22 мар 2014, 15:42

С6. Целые числа

в форуме Начала анализа и Другие разделы школьной математики

oleg_n1

3

389

31 май 2013, 02:24

Собственные числа

в форуме Линейная и Абстрактная алгебра

Maxmax87

15

370

19 июн 2015, 12:52

Комплексные числа

в форуме Комплексный анализ и Операционное исчисление

helpmeplz

20

416

31 янв 2013, 13:45

Сравнить два числа

в форуме Алгебра

Gagarin

7

169

24 июн 2015, 10:27


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 34


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved