Эргодичность центральных мер на пространстве путей в графе Юнга — Фибоначчи

Рассмотрим слова над алфавитом {1,2} с данной суммой цифр n. Как известно, их количество есть число Фибоначчи Fn+1 (F0 = 0, F1 = 1, Fk+2 = Fk+1 +Fk), и это самая распространённая комбинаторная интерпре- тация чисел Фибоначчи. Также можно думать о разбиениях полосы 2 × n на домино 1 × 2 и 2 × 1, сопоставляя двойки парам горизонтальных домино, а единицы вертикальным домино.
Введём на этом множестве слов частичный порядок: будем говорить, что слово x предшествует слову y, если после удаления общего суффикса в слове y остаётся не меньше двоек, чем в слове x остаётся цифр.
Это действительно частичный порядок, более того, соответствующее ча- стично упорядоченное множество является модулярной решёткой, извест- ной как решётка Юнга – Фибоначчи.
Графом Юнга – Фибоначчи (он изображён на рисунке выше) называют диаграмму Хассе этой решётки. Это градуированный граф, который мы представляем растущим снизу вверх начиная с пустого слова. Градуиров- кой служит функция суммы цифр. Опишем явно, как устроены ориентиро- ванные рёбра. Рёбра “вверх” из данного слова x ведут в слова, получаемые из x одной из двух операций:
2

1. заменить самую левую единицу на двойку;
2. вставить единицу левее чем самая левая единица.
Этот граф помимо модулярности является 1-дифференциальным, то есть для каждой вершины исходящая степень на 1 превосходит входящую степень.
Изучение градуированного графа Юнга – Фибоначчи было иницииро- вано в 1988 году одновременно и независимо такими математиками, как Ричард Стенли [9] и Сергей Владимирович Фомин [7].
Причина интереса к нему в том, что существует всего две 1-дифференциальных модулярных решётки, вторая — это решётка диаграмм Юнга, имеющая ключевое значение в теории представлений симметрической группы.
Центральные вопросы о градуированных графах касаются центральных мер на пространстве (бесконечных) путей в графе. Эта точка зрения после- довательно развивалась в работах Анатолия Моисеевича Вершика, к недав- нему обзору которого [4] и приводимой там литературе мы отсылаем чита- теля.
Среди центральных мер выделяют те, которые являются пределами мер, индуцированных путями в далёкие вершины — так называемую границу Мартина графа.
Граница пространства путей графа Юнга – Фибоначчи изучалась в ра- боте Фредерика Гудмана и Сергея Васильевича Керова (2000) [5].
Они использовали алгебраический формализм Окады [6].
Как следует из самого определения, асимптотический вопрос о грани- це напрямую связан с перечислительным вопросом о числе путей между двумя вершинами графа. Отметим важную общую работу С. В. Фомина [8] о перечислении путей в градуированных графах, в которой приводит- ся ряд общих тождеств и указывается связь помимо прочего с обобщением алгоритма Робинсона – Шенстеда – Кнута .
Гудман и Керов обходятся без явных формул для числа путей, хотя, как указал автору Павел Павлович Никитин, из их рассуждений и можно их извлечь — но количество слагаемых оказывается экспоненциальным по длине меньшего из слов. Формула с полиномиальным числом слагаемых была получена в работе [1], (сокращённая версия которой опубликована как [2]). Ниже используются ссылки на оба текста.
Керов и Гудман доказали, что список интересующих нас центральных мер исчерпывается следующими мерами:
1) Мера Планшереля: мера множества путей, проходящих через данную вершину v, равна d(ε,v)2 , где d(u, v) – количество путей “вниз” из v в
u.
n!
2) Меры μ{wi′}, параметризующиеся некоторой бесконечной последова- тельностью вершин графа Юнга–Фибоначчи. Нам удобнее другое эк- вивалентное определение в терминах некоторого бесконечного слова w (содержащего “достаточно мало” двоек) и числа β ∈ (0, 1]. См. по- дробнее Лемму 1.
3

Доказательство эргодичности меры Планшереля было получено Керо- вым и Гнединым [3]. Оно основано на следующей Лемме: мера Планшереля сосредоточена на путях, вершины которых содержат “достаточно много” двоек. Мы доказываем аналогичное утверждение для остальных мер μw,β, откуда стандартным рассуждением получается эргодичность.
Основной результат первой части этой работы — Теорема 2 и ей След- ствия 5 и 6. Во второй части статьи Следствия 5 и 6 используются “как чёр- ный ящик” для доказательства Теорем 3 и 4. Из Теорем 3 и 4 станадартным рассуждением получается главный результат данной работы – Следствие 14.