| Статистика |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
|
Главная » 2017 » Май » 23 » Теорема Рамсея
|
[править | править вики-текст]
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Теорема Рамсея — теорема комбинаторики, доказанная английским математиком Фрэнком Рамсеем. Встречается в литературе в разных формулировках.
Содержание
[скрыть]
1 Теорема
2 Числа Рамсея
2.1 Таблица значений
2.2 Асимптотические оценки
3 См. также
4 Примечания
5 Ссылки
Теорема[править | править вики-текст]
Теоретико-множественная формулировка:
Пусть
p
{\displaystyle p}
,
q
{\displaystyle q}
и
r
{\displaystyle r}
— натуральные числа, причем
p
,
q
⩾
r
{\displaystyle p,\;q\geqslant r}
. Тогда существует число
N
=
N
(
p
,
q
,
r
)
{\displaystyle N=N(p,\;q,\;r)}
, обладающее следующим свойством: если все
r
{\displaystyle r}
-элементные подмножества
N
{\displaystyle N}
-элементного множества
S
{\displaystyle S}
произвольным образом разбиты на два непересекающихся семейства
α
{\displaystyle \alpha }
и
β
{\displaystyle \beta }
, то либо существует
p
{\displaystyle p}
-элементное подмножество множества
S
{\displaystyle S}
, все
r
{\displaystyle r}
-элементные подмножества которого содержатся в
α
{\displaystyle \alpha }
, либо существует
q
{\displaystyle q}
-элементное подмножество, все
r
{\displaystyle r}
-элементные подмножества которого содержатся в
β
{\displaystyle \beta }
.
Частный случай теоремы (для
r
=
2
{\displaystyle r=2}
,
p
=
q
{\displaystyle p=q}
) удобно формулировать на языке теории графов:
Для любых натуральных чисел
n
{\displaystyle n}
,
k
{\displaystyle k}
любой достаточно большой полный граф, ребра которого раскрашены в
n
{\displaystyle n}
цветов, содержит одноцветный полный подграф с
k
{\displaystyle k}
вершинами.
Числа Рамсея[править | править вики-текст]
Эта теорема положила начало теории Рамсея. В случае раскраски рёбер графа в два цвета (чёрный и белый) теорема утверждает, что достаточно большой полный граф содержит либо чёрный полный подграф размера
r
{\displaystyle r}
, либо белый размера
s
{\displaystyle s}
. Минимальное число
R
(
r
,
s
)
{\displaystyle R(r,\;s)}
, при котором это выполнено, называют числом Рамсея, то есть:
R
(
s
,
t
)
=
min
{
n
∣
∀
G
(
V
,
E
)
:
|
V
|
=
n
⇒
ω
(
G
)
⩾
s
∨
α
(
G
)
⩾
t
}
.
{\displaystyle R(s,\;t)=\min\{n\mid \forall G(V,\;E)\colon |V|=n\Rightarrow \omega (G)\geqslant s\lor \alpha (G)\geqslant t\}.}
Здесь
G
(
V
,
E
)
{\displaystyle G(V,\;E)}
— граф
G
{\displaystyle G}
с множеством вершин
V
{\displaystyle V}
и множеством ребер
E
{\displaystyle E}
,
ω
(
G
)
{\displaystyle \omega (G)}
— кликовое число графа
G
{\displaystyle G}
, а
α
(
G
)
{\displaystyle \alpha (G)}
— независимое число графа
G
{\displaystyle G}
.
Таблица значений[править | править вики-текст]
Следующая таблица значений чисел Рамсея частично взята из таблицы Радзишовского,[1] кроме
R
(
4
,
6
)
⩾
36
{\displaystyle R(4,\;6)\geqslant 36}
, что доказано Джоффри Икзу (Exoo) в 2012 году,[2] и
R
(
3
,
10
)
⩽
42
{\displaystyle R(3,\;10)\leqslant 42}
, что доказано Яном Гёдгебером (Goedgebeur) и Станиславом Радзишовским в 2012 году.[3] Новую нижнюю границу для
R
(
4
,
8
)
{\displaystyle R(4,\;8)}
смотри: arxiv:1212.1328.
r, s
1
2
3
4
5
6
7
8
9
10
1
1
1
1
1
1
1
1
1
1
1
2
1
2
3
4
5
6
7
8
9
10
3
1
3
6
9
14
18
23
28
36
40 — 42
4
1
4
9
18
25
36 — 41
49 — 61
58 — 84
73 — 115
92 — 149
5
1
5
14
25
43 — 49
58 — 87
80 — 143
101 — 216
126 — 316
144 — 442
6
1
6
18
36 — 41
58 — 87
102 — 165
113 — 298
132 — 495
169 — 780
179 — 1171
7
1
7
23
49 — 61
80 — 143
113 — 298
205 — 540
217 — 1031
241 — 1713
289 — 2826
8
1
8
28
58 — 84
101 — 216
132 — 495
217 — 1031
282 — 1870
317 — 3583
331 — 6090
9
1
9
36
73 — 115
126 — 316
169 — 780
241 — 1713
317 — 3583
565 — 6588
581 — 12677
10
1
10
40 — 42
92 — 149
144 — 442
179 — 1171
289 — 2826
331 — 6090
581 — 12677
798 — 23556
Асимптотические оценки[править | править вики-текст]
Из неравенства
R
(
r
,
s
)
⩽
R
(
r
−
1
,
s
)
+
R
(
r
,
s
−
1
)
{\displaystyle R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)}
вытекает, что
R
(
r
,
s
)
⩽
(
r
+
s
−
2
r
−
1
)
.
{\displaystyle R(r,\;s)\leqslant {\binom {r+s-2}{r-1}}.}
В частности отсюда вытекает верхняя граница (Эрдёш, Секереш)
R
(
s
,
s
)
⩽
(
1
+
o
(
1
)
)
4
s
−
1
π
s
.
{\displaystyle R(s,\;s)\leqslant (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.}
Нижняя граница
R
(
s
,
s
)
⩾
(
1
+
o
(
1
)
)
s
2
e
2
s
/
2
,
{\displaystyle R(s,\;s)\geqslant (1+o(1)){\frac {s}{{\sqrt {2}}e}}2^{s/2},}
получена Эрдёшем в 1947 году с помощью его вероятностного метода.
Современные оценки получены Спенсером (англ.) и Конлоном соответственно.
(
1
+
o
(
1
)
)
2
s
e
2
s
/
2
⩽
R
(
s
,
s
)
⩽
s
−
c
log
s
/
log
log
s
4
s
.
{\displaystyle (1+o(1)){\frac {{\sqrt {2}}s}{e}}2^{s/2}\leqslant R(s,\;s)\leqslant s^{-c\log s/\log \log s}4^{s}.}
Очевидно, что эти оценки незначительно улучшают первые результаты и не близки между собой.
Эрдёш полагал, что в случае крайней необходимости человечество ещё способно найти
R
(
5
,
5
)
{\displaystyle R(5,\;5)}
, но не
R
(
6
,
6
)
{\displaystyle R(6,\;6)}
.
Известна также найденная Кимом в 1995 году оценка
R
(
3
,
t
)
⩾
(
1
162
+
o
(
1
)
)
t
2
ln
t
{\displaystyle R(3,\;t)\geqslant \left({\frac {1}{162}}+o(1)\right){\frac {t^{2}}{\ln {t}}}}
. В сочетании с оценкой
R
(
3
,
t
)
⩽
(
1
+
o
(
1
)
)
t
2
ln
t
{\displaystyle R(3,\;t)\leqslant (1+o(1)){\frac {t^{2}}{\ln {t}}}}
это неравенство задаёт порядок роста величины
R
(
3
,
t
)
=
Θ
(
t
2
ln
t
)
{\displaystyle R(3,\;t)=\Theta \left({\frac {t^{2}}{\ln {t}}}\right)}
.
См. также[править | править вики-текст]
Теория Рамсея
Примечания[править | править вики-текст]
↑ Dynamic Surveys.
↑ B. McKay, Ramsey Graphs
↑ Goedgebeur, Jan & Radziszowski, Stanisław (2012), "New computational upper bounds for Ramsey numbers R(3, k)", arΧiv:1210.5826
Ссылки[править | править вики-текст]
Прасолов В. В. Теорема Рамсея (см. разбор задачи 22.7)
Теория Рамсея
Источник — «https://ru.wikipedia.org/w/index.php?title=Теорема_Рамсея&oldid=83962220»
Категории: Теория множествТеоремы теории графовТеория Рамсея
|
|
Категория: Почитать |
Просмотров: 186 |
Добавил: oooo_81
| Рейтинг: 0.0/0 |
|
| Календарь | | « Май 2017 » | | Пн | Вт | Ср | Чт | Пт | Сб | Вс | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | 22 | 23 | 24 | 25 | 26 | 27 | 28 | | 29 | 30 | 31 |
|
|