De stelling van Erdös en Szekeres

Gegeven is een rij van n^2+1 verschillende getallen. Hieruit kan je zeker ofwel een momotoon dalende ofwel een monotoon stijgende deelrij van n+1 elementen kiezen.

erdos

 

 

szekeres

 

 

 

 

 

 

 

Bekijken we een eenvoudig voorbeeld met n=3. We hebben dus een rij van 10 verschillende getallen en we moeten een monotoon dalende of monotoon stijgende deelrij vinden van 4 elementen.  In 2,6,13,4,8,7,3,50,25,10 zit de deelrij 2,6,8,50 die monotoon stijgend is. Met een rij van 9 elementen lukt het niet om een monotoon dalende of monotoon stijgende deelrij te vinden van 4 elementen. Neem bijvoorbeeld 7,8,9,4,5,6,1,2,3.

Als we de positie van een element in de rij als x-coördinaat en het element van de rij als y-coördinaat gebruiken kunnen we aan de stelling een meetkundige interpretatie geven: zo er is bijvoorbeeld een pad met 4 stijgende verbindingslijnen te vinden bij 17 gegeven punten:

kerstboom018