Stelling van Van der Waerden

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De stelling van Van der Waerden, genoemd naar Bartel Leendert van der Waerden, is een stelling uit de combinatoriek en een van fundamentele resultaten uit de Ramsey-theorie. Van der Waerden publiceerde ze in 1927.[1] De stelling zegt dat, wanneer men de positieve gehele getallen in eindig vele klassen verdeelt, minstens een van deze klassen een rekenkundige rij van willekeurige lengte bevat.

Meer formeel luidt de stelling: voor elke positieve gehele getallen r en k bestaat er een getal N zodanig dat, wanneer men de gehele getallen 1 tot en met N in r klassen verdeelt, er minstens een klasse is die een rekenkundige rij van lengte k bevat. Het kleinste getal N waarvoor dit geldt noemt men het Van der Waerden-getal W(r,k).

Van der Waerden-getallen[bewerken]

Van der Waerden bewees wel dat deze getallen bestaan maar zijn bewijs gaf niet aan hoe ze konden berekend worden. Er is nog geen formule gekend waarmee ze kunnen berekend worden, en er zijn slechts weinig Van der Waerden-getallen exact gekend.

Het geval r=1 is triviaal: W(1,k)=k voor elke k (er is slechts 1 klasse, namelijk die van de positieve gehele getallen, en die bevat elke rekenkundige rij 1,2,...k).

Ook de Van der Waerden-getallen W(r,2) zijn eenvoudig te bepalen. W(r,2) = r+1: zodra we een tweede getal in een klasse onderbrengen, bevat deze klasse een rekenkundige rij van twee elementen; en voor r klassen gebeurt dit ten laatste bij het getal r+1. Dit is niet meer of minder dan het duiventilprincipe.

Voor r=2 met twee klassen zijn enkel de eerste Van der Waerden-getallen gekend: W(2,2) = 5; W(2,3) = 9; W(2,4) = 35; W(2,5) = 178; W(2,6) = 1132. Elwyn Berlekamp vond voor deze getallen de volgende ondergrens:

wanneer p een priemgetal is.[2]

Bovengrens[bewerken]

Van der Waerden leidde in zijn bewijs een bovengrens voor W(r,k) af, die echter zeer snel stijgt (even snel als de Ackermannfunctie) en wellicht veel hoger is dan de reële waarde.[3] Later werd die verbeterd, maar bleef nog steeds enorm groot. De beste gekende bovengrens, bepaald door Timothy Gowers in 2001[4], is:

Externe links[bewerken]