When all Permutations are Combinatorial Similarities

Abstract

Let $(X,d)$ be a semimetric space. A permutation $\Phi$ of the set $X$ is a combinatorial self similarity of $(X,d)$ if there is a bijective function $f:d(X^2)\to d(X^2)$ such that $$d(x,y)=f(d(\Phi (x),\Phi (y)))$$ for all $x$, $y\in X$. We describe the set of all semimetrics $\rho$ on an arbitrary nonempty set $Y$ for which every permutation of $Y$ is a combinatorial self similarity of $(Y,\rho )$.

14 pages, 3 figures