Cubrir un conjunto con imágenes de una transversal

Question

Dejemos que $G$ sea un grupo de permutación sobre un conjunto finito $\Omega$ con órbitas $\Omega_1,\ldots,\Omega_k$ . Por un transversal nos referimos a un conjunto $\lbrace\omega_1,\ldots,\omega_k\rbrace$ con $\omega_j\in\Omega_j$ para cada $j$ .

Para una transversal $\tau=\lbrace\omega_1,\ldots,\omega_k\rbrace$ y el subconjunto $H\subseteq G$ , dejemos que $$H(\tau) = \bigcup_{h\in H} \lbrace\omega_1^h,\ldots,\omega_k^h\rbrace. $$

Definir $N=N(G)$ para ser el menor número entero tal que para alguna transversal $\tau$ y algunos $H\subseteq G$ tenemos $|H|=N$ y $H(\tau)=\Omega$ .

Pregunta: ¿Qué es $N(G)$ ?

Dejemos que $n=|\Omega|$ y $m=\max_{i=1}^k |\Omega_i|$ . Es fácil ver que $N(G)\ge m$ . Tomando una transversal arbitraria y subconjuntos aleatorios $H$ se puede demostrar de forma no constructiva que $N(G)\le m\log n$ .

Esta es una versión ideal de una pregunta que surgió sobre la ruptura de la simetría en los problemas de optimización finita.

Answer 1

Parece lo siguiente.

Puedo proponer el siguiente ejemplo con un límite inferior no tan trivial. Exactamente, para $l\ge 2$ Tengo $m=2^{l-1}$ , $n=2^{l-1}(2^l-1)$ y $N=2^l-1$ .

Dejemos que $G=\Bbb Z_2^l$ ser un $l$ -enfermedad del grupo $\Bbb Z_2=\Bbb Z/2{\Bbb Z}$ . Sea $g$ sea un elemento no nulo del grupo $G$ . Entonces $g$ genera un subgrupo de dos elementos $G_g=\{0,g\}$ . Sea $\Omega_g=G/G_g$ ser un $G$ -con una acción natural $x[y+G_g]=[x+y+G_g]$ de $G$ en su grupo cociente. Entonces $m=|\Omega_g|=2^{l-1}$ . Sea $\Omega$ sea una suma disjunta de todos los $\Omega_g$ con $g\in G\setminus\{0\}$ . Entonces $n=|\Omega|=2^{l-1}(2^l-1).$ Si $\tau $ es una transversal arbitraria, entonces $(G\setminus\{0\})(\tau)=\Omega$ porque para cada elemento $\omega_j\in\Omega_j$ existe un elemento no nulo $g\in G$ tal que $g(\omega_j)=\omega_j$ . Así que $N\le |G|-1=2^l-1$ . Ahora dejemos que $\tau=\{\omega_g:g\in G\setminus\{0\}\}$ sea una transversal y $H\subset G$ sea un conjunto tal que $|H|=N$ y $H(\tau)=\Omega$ . Supongamos que $H\le |G|-2$ . Sea $x,y\in G\setminus H$ sean elementos diferentes. Poner $g=y-x$ . Porque $H(\omega_g)=\Omega_g$ tenemos $H[x_g+G_g]=G/G_g$ para algún representante $x_g\in\omega_g$ . Esto significa que $G=H+x_g+G_g$ y $G=H+G_g\subset G\setminus\{x,y\},$ una contradicción.