Vikipedio:Projekto matematiko/Teoremo de Ramsey

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Teoremo de Ramsey
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

Ĉi tiu artikolo iras enen teknika (detaloj, detalas) sufiĉe rapide. Por malmulte _gentler_ enkonduko vidi Teorio de Ramsey.

En kombinatoriko, Teoremo de Ramsey ŝtatoj (tiu, ke, kiu) en koloranta granda plena grafeo (tio estas simpla grafeo, kie rando trakonektas ĉiu paro de verticoj), unu estos trovi plenumi (subgrafeoj, subgrafeas) ĉiuj de la sama koloro. En preciza (propozicio, frazo, ordono), por (ĉiu, iu) paro de pozitiva (entjeroj, entjeras) (r,s), tie ekzistas entjero R(r,s) tia (tiu, ke, kiu) por (ĉiu, iu) plena grafeo sur R(r,s) verticoj, kies randoj estas kolorita (ruĝa, legita) aŭ blua, tie ekzistas ĉu plenumi subgrafeo sur r verticoj kiu estas tute blua, aŭ plenumi subgrafeo sur s verticoj kiu estas tute (ruĝa, legita). Ĉi tie R(r,s) signifas entjero (tiu, ke, kiu) dependas sur ambaŭ r kaj s.

Teoremo de Ramsey estas fundamenta rezulto en kombinatoriko. La unua versio de ĉi tiu rezulto estis (pruvita, pruvis) per F. P. Ramsey-a. Ĉi tiu iniciatis la kombina teorio, nun (nomita, vokis) Teorio de Ramsey, (tiu, ke, kiu) (strebas, kandidatas) reguleco _amid_ afekcio: ĝeneralaj kondiĉoj por la ekzisto de (substrukturoj, substrukturas) kun regulaj propraĵoj. En ĉi tiu aplika ĝi estas demando de la ekzisto de homogena (subaroj, subaras), tio estas, (subaroj, subaras) koneksaj randoj de nur unu koloro.

Vastigaĵo de ĉi tiu teoremo aplikas al (ĉiu, iu) finia nombro de koloroj, iom ol (justa, ĵus) du. Pli detale, la teoremaj ŝtatoj (tiu, ke, kiu) por (ĉiu, iu) donita nombro de (koloroj, koloras, kolorigas) c, kaj (ĉiu, iu) donita (entjeroj, entjeras) n₁,...,n_c, estas nombro, R(n₁, ..., n_c; c), tia (tiu, ke, kiu) se la randoj de plena grafeo de (mendi, ordo) R(n₁, ..., n_c; c) estas kolorigita kun c malsama (koloroj, koloras, kolorigas), tiam por iu mi inter 1 kaj c, ĝi devas enhavi plenumi subgrafeo de (mendi, ordo) n_mi kies randoj estas ĉiu koloro mi. La speciala okazo pli supre havas c = 2 (kaj n₁ = r kaj n₂ = s).

Enhavo

1 Ekzemplo: R(3,3;2)=6
2 Pruvo de la teoremo
3 Ramsey-aj nombroj
4 (Vastigaĵoj, Vastigaĵas) de la teoremo
5 Malfinia Teorio de Ramsey
6 Malfinia versio (implicas, enhavas) la finia
7 Vidi ankaŭ
8 Ekstera (ligoj, ligas)

[redaktu] Ekzemplo: R(3,3;2)=6

2-koloriganta de K_5 sen _monochromatic_ K_3

Supozi la randoj de plena grafeo sur 6 verticoj estas kolorita (ruĝa, legita) kaj blua. (Preno, Preni) vertico v. Estas 5 randoj incida al v kaj (do, tiel) (per la faka principo) almenaŭ 3 de ilin devas esti la sama koloro. Sen malprofito de universaleco ni povas alpreni almenaŭ 3 de ĉi tiuj randoj, trakonektanta al verticoj r, s kaj t, estas blua. (Se ne, interŝanĝi (ruĝa, legita) kaj blua en kio sekvas.) Se (ĉiu, iu) de la randoj (r, s), (r, t), (s, t) estas ankaŭ blua tiam ni havi tute blua triangulo. Se ne, tiam tiuj tri randoj estas ĉiuj (ruĝa, legita) kaj ni havi kun tute (ruĝa, legita) triangulo. Ekde ĉi tiu argumento (laboroj, laboras) por (ĉiu, iu) koloranta (ĉiu, iu) K₆ enhavas _monochromatic_ K₃ kaj pro tio (tiu, ke, kiu) R(3,3;2) ≤ 6. La populara versio de ĉi tiu estas (nomita, vokis) la teoremo de amikoj kaj fremduloj.

