1 Введение. Основные понятия 2
2 Пути в графе Юнга с прыжками из пустой диаграммы в прямоугольную 4
3 Пути в графе Юнга с прыжками из маленьких диаграмм в прямоугольную 9
3.1 Вычисление числа путей, стартующих из двуклеточных диаграмм 10
3.2 Вычисление числа путей, стартующих из трехклеточных диаграмм и некоторых четырехклеточных 12
4 Другой взгляд на перечисление путей с помощью определителя 15
4.1 Примеры использования строчечного определителя 17
5 Центральные меры на графе Юнга с прыжками 20
5.1 Основные понятия 20
5.2 Критерий вырожденности мер, порождаемых прямоугольниками 21
5.3 Центральные меры на графе прыжков двустрочечных диаграмм 23
Список литературы 26
В начале мы напомним про градуированные графы и граф Юнга, а затем
определим граф Юнга с прыжками.
Определение. Пусть V # некоторое (обычно счётное) множество
вершин, E # множество рёбер, каждому из которых сопоставлена
упорядоченная пара (u, v) ∈ V 2 вершин (разным рёбрам может соот-
ветствовать одна и та же пара вершин, то есть допускаются крат-
ные рёбра). Вершина u называется началом такого ребра uv, v # кон-
цом, также говорим, что u # непосредственный предок v, а v # непо-
средственный потомок u. Потомками u будем называть все вершины, в
которые можно добраться от u, а предками все вершины, из которых
можно дойти в u. Ориентированный граф G = (V, E) будем называть
градуированным, если существует отображение
rank : V → Z
v → |v|
такое, что |v| = |u| + 1 для любого ребра uv ∈ E(G). Величина |v| назы-
вается рангом вершины v.
Разбиением числа n называется последовательность λ =
(λ1, λ2, . . . , λk) целых неотрицательных чисел такая, что λ1 > λ2 >
. . . > λk и |λ| := ∑i λi = n. Разбиения вида (λ1, λ2, . . . , λk) и
(λ1, λ2, . . . , λk, 0, . . . , 0) отождествляются. Каждому разбиению λ со-
ответствует диаграмма Юнга # набор клеток (единичных квадратиков),
составленных в строки длины λ1, λ2, . . . и выравненных по левому
краю. В качестве примера рассмотрим соответствие диаграммам двух
разбиений числа 9 в сумму 4+4+1 (рис. 1a) и в сумму 4+3+2 (рис. 1b).
Рис. 1: Диаграммы, соответствующие разбиению числа 9
Определим граф Юнга (рис. 2) следующим образом: вершинами яв-
ляются всевозможные диаграммы Юнга (в том числе пустая, которая
соответствует разбиению числа 0). Рангом диаграммы является коли-
чество клеток в ней. Между диаграммами λ и μ проведено ребро, если
|λ| = |μ| − 1 и μi > λi для всех i.
Рис. 2: Начало графа Юнга
Теперь определим граф с прыжками для градуированного графа G.
Множеством вершин теперь будет являться V (G) × {1, 2, . . .}. Назовем
вершины множества Vi = V (G) × {i} # i-м уровнем графа с прыжками.
Между вершинами λ ∈ Vi и μ ∈ Vi+1 в соседних уровнях проведено реб-
ро, если в исходном графе G существовал путь из λ в μ (одна вершина
без рёбер # это тоже путь). Полученный граф также является градуи-
рованным, ранг вершин множества Vi равен i.
Для графа Юнга мы также можем определить граф Юнга с прыж-
ками. Будем говорить, что диаграмма λ вложена в диаграмму μ и обо-
значать λ ⊂ μ, если μi > λi для всех i. Иными словами, если из λ в μ
есть путь в графе Юнга.
Замечание. У графа Юнга с прыжками степень каждой вершины бес-
конечна, но если рассмотреть индуцированный подграф на множестве
диаграмм с не более чем m клетками, то степень у каждой из вершин
будет конечной.
Из многих изученных градуированных графов (см. напр. [8, 12]) граф
Юнга с прыжками больше всего напоминает граф Гельфанда – Цетлина,
соответствующий ветвелению унитарных групп: вершины k-го уровня со-
ответствуют неубывающим целочисленным последовательностям длины
k, а ребро соответствует тому, что соответствующие последовательности
перемежаются. Но при изучении графа Юнга с прыжками возникают
существенные специфические сложности, что видно из дальнейшего.
