|
Intelligent systems. Theory and applications, 2018, Volume 22, Issue 2, Pages 53–81
(Mi ista18)
|
|
|
|
This article is cited in 2 scientific papers (total 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.
Citation:
I. B. Kazakov, “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”, Intelligent systems. Theory and applications, 22:2 (2018), 53–81
Linking options:
https://www.mathnet.ru/eng/ista18 https://www.mathnet.ru/eng/ista/v22/i2/p53
|
Statistics & downloads: |
Abstract page: | 153 | Full-text PDF : | 161 | References: | 16 |
|