On the number of metric functions of a Boolean cube

We obtain the limit of the $2^n$th root (asymptotics of the logarithm) of the number of pseudo-Boolean functions of $n$ variables that map adjacent vertices of the Boolean cube into adjacent vertices of an arbitrary graph, is obtained. This result is extended to mappings of vertices of Cartesian products of arbitrary graphs.
This research was supported by the Russian Foundation for Basic Research, grants 00–01–00351 and 01–01–00266.