Михаил Блудов, "Сложности графов и топологические фокусы"

доклад на кружочке 9 апреля 2025. Алиса и Боб играют в игру. Боб загадал граф G на n вершинах. Алиса хочет узнать, верно ли, что граф, который загадал Боб, обладает свойством P (например, является ли граф связным)? Алиса может задать вопрос Бобу: "Верно ли, что ребро e лежит в твоем графе G?". Сложность свойства P — это минимальное количество вопросов, за которые Алиса гарантированно узнает, обладает ли граф G свойством P. Свойство P называют уклончивым, если Алисе, для разрешения своей дилемы, нужно задать n(n-1)/2 вопросов (то есть задать вопрос про каждое ребро). Свойство графов P назовем убывающим, если оно остается верным для графа при удалении из него любого ребра. Например, свойство быть несвязным — убывающее. Гипотеза Карпа гласит, что все нетривиальные убывающие свойства уклончивы. Гипотеза разрешена (внезапно) для случая n=p^k, то есть когда количество вершин есть степень простого! Доказательство использует топологические понятия и методы, некоторыми из них мы воспользуемся как черным ящиком, а некоторые (например, коллапсируемость симплициального комплекса) будут вполне приятными и комбинаторными.