Про формулу Лефшеца у меня в планах ещё два рассказа, но пока я их пишу — напишу чуть-чуть про другое.

Вот есть проблема 4 красок. Ну и наверное, все знают, что она решена, и решена с заметным применением компьютера для перебора вариантов.

А что, если поменять формулировку вопроса? Раньше у картографа был один набор из 4 цветов, и он пытается раскрасить все страны в эти цвета так, чтобы не было соседних стран, раскрашенных одним цветом.

Представим себе, что сначала картограф спрашивает у каждой страны набор из k цветов, которые эту страну устраивают. А то раскрасишь тут Тридевятое королевство в оранжевый цвет, а король возмутится, что это-де цвет любимой виверны кого-то из его родственников, которая у него все пряники как-то раз сожрала. И всё, несдобровать картографу.

Так что лучше уж опросить королей и королев заранее — а потом бедный картограф попытается раскрасить карту так, чтобы каждая страна была окрашена в один из выбранных ею цветов, и опять же, чтобы соседние страны не были окрашены одинаково.

Ну и вопрос тот же самый — какое число вариантов цветов k нужно спрашивать картографу, чтобы уж точно получилось раскрасить карту?

Собственно, совершенно необязательно работать именно с картой — такой же вопрос можно задать про любой граф. А именно:

Определение. Граф называется k-выбираемым (k-choosable), если для любого способа сопоставить каждой его вершине набор из k «разрешённых» цветов его вершины можно раскрасить так, чтобы каждая вершина была раскрашена в один из соответствующих цветов, и соседние вершины были бы раскрашены в разные цвета.

Рассматривать такие вопросы предложили в конце 1970-ых Визинг и Эрдёш, Рубин и Тэйлор; см. P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs и В. Г. Визинг, Раскраска вершин графа в предписанные цвета, 1976.

На первый взгляд (особенно, если начинать с задачи четырёх красках) может показаться, что это лишнее усложнение: ведь если наборы цветов в разных вершинах разные, казалось бы, раскрасить будет даже проще? Не будет ли наихудшей ситуацией, если списки цветов во всех вершинах просто одинаковы (ну и тогда наименьшее k будет просто хроматическим числом графа)?

Но оказывается, что нет — наименьшее k может быть (сильно) больше хроматического числа!