Un teorema sobre cubiertas de grupos

Como pueden comprobar, no me agrada escribir sobre "tecnicismos" matemáticos en esta bitácora (ni en cualquier otra, si la tuviera). Esta entrada será una de las excepciones, pues el siguiente teorema de Bollobás, Janson y Riordan (o en realidad una versión un poco más general) tiene que ver con lo que he estado investigando recientemente, la demostración me gustó mucho y me parece particularmente hermosa (¡y elemental!).

Tomemos primero un grupo abeliano finito $G$, y supongamos que $S\subset G$ es tal que $|S| = \frac{|G|}{2}$. Con la notación aditiva para la operación del grupo, nos interesa encontrar un subconjunto $T$ de $G$ de cardinalidad mínima tal que $\bigcup_{t\in T} (t+S) = G$. Denotemos con $\tau(S,G)=|T|$ a este número óptimo.

Un esquema para obtener un $T$ pequeño y que sirva para acotar a $\tau(S,G)$ es el clásico algoritmo voraz. Supongamos que ya hemos encontrado $t_{1},\ldots,t_{j}$ tales que $\bigcup_{i=1}^{j}(t_{i}+S)\neq G$; entonces elegimos a $t_{j+1}$ tal que $\bigcup_{i=1}^{j+1}(t_{i}+S)$ sea de cardinalidad máxima. Detenemos el proceso cuando logremos cubrir a todo $G$. Denotemos con $\tau_{V}(S,G)$ al número de elementos $t_{i}$ que resultan con este algoritmo.

Teorema (Bollobás, Janson y Riordan, 2010). Con la notación anterior, se satisface \[ \tau(S,G)\leq \tau_{V}(S,G) \leq \lceil\log_{2}|G|\rceil. \]
¡Me parece un resultado maravilloso! Nos revela que basta una cantidad cuando más logarítmica de traslaciones de una mitad de $G$ para cubrirlo por completo. La demostración, además, es algo probabilística.

Demostración. Sea $M_{j} = G\setminus \bigcup_{i=1}^{j}(t_{i}+S)$ el conjunto de los elementos no cubiertos después de $j$ pasos del algoritmo voraz. A mí me sorprendió que los autores afirmaran que una elección aleatoria de $t_{j+1}$ en promedio cubre $\frac{|M_{j}|}{2}$ elementos de $M_{j}$. Fíjense: sea $\chi_{M_{j}}$ la función característica de $M_{j}$. Entonces, el promedio de elementos cubiertos por todas las traslaciones es \begin{align*} \frac{1}{|G|}\sum_{t\in G} \sum_{s\in S} \chi_{M_{j}}(t+s) &= \frac{1}{|G|} \sum_{s\in S}\sum_{t\in G} \chi_{M_{j}}(t+s)\\ &= \frac{1}{|G|}\sum_{s\in S}|M_{j}| = \frac{1}{|G|}|S||M_{j}| =\frac{|M_{j}|}{2}, \end{align*} como habían prometido. Ahora bien, por ser éste el promedio, la elección óptima del $t_{j+1}$ debe cubrir por lo menos tal cantidad de elementos (¡el principio de las casillas disfrazado!). Así \[ |M_{j+1}| \leq |M_{j}|(1-\tfrac{1}{2}) = \frac{|M_{j}|}{2}, \] y es inmediato que en cuando mucho $\lceil\log_{2}|G|\rceil$ pasos debe terminar el algoritmo voraz su ejecución. QED.

Como dije antes, sin mucho esfuerzo se puede demostrar algo más general y un poco más fuerte (revisen el artículo original para mayores e interesantes detalles), pero para mis propósitos con eso basta. Bueno, no del todo, porque en el caso que me interesa las traslaciones no se pueden tomar entre todo el grupo, sino solamente en una mitad (y distinta de $S$). Bajo esas condiciones, el problema se complica porque ya no es fácil estimar el promedio de elementos cubiertos en cada etapa del algoritmo voraz.