Teorema lui Ramsey

Teorema lui Ramsey este o teoremă de combinatorie asupra partițiilor de mulțimi, formulată și demonstrată de matematicianul englez Frank Ramsey în 1930 [1] . Apare în literatură în diverse formulări. Această teoremă a marcat începutul teoriei Ramsey .

Formulări

Formularea teoretică a mulțimilor

Caz special N ( p , q , r )

Fie , și să fie numere naturale , și . $p$ $q$ $r$ $p,\;q\geqslant r$

Atunci există un număr cu următoarea proprietate: dacă toate submulțimile -element ale mulțimii -element sunt împărțite în mod arbitrar în două familii disjunse și , atunci fie există o submulțime -element a mulțimii ale căror submulțimi -element sunt conținute în , sau există o submulțime -element, toate subseturile -element ale căror subseturi sunt conținute în . $N=N(p,\;q,\;r)$ $r$ $N$ $S$ $\alfa$ $\beta$ $p$ $S$ $r$ $\alfa$ $q$ $r$ $\beta$

Caz general

Lăsați mulțimea să aibă elemente. Luați în considerare subseturile sale , denotați totalitatea tuturor acestor subseturi , partiții ordonate , numere care definesc partiția . $S$ $N$ $r$ $r\geqslant 1$ $P_{r}(S)$ $t$ $P_{r}(S)=A_{1}\cup A_{2}\cup \ldots \cup A_{t)$ ${\displaystyle q_{1},\q_{2},\\ldots,\q_{t))$ $1\leqslant r\leqslant q_{1},\;q_{2},\;\ldots,\;q_{t)$

Atunci pentru orice partiție ordonată a mulțimii există un număr minim astfel încât dacă , atunci există o submulțime a mulțimii , adică o astfel de submulțime a mulțimii ale căror toate -submulțimile sunt conținute în [2] . $t$ $P_{r}(S)$ $N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;r)$ $N\geqslant N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;r)$ $(q_{i},\;A_{i})$ $S$ $q_{i}$ $S$ $r$ $A_{i},\ 1\leqslant t\leqslant t$

Anunțat în limbajul teoriei grafurilor

Pentru orice numere naturale , orice colorare a muchiilor unui graf complet suficient de mare conține un subgraf complet cu vârfuri pentru o anumită culoare . În special, pentru orice și , un grafic complet suficient de mare de colorare în două culori (alb și negru) conține fie un subgraf complet de vârf negru, fie un subgraf complet alb de vârf. $c$ ${\displaystyle n_{1},\n_{2},\\ldots,\n_{c))$ $c$ $n_{i}$ $i$ $r$ $s$ $r$ $s$

Numerele Ramsey

Numărul minim pentru care este valabil se numește numărul Ramsey. $R(r,\;s)$

De exemplu, egalitatea înseamnă că, pe de o parte, în orice colorare în două culori a unui grafic complet există un triunghi cu o singură culoare și, pe de altă parte, că graficul complet admite o colorare în două culori fără o culoare. triunghiuri. $R(3,\;3)=6$ $K_{6}$ $K_{5}$

În general, pentru colorarea -color se folosește notația pentru numărul minim de vârfuri care asigură existența unei culori . $c$ $R(n_{1},\;n_{2},\;\ldots ,\;n_{c})$ $K_{n_{i)}$ $i$

Dovada teoremei lui Ramsey

Carcasă în două culori

Lema 1. $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1).$

Dovada. Să demonstrăm folosind metoda inducției matematice pe . $r+s$

baza de inducție. , deoarece un grafic cu 1 vârf poate fi considerat un grafic complet de orice culoare. $R(n,\;1)=R(1,\;n)=1$

