Потапов В. Н.
Кликосочетания в k-значном n-мерном кубе

Кликосочетанием в k-значном n-мерном кубе (гиперкубе) называется набор непересекающихся одномерных граней. Кликосочетание называется совершенным, если оно покрывает все вершины гиперкуба. Показано, что число совершенных кликосочетаний в k-значном n-мерном кубе выражается как k-мерный перманент массива смежности некоторого гиперграфа. Вычислен порядок логарифма числа совершенных кликосочетаний в k-значном n-мерном кубе при любом натуральном k и n → ∞.
Совершенное кликосочетание называется точным, если в каждой двумерной грани гиперкуба лежит ровно одна одномерная грань из кликосочетания. Точные кликосочетания являются частным случаем дизайнов Ханани. Доказано, что для существования точного кликосочетания в k-значном n-мерном кубе необходимо, чтобы k = 2m и n = 4m для некоторого натурального m. Предложена конструкция точных кликосочетаний при k = 2 ^t, n = 2 ^t+1 для любого натурального t.

Potapov V. N.
Clique matchings in the k-ary n-dimensional cube

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 → ∞.
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.

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

• PDF file
• PostScript file