Флип-графы Рассмотрим облако из n точек на плоскости. Это облако точек можно триангулировать несколькими способами. Определим флип-граф так: множество вершин - это множество всех возможных триангуляций нашего облака точек, две триангуляции смежные, если они отличаются на одно ребро. На картинках есть примеры для n=5 и n=6 точек в выпуклом положении. Количество вершин во флип-графе растет экспоненциально от n. Можно задать следующий вопрос: если случайно блуждать по флип-графу полиномиальное время, придем ли мы в примерно случайное состояние (то есть, верно ли, что mixing time соответствующей цепи Маркова полиномиально от n)? Для облаков точек общего вида это открытый вопрос. Для точек в выпуклом положении ответ "да". Mixing time можно оценить через спектр матрицы смежности флип-графа. На последнем графике - спектральный зазор от n для флип-графов трех семейств облаков точек: точек в выпуклом положении, случайно накиданных точек, и точек в квадратной сетке.