TY - JOUR

T1 - О комбинаторной структуре графов Рози

AU - Дубашинский, М.Б.

PY - 2012

Y1 - 2012

N2 - Пусть S0m – множество всех неприводимых перестановок чисел {1,…,m} (m≥3). На множестве S0m определены отображения индукции Рози a и b. Для перестановки π∈S0m обозначим через R(π) орбиту перестановки π при действиях отображений a и b, снабженную структурой ориентированного графа в соответствии с действием отображений a и b на этом множестве: ребра этого графа относятся к одному из двух типов a и b. Будем говорить, что граф R(π) есть дерево, составленное из циклов, если любой простой цикл в этом графе состоит из ребер одного типа. Равносильная формулировка этого условия такова: граф R∗(π), двойственный к графу R(π), есть дерево. Основной результат настоящей работы состоит в следующем: если граф R(π) перестановки π∈S0m есть дерево, составленное из циклов, то множество R(π) содержит перестановку π0:i↦m+1−i, i=1,…,m. Доказан обратный результат: граф R(π0) есть дерево, составленное из циклов; при этом в явном виде установлена структура этого графа.

AB - Пусть S0m – множество всех неприводимых перестановок чисел {1,…,m} (m≥3). На множестве S0m определены отображения индукции Рози a и b. Для перестановки π∈S0m обозначим через R(π) орбиту перестановки π при действиях отображений a и b, снабженную структурой ориентированного графа в соответствии с действием отображений a и b на этом множестве: ребра этого графа относятся к одному из двух типов a и b. Будем говорить, что граф R(π) есть дерево, составленное из циклов, если любой простой цикл в этом графе состоит из ребер одного типа. Равносильная формулировка этого условия такова: граф R∗(π), двойственный к графу R(π), есть дерево. Основной результат настоящей работы состоит в следующем: если граф R(π) перестановки π∈S0m есть дерево, составленное из циклов, то множество R(π) содержит перестановку π0:i↦m+1−i, i=1,…,m. Доказан обратный результат: граф R(π0) есть дерево, составленное из циклов; при этом в явном виде установлена структура этого графа.

M3 - статья

VL - 277

SP - 57

EP - 73

JO - ТРУДЫ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН

JF - ТРУДЫ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН

SN - 0371-9685

ER -