Ramsey-theorie: verschil tussen versies

Verwijderde inhoud Toegevoegde inhoud

In de regel

Huidige versie van 5 mei 2023 om 21:18

De Ramsey-theorie maakt deel uit van de combinatoriek, een deelgebied van de discrete wiskunde. Ramsey-theorie gaat over de vraag hoeveel elementen uit een met een zekere wiskundige structuur uitgeruste verzameling gekozen moeten worden, opdat dezelfde wiskundige structuur in een deelverzameling teruggevonden kan worden, waarbij tevens aan een bepaalde eigenschap wordt voldaan. De theorie is genoemd naar de vroegtwintigste-eeuwse Britse wiskundige Frank Ramsey. Het centrale thema van de theorie is, dat in grote systemen altijd patronen zullen opduiken.^[1]

Het postvakprincipe

Een bekend principe uit de combinatoriek^[2] betreft het zogenaamde postvakprincipe.

Dit principe stelt dat er ten minste twee ballen in één bak terechtkomen bij het verdelen van $n$ ballen over $n-1$ bakken $(n>1).$ Meer algemeen geldt dat er een bak met ten minste $a$ ballen moet bestaan na het toewijzen van $n(a-1)+1$ ballen aan $n$ bakken $(n>0,a>0).$ Het postvakprincipe wordt vaak ook zo geformuleerd: Na toekenning van $a$ ballen aan $n$ bakken zal er een bak zijn met (naar boven afgerond) ten minste $a/n$ ballen $(n>0,a>0).$

Het postvakprincipe laat ons zien dat een willekeurige structuur (een willekeurige verdeling van ballen over een vast aantal bakken) vanaf een bepaalde omvang (een bepaald aantal ballen) noodzakelijkerwijs een regelmatige deelstructuur moet bevatten (een bak met minimaal een bepaald aantal ballen). De minimale omvang waarbij een regelmatige deelstructuur noodzakelijkerwijs optreedt kan in sommige gevallen (zoals in het geval van het postvakprincipe) exact berekend worden. Kortgezegd komt het erop neer dat totale chaos onmogelijk is: vanaf een bepaalde omvang moeten willekeurige structuren noodzakelijkerwijs regelmatige deelstructuren bevatten.

In de Ramsey-theorie wordt deze gedachte opgepakt en verder uitgewerkt. De Ramsey-theorie bestaat uit een collectie gelijksoortige stellingen die allemaal het bestaan van regelmatige deelstructuren aantonen in willekeurige structuren van voldoende omvang.

De centrale stelling van de Ramsey-theorie wordt ook wel de stelling van Ramsey genoemd, naar Frank P. Ramsey, die deze stelling in 1928 formuleerde en bewees. Het is feitelijk een generalisatie van het postvakprincipe. We geven hieronder de eindige versie van deze stelling.

De stelling van Ramsey

Laat $n,a_{1},\ldots ,a_{n},q>0$ gehele getallen zijn. Dan bestaat er een kleinste geheel getal $R(a_{1},\ldots ,a_{n},q)$ zodanig dat voor iedere $q$ -kleuring met kleuren $1,\ldots ,n$ van een verzameling met ten minste $R(a_{1},\ldots ,a_{n},q)$ elementen geldt dat er een $i$ bestaat en een deelverzameling met $a_{i}$ elementen waarvan alle $q$ -deelverzamelingen dezelfde kleur $i$ hebben."

Hierbij is een $q$ -deelverzameling een deelverzameling met $q$ elementen en een $q$ -kleuring van een verzameling een toewijzing van een kleur aan iedere $q$ -deelverzameling van deze verzameling.

Dat de stelling van Ramsey inderdaad een generalisatie is van het postvakprincipe kan ingezien worden door $q$ gelijk te nemen aan 1 en alle $a_{i}$ gelijk te kiezen aan eenzelfde vast getal $a>0:$

R(a,\ldots ,a,q)=n(a-1)+1

Ramsey-getallen

De getallen $R(a_{1},\ldots ,a_{n},q)$ worden wel Ramsey-getallen genoemd. Zo is $R(3,3,2)=6.$ Dit betekent dus dat een 2-kleuring met 2 kleuren van een verzameling met 6 elementen noodzakelijkerwijs een deelverzameling van drie elementen moet bevatten waarvan alle 2-deelverzamelingen dezelfde kleur hebben.

Deze uitspraak kan geïnterpreteerd worden als een uitspraak over volledige grafen: Een volledige graaf met 6 punten waarvan iedere lijn rood of blauw is, moet drie punten bevatten waarvan de onderlinge drie verbindingslijnen allemaal rood of allemaal blauw zijn. Op een feestje waar zes mensen aanwezig zijn moeten er dus drie mensen te vinden zijn die elkaar onderling kennen of elkaar onderling niet kennen.

Het is in het algemeen zeer moeilijk om Ramsey-getallen te berekenen en alleen van kleine Ramsey-getallen is dan ook de exacte waarde bekend.

Bronnen, noten en/of referenties

↑ (en) Sloman, Leila, After Nearly a Century, a New Limit for Patterns in Graphs. Quanta Magazine (2 mei 2023). Geraadpleegd op 5 mei 2023. “Its central lesson is that “you cannot create a completely chaotic system,” said Benny Sudakov, a mathematician at the Swiss Federal Institute of Technology Zurich.”
↑ Hieraan heeft de Hongaar Paul Erdős in hoge mate bijgedragen.

[1] (en) Sloman, Leila, After Nearly a Century, a New Limit for Patterns in Graphs. Quanta Magazine (2 mei 2023). Geraadpleegd op 5 mei 2023. “Its central lesson is that “you cannot create a completely chaotic system,” said Benny Sudakov, a mathematician at the Swiss Federal Institute of Technology Zurich.”

[2] Hieraan heeft de Hongaar Paul Erdős in hoge mate bijgedragen.

[1]

[2]

@@ Regel 1: / Regel 1: @@
-De '''Ramseytheorie''' maakt deel uit van de [[combinatoriek]] een deelgebied van de [[discrete wiskunde]]. Ramsey-theorie gaat over de vraag hoeveel [[element (wiskunde)|elementen]] uit een met een zekere [[wiskundige structuur]] uitgeruste [[verzameling (wiskunde)|verzameling]] gekozen moeten worden, opdat dezelfde wiskundige structuur in een [[deelverzameling]] teruggevonden kan worden, waarbij tevens aan een bepaalde eigenschap wordt voldaan. De theorie is genoemd naar de vroegtwintigste-eeuwse [[Verenigd Koninkrijk|Britse]] [[wiskundige]] [[Frank Ramsey]].
+De '''Ramsey-theorie''' maakt deel uit van de [[combinatoriek]], een deelgebied van de [[discrete wiskunde]]. Ramsey-theorie gaat over de vraag hoeveel [[element (wiskunde)|elementen]] uit een met een zekere [[wiskundige structuur]] uitgeruste [[verzameling (wiskunde)|verzameling]] gekozen moeten worden, opdat dezelfde wiskundige structuur in een [[deelverzameling]] teruggevonden kan worden, waarbij tevens aan een bepaalde eigenschap wordt voldaan. De theorie is genoemd naar de vroegtwintigste-eeuwse [[Verenigd Koninkrijk|Britse]] [[wiskundige]] [[Frank Ramsey]]. Het centrale thema van de theorie is, dat in grote systemen altijd patronen zullen opduiken.<ref>{{Citeer web |url=https://www.quantamagazine.org/after-nearly-a-century-a-new-limit-for-patterns-in-graphs-20230502/ |titel=After Nearly a Century, a New Limit for Patterns in Graphs |achternaam=Sloman |voornaam=Leila |datum=2023-05-02 |bezochtdatum=2023-05-05 |werk=Quanta Magazine |taal=en |citaat=Its central lesson is that “you cannot create a completely chaotic system,” said [[Benny Sudakov]], a mathematician at the Swiss Federal Institute of Technology Zurich.}}</ref>
 ==Het postvakprincipe==
 Een bekend principe uit de [[combinatoriek]]<ref>Hieraan heeft de Hongaar [[Paul Erdős]] in hoge mate bijgedragen.</ref> betreft het zogenaamde [[ladenprincipe|postvakprincipe]].
-Dit principe stelt dat er ten minste twee ballen in één bak terechtkomen bij het verdelen van n ballen over n-1 bakken (n>1). Meer algemeen geldt dat er een bak met ten minste a ballen moet bestaan na het toewijzen van n(a-1)+1 ballen aan n bakken (n>0,a>0). Het postvakprincipe wordt vaak ook zo geformuleerd: Na toekenning van a ballen aan n bakken zal er een bak zijn met (naar boven afgerond) ten minste a/n ballen (n>0,a>0).
+Dit principe stelt dat er ten minste twee ballen in één bak terechtkomen bij het verdelen van <math>n</math> ballen over <math>n-1</math> bakken <math>(n>1).</math> Meer algemeen geldt dat er een bak met ten minste <math>a</math> ballen moet bestaan na het toewijzen van <math>n(a-1)+1</math> ballen aan <math>n</math> bakken <math>(n>0,a>0).</math> Het postvakprincipe wordt vaak ook zo geformuleerd: Na toekenning van <math>a</math> ballen aan <math>n</math> bakken zal er een bak zijn met (naar boven afgerond) ten minste <math>a/n</math> ballen <math>(n>0,a>0).</math>
 Het postvakprincipe laat ons zien dat een willekeurige structuur (een willekeurige verdeling van ballen over een vast aantal bakken) vanaf een bepaalde omvang (een bepaald aantal ballen) noodzakelijkerwijs een regelmatige deelstructuur moet bevatten (een bak met minimaal een bepaald aantal ballen). De minimale omvang waarbij een regelmatige deelstructuur noodzakelijkerwijs optreedt kan in sommige gevallen (zoals in het geval van het postvakprincipe) exact berekend worden. Kortgezegd komt het erop neer dat totale [[Chaos (situatie)|chaos]] onmogelijk is: vanaf een bepaalde omvang moeten willekeurige structuren noodzakelijkerwijs regelmatige deelstructuren bevatten.
-In de '''Ramsey-theorie''' wordt deze gedachte opgepakt en verder uitgewerkt. De Ramsey-theorie bestaat uit een collectie gelijksoortige [[stelling (wiskunde)|stelling]]en  die allemaal het bestaan van regelmatige deelstructuren aantonen in willekeurige structuren van voldoende omvang.
+In de '''Ramsey-theorie''' wordt deze gedachte opgepakt en verder uitgewerkt. De Ramsey-theorie bestaat uit een collectie gelijksoortige [[stelling (wiskunde)|stelling]]en die allemaal het bestaan van regelmatige deelstructuren aantonen in willekeurige structuren van voldoende omvang.
-De centrale stelling van de Ramsey-theorie wordt ook wel de stelling van Ramsey genoemd (naar Frank P. Ramsey die deze stelling in 1928 formuleerde en bewees) en is feitelijk een generalisatie van het postvakprincipe. We geven hieronder de eindige versie van deze stelling.
+De centrale stelling van de Ramsey-theorie wordt ook wel de stelling van Ramsey genoemd, naar Frank P. Ramsey, die deze stelling in 1928 formuleerde en bewees. Het is feitelijk een generalisatie van het postvakprincipe. We geven hieronder de eindige versie van deze stelling.
 ==De stelling van Ramsey==
-"Laat n, a_1, ... , a_n, q > 0 gehele [[getal (wiskunde)|getal]]len zijn. Dan bestaat er een kleinste geheel getal R(a_1, ...,a_n;q) zodanig dat voor iedere q-kleuring met kleuren 1, ...,n van een verzameling met ten minste R(a_1, ...,a_n;q) elementen geldt dat er een i bestaat en  een deelverzameling met a_i elementen waarvan alle q-deelverzamelingen dezelfde kleur i hebben."
+Laat <math>n,a_1,\ldots,a_n,q>0</math> gehele [[getal (wiskunde)|getal]]len zijn. Dan bestaat er een kleinste geheel getal <math>R(a_1,\ldots,a_n,q)</math> zodanig dat voor iedere <math>q</math>-kleuring met kleuren <math>1,\ldots,n</math> van een verzameling met ten minste <math>R(a_1,\ldots,a_n,q)</math> elementen geldt dat er een <math>i</math> bestaat en een deelverzameling met <math>a_i</math> elementen waarvan alle <math>q</math>-deelverzamelingen dezelfde kleur <math>i</math> hebben."
-Hierbij is een q-deelverzameling een deelverzameling met q elementen en een q-kleuring van een verzameling een toewijzing van een kleur aan iedere q-deelverzameling van deze verzameling.
+Hierbij is een <math>q</math>-deelverzameling een deelverzameling met <math>q</math> elementen en een <math>q</math>-kleuring van een verzameling een toewijzing van een kleur aan iedere <math>q</math>-deelverzameling van deze verzameling.
-Dat de [[stelling (wiskunde)|stelling]] van Ramsey inderdaad een generalisatie is van het postvakprincipe kan ingezien worden door q gelijk te nemen aan 1 en alle a_1 t/m a_n gelijk te kiezen aan eenzelfde vast getal a>0:
+Dat de [[stelling (wiskunde)|stelling]] van Ramsey inderdaad een generalisatie is van het postvakprincipe kan ingezien worden door <math>q</math> gelijk te nemen aan 1 en alle <math>a_i</math> gelijk te kiezen aan eenzelfde vast getal <math>a>0:</math>
-R(a, ... ,a;1) = n(a-1) + 1
+:<math>R(a,\ldots,a,q) = n(a-1) + 1</math>
 ==Ramsey-getallen==
-De getallen R(a_1, ...,a_n;q) worden ook wel '''Ramsey-getallen''' genoemd. Zo is het Ramsey-getal R(3,3;2) gelijk aan 6. Dit betekent dus dat een 2-kleuring met 2 kleuren van een verzameling met 6 elementen noodzakelijkerwijs een deelverzameling van drie elementen moet bevatten waarvan alle 2-deelverzamelingen dezelfde kleur hebben.
+De getallen <math>R(a_1,\ldots,a_n,q)</math> worden wel ''Ramsey-getallen'' genoemd. Zo is <math>R(3,3,2)=6.</math> Dit betekent dus dat een 2-kleuring met 2 kleuren van een verzameling met 6 elementen noodzakelijkerwijs een deelverzameling van drie elementen moet bevatten waarvan alle 2-deelverzamelingen dezelfde kleur hebben.
 Deze uitspraak kan geïnterpreteerd worden als een uitspraak over volledige grafen: Een volledige graaf met 6 punten waarvan iedere lijn rood of blauw is, moet drie punten bevatten waarvan de onderlinge drie verbindingslijnen allemaal rood of allemaal blauw zijn. Op een feestje waar zes mensen aanwezig zijn moeten er dus drie mensen te vinden zijn die elkaar onderling kennen of elkaar onderling niet kennen.
-Het is in het algemeen zéér moeilijk om Ramsey-getallen te berekenen en van slechts weinig Ramsey-getallen is dan ook de exacte waarde bekend.
+Het is in het algemeen zeer moeilijk om Ramsey-getallen te berekenen en alleen van kleine Ramsey-getallen is dan ook de exacte waarde bekend.
-==Voetnoot==
-<references/>
+{{Appendix}}
 [[Categorie:Combinatoriek]]
 [[Categorie:Grafentheorie]]
-[[ar:نظرية رمزي]]
-[[de:Ramseytheorie]]
-[[en:Ramsey theory]]
-[[es:Teoría de Ramsey]]
-[[fa:نظریه رمزی]]
-[[fi:Ramseyn lause]]
-[[fr:Théorie de Ramsey]]
-[[he:תורת רמזי]]
-[[it:Teoria di Ramsey]]
-[[no:Ramsey-teori]]
-[[ro:Teoria lui Ramsey]]
-[[ru:Теория Рамсея]]
-[[sv:Ramseyteori]]
-[[tr:Ramsey Kuramı]]
-[[ur:ریمزی نظریہ]]