Covering a set with images of a transversal

Question

Let $G$ be a permutation group on a finite set $\Omega$ with orbits $\Omega_1,\ldots,\Omega_k$. By a transversal we mean a set $\lbrace\omega_1,\ldots,\omega_k\rbrace$ with $\omega_j\in\Omega_j$ for each $j$.

For a transversal $\tau=\lbrace\omega_1,\ldots,\omega_k\rbrace$ and subset $H\subseteq G$, let $$H(\tau) = \bigcup_{h\in H} \lbrace\omega_1^h,\ldots,\omega_k^h\rbrace. $$

Define $N=N(G)$ to be the smallest integer such that for some transversal $\tau$ and some $H\subseteq G$ we have $|H|=N$ and $H(\tau)=\Omega$.

Question: What is $N(G)$?

Let $n=|\Omega|$ and $m=\max_{i=1}^k |\Omega_i|$. It is easy to see that $N(G)\ge m$. By taking an arbitrary transversal and random subsets $H$, one can show non-constructively that $N(G)\le m\log n$.

This is an ideal version of a question that arose about symmetry breaking in finite optimization problems.

Answer 1

It seems the following.

I can propose the following example with a not so trivial lower bound. Exactly, for $l\ge 2$ I have $m=2^{l-1}$, $n=2^{l-1}(2^l-1)$ and $N=2^l-1$.

Let $G=\Bbb Z_2^l$ be an $l$-th power of the group $\Bbb Z_2=\Bbb Z/2{\Bbb Z}$. Let $g$ be a non-zero element of the group $G$. Then $g$ generates a two-element subgroup $G_g=\{0,g\}$. Let $\Omega_g=G/G_g$ be a $G$-set with a natural action $x[y+G_g]=[x+y+G_g]$ of $G$ on its quotient group. Then $m=|\Omega_g|=2^{l-1}$. Let $\Omega$ be a disjoint sum of all $\Omega_g$ with $g\in G\setminus\{0\}$. Then $n=|\Omega|=2^{l-1}(2^l-1).$ If $\tau $ is an arbitrary transversal, then $(G\setminus\{0\})(\tau)=\Omega$, because for each element $\omega_j\in\Omega_j$ there exists a non-zero element $g\in G$ such that $g(\omega_j)=\omega_j$. So $N\le |G|-1=2^l-1$. Now let $\tau=\{\omega_g:g\in G\setminus\{0\}\}$ be a transversal and $H\subset G$ be a set such that $|H|=N$ and $H(\tau)=\Omega$. Suppose that $H\le |G|-2$. Let $x,y\in G\setminus H$ be different elements. Put $g=y-x$. Because $H(\omega_g)=\Omega_g$, we have $H[x_g+G_g]=G/G_g$ for some representative $x_g\in\omega_g$. This means $G=H+x_g+G_g$ and $G=H+G_g\subset G\setminus\{x,y\},$ a contradiction.