WisFaq!

Is een kleuringsprobleem terug te voeren naar een eindige versie?

Beste meneer/mevrouw,

Stel dat er, als je met r kleuren kleurt, noodzakelijkerwijs een monochromatische oplossing bestaat voor een bepaalde vergelijking. Moet er dan een f(r) Î bestaan, zodat een r-kleuring van S, met S = {1, 2, .., f(r)}, een monochromatische oplossing impliceert?
Bij voorbaat dank!

Wouter van Doorn
3-4-2010

Antwoord

Het antwoord is ja. Dat volgt uit het compactheidsprincipe. Als er voor elke N een kleuring k_N van {1,2,...,N} met r kleuren is, zonder monochrome oplossing dan is er een deelrij die naar een kleuring k van convergeert (hier gebruik je de compactheid van r). Voor deze kleuring bestaat dan geen monochrome oplossing.

Zie Compactness Theorm (Wikipedia) [http://en.wikipedia.org/wiki/Compactness_theorem]

kphart
3-4-2010