Теория графов — раздел математики, возникший на стыке комбинаторики, топологии и программирования, бурно развивающийся в последнее время. Он относительно доступен для начинающих, но в то же время содержит красивые сложные результаты и нерешенные проблемы. На просеминаре большая часть материала будет преподноситься в виде задач; будет предложено также много задач для исследования. Опыт самостоятельных исследований, который смогут приобрести участники просеминара, мотивирует их к изучению новых теорий и подскажет, как их правильно изучать.
На просеминаре будут разбираться проблемы существования вложений (с некоторыми дополнительными свойствами) графов в плоскость и в поверхности, а также их аналоги для "двумерных графов". Основная идея — применять алгебраические препятствия.
Любому студенту НМУ достаточно знаний для овладения этим курсом. Однако предполагается, что участники либо имеют опыт работы с графами, либо готовы потратить много времени и сил на приобретение такого опыта в процессе работы в просеминаре. Материал этого просеминара не пересекается с материалом спецкурса А.Б.Скопенкова прошлого семестра.
1. Классификации Маклейна-Эдкисона и Уитни узлов из графов на плоскости. Основная теорема топологии и классификация отображений графов в плоскость с непересекающимися образами. То же для пространства. Проблема классификации орнаментов.
2. Определение и примеры 2-полиэдров и континуумов. Критерии Куратовского, Халина-Юнга и Клэйтора планарности графов, двумерных полиэдров и пеановских континуумов.
3. Узкие деревья на плоскости. Теорема Мура о несчетных семействах триодов на плоскости и ее обобщения.
4. Спроектированные вложения графов в плоскость: препятствие Ван Кампена.
5. Примеры двумерных полиэдров, невложимых в R4. Препятствия Ван Кампена к вложимости графов в плоскость и двумерных полиэдров в R4. Полнота такого препятствия для плоскости и неполнота для R4.
6. Конфигурационное пространство пар различных точек (взрезанный квадрат). Препятствия взрезанного квадрата к вложимости в плоскость, в R3 и в R4. Взрезанные квадраты некоторых графов. Полнота этого препятствия для вложимости графов и пеановских континуумов в плоскость.
7. Вложимость двумерных полиэдров в R3: примеры, неполнота препятствия взрезанного квадрата, проблема алгоритмической раснознаваемости.
8.* 3-адический соленоид Виеториса-Ван Данцига как пример неполноты препятствия взрезанного квадрата к вложимости континуумов в плоскость.
