Ramsey teori

Ramsey-teorin är en gren av matematiken som studerar de förhållanden under vilka någon ordning måste uppträda i godtyckligt formade matematiska objekt. Uppkallad efter Frank Ramsey .

Problem i Ramsey-teorin tar vanligtvis formen av frågan "hur många element ska det finnas i något objekt för att garantera att ett givet villkor är uppfyllt eller att en given struktur existerar". Det enklaste exemplet:

Bevisa att i en grupp på 6 personer finns det antingen 3 personer som känner varandra, eller 3 personer som inte känner varandra i par.

Klassiska resultat

Anta till exempel att vi vet att kaninerna placeras i burar. Hur stor måste den vara för att garantera att det finns minst 2 kaniner i en av burarna? Enligt Dirichlets princip , om , så finns det en cell som innehåller minst 2 kaniner. Ramseys teori generaliserar denna princip [1] . $n$ $m$ $n$ $n>m$

Ramseys teorem

Ramsey själv bevisade följande teorem:

Låt siffror ges . Sedan finns det en sådan siffra att oavsett hur vi färgar kanterna på den fullständiga grafen vid hörnen , så finns det antingen en komplett subgraf av den första färgen vid hörnen, eller en komplett subgraf av den 2:a färgen vid hörnen , ... eller en komplett subgraf av den e färgen vid hörnen. [2] ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$ $R$ $R$ $n$ $a_{1}$ $a_{2}$ $n$ $en$

Det generaliserades också av honom till fallet med en hypergraf .

Det minsta antal för vilket, för en given uppsättning argument , färgen som anges i satsen finns, kallas Ramsey-talet. Värdena för Ramsey-talen är kända för ett mycket litet antal uppsättningar argument. $R$ ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$

Van der Waerdens teorem

Van der Waerdens sats liknar formuleringen men skiljer sig i bevis.

För varje uppsättning siffror finns det ett sådant tal att, oavsett hur vi färgar de första naturliga talen i färger, finns det antingen en aritmetisk progression av den första längdfärgen , eller en aritmetisk progression av den andra längdfärgen , . .., eller en aritmetisk utveckling av längdens th färg . [3] ${\displaystyle a_{1},\,a_{2},\,\ldots ,\,a_{n))$ $W$ $W$ $n$ $a_{1}$ $a_{2}$ $n$ $en$

Det minsta sådana numret kallas van der Waerden-numret .

Istället för en uppsättning naturliga tal kan vi överväga ett gitter och aritmetiska progressioner - siffror i det, homotetiska till det givna, och påståendet om satsen förblir sann (generaliserad van der Waerden-sats). ${\mathbb Z}^{n}$

Hales-Jewett-satsen

För alla tal och det är möjligt att hitta ett tal så att om cellerna i en -dimensionell kub med en längdsida är färgade i färger, så finns det minst en linje (rader, kolumner, vissa diagonaler anses vara linjer) från enfärgade celler. [fyra] $n$ $c$ $H$ $H$ $n$ $c$ $n$

Av detta teorem följer att när man spelar flerdimensionell tic-tac-toe för valfri längd av linjen och valfritt antal spelare, kan du hitta ett sådant antal dimensioner att oavgjort blir omöjligt.

Erdős-Székeres förmodan konvex polygonförmodan

För alla naturliga , en tillräckligt stor uppsättning punkter i en allmän position på planet har en delmängd av punkter som är hörn av en konvex polygon. [5] $N$ $N$

Enligt Erdős och Székeres gissning om konvexa polygoner ges antalet punkter i den allmänna positionen där en konvex -gon nödvändigtvis existerar av $N$

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

för alla . De bevisade också att en konvex -gon kanske inte finns i en uppsättning med ett mindre antal punkter. $N$ $N$

Kroots monokromatiska egyptiska bråksats

För varje färgning av heltal med stora färger finns det en ändlig monokromatisk delmängd av heltal så att $ett$ $r>0$ $S$

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

I detta fall begränsas det maximala elementet, och därmed storleken på mängden , av en exponentiell funktion med en konstant bas. $S$ $r$

Denna Erdős-Graham gissning bevisades av Ernest Krut ] 2003 .

Funktioner i teorin

Resultat inom ramen för Ramsey-teorin kännetecknas av två egenskaper. För det första är de inte konstruktiva. Det är bevisat att någon struktur existerar, men inget annat sätt att konstruera den än direkt uppräkning föreslås. För det andra, för att de önskade strukturerna ska existera, krävs att föremålen som innehåller dem består av ett mycket stort antal element. Beroendet av antalet element i ett objekt på storleken på strukturen är vanligtvis åtminstone exponentiellt.

Anteckningar

↑ Genomgång av resultat fram till 1990: Graham, R .; Rothschild, B. & Spencer, JH (1990), Ramsey Theory (2:a upplagan), New York: John Wiley and Sons, ISBN 0-471-50046-1 .
↑ Ramsey, FP Om ett problem med formell logik // Proc . London Math. soc. Serie 2. - 1930. - Vol. 30 . - s. 264-286 . - doi : 10.1112/plms/s2-30.1.264 .
↑ van der Waerden, B. L. Beweis einer Baudetschen Vermutung (tyska) // Nieuw. Båge. Wisk.. - 1927. - Bd. 15 . - S. 212-216 .
↑ Hales A., Jewett R. Regelbundenhet och positionsspel (eng.) // Trans. amer. Matematik. Soc.. - 1963. - Vol. 106 . - S. 222-229 . - doi : 10.2307/1993764 . Arkiverad från originalet den 19 januari 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 > Arkiverad från februari 19, 2019 på Wayback Machine .

Litteratur

Martin Gardner . Kapitel 17. Ramsey-teori // Från Penrose-plattor till starka chiffer = Penrose-plattor till Trapdoor-chiffer från engelska. Yu. A. Danilova. - M .: Mir , 1993. - S. 288-308. — 416 sid. — 10 000 exemplar. — ISBN 5-03-001991-X .

Länkar

Ramsey teori