RUS  ENG
Full version
SEMINARS

2023-ary quasigroups and related topics
March 30, 2018 11:00, Novosibirsk, Sobolev Institute of Mathematics, room 115


Some results on matrices that are extremal for existence of polyplex

A. A. Taranenko

Abstract: A polyplex of size $ M $ is a nonnegative multidimensional matrix in which the sum of all elements is equal to $ M $, and the sum of elements in any hyperface is not greater than one. A polyplex is said to be complete if its size is equal to its order $ n $. An extremal matrix for polyplexes is a multidimensional $ (0,1) $ matrix, in which there is no complete polyplex, but when any zero element is replaced by a single full polyplex, there is.
A $ d \ times n $ -table $ \ Lambda $ with non-negative elements is called a covering by hyperplanes of the $ d $ -dimensional $ (0,1) $ -matrix $ A $ if $ a _ {\ alpha} = 1 $ is true $ \ sum \ limits_ {i = 1} ^ d \ lambda_ {i, \ alpha_i} \ geq 1 $. The covering size of the hyperplanes $ \ Lambda $ is equal to the sum of all its elements.
It is easy to prove that the maximum size of a polyplex in a matrix is ​​equal to the minimal size of the covering of the matrix by hyperplanes. It is shown that any extremal matrix for can be encoded by an optimal covering by facets. Some necessary and sufficient conditions are obtained to cover with hyperplanes an extremal matrix. Also, several hypotheses have been put forward on the properties of extremal matrices.


© Steklov Math. Inst. of RAS, 2024