On the Cardinality Spectrum and the Number of Latin Bitrades of Order 3

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·2ⁿ) and large (from 14·3ⁿ⁻³) cardinalities of bitrades of dimension n and prove that the cardinality of a bitrade takes only values equivalent to 0 or 2ⁿ 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 → ∞ we prove that the number of nonequivalent bitrades is not less than 2⁽²/^3−o(1))n and not greater than \(2^{\alpha^n}\), α < 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₀ 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.