On a Property of a Three-Dimensional Matrix. (30th October 2013)

• Record Type: Journal Article
• Authors: Blokh, David
• Other Names: Lai Hong J. Academic Editor.
• Is Part Of: Journal of discrete mathematics. Volume 2013(2013)
• Publication Date: 2013-10-30
• Subjects: Computer science -- Mathematics -- Periodicals; Computer science -- Mathematics; Periodicals; 511.1
• DOI: 10.1155/2013/797249
• Languages: English
• ISSNs: 2090-9837

Abstract

Abstract : Let S n be the symmetrical group acting on the set 1, 2, …, n and x, y ∈ S n . 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 ( i 1, x ( i 1 ), y ( i 1 ) ), ( i 2, x ( i 2 ), y ( i 2 ) ), ( i 3, x ( i 3 ), y ( i 3 ) ) ∈ W such that | i 1 - x ( i 2 ) | ≤ 1, | i 1 - y ( i 3 ) | ≤ 1, and | x ( i 2 ) - y ( i 3 ) | ≤ 1 . The application of this theorem to the three-dimensional assignment problem is considered.