Андрей Михайлович Райгородский

Раскраски графов и топология

А.М. Райгородский планирует провести 1 занятие.

Напомним, что хроматическое число графа — это минимальное количество цветов, в которые можно так покрасить его вершины, чтобы концы любого его ребра имели разные цвета. Задача отыскания хроматического числа графа крайне сложна. Один из наиболее красивых и, надо заметить, неожиданных подходов к ее решению был предложен в 70-е годы XX века. Этот подход основан на применении одной глубокой теоремы, которую обычно связывают с именем известного польского тополога К. Борсука. Замечательно то, что и сама теорема, и основная идея ее применения допускают совершенно элементарное изложение. На занятии мы обсудим упомянутые вопросы, а также поговорим о дальнейших направлениях исследования. Занятие рассчитано в первую очередь на студентов, но оно будет доступно и школьникам.

Organization Committee e-mail:
dubna@mccme.ru