Ramsey elmélet

A Ramsey-elmélet a matematikának egy olyan ága , amely azt vizsgálja, hogy milyen feltételek mellett kell valamilyen rendnek megjelennie az önkényesen kialakított matematikai objektumokban. Frank Ramseyről kapta a nevét .

A Ramsey-elmélet problémái általában a következő kérdés formájában jelentkeznek: „hány elemnek kell lennie egy objektumnak ahhoz, hogy garantáljuk egy adott feltétel teljesülését vagy egy adott struktúra létezését”. A legegyszerűbb példa:

Bizonyítsuk be, hogy bármely 6 fős csoportban vagy 3 ember ismeri egymást, vagy 3 ember, akik nem ismerik egymást párban.

Klasszikus eredmények

Tegyük fel például, hogy tudjuk, hogy a nyulakat ketrecbe helyezik . Mekkora legyen ahhoz , hogy az egyik ketrecben legalább 2 nyúl legyen? Dirichlet-elv szerint , ha , akkor van egy sejt, amely legalább 2 nyulat tartalmaz. Ramsey elmélete általánosítja ezt az elvet [1] . $n$ $m$ $n$ $n>m$

Ramsey-tétel

Maga Ramsey bebizonyította a következő tételt:

Legyenek számok megadva . Aztán van egy olyan szám , hogy akárhogyan is színezzük színekkel a teljes gráf éleit a csúcsoknál, a csúcsokban vagy az 1. szín teljes részgráfja van, vagy a csúcsokban a 2. szín teljes részgráfja. , ... vagy a csúcsokban lévő th szín teljes részgráfja . [2] ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$ $R$ $R$ $n$ $a_{1}$ $a_{2}$ $n$ $a_n$

A hipergráf esetére is általánosította .

Ramsey-számnak nevezzük azt a minimális számot , amelynél egy adott argumentumhalmaznál létezik a tételben meghatározott színezés. A Ramsey-számok értékei nagyon kevés argumentumkészletről ismertek. $R$ ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$

Van der Waerden tétele

A van der Waerden-tétel megfogalmazásában hasonló, de bizonyításban különbözik.

Bármely számhalmazhoz létezik olyan szám , hogy akárhogyan is színezzük színekkel az első természetes számokat , létezik vagy a hossz 1. színének számtani sorozata , vagy a 2. hosszúságú szín számtani sorozata , . .., vagy a hossz színének számtani sorozata . [3] ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$ $W$ $W$ $n$ $a_{1}$ $a_{2}$ $n$ $a_n$

A legkisebb ilyen számot van der Waerden számnak nevezik .

Természetes számok halmaza helyett tekinthetünk rácsot és számtani progressziókat - benne az adott számmal homotetikus alakzatokat, és a tétel állítása igaz marad (általánosított van der Waerden tétel). ${\mathbb Z}^{n}$

A Hales-Jewett tétel

Bármilyen számhoz és lehet találni olyan számot , hogy ha egy hosszú oldalú -dimenziós kocka celláit színekkel színezzük ki , akkor legalább egy vonal van (sorok, oszlopok, egyes átlók vonalnak számítanak) egyszínű cellák. [négy] $n$ $c$ $H$ $H$ $n$ $c$ $n$

Ebből a tételből az következik, hogy ha többdimenziós tic-tac-toe-t játszunk tetszőleges vonalhosszon és tetszőleges számú játékos esetén, akkora számú dimenziót találhatunk, hogy lehetetlen lesz döntetlen.

Az Erdős-Székeres sejtés Konvex sokszög sejtés

Bármely természetes , a síkon általános helyzetben lévő pontok bármely kellően nagy halmaza rendelkezik olyan pontok részhalmazával , amelyek egy konvex sokszög csúcsai. [5] $N$ $N$

Erdős és Székeres konvex sokszögekre vonatkozó sejtése szerint az általános helyzetű azon pontok számát, amelyeknél szükségszerűen létezik egy konvex -gon , a $N$

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

mindenkinek . Azt is bebizonyították, hogy konvex -gon nem létezik egy kisebb pontszámú halmazban. $N$ $N$

Kroot monokromatikus egyiptomi törttétele

A nagy színű egész számok bármilyen színezéséhez létezik az egész számok véges monokromatikus részhalmaza , $egy$ $r>0$ $S$

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

Ebben az esetben a maximális elemet, és így a halmaz méretét egy exponenciális függvény korlátozza állandó bázissal. $S$ $r$

Ezt az Erdős-Graham sejtést Ernest Krut igazolta 2003 - ban .

Az elmélet jellemzői

A Ramsey-elmélet keretében elért eredményeket két tulajdonság jellemzi. Először is, nem konstruktívak. Bebizonyosodott, hogy létezik valamilyen struktúra, de a közvetlen felsoroláson kívül semmilyen más módot nem javasolnak a felépítésére. Másodszor, a kívánt struktúrák létezéséhez szükséges, hogy az azokat tartalmazó objektumok nagyon sok elemből álljanak. Egy objektum elemszámának a szerkezet méretétől való függése általában legalább exponenciális.

Jegyzetek

↑ Eredmények áttekintése 1990-ig: Graham, R .; Rothschild, B. & Spencer, JH (1990), Ramsey Theory (2. kiadás), New York: John Wiley and Sons, ISBN 0-471-50046-1 .
↑ Ramsey, FP A formális logika problémájáról // Proc . London Math. szoc. Sorozat 2. - 1930. - 2. évf. 30 . - P. 264-286 . - doi : 10.1112/plms/s2-30.1.264 .
↑ van der Waerden, B. L. Beweis einer Baudetschen Vermutung (német) // Nieuw. Boltív. Wisk.. - 1927. - Bd. 15 . - S. 212-216 .
↑ Hales A., Jewett R. Szabályossági és helyzeti játékok (ang.) // Ford. amer. Math. Soc.. - 1963. - 1. évf. 106 . - P. 222-229 . - doi : 10.2307/1993764 . Az eredetiből archiválva : 2022. január 19.
↑ Erdős, P. & Szekeres, G. (1935), A kombinatorikus probléma a geometriában , Compositio Math vol. 2: 463-470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > Archivált : február 2019. 19. a Wayback Machine -nél .

Irodalom

Martin Gardner . 17. fejezet Ramsey-elmélet // A Penrose-csempéktől az erős titkosításokig = Penrose-csempéktől a csapóajtó-rejtjelekig angolról. Yu. A. Danilova. - M .: Mir , 1993. - S. 288-308. — 416 p. — 10.000 példány. — ISBN 5-03-001991-X .

Linkek

Ramsey elmélet