(Alterna, Alterni) pruvo (laboroj, laboras) per duopa kalkulo. Ĝi iras kiel sekvas. Grafo la nombro de (mendita, ordita) (triopoj, triopas) de verticoj x, y, z tia (tiu, ke, kiu) la rando (_xy_) estas (ruĝa, legita) kaj la rando (_yz_) estas blua. Unue, (ĉiu, iu) donita vertico estos esti la mezo de ĉu 0×5=0, 1×4=4 aŭ 2 &(tempoj, tempas); 3 = 6 tia (triopoj, triopas). Pro tio estas maksimume 6×6=36 tia (triopoj, triopas). Due, por (ĉiu, iu) ne-_monochromatic_ triangulo (_xyz_), tie ekzistas precize du tia (triopoj, triopas). Pro tio estas maksimume 18 ne-_monochromatic_ trianguloj. Pro tio estas almenaŭ 2 _monochromatic_ trianguloj.

Male, ĝi estas ebla al 2-koloro K₅ sen kreanta (ĉiu, iu) _monochromatic_ K₃, montranta (tiu, ke, kiu) R(3,3;2) > 5. La unika koloriganta estas montrita dekstren. Tial R(3,3;2) = 6.

[redaktu] Pruvo de la teoremo

Ni pruvi la teoremo por la 2-koloro (kesto, okazo), per indukto sur r + s. Ĝi estas klara de la difino (tiu, ke, kiu) por ĉiuj n, R(n, 1) = R(1, n) = 1. Ĉi tiu startas la indukto. Ni pruvi (tiu, ke, kiu) R(r, s) ekzistas per trovanta eksplicita baro por ĝi. Per la indukta hipotezo R(r − 1, s) kaj R(r, s − 1) ekzisti.

Pretendi: R(r, s) ≤ R(r − 1, s) + R(r, s − 1): Konsideri plena grafeo sur R(r − 1, s) + R(r, s − 1) verticoj. (Preno, Preni) vertico v de la (grafikaĵo, grafeo) kaj konsideri du (subgrafeoj, subgrafeas) M kaj N kie vertico w estas en M se kaj nur se (v, w) estas blua kaj estas en N alie.

Nun |M| ≥ R(r − 1, s) aŭ |N| ≥ R(r, s − 1), denove per la faka principo. En la antaŭa (kesto, okazo) se M havas (ruĝa, legita) K_s tiam (do, tiel) faras la originala (grafikaĵo, grafeo) kaj ni estas (finita, finpretigita). Alie M havas blua K_r−1 kaj (do, tiel) M unio {v} havas blua K_r per difino de M. La lasta (kesto, okazo) estas analoga.

Tial la pretendi estas vera kaj ni havi (plenumita, plenumis) la pruvo por 2 koloroj. Ni nun pruvi la rezulto por la ĝenerala (kesto, okazo) de c koloroj. La pruvo estas denove per indukto, ĉi tiu tempo sur la nombro de koloroj c. Ni havi la rezulto por c = 1 (bagatele) kaj por c = 2 (pli supre). Nun estu c > 2.

Pretendi: R(n₁, ..., n_c; c) ≤ R(n₁, ..., n_c−2, R(n_{c− 1}, n_c; 2); c − 1)

