Центральные меры в графах, связанных с графом Юнга

В начале мы напомним про градуированные графы и граф Юнга, а затем определим граф Юнга с прыжками.
Определение. Пусть 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).
a) b)
Рис. 1: Диаграммы, соответствующие разбиению числа 9
Определим ðððð ðððð (рис. 2) следующим образом: вершинами яв- ляются всевозможные диаграммы Юнга (в том числе пустая, которая
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, а ребро соответствует тому, что соответствующие последовательности
3

перемежаются. Но при изучении графа Юнга с прыжками возникают существенные специфические сложности, что видно из дальнейшего.