Stelling van Van der Waerden
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 als bewijs van het vermoeden van Baudet.[1][2] 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.
Stelling
[bewerken | brontekst bewerken]Voor elke twee positieve gehele getallen en bestaat er een getal zodanig dat, als men de gehele getallen 1 tot en met in klassen verdeelt, er minstens een klasse is die een rekenkundige rij van lengte bevat. Het kleinste getal waarvoor dit geldt noemt men het Van der Waerden-getal
Van der Waerden-getallen
[bewerken | brontekst bewerken]Van der Waerden bewees wel dat deze getallen bestaan, maar zijn bewijs gaf niet aan hoe ze berekend konden worden. Er is nog geen formule bekend waarmee ze berekend kunnen worden, en er zijn slechts weinig Van der Waerden-getallen exact bekend.
Het geval is triviaal: voor elke (er is slechts 1 klasse, namelijk die van de positieve gehele getallen, en die bevat elke rekenkundige rij ).
Ook de Van der Waerden-getallen zijn eenvoudig te bepalen. Er geldt , want zodra een tweede getal in een klasse ondergebracht wordt, bevat deze klasse een rekenkundige rij van twee elementen; en voor klassen gebeurt dit ten laatste bij het getal . Dit is niets anders dan het duiventilprincipe.
Voor met twee klassen zijn alleen de eerste vijf Van der Waerden-getallen bekend:
Elwyn Berlekamp vond voor deze getallen als een priemgetal is[3] de volgende ondergrens:
Bovengrens
[bewerken | brontekst bewerken]Van der Waerden leidde in zijn bewijs een bovengrens voor af, die echter zeer snel stijgt (even snel als de Ackermannfunctie) en wellicht veel hoger is dan de reële waarde.[4] Later werd die verbeterd, maar bleef nog steeds enorm groot. De beste gekende bovengrens, bepaald door Timothy Gowers in 2001[5], is:
Externe links
[bewerken | brontekst bewerken]- ↑ B.L. van der Waerden. "Beweis einer Baudetschen Vermutung." Nieuw Archief voor Wiskunde, Serie 2, (1927), vol. 15, blz; 212-216.
- ↑ Pyth.eu Hart, P.K. Het Vermoeden van Baudet 4 mei 2019. Geraadpleegd op 23 juli 2019.
- ↑ Berlekamp, E. (1968). A construction for partitions which avoid long arithmetic progressions. Canadian Mathematical Bulletin 11: 409–414. DOI: 10.4153/CMB-1968-047-7.
- ↑ Paul Erdös. "Some Problems and Results on Combinatorial Number Theory." Annals of the New York Academy of Sciences (1989), vol. 576, nr. 1, blz. 132-145. DOI:10.1111/j.1749-6632.1989.tb16392.x
- ↑ Gowers, Timothy (2001). A new proof of Szemerédi's theorem. Geom. Funct. Anal. 11 (3): 465–588. DOI: 10.1007/s00039-001-0332-9.