Teoria Ramsey

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. Numit după Frank Ramsey .

Problemele din teoria Ramsey iau de obicei forma întrebării „câte elemente ar trebui să existe într-un obiect pentru a garanta că o anumită condiție este îndeplinită sau că există o anumită structură”. Cel mai simplu exemplu:

Demonstrați că în orice grup de 6 persoane sunt fie 3 persoane care se cunosc, fie 3 persoane care nu se cunosc în perechi.

Rezultate clasice

Să presupunem, de exemplu, că știm că iepurii sunt puși în cuști. Cât de mare trebuie să fie pentru a garanta că într-una dintre cuști sunt cel puțin 2 iepuri? Conform principiului lui Dirichlet , dacă , atunci există o celulă care conține cel puțin 2 iepuri. Teoria lui Ramsey generalizează acest principiu [1] . $n$ $m$ $n$ $n>m$

Teorema lui Ramsey

Ramsey însuși a demonstrat următoarea teoremă:

Să fie date numere . Apoi există un astfel de număr încât, indiferent de cum colorăm în culori marginile graficului complet la vârfuri , există fie un subgraf complet al primei culori la vârfuri, fie un subgraf complet al celei de-a doua culori la vârfuri . , ... sau un subgraf complet al celei de-a --a culori la vârfuri. [2] $a_{1},\,a_{2},\,\ldots ,\,a_{n)$ $R$ $R$ $n$ $a_{1}$ $a_{2}$ $n$ $un$

A fost generalizat de el și la cazul unui hipergraf .

Numărul minim pentru care, pentru un anumit set de argumente , există colorarea specificată în teoremă se numește număr Ramsey. Valorile numerelor Ramsey sunt cunoscute pentru un număr foarte mic de seturi de argumente. $R$ $a_{1},\,a_{2},\,\ldots ,\,a_{n)$

Teorema lui Van der Waerden

Teorema van der Waerden este similară în formulare, dar diferă în demonstrație.

Pentru orice set de numere, există un astfel de număr încât, indiferent de modul în care colorăm primele numere naturale în culori, există fie o progresie aritmetică a primei culori a lungimii , fie o progresie aritmetică a celei de-a doua culori a lungimii , . .., sau o progresie aritmetică a celei de-a- lea culori a lungimii . [3] $a_{1},\,a_{2},\,\ldots ,\,a_{n)$ $W$ $W$ $n$ $a_{1}$ $a_{2}$ $n$ $un$

Cel mai mic astfel de număr se numește numărul van der Waerden .

În loc de o mulțime de numere naturale, putem considera o rețea și progresii aritmetice - cifre din ea, omotetice cu cea dată, iar afirmația teoremei rămâne adevărată (teorema generalizată van der Waerden). ${\mathbb Z}^{n}$

Teorema Hales-Jewett

Pentru orice numere și este posibil să găsiți un număr astfel încât dacă celulele unui cub -dimensional cu o latură de lungime sunt colorate în culori, atunci există cel puțin o linie (rândurile, coloanele, unele diagonale sunt considerate linii) de la celule cu o singură culoare. [patru] $n$ $c$ $H$ $H$ $n$ $c$ $n$

Din această teoremă rezultă că atunci când jucați tic-tac-toe multidimensional pentru orice lungime a liniei și orice număr de jucători, puteți găsi un astfel de număr de dimensiuni încât o remiză va fi imposibilă.

Conjectura Erdős-Székeres Conjectura poligonului convex

Pentru orice natural , orice set suficient de mare de puncte într-o poziție generală pe plan are o submulțime de puncte care sunt vârfuri ale unui poligon convex. [5] $N$ $N$

Conform conjecturii lui Erdős și Székeres asupra poligoanelor convexe, numărul de puncte din poziția generală la care există în mod necesar un -gon convex este dat de $N$

f(N)=1+2^{N-2)

pentru toată lumea . De asemenea, au demonstrat că un -gon convex poate să nu existe într-o mulțime cu un număr mai mic de puncte. $N$ $N$

Teorema fracției egiptene monocromatice a lui Kroot

Pentru orice colorare a numerelor întregi mari în culori, există un subset finit monocromatic de numere întregi astfel încât $unu$ $r>0$ $S$

\sum _{n\in S}1/n=1.

În acest caz, elementul maxim și, prin urmare, dimensiunea mulțimii , este limitat de o funcție exponențială de cu o bază constantă. $S$ $r$

Această conjectura Erdős-Graham a fost dovedită de Ernest Krut în 2003 .

Caracteristicile teoriei

Rezultatele din cadrul teoriei Ramsey sunt caracterizate de două proprietăți. În primul rând, nu sunt constructive. Se dovedește că există o structură, dar nu se propune o altă modalitate de a o construi decât enumerarea directă. În al doilea rând, pentru ca structurile dorite să existe, este necesar ca obiectele care le conțin să fie formate dintr-un număr foarte mare de elemente. Dependența numărului de elemente ale unui obiect de dimensiunea structurii este de obicei cel puțin exponențială.

Note

↑ Revizuirea rezultatelor până în 1990: Graham, R .; Rothschild, B. & Spencer, JH (1990), Ramsey Theory (ed. a doua), New York: John Wiley and Sons, ISBN 0-471-50046-1 .
↑ Ramsey, FP Despre o problemă de logică formală // Proc . London Math. soc. Seria 2. - 1930. - Vol. 30 . - P. 264-286 . - doi : 10.1112/plms/s2-30.1.264 .
↑ van der Waerden, B. L. Beweis einer Baudetschen Vermutung (germană) // Nieuw. Arc. Wisk.. - 1927. - Bd. 15 . - S. 212-216 .
↑ Hales A., Jewett R. Regularity and positional games (ing.) // Trad. amer. Matematică. Soc.. - 1963. - Vol. 106 . - P. 222-229 . - doi : 10.2307/1993764 . Arhivat din original pe 19 ianuarie 2022.
↑ Erdős, P. & Szekeres, G. (1935), A combinatorial problem in geometry , Compositio Math vol. 2: 463-470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > Arhivat din februarie 19, 2019 la Wayback Machine .

Literatură

Martin Gardner . Capitolul 17. Teoria Ramsey // De la țiglele Penrose la cifrurile puternice = țiglele Penrose la cifrurile Trapdoor din engleza. Yu. A. Danilova. - M .: Mir , 1993. - S. 288-308. — 416 p. — 10.000 de exemplare. — ISBN 5-03-001991-X .

Link -uri

Teoria Ramsey