• Март 12, Март 19 (образовательный семинар), 2007
  • Андрей Ромащенко
  • Аннотация
  • Рассматривается задача о замощениях плоскости плитками из некоторого конечного набора (tiling), в которых разрешены нарушения локальных правил согласованности плиток в редких (случайно выбранных) местах. Мы построим набор плиток (tiling set), для которого всякое замощение плоскости, согласованное со случайным множеством локальных ошибок (а) близко к апериодическому замощению плоскости без ошибок, и (б) далеко от любой периодической конфигурации.

    Алгоритмическая часть доказательства использует идею само-моделирующихся автоматов Дж. фон Неймана. Теоретико-вероятностная чать рассуждения основана на лемме Гача–Грэя о разделении множества случайных ошибок на изолированные острова разных рангов.