Игорь Пак

Предположим, имеется $n$ чисел $(a_1,...,a_n)$, которые требуется отсортировать. Предположим также, что имеется информация о сравнениях между некоторыми парами этих чисел, заданная как частичный порядок (poset). Можно ли придумать “оптимальную сортировку”, которая принимает во внимание этот частичный порядок и сортирует за наименьшее количество дополнительных сравнений? Оказывается, это сделать можно (с точностью до константы) — это теорема Кана и Сакса (Kahn–Saks theorem, 1984).

Доказательство, которое я расскажу, использует удивительную связь с геометрией многогранников, геометрические неравенства Брунна–Минковского и теорему Грюнбаума из функционального анализа. Заранее знать всего этого не требуется, я по порядку всё расскажу, ничего особенного и не используя.