Графы-экспандеры и их применения

Рассказ будет посвящен графам-экспандерам, их свойствам и применениям. В широком смысле, (мульти)граф является экспандером, если любая его небольшая область имеет сравнительно большую окрестность. Мы обсудим непосредственные применения экспандеров в таких задачах, как построение эффективных сетей и самоисправляющих кодов, и «экономия» случайных битов в рандомизированных алгоритмах. Кроме этого, мы поговорим про связь расширительной величины графа с его спектральными характеристиками, и случайные блуждания в экспандерах.