RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2023 Volume 20, Issue 2, Pages 1052–1063 (Mi semr1628)

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.

UDC: 519.142.1

MSC: 15B34

Received April 3, 2023, published November 14, 2023

Language: English

DOI: 10.33048/semi.2023.20.065



© Steklov Math. Inst. of RAS, 2024