On a Property of a Three-Dimensional Matrix

Abstract EN

Let Sn be the symmetrical group acting on the set 1,2,…,n and x,y∈Sn.

Consider the set W={(i,x(i),y(i))∣1≤i≤n, |i-x(i)|>1∨|i-y(i)|>1∨|x(i)-y(i)|>1}.

The main result of this paper is the following theorem.

If the number of W set entries is more than [n/3], then there exist entries (i1,x(i1),y(i1)),(i2,x(i2),y(i2)),(i3,x(i3),y(i3))∈W such that |i1-x(i2)|≤1, |i1-y(i3)|≤1, and |x(i2)-y(i3)|≤1.

The application of this theorem to the three-dimensional assignment problem is considered.