Tranziție prin inducție . Lasă și . Luați în considerare un grafic vertex complet alb-negru . Luați un vârf arbitrar și notați cu și seturile incidente în subgrafele alb și negru, respectiv. Deoarece în graficul vârfurilor, conform principiului Dirichlet (combinatorie) , fie , fie . $r>1$ $s>1$ $R(r-1,\;s)+R(r,\;s-1)$ $v$ $M$ $N$ $v$ $R(r-1,\;s)+R(r,\;s-1)=|M|+|N|+1$ $|M|\geqslant R(r-1,\;s)$ $|N|\geqslant R(r,\;s-1)$

Lasă . Apoi fie în (și deci în întregul grafic) există alb , care completează demonstrația, fie există negru în , care împreună cu formează negru . Cazul este tratat în mod similar. $|M|\geqslant R(r-1,\;s)$ $M$ $K_{s}$ $M$ $K_{r-1}$ $v$ $K_{r)$ $|N|\geqslant R(r,\;s-1)$

Cometariu. Dacă ambele sunt egale, inegalitatea poate fi întărită: . $R(r-1,\;s)$ $R(r,\;s-1)$ $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)-1$

Dovada . Să presupunem că ambele sunt egale. Setați și luați în considerare un grafic alb-negru al vârfurilor. Dacă gradul celui de-al-lea vârf din subgraful negru, atunci, conform lemei strângerii de mână , este par. Deoarece este impar, trebuie să existe un par . Pentru certitudine, presupunem că este egal. Notați cu și vârfurile incidente vârfului 1 în subgrafele alb și, respectiv. Atunci ambele sunt egale. Conform principiului Dirichlet (combinatoric) , fie , fie . Deoarece este par și impar, prima inegalitate poate fi întărită, deci fie , fie . $p=R(r-1,\;s)$ $q=R(r,\;s-1)$ $t=p+q-1$ $t$ $d_{i}$ $i$ $\sum _{i=1}^{t}d_{i}$ $t$ $d_{i}$ $d_{1}$ $M$ $N$ $|M|=d_{1}$ $|N|=t-1-d_{1}$ $|M|\geqslant p-1$ $N\geqslant q$ $|M|$ $p-1$ $|M|\geqslant p$ $|N|\geqslant q$

Să presupunem că . Apoi, fie subgraful generat de mulțime conține alb și demonstrația este completă, fie conține negru , care împreună cu vârful 1 formează negru . Cazul este tratat în mod similar. $|M|\geqslant p=R(r-1,\;s)$ $M$ $K_{s}$ $K_{r-1}$ $K_{r)$ $|N|\geqslant q=R(r,\;s-1)$

Un caz de mai multe culori.

Lema 2. Dacă , atunci $c>2$ $R(n_{1},\;\ldots,\;n_{c})\leqslant R(n_{1},\;\ldots,\;n_{c-2},\;R(n_ {c-1},\;n_{c})).$

Dovada. Luați în considerare un grafic de vârfuri și colorați-i marginile cu culori. Vom lua în considerare temporar culorile și o singură culoare. Apoi graficul devine -colorat. Conform definiției numărului , un astfel de grafic fie conține, pentru o anumită culoare , cum ar fi ceva colorat de culoarea comună și . În primul caz, dovada este completă. În al doilea caz, returnăm culorile anterioare și observăm că, prin definiția numărului Ramsey, graficul complet - vârf conține fie culori , fie culori , deci afirmația este complet dovedită. $R(n_{1},\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ $c$ $c-1$ $c$ $(c-1)$ $R(n_{1},\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ $K_{n_{i)}$ $i$ $1\leqslant i\leqslant c-2$ $K_{R(n_{c-1},\;n_{c))))$ $c-1$ $c$ $R(n_{c-1},\;n_{c})$ $K_{n_{c-1)}$ $c-1$ $K_{n_{c))$ $c$

Lema 1 implică faptul că numerele Ramsey pentru . Din aceasta, pe baza Lemei 2, rezultă că pentru orice . Aceasta demonstrează teorema Ramsey. $c=2$ $R(n_{1},\;\ldots ,\;n_{c})$ $c$

Semnificațiile numerelor Ramsey

Tabel de valori

Există foarte puține date pentru la [3] . Următorul tabel de valori pentru numerele Ramsey pentru este preluat din tabelul lui Radzishevsky [4] , datele sunt din 2020. $N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;t)$ $t>2$ $N(q_{1},\;q_{2};\;2)$

