|
This article is cited in 2 scientific papers (total in 2 papers)
Coding Theory
On the cardinality spectrum and the number of latin bitrades of order $3$
D. S. Krotov, V. N. Potapov Sobolev Institute of Mathematics, Siberian Branch
of the Russian Academy of Sciences, Novosibirsk, Russia
Abstract:
By a (Latin) unitrade of order $k$, we call a subset of vertices of the Hamming graph $H(n, k)$ that intersects any maximal clique at either $0$ or $2$ vertices. A bitrade is a bipartite unitrade, i.e., a unitrade that can be split into two independent subsets. We study the cardinality spectrum of bitrades in the Hamming graph $H(n, k)$ with $k = 3$ (ternary hypercube) and the growth of the number of such bitrades as $n$ grows. In particular, we determine all possible small (up to $2.5\cdot 2^n$) and large (from $14\cdot 3^{n-3}$) cardinalities of bitrades of dimension n and prove that the cardinality of a bitrade takes only values equivalent to $0$ or $2^n$ modulo $3$ (this result can be treated in terms of a ternary Reed–Muller type code). A part of the results are valid for an arbitrary $k$. For $k = 3$ and $n\to\infty$ we prove that the number of nonequivalent bitrades is not less than $2^{(2/3-o(1))n}$ and not greater than $2^{\alpha^n}$, $\alpha < 2$ (the growth order of the double logarithm of this number remains unknown). Alternatively, the studied set $B_n$ of bitrades of order $3$ can be defined as follows: $B_0$ consists of three rationals $- 1, 0, 1$; $B_n$ consists of ordered triples $(a, b, c)$ of elements from $B_{n-1}$ such that $a+b+c=0$.
Keywords:
Latin bitrades, unitrades, Reed–Muller codes, combinatorial configurations, Boolean functions.
Received: 24.12.2018 Revised: 19.09.2019 Accepted: 12.11.2019
Citation:
D. S. Krotov, V. N. Potapov, “On the cardinality spectrum and the number of latin bitrades of order $3$”, Probl. Peredachi Inf., 55:4 (2019), 52–75; Problems Inform. Transmission, 55:4 (2019), 343–365
Linking options:
https://www.mathnet.ru/eng/ppi2303 https://www.mathnet.ru/eng/ppi/v55/i4/p52
|
Statistics & downloads: |
Abstract page: | 294 | Full-text PDF : | 30 | References: | 26 | First page: | 4 |
|