Аннотация:
Полиплекс размера $M$ – это неотрицательная многомерная матрица, в которой сумма всех элементов равна $M$, а сумма элементов в любой гиперграни не больше единицы. Полиплекс называется полным, если его размер равен его порядку $n$. Экстремальная матрица для полиплексов – это многомерная $(0,1)$-матрица, в которой нет полного полиплекса, но при замене любого нулевого элемента на единичный полный полиплекс возникает.
$d \times n$-таблица $\Lambda$ с неотрицательными элементами называется покрытием гиперплоскостями $d$-мерной $(0,1)$-матрицы $A$ если для любого $a_{\alpha} =1$ верно $\sum\limits_{i=1}^d \lambda_{i, \alpha_i} \geq 1$. Размер покрытия гиперплоскостями $\Lambda$ равен сумме всех его элементов.
Несложно доказать, что максимальный размер полиплекса в матрице равен минимальному размеру покрытия матрицы гиперплоскостями. Показано, что любая экстремальная матрица может быть закодирована оптимальным покрытием гипергранями. Получены некоторые необходимые и достаточные условия для того, чтобы покрытие гиперплоскостями задавало экстремальную матрицу. Также выдвинуто несколько гипотез о свойствах экстремальных матриц.
|
