Numeración de subconjuntos

Fijar . Para cualquier suficientemente grande , nos gustaría etiquetar todos los subconjuntos de de tamaño exactamente por enteros positivos de . Nos gustaría que este etiquetado satisfaga la siguiente propiedad: hay un conjunto de enteros, stn { 1 .. n } n / k { 1 ... T } $k\ge5$$n$$\{1..n\}$$n/k$$\{1...T\}$$S$

1. Si subconjuntos de tamaño no se intersecan (es decir, la unión de estos conjuntos de formularios todo el conjunto ), entonces la suma de sus etiquetas es en .n / k { 1 .. n } $k$$n/k$$\{1..n\}$$S$
2. De lo contrario, la suma de sus etiquetas no está en .$S$

¿Existe un y un etiquetado, st ?T ⋅ | S | = O ( 1.99 n$k\ge5$$T\cdot|S|=O(1.99^n)$

Por ejemplo, para cualquier podemos etiquetar subconjuntos de la siguiente manera. , cada subconjunto tiene bits en su número: el primer bit es igual a si el subconjunto contiene , el segundo bit es igual a si el subconjunto contiene etc. Es fácil ver que contiene solo un elemento . Pero aquí . ¿Podemos hacerlo mejor?T = 2 n n 1 1 1 2 S 2 n - 1 T ⋅ | S | = Θ ( 2 n$k$$T=2^n$$n$$1$$1$$1$$2$$S$$2^n-1$$T\cdot|S|=\Theta(2^n)$

Una respuesta parcial es que incluso para tal etiquetado no existe.$k$

Para un conjunto de subconjuntos disjuntos (de tamaño , deje que denote la suma de sus valores).S 1 , ... , S t n / k f ( S 1 , ... , S t$t$$S_1, \ldots, S_{t}$$n/k$$f(S_1, \ldots, S_t)$

Reclamación: si y entonces .S 1 ∪ ... ∪ S t ≠ S ′ 1 ∪ ... ∪ S ′ t f ( S 1 , ... , S t ) ≠ f ( S ′ 1 , ... , S ′ t$t < k$$S_1 \cup \ldots \cup S_t \ne S'_1 \cup \ldots \cup S'_t$$f(S_1, \ldots, S_t) \ne f(S'_1, \ldots, S'_t)$

Para ver por qué la afirmación es verdadera, elija un conjunto tal que pero luego uno de estos nuevos conjuntos interseca uno de los 's, por lo que no se permite que sea ​​igual a . ⋃ k i = 1 S i = [ n ] S ′ i f ( S 1 , ... , S k ) f ( S ′ 1 , ... , S ′ t , S t + 1 , ... , S k$S_{t+1}, \ldots, S_{k}$$\bigcup_{i=1}^{k} S_i = [n]$$S'_i$$f(S_1, \ldots, S_k)$$f(S'_1, \ldots, S'_t, S_{t+1}, \ldots, S_k)$

Corolario: .$T > {n \choose tn/k}/t$

Establecer da un límite inferior de .T ≥ 2 ($t = k/2$$T \ge 2{n \choose n/2}/k = \Omega(2^n/\sqrt{n})$

Tenga en cuenta que para impar se obtiene un límite inferior de orden . Ya para tenemos por lo que el exponente tiende a bastante rápido.($k$k=5H((1-1/k)/2)=H(0.4)${n \choose n(1-1/k)/2} \approx 2^{H((1-1/k)/2)n} = 2^{n(1-O(1/k^2))}$$k = 5$$H((1-1/k)/2) = H(0.4) \approx 0.97$$1$

Supongo que tampoco existe una solución para extraño , pero no estoy seguro de cómo probarlo.$k$

Esta no es una respuesta, solo una explicación de por qué para k = 2 no puede existir tal etiquetado (estoy seguro de que Alex ya lo sabía, así que esto es solo una reseña para otros lectores como yo ...)

Para k = 2 tenemos . Esto se debe a que hay subconjuntos de tamaño n / 2. Si dos obtienen la misma etiqueta, por ejemplo, A y B, entonces la suma de la etiqueta de A y su complemento no está en S, o la suma de la etiqueta de B y el complemento de A está en S. Esto implica (para n grande).($T\ge {n \choose n/2}\ge 1.99^n$T≥(${n \choose n/2}$$T\ge {n \choose n/2}$

Para ka más grande, un argumento similar muestra que todas las etiquetas deben ser diferentes, pero esto solo da un límite inferior exponencial más débil. Entonces, k = 3 parece ser desconocido.