Pruvo: La dekstra flanko de la neegalaĵo ekzistas per indukta hipotezo. Konsideri (grafikaĵo, grafeo) sur ĉi tiuj multaj verticoj kaj kolora ĝi kun c koloroj. Nun 'iri akromatopsia' kaj (ŝajnigi, simuli) (tiu, ke, kiu) c − 1 kaj c estas la sama koloro. Tial la (grafikaĵo, grafeo) estas nun (c − 1)-koloris. Per la indukta hipotezo, ĝi enhavas ĉu K_n_{_mi} _monochromatically_ koloris kun koloro mi por iu 1 ≤ mi ≤ (c − 2) aŭ K_R(n_{_c−1,n_c;2)}-koloris en la 'malklariĝis koloro'. En la antaŭa (kesto, okazo) ni estas (finita, finpretigita). En la lasta (kesto, okazo), ni reakiri nia (aspekto, celilo) denove kaj vidi de la difino de R(n_c−1, n_c; 2) ni devas havi ĉu (c − 1)-_monochrome_ K_n_{_c−1} aŭ c-_monochrome_ K_{_{n_{_c}}}. En ĉu (kesto, okazo) la pruvo estas plenumi.

[redaktu] Ramsey-aj nombroj

La nombroj R(r,s) en Teoremo de Ramsey (kaj ilia (vastigaĵoj, vastigaĵas) al pli ol du koloroj) estas sciata kiel Ramsey-aj nombroj. Supera baro por R(r,s) povas esti ekstraktita de la pruvo de la teoremo, kaj alia (argumentoj, argumentas) doni subaj baroj. Tamen, estas vasta breĉo inter la plej striktaj subaj baroj kaj la plej striktaj superaj baroj. (Sekve, Sinsekve), estas tre kelkaj nombroj r kaj s por kiu ni scii la akurata valoro de R(r,s). Komputanta suba baro L por R(r,s) kutime postulas eksponanta blua/(ruĝa, legita) koloranta de la (grafikaĵo, grafeo) K_L−1 sen blua K_r subgrafeo kaj ne (ruĝa, legita) K_s subgrafeo. Serĉanta ĉiuj _colourings_ de (grafikaĵo, grafeo) K_n iĝas kompute ege malfacila kiel n (multigas, pligrandiĝoj, pligrandiĝas); la nombro de _colourings_ kreskas super-eksponente.

Je la tempo de skribanta, (eĉ, ebena, para) la akurata valoro de R(5,5) estas nekonato, kvankam ĝi estas sciata al (mensogi, kuŝi) inter 43 kaj 49 (inkluziva), kaj, (mezuranta, drinkejanta, baranta) breĉo en teorio, ĝi estas (kredeble, verŝajne) la (kesto, okazo) (tiu, ke, kiu) la akurata valoro de R(6,6) estos resti nekonato eterne.

"Imagi alilandana forto, vaste pli pova ol ni (landanta, bienanta) sur Tero kaj postulanta la valoro de R(5, 5) aŭ ili estos detrui nia planedo. En (tiu, ke, kiu) (kesto, okazo), ni devus marŝalaj ĉiuj niaj komputiloj kaj ĉiuj nia (matematikistoj, matematikistas) kaj provi al trovi la valoro. Sed supozi, anstataŭe, (tiu, ke, kiu) ili demandita por R(6, 6), ni devus provi al detrui la alilandanoj". - (Paŭlo, Bono) _Erd_ős

R(r,s) por (valoroj, valoras) de r kaj s supren al 10 estas montrita en la (baremo, tabelo, tablo) pli sube. Kie la akurata valoro estas nekonato, la (baremo, tabelo, tablo) (listoj, listas) la plej bona sciata (baroj, baras). R(r,s) por (valoroj, valoras) de r kaj s malpli ol 3 estas donita per R(1,s) = 1 kaj R(2,s) = s por ĉiuj (valoroj, valoras) de s. La norma katastro sur la evoluo de Ramsey-a nombro esplori havas estas skribita per _Stanisław_ _Radziszowski_, ankaŭ la matematikisto kiu fundamenti R(4,5).

