|
Discrete mathematics and mathematical cybernetics
Multidimensional threshold matrices and extremal matrices of order $2$
A. A. Taranenko Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
Abstract:
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.
Keywords:
multidimensional matrix, extremal matrix, threshold matrix, selfdual Boolean function.
Received April 3, 2023, published November 14, 2023
Citation:
A. A. Taranenko, “Multidimensional threshold matrices and extremal matrices of order $2$”, Sib. Èlektron. Mat. Izv., 20:2 (2023), 1052–1063
Linking options:
https://www.mathnet.ru/eng/semr1628 https://www.mathnet.ru/eng/semr/v20/i2/p1052
|
Statistics & downloads: |
Abstract page: | 28 | Full-text PDF : | 19 | References: | 14 |
|