2009-06: Assignability of 3-dimensional totally tight matrices

DIMACS TR: 2009-06

Assignability of 3-dimensional totally tight matrices

Authors: Endre Boros, Vladimir A. Gurvich, Igor E. Zverovich and Wei Shao

ABSTRACT
A 3-dimensional totally tight matrix A = (aijk) has the property that every 2 * 2 submatrix has a constant line [a row or a column]. We prove that all such matrices are assignable, that is it is possible to assign a label to each of the axial planes so that every aijk is equal to at least one of the corresponding labels. The result can be easily extended to the case of multi-dimensional matrices.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-06.pdf

DIMACS Home Page