Ramseyn teoria

Ramseyn teoria on matematiikan haara , joka tutkii olosuhteita, joissa jonkin järjestyksen täytyy esiintyä mielivaltaisesti muodostetuissa matemaattisissa objekteissa. Nimetty Frank Ramseyn mukaan .

Ramseyn teorian ongelmat ilmenevät yleensä kysymyksen muodossa "kuinka monta elementtiä jossakin objektissa pitäisi olla, jotta voidaan taata, että tietty ehto täyttyy tai tietty rakenne on olemassa". Yksinkertaisin esimerkki:

Todista, että missä tahansa 6 hengen ryhmässä on joko 3 henkilöä, jotka tuntevat toisensa, tai 3 henkilöä, jotka eivät tunne toisiaan pareittain.

Klassiset tulokset

Oletetaan esimerkiksi, että tiedämme, että kanit on sijoitettu häkkeihin. Kuinka suuri sen tulee olla , jotta yhdessä häkissä on vähintään 2 kania? Dirichlet'n periaatteen mukaan jos , niin on solu, joka sisältää vähintään 2 kania. Ramseyn teoria yleistää tämän periaatteen [1] . $n$ $m$ $n$ $n>m$

Ramseyn lause

Ramsey itse todisti seuraavan lauseen:

Olkoon numerot annettu . Sitten on sellainen luku , että riippumatta siitä, kuinka värjätään täydellisen graafin reunat pisteissä väreillä , kärjeissä on joko 1. värin täydellinen aligraafi tai pisteissä 2. värin täydellinen aligraafi. , ... tai täydellinen aligraafi :nnen värin pisteissä . [2] ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$ $R$ $R$ $n$ $a_{1}$ $a_{2}$ $n$ $a_n$

Hän myös yleisti sen hypergraafin tapaukseksi .

Vähimmäislukua , jolle tietylle argumenttijoukolle on olemassa lauseessa määritetty väritys, kutsutaan Ramsey-luvuksi. Ramsey-lukujen arvot tunnetaan hyvin pienestä määrästä argumenttijoukkoja. $R$ ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$

Van der Waerdenin lause

Van der Waerdenin lause on samanlainen muotoilultaan, mutta eroaa todistuksesta.

Jokaiselle lukujoukolle on olemassa sellainen luku , että riippumatta siitä, kuinka värjätään ensimmäiset luonnolliset luvut väreillä, on olemassa joko pituuden 1. värin aritmeettinen kulku tai pituuden 2. värin aritmeettinen progressio . .. tai pituuden :nnen värin aritmeettinen progressio . [3] ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$ $W$ $W$ $n$ $a_{1}$ $a_{2}$ $n$ $a_n$

Pienintä tällaista lukua kutsutaan van der Waerdenin numeroksi .

Luonnollisten lukujen joukon sijasta voimme tarkastella hilaa , ja aritmeettisia progressioita - siinä olevia lukuja, jotka ovat homoteettisia annetun luvun kanssa, ja lauseen väite pysyy tosi (yleistetty van der Waerdenin lause). ${\mathbb Z}^{n}$

Hales-Jewett-lause

Kaikille luvuille ja on mahdollista löytää sellainen luku , että jos -ulotteisen kuution solut, joiden sivu on värjätty väreillä, on vähintään yksi viiva (rivit, sarakkeet, jotkut lävistäjät katsotaan viivoiksi) yksiväriset solut. [neljä] $n$ $c$ $H$ $H$ $n$ $c$ $n$

Tästä lauseesta seuraa, että kun pelaat moniulotteista tic-tac-toea millä tahansa linjan pituudella ja millä tahansa määrällä pelaajia, voit löytää sellaisen määrän ulottuvuuksia, että tasapeli on mahdotonta.

Erdős-Székeres-oletus Kupera monikulmio-oletus

Jokaiselle luonnolliselle pisteelle, jokaisella riittävän suurella pistejoukolla yleisessä paikassa tasossa on osajoukko pisteitä, jotka ovat kuperan monikulmion kärkipisteitä. [5] $N$ $N$

Erdősin ja Székeresin konveksia polygoneja koskevan arvelun mukaan niiden yleisen sijainnin pisteiden lukumäärä, joissa konveksi kulmio on välttämättä olemassa, saadaan $N$

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

kaikille . He myös osoittivat, että kuperaa -gonia ei välttämättä ole joukossa, jossa on pienempi määrä pisteitä. $N$ $N$

Krootin monokromaattinen egyptiläinen murtolause

Jokaiselle suurikokoisten kokonaislukujen värjäykseen on olemassa äärellinen monokromaattinen kokonaislukujen osajoukko, $yksi$ $r>0$ $S$

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

Tässä tapauksessa maksimielementtiä ja siten joukon kokoa rajoittaa eksponentiaalinen funktio vakiokantaisella. $S$ $r$

Ernest Krut todisti tämän Erdős-Grahamin arvelun vuonna 2003 .

Teorian piirteet

Ramseyn teorian puitteissa saaduille tuloksille on tunnusomaista kaksi ominaisuutta. Ensinnäkin ne eivät ole rakentavia. On todistettu, että jokin rakenne on olemassa, mutta sen rakentamiseksi ei ehdoteta muuta tapaa kuin suoraa luettelointia. Toiseksi haluttujen rakenteiden olemassaolo edellyttää, että ne sisältävät objektit koostuvat erittäin suuresta määrästä elementtejä. Objektin elementtien lukumäärän riippuvuus rakenteen koosta on yleensä vähintään eksponentiaalinen.

Muistiinpanot

↑ Tuloskatsaus vuoteen 1990 asti: Graham, R .; Rothschild, B. & Spencer, JH (1990), Ramsey Theory (2. painos), New York: John Wiley and Sons, ISBN 0-471-50046-1 .
↑ Ramsey, FP Formaalisen logiikan ongelmasta // Proc . Lontoon matematiikka. soc. Sarja 2. - 1930. - Voi. 30 . - s. 264-286 . - doi : 10.1112/plms/s2-30.1.264 .
↑ van der Waerden, B. L. Beweis einer Baudetschen Vermutung (saksa) // Nieuw. Kaari. Wisk.. - 1927. - Bd. 15 . - S. 212-216 .
↑ Hales A., Jewett R. Säännöllisyys ja asemapelit (eng.) // Trans. amer. Matematiikka. Soc.. - 1963. - Voi. 106 . - s. 222-229 . - doi : 10.2307/1993764 . Arkistoitu alkuperäisestä 19. tammikuuta 2022.
↑ Erdős, P. & Szekeres, G. (1935), A kombinatorinen ongelma geometriassa , Compositio Math vol. 2: 463-470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > Arkistoitu helmikuusta 19. 2019 Wayback Machinessa .

Kirjallisuus

Martin Gardner . Luku 17. Ramseyn teoria // Penrose-laatoista vahvoiksi salakirjoiksi = Penrose-laatoista trapdoor-salauksiin englannista. Yu. A. Danilova. - M .: Mir , 1993. - S. 288-308. — 416 s. - 10 000 kappaletta. — ISBN 5-03-001991-X .

Linkit

Ramseyn teoria