r,s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40–43
4	1	4	9	18	25	35–41	49–61	56–84	69–115	92–149
5	1	5	14	25	43–49	58–87	80–143	101–216	121–316	141–442
6	1	6	18	35–41	58–87	102–165	111–298	127–495	169–780	178–1171
7	1	7	23	49–61	81–143	111–298	205–540	216–1031	232–1713	< 2826
8	1	8	28	56–84	101–216	127–495	216–1031	282–1870	317–3583	< 6090
9	1	9	36	69–115	121–316	169–780	232–1713	317–3583	565–6588	580–12677
10	1	10	40–43	92–149	141–442	178–1171	< 2826	< 6090	580–12677	798–23556

[redaktu] (Vastigaĵoj, Vastigaĵas) de la teoremo

La teoremo povas ankaŭ esti etendita al _hypergraphs_. m-_hypergraph_ estas (grafikaĵo, grafeo) kies "randoj" estas aroj de m verticoj - en normala (grafikaĵo, grafeo) rando estas aro de 2 verticoj. La plena (propozicio, frazo, ordono) de Teoremo de Ramsey por _hypergraphs_ estas (tiu, ke, kiu) por (ĉiu, iu) (entjeroj, entjeras) m kaj c, kaj (ĉiu, iu) (entjeroj, entjeras) n₁,...,n_c, estas entjero R(n₁,...,n_c;c,m) tia (tiu, ke, kiu) se la _hyperedges_ de plenumi m-_hypergraph_ de (mendi, ordo) R(n₁,...,n_c;c,m) estas kolorigita kun c malsama (koloroj, koloras, kolorigas), tiam por iu mi inter 1 kaj c, la _hypergraph_ devas enhavi plenumi sub-m-_hypergraph_ de (mendi, ordo) n_mi kies _hyperedges_ estas ĉiu koloro mi. Ĉi tiu teoremo estas kutime (pruvita, pruvis) per indukto sur m, la '_hyper_Eco' de la (grafikaĵo, grafeo). La bazo (kesto, okazo) por la pruvo estas m=2, kiu estas akurate la teoremo pli supre.

[redaktu] Malfinia Teorio de Ramsey

Plui rezulto, ankaŭ kutime (nomita, vokis) Teoremo de Ramsey, aplikas al malfinio (grafikaĵoj, grafeoj). En ĉirkaŭteksto kie finia (grafikaĵoj, grafeoj) estas ankaŭ estante diskutis ĝi estas ofte (nomita, vokis) la "Malfinia Teoremo de Ramsey". Kiel intuicio provizis per la _pictorial_ prezento de (grafikaĵo, grafeo) estas malkreskita kiam movanta de finia al malfinio (grafikaĵoj, grafeoj), (teoremoj, teoremas) en ĉi tiu areo estas kutime frazita en aro-teoria terminologio.

Teoremo: Estu X esti iu kalkuleble malfinia aro kaj koloro la eroj de X⁽ⁿ⁾ (la (subaroj, subaras) de X de amplekso n) en c malsamaj koloroj. Tiam tie ekzistas iu malfinia subaro M de X tia (tiu, ke, kiu) la amplekso n (subaroj, subaras) de M ĉiuj havi la sama koloro.

