Silver Cubes

摘要

An n × n matrix A is said to be silver if, for i = 1,2,...,n, each symbol in {1,2,...,2n ? 1} appears either in the ith row or the ith column of A. The 38th International Mathematical Olympiad asked whether a silver matrix exists with n = 1997. More generally, a silver cube is a triple (K n d , I, c) where I is a maximum independent set in a Cartesian power of the complete graph K n , and $c:V(K_n^d)rightarrow {1,2,dots,d(n-1)+1}$ is a vertex colouring where, for v ∈ I, the closed neighbourhood N[v] sees every colour. Silver cubes are related to codes, dominating sets, and those with n a prime power are also related to finite geometry. We present here algebraic constructions, small examples, and a product construction. The nonexistence of silver cubes for d = 2 and some values of n, is proved using bounds from coding theory.