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 kN 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
|