Pruvo: La pruvo estas donita por c=2. Ĝi estas facila al pruvi la teoremo por ajna nombro de koloroj uzanta 'koloro-blindeco' argumento kiel pli supre. La pruvo estas per indukto sur 'n', la amplekso de la (subaroj, subaras). Por n = 1,la (propozicio, frazo, ordono) estas ekvivalento al (diranta, dirante) (tiu, ke, kiu) se vi fendi malfinia aro enen du aroj, unu de ilin estas malfinio. Ĉi tiu estas evidenta. Alprenanta la teoremo estas vera por n ≤ r, ni pruvi ĝi por n = r + 1. Donita 2-koloranta de la (r + 1)-ero (subaroj, subaras) de malfinia aro X, elekti ero a₀ de X ((tononomo, noto, noti) (tiu, ke, kiu) en la (propozicio, frazo, ordono) de la teoremo ni insistita (tiu, ke, kiu) X estis kalkuleble malfinio, se X estis ĝenerala malfinia aro ni devus postuli la aksiomo de elekto al fari ĉi tiu elekto) kaj estu Y = X\a₀. Ni tiam konkludi 2-koloranta de la r-ero (subaroj, subaras) de Y, per (justa, ĵus) adicianta a₀ al ĉiu r-era subaro (al preni (r+1)-era subaro de X). Per la indukta hipotezo, tie ekzistas malfinia subaro Y₁ en Y tia (tiu, ke, kiu) ĉiu r-era subaro de Y estas kolorita la sama koloro en la konkludis koloranta. Pro tio ni havi elektita ero a₀ kaj subaro Y₁ tia (tiu, ke, kiu) ĉiu (r+1)-era subaro de X konsistanta de a₀ kaj r eroj de Y₁ havas la sama koloro. Daŭranta en ĉi tiu ni povas elekti a₁ de Y₁ kaj subaro Y₂ de Y₁ kun la samaj propraĵoj. Ni fino kun vico {a₀,a₁,a₂,...} tia (tiu, ke, kiu) la koloro de ĉiu (r + 1)-era subaro (a_mi(1),a_mi(2),...,a_mi(r+1)) kun mi(1) < mi(2) < ... < mi(r + 1) dependas nur sur la valoro de mi(1). Plui, estas malfinie multaj (valoroj, valoras) de mi(n) tia (tiu, ke, kiu) ĉi tiu koloro estos esti la sama. Preni ĉi tiuj a_mi(n)'s al preni la deziris _monochromatic_ aro.

[redaktu] Malfinia versio (implicas, enhavas) la finia

Ĝi estas facila al (dedukti, konkludi) la finia Teoremo de Ramsey de la malfinio unu uzanta pruvo per kontraŭdiro. Supozi la finia Ramsey-a Teoremo estas malvera. Tiam tie ekzistas $c, n, T$ tia (tiu, ke, kiu) por ĉiu entjero $k$ , tie ekzistas $c$ -koloranta de $[k] (n)$ , sen _monochromatic_ aro de amplekso $T$ . Estu $C k$ signifi la $c$ -_colourings_ de $[k] (n)$ sen _monochromatic_ aro de amplekso $T$ .

Por (ĉiu, iu) entjero k, donita (ĉiu, iu) koloranta en $C k + 1$ , se ni limigi la koloranta al $[k] (n)$ (per ignoranta la koloro de ĉiuj aroj enhavanta $k + 1$ ), tiam ni preni koloranta en $C k$ . Difini $C^{1}_k$ al esti la _colourings_ en $C k$ kiu estas limigoj de _colourings_ en $C k + 1$ . Ekde $C k + 1$ estas ne malplena, nek estas $C^{1}_k$ .

Simile, la limigo de (ĉiu, iu) koloranta en $C^{1}_{k+1}$ estas en $C^{1}_k$ , permesanta ni al difini $C^{2}_k$ kiel la aro de ĉiuj tiaj limigoj, kiu ni povas vidi estas ne malplena. Daŭri farante (do, tiel), difinanta $C^{n}_k$ por ĉiuj (entjeroj, entjeras) $n, k$ .

Nun, por (ĉiu, iu) entjero $k$ , $C_k\supseteq C^1_k\supseteq C^2_k\supseteq \dots$ , kaj ĉiu aro estas ne-malplena. Plue, $|C_k|\le c^{\frac{k!}{n!(k-n)!}}$ , kaj de ĉi tie $C k$ estas finia. Ĝi sekvas (tiu, ke, kiu) la komunaĵo de ĉiuj de ĉi tiuj aroj devas esti ne-malplena. Estu $D_k=C_k\cap C^1_k\cap C^2_k\cap \dots$ . Tiam ĉio en $D k$ estas la limigo de io en $D k + 1$ . Pro tio ni povas starti kun io en $D n$ , kaj _unrestrict_ al io en $D n + 1$ , kaj daŭri farante (do, tiel), al preni koloranta de $\mathbb N^{(n)}$ sen _monochromatic_ aro de amplekso $T$ .

Se ni preni taŭgi topologia starpunkto, ĉi tiu argumento iĝas norma kompakteca argumento montranta (tiu, ke, kiu) la malfinia versio de la teoremo (implicas, enhavas) la finia versio.