$r,\s$	unu	2	3	patru	5	6	7	opt	9	zece
unu	unu	unu	unu	unu	unu	unu	unu	unu	unu	unu
2	unu	2	3	patru	5	6	7	opt	9	zece
3	unu	3	6	9	paisprezece	optsprezece	23	28	36	[40, 42]
patru	unu	patru	9	optsprezece	25	[36, 41]	[49, 61]	[59, 84]	[73, 115]	[92, 149]
5	unu	5	paisprezece	25	[43, 48]	[58, 87]	[80, 143]	[101, 216]	[133, 316]	[149, 442]
6	unu	6	optsprezece	[36, 41]	[58, 87]	[102, 165]	[115, 298]	[134, 495]	[183, 780]	[204, 1171]
7	unu	7	23	[49, 61]	[80, 143]	[115, 298]	[205, 540]	[217, 1031]	[252, 1713]	[292, 2826]
opt	unu	opt	28	[59, 84]	[101, 216]	[134, 495]	[217, 1031]	[282, 1870]	[329, 3583]	[343, 6090]
9	unu	9	36	[73, 115]	[133, 316]	[183, 780]	[252, 1713]	[329, 3583]	[565, 6588]	[581, 12677]
zece	unu	zece	[40, 42]	[92, 149]	[149, 442]	[204, 1171]	[292, 2826]	[343, 6090]	[581, 12677]	[798, 23556]

Estimări asimptotice

Din inegalitate rezultă că $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)$

R(r,\;s)\leqslant {\binom {r+s-2}{r-1)).

În special, de aici urmează limita superioară ( Erdős , Sekeres )

R(s,\;s)\leqslant (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.

Concluzie

R(s,\;s)\geqslant (1+o(1)){\frac {s}({\sqrt {2}}e}}2^{s/2},

obţinut de Erdős în 1947 folosind metoda sa probabilistică .

Estimările moderne sunt de la Spencer și, respectiv, Conlon.

(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}.

Evident, aceste estimări îmbunătățesc ușor primele rezultate și nu sunt aproape unele de altele.

Erdős credea că, în caz de urgență, omenirea este încă capabilă să găsească , dar nu . $R(5,\;5)$ $R(6,\;6)$

Este cunoscută și estimarea găsită de Kim în 1995 . În combinație cu estimarea , această inegalitate stabilește ordinea de creștere a . $R(3,\;t)\geqslant \left({\frac {1}{162}}+o(1)\right){\frac {t^{2}}{\ln {t} }}$ $R(3,\;t)\leqslant (1+o(1)){\frac {t^{2}}{\ln {t)))$ $R(3,\;t)=\Theta \left({\frac {t^{2}}{\ln {t}}}\right)$

Variații și generalizări

Teorema Erdős-Rado este o generalizare a teoremei Ramsey la mulțimi nenumărate.

Teoria Ramsey este o ramură a matematicii care studiază condițiile în care o anumită ordine trebuie să apară în obiectele matematice formate în mod arbitrar.

Note

↑ F. P. Ramsey Despre o problemă de logică formală. - Proc. London Math. Soc.”, a 2-a ser., 30 (1930), pp. 264-286
↑ Ribnikov, 1972 , p. 93.
↑ Ribnikov, 1972 , p. 96.
↑ Stanisław Radziszowski. Numerele Ramsey mici (engleză) // Jurnalul electronic de combinatorie. - 2017. - 3 martie. — ISSN 1077-8926 . Arhivat din original pe 29 mai 2017. (reviziunea 15)

Link -uri

Teorema lui Prasolov V. V. Ramsey (vezi analiza problemei 22.7)
Teoria Ramsey

Literatură

Rybnikov K.A. Introducere în analiza combinatorie. - Universitatea de Stat din Moscova, 1972.