Структура графа на множестве перестановок $S_n$, задаваемая моделью ошибки в скрытом канале перестановки пакетов

Статья посвящена изучению структуры графа, порождаемой на множестве перестановок моделью ошибки канала перестановки пакетов, введенной в работе И.Б. Казакова "Кодирование в скрытом канале перестановки пакетов". Установлено, что граф можно разделить на слои, являющиеся независимыми множествами. Введено понятие характеристического графа перестановки и доказано, что номер слоя определяется числом его ребер. Получен результат о степенях вершин слоя в $(S_n)^2$, и на основании его дана оценка мощности конструируемого послойного кода. Разработан инструментарий для получения верхних оценок мощности кодов. Введены понятия симметрического слоя и разбиения графа. Приведены конкретные примеры разбиения $S_n$ на призмы, а также на произведения графов — обобщение понятия призмы. Построено вложение в $E_{\frac {n(n-1)}2}$, $S_n$ оказывается ограничением $E_{\frac {n(n-1)}2}$. Получен побочный результат алгебраического характера, связывающий размер подгруппы $H \subset S_n$ и содержание в ней $n$-шаговых перестановок.