\require{AMSmath}

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
Student universiteit - zaterdag 3 april 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)

kphart
zaterdag 3 april 2010

©2001-2024 WisFaq