Потапов В. Н.
Многомерные латинские битрейды

Подмножество k-значного n-мерного гиперкуба называется унитрейдом (объединенным битрейдом), если мощности его пересечений с одномерными гранями гиперкуба принимают только два значения 0 и 2. Унитрейд называется двудольным (гамильтоновым), если соответствующий ему подграф гиперкуба является двудольным (гамильтоновым). Пара долей двудольного унитрейда называется n-мерным латинским битрейдом. Для троичного n-мерного гиперкуба определено число различных унитрейдов и получена экспоненциальная нижняя оценка числа неэквивалентных латинских битрейдов. Перечислены все возможные n-мерные латинские битрейды мощности, меньшей чем 2ⁿ⁺¹.

Подмножество k-значного n-мерного гиперкуба называется t-кратным МДР-кодом, если оно пересекается с каждой одномерной гранью гиперкуба ровно по t элементам. Симметрическая разность двух однократных МДР-кодов является двудольным унитрейдом. Каждая из компонент соответствующего латинского битрейда является свитчинговой компонентой одного из этих МДР-кодов. Исследованы вопросы о мощностях компонент МДР-кодов и возможности получения латинских битрейдов заданной мощности из МДР-кодов. Кроме того, доказано, что любой МДР-код вкладывается в гамильтонов двукратный МДР-код.

Potapov V. N.
Multidimensional Latin bitrades

A subset of the n-dimensional k-valued hypercube is a unitrade or united bitrade whenever the size of its intersections with the one-dimensional faces of the hypercube takes only the values 0 and 2. A unitrade is bipartite or Hamiltonian whenever the corresponding subgraph of the hypercube is bipartite or Hamiltonian. The pair of parts of a bipartite unitrade is an n-dimensional Latin bitrade. For the n-dimensional ternary hypercube we determine the number of distinct unitrades and obtain an exponential lower bound on the number of inequivalent Latin bitrades. We list all possible n-dimensional Latin bitrades of size less than 2ⁿ⁺¹.

A subset of the n-dimensional k-valued hypercube is a t-fold MDS code whenever the size of its intersection with each one-dimensional face of the hypercube is exactly t. The symmetric difference of two single MDS codes is a bipartite unitrade. Each component of the corresponding Latin bitrade is a switching component of one of these MDS codes. We study the sizes of the components of MDS codes and the possibility of obtaining Latin bitrades of a size given from MDS codes. Furthermore, each MDS code is shown to embed in a Hamiltonian 2-fold MDS code.

Полный текст статьи / Full texts:

• PDF file
• PostScript file