Multidimensional threshold matrices and extremal matrices of order 2

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.