Niezapomniana konstrukcja Thuego dowodzi istnienia dowolnie długich
ciągów bez powtórzeń nad jedynie trzema symbolami. Ciąg x_1,...,x_k
jest wybrany ze zbiorów (list) L_1,...,L_k, jeśli s_i należy do L_i
dla każdego i. Wciąż nieznana jest najmniejsza liczba naturalna N
taka, że z dowolnego ciągu list o rozmiarze N można wybrać ciąg bez
powtórzeń. Podczas referatu zaprezentuję elementarny argument
dowodzący N <= 4. Dowód i jego ekspozycja jest pod wielkim wpływem
dopiero co opublikowanego przez Mosera i Tardosa nowego
algorytmicznego dowodu Lokalnego Lematu Lovasza.
|
|