RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2023, том 20, выпуск 2, страницы 1052–1063 (Mi semr1628)

Дискретная математика и математическая кибернетика

Multidimensional threshold matrices and extremal matrices of order $2$

A. A. Taranenko

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Аннотация: The paper is devoted to multidimensional $(0,1)$-matrices extremal with respect to containing a polydiagonal (a fractional generalization of a diagonal). Every extremal matrix is a threshold matrix, i.e., an entry belongs to its support whenever a weighted sum of incident hyperplanes exceeds a given threshold.
Firstly, we prove that nonequivalent threshold matrices have different distributions of ones in hyperplanes. Next, we establish that extremal matrices of order $2$ are exactly selfdual threshold Boolean functions. Using this fact, we find the asymptotics of the number of extremal matrices of order $2$ and provide counterexamples to several conjectures on extremal matrices. Finally, we describe extremal matrices of order $2$ with a small diversity of hyperplanes.

Ключевые слова: multidimensional matrix, extremal matrix, threshold matrix, selfdual Boolean function.

УДК: 519.142.1

MSC: 15B34

Поступила 3 апреля 2023 г., опубликована 14 ноября 2023 г.

Язык публикации: английский

DOI: 10.33048/semi.2023.20.065



© МИАН, 2024