Separating subsets from their images

Abstract

Let $G$ be a transitive permutation group acting on $\hat{I}\text{c◯}$. In this paper, we introduce and study the parameter $\mathbf{m}(G)$, which denotes the size of the smallest set of points $A$ such that, for every permutation $g\in G$, $A\cap A^g$ is nonempty. In particular, we focus on deriving general bounds for arbitrary transitive groups, and on the asymptotic behaviour of certain families of primitive groups. We also provide a classification of transitive groups with $\mathbf{m}(G)$ largest possible, namely with $\mathbf{m}(G)=\lceil (|\hat{I}\text{c◯}|+1)/2\rceil$.

40 pages; Section 7 extended