Supongamos que queremos encontrar un número exponencial de subconjuntos de $\{1,....,n\}$ s.t. para cada uno de los dos subconjuntos, denotados como $S,T$ que tenemos: $|(S\setminus T)\cup(T\setminus S)|=\Omega(n)$ . Dado que hay como máximo $2^n$ esto significa que el conjunto que buscamos es de cardinalidad $2^{\Omega(n)}$ ¿alguna idea sobre cómo construirlo?
Respuesta
¿Demasiados anuncios?
kodlu
Puntos
1178
Dejemos que $\alpha \in (0,1)$ y definir $\Delta(S,T)$ como la diferencia simétrica de conjuntos, que es su cantidad. Quieres encontrar una gran familia de conjuntos $\cal F$ todos cuyos miembros son subconjuntos de $\{1,2,\ldots,n\}$ tal que $$ S\neq T \in {\cal F} \Rightarrow \Delta(S,T)\geq \alpha n. $$ En el lenguaje de la teoría de la codificación, donde el soporte de un conjunto $A$ puede asociarse a un vector binario $c_A=(\chi[k \in A]: 1\leq k\leq n),$ donde $\chi(\cdot)$ es la función indicadora de un evento, se busca un código con tasa positiva y distancia mínima.
Así que quieres encontrar exponencialmente muchas palabras de código binario de longitud $n$ que difieren entre sí al menos en $\alpha n$ coordenadas, que es la distancia mínima del código.
Tales colecciones de palabras clave existen, por argumentos de codificación aleatoria, construirlas explícitamente es más difícil.
El límite inferior de Gilbert-Varshamov (en forma asintótica) establece que para $n$ lo suficientemente grande hay un código $C$ de la tasa $R$ (donde $R=\log_2(\#C)/n$ y la distancia mínima $\alpha n$ siempre que la desigualdad $$ R\geq 1-H_2(\delta) $$ donde $H_2$ es la entropía de Shannon. La versión finita es que existe un código que satisface $$ \#C\geq \frac{2^n}{\sum_{j=0}^{\lfloor \delta n\rfloor-1} \binom{n}{j}} $$ donde la suma de abajo es el número de vectores binarios dentro de la distancia $\delta n$ de una determinada palabra clave, el volumen de una llamada esfera de Hamming de radio $d-1.$
En cuanto a las construcciones, las construcciones deterministas explícitas son difíciles de encontrar.
