|
Sibirskii Matematicheskii Zhurnal, 2011, Volume 52, Number 2, Pages 384–392
(Mi smj2204)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Clique matchings in the $k$-ary $n$-dimensional cube
V. N. Potapovab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Mechanics and Mathematics Department, Novosibirsk, Russia
Abstract:
A clique matching in the $k$-ary $n$-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the $k$-ary $n$-dimensional cube can be expressed as the $k$-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the $k$-ary $n$-dimensional cube for an arbitrary positive integer $k$ as $n\to\infty$.
A perfect clique matching is called precise if each two-dimensional face of the hypercube includes a sole one-dimensional face of the clique matching. Precise clique matchings are particular cases of H-designs. We prove that for the existence of precise clique matchings in the $k$-ary $n$-dimensional cube it is necessary that $k=2m$ and $n=4m$ for some positive integer m. We propose a construction of precise clique matchings for $k=2^t$ and $n=2^{t+1}$ with an arbitrary positive integer $t$.
Keywords:
perfect matching, clique matching, permanent, MDS code, H-design.
Received: 07.04.2010 Revised: 24.12.2010
Citation:
V. N. Potapov, “Clique matchings in the $k$-ary $n$-dimensional cube”, Sibirsk. Mat. Zh., 52:2 (2011), 384–392; Siberian Math. J., 52:2 (2011), 303–310
Linking options:
https://www.mathnet.ru/eng/smj2204 https://www.mathnet.ru/eng/smj/v52/i2/p384
|
Statistics & downloads: |
Abstract page: | 281 | Full-text PDF : | 78 | References: | 47 | First page: | 1 |
|