This article is cited in 2 papers

The structure of a graph induced on the set of permutations $S_n$ by an error model of a covert channel based on packet permutations

I. B. Kazakov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The paper I.B. Kazakov, "Encoding in a covert channel of packet permutations" introduced a number of error models for codes over sets of permutations. Such error models induce graph structure on sets of permutations. Our research is focused on properties of these graphs. We show that the graphs consist of layers of independent sets; the layer that contains the given permutation is determined by the number of edges in the characteristic graph of the permutation. We estimate vertex degrees in the layers of the graph $(S_n)^2$ and use this estimate to bound the cardinality of an error-correcting kayer-based code. After that we develop a number of aids that allow to obtain upper bounds of code cardinality. We introduce the notions of symmetric layers and graph partitions and decompose $S_n$ for some values of into prisms and into graph products, i.e. generalised prisms. We also embed the graph $S_n$ into $E_{\frac {n(n-1)}2}$. Finally establish a connection between sizes of subgroups $H\subset S_n$ and presence of $n$-step permutations in these subgroups.

Keywords: permutations, graph structure, error-correcting code.