Maruša Lekše: Separating subsets from their images

Separating subsets from their images Maruša Lekše (IMFM)

Abstract: Let 𝐺 be a transitive permutation group of degree 𝑛. Let m(𝐺) be the largest integer such that, for every set 𝐴 of this size, we are guaranteed the existence of a permutation 𝑔 ∈ 𝐺 such that 𝐴 ∩ 𝐴𝑔 is empty. By Neumann’s Separation Lemma, we know that m(𝐺) ≥ √𝑛. Experimental evidence suggests that, unless 𝐺 contains a large alternating subgroup, m(𝐺) grows asymptotically as 𝒪(√𝑛). We discuss for which families of permutation groups we can currently establish this expected bound (e.g., automorphism groups of 𝑘-valent graphs whose vertex-stabiliser has bounded order). This is joint work with Marco Barbieri, Kamilla Rekvényi and Primož Potočnik.