Independent permutations, as related to a problem of Moser and a theorem of Pólya

Abstract

We introduce the notion of a set of independent permutations on the domain {0, 1,... n - 1}, and obtain bounds on the size of the largest such set. The results are applied to a problem proposed by Moser in which he asked for the largest number of nodes in a d-cube of side n such that no n of these nodes are collinear. Independent permutations are also related to the problem of placing n non-capturing superqueens (chess queens with wrap-around capability) on an n × n board. As a special case of this treatment we obtain Pólya's theorem that this problem can be solved if and only if n is not a multiple of 2 or 3. © 1974.