Ramseys teorem

Ramseys teorem är ett kombinatoriskt teorem om mängdpartitioner, formulerat och bevisat av den engelske matematikern Frank Ramsey 1930 [1] . Det förekommer i litteraturen i olika formuleringar. Detta teorem markerade början av Ramsey teorin .

Formuleringar

Mängdsteoretisk formulering

Specialfall N ( p , q , r )

Låt , och vara naturliga tal , och . $sid$ $q$ $r$ $p,\;q\geqslant r$

Sedan finns det ett nummer med följande egenskap: om alla -element-delmängder av -elementmängden är godtyckligt uppdelade i två disjunkta familjer och , så finns det antingen en -element-undermängd av mängden vars alla -elementundermängder ingår i , eller så finns det en -element-undermängd, alla -element-undermängder vars undermängder ingår i . $N=N(p,\;q,\;r)$ $r$ $N$ $S$ $\alfa$ $\beta$ $sid$ $S$ $r$ $\alfa$ $q$ $r$ $\beta$

Allmänt fall

Låt uppsättningen ha element. Betrakta dess -undermängder , beteckna helheten av alla dessa undermängder , ordnade -partitioner , nummer som definierar partitionen . $S$ $N$ $r$ $r\geqslant 1$ $P_{r}(S)$ $t$ ${\displaystyle P_{r}(S)=A_{1}\cup A_{2}\cup \ldots \cup A_{t))$ ${\displaystyle q_{1},\ q_{2},\ \ldots ,\ q_{t))$ ${\displaystyle 1\leqslant r\leqslant q_{1},\;q_{2},\;\ldots ,\;q_{t))$

Sedan för varje ordnad -partition av mängden finns det ett minimalt antal så att om , så finns det en delmängd av mängden , det vill säga en sådan delmängd av mängden vars alla -undermängder finns i [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$

Anges på grafteorin

För alla naturliga tal innehåller valfri färgning av kanterna på en tillräckligt stor komplett graf en komplett subgraf med hörn för en viss färg . I synnerhet, för alla och , innehåller en tillräckligt stor komplett graf med tvåfärgad (svart och vit) färgning antingen en komplett svart vertexsubgraf eller en komplett vit vertexsubgraf. $c$ ${\displaystyle n_{1},\ n_{2},\ \ldots ,\ n_{c))$ $c$ $n_{i}$ $i$ $r$ $s$ $r$ $s$

Ramsey nummer

Det minsta antal som detta gäller kallas Ramsey-numret. $R(r,\;s)$

Till exempel innebär jämlikhet att det å ena sidan i varje tvåfärgsfärgning av en komplett graf finns en enfärgad triangel, och å andra sidan att hela grafen tillåter en tvåfärgsfärgning utan enfärgad trianglar. $R(3,\;3)=6$ $K_{6}$ $K_{5}$

I allmänhet, för färgfärgning, används notationen för det minsta antalet hörn som säkerställer att det finns någon färg . $c$ $R(n_{1},\;n_{2},\;\ldots ,\;n_{c})$ $K_{n_{i))$ $i$

Bevis för Ramseys teorem

Tvåfärgat fall

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

Bevis. Låt oss bevisa att använda metoden för matematisk induktion på . $r+s$

basen för induktion. , eftersom en graf med 1 vertex kan betraktas som en komplett graf av vilken färg som helst. $R(n,\;1)=R(1,\;n)=1$

Induktionsövergång . Låt och . Tänk på en komplett svart-vit vertexgraf. Ta en godtycklig vertex och beteckna med och händelseuppsättningarna i de svarta respektive vita subgraferna. Eftersom i vertexgrafen, enligt Dirichlet-principen (kombinatorik) , antingen , eller . $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)$

Låt . Då finns antingen i (och därför i hela grafen) vitt , som kompletterar beviset, eller så finns det svart i , som tillsammans med bildar svart . Ärendet behandlas på liknande sätt. $|M|\geqslant R(r-1,\;s)$ $M$ $K_{s}$ $M$ $K_{r-1}$ $v$ ${\displaystyle K_{r))$ $|N|\geqslant R(r,\;s-1)$

Kommentar. Om båda är jämna kan ojämlikheten förstärkas: . $R(r-1,\;s)$ $R(r,\;s-1)$ $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)-1$

Bevis . Anta att båda är jämna. Ställ in och betrakta en svartvit graf av hörn. Om graden av det -:e hörnet i den svarta subgrafen är jämnt, enligt handskakningslemma . Eftersom det är udda måste det finnas en jämn . För visshetens skull antar vi att det är jämnt. Beteckna med och de hörn som faller in på vertex 1 i de svarta och vita subgraferna. Då är båda jämna. Enligt Dirichlet-principen (kombinatorik) , antingen , eller . Eftersom det är jämnt och udda kan den första ojämlikheten förstärkas, så antingen , eller . $p=R(r-1,\;s)$ $q=R(r,\;s-1)$ $t=p+q-1$ $t$ $d_{i}$ $i$ ${\displaystyle \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$

Antag . Då innehåller antingen subgrafen som genereras av uppsättningen vitt och beviset är komplett, eller så innehåller det svart , som tillsammans med vertex 1 bildar svart . Ärendet behandlas på liknande sätt. $|M|\geqslant p=R(r-1,\;s)$ $M$ $K_{s}$ $K_{r-1}$ ${\displaystyle K_{r))$ $|N|\geqslant q=R(r,\;s-1)$

Ett fall med fler färger.

Lemma 2. Om , då $c>2$ $R(n_{1},\;\ldots ,\;n_{c})\leqslant R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_ {c-1},\;n_{c})).$

Bevis. Betrakta en graf över hörn och färglägg dess kanter med färger. Vi kommer tillfälligt att överväga färgerna och en färg. Då blir grafen -färgad. Enligt definitionen av nummer innehåller en sådan graf antingen, för någon färg , såsom något färgat av den vanliga färgen och . I det första fallet är beviset komplett. I det andra fallet returnerar vi de tidigare färgerna och noterar att enligt definitionen av Ramsey-numret innehåller grafen med komplett vertex antingen färger eller färger , så påståendet är helt bevisat. $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$ ${\displaystyle 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$

Lemma 1 antyder att Ramsey siffrorna för . Av detta, utifrån Lemma 2, följer att för eventuella . Detta bevisar Ramsey-satsen. $c=2$ $R(n_{1},\;\ldots ,\;n_{c})$ $c$

Betydelser av Ramsey-tal

Värdetabell

Det finns mycket lite data för vid [3] . Följande värdetabell för Ramsey-tal för är hämtad från Radzishevskys tabell [4] , data är från 2020. $N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;t)$ $t>2$ $N(q_{1},\;q_{2};\;2)$

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

Asymptotiska uppskattningar

Av ojämlikheten följer att $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)$

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

I synnerhet följer den övre gränsen härifrån ( Erdős , Sekeres )

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

Slutsats

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

erhållits av Erdős 1947 med hans probabilistiska metod .

Moderna uppskattningar är från Spencer respektive 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}.

Uppenbarligen förbättrar dessa uppskattningar de första resultaten något och ligger inte nära varandra.

Erdős trodde att i nödfall kan mänskligheten fortfarande hitta , men inte . $R(5,\;5)$ $R(6,\;6)$

Uppskattningen som Kim hittade 1995 är också känd . I kombination med skattningen sätter denna ojämlikhet ordningen för tillväxten av . $R(3,\;t)\geqslant \left({\frac {1}{162}}+o(1)\right){\frac {t^{2}}{\ln {t} }}$ ${\displaystyle R(3,\;t)\leqslant (1+o(1)){\frac {t^{2}}{\ln {t))))$ $R(3,\;t)=\Theta \left({\frac {t^{2}}{\ln {t}}}\right)$

Variationer och generaliseringar

Erdős-Rado-satsen är en generalisering av Ramsey-satsen till oräkneliga mängder.

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.

Anteckningar

↑ F. P. Ramsey Om ett problem med formell logik. - Proc. London Math. Soc.", 2nd ser., 30 (1930), sid. 264-286
↑ Rybnikov, 1972 , sid. 93.
↑ Rybnikov, 1972 , sid. 96.
↑ Stanisław Radziszowski. Small Ramsey Numbers (engelska) // The Electronic Journal of Combinatorics. - 2017. - 3 mars. — ISSN 1077-8926 . Arkiverad från originalet den 29 maj 2017. (revision 15)

Länkar

Prasolov V. V. Ramseys teorem (se analysen av problem 22.7)
Ramsey teori

Litteratur

Rybnikov K.A. Introduktion till kombinatorisk analys. - Moscow State University, 1972.