Problema de los subconjuntos que suman 0

Question

Dejemos que $X=\{x_1,...,x_n\}$ sea un conjunto múltiple de $n$ números reales, y que $x_1+\dots+x_n = 0$ . ¿Hay alguna manera de encontrar el número máximo de subconjuntos únicos cualquier $X$ puede haber dado $n$ , de forma que cada subconjunto sume $0$ pero no contiene ningún subconjunto que sume $0$ ?

O más precisamente, es el siguiente máximo sobre todos los conjuntos múltiples de tamaño $n$ acotado por encima polinomialmente como $n$ ¿se hace grande?: $max\{|f(X)| : X = \{x_1,...,x_n\} \land x_1+\dots+x_n = 0\}$ donde $f(X) = \{Y \subseteq X : sumY=0 \land \forall_{Z\subset Y}sumZ\neq0 \}$ .

Me interesa esto como límite para un algoritmo. Tengo la sensación de que no crece muy rápido, pero no estoy seguro de cómo abordar el problema.

He intentado hacer fuerza bruta para valores pequeños de $x$ y han encontrado los siguientes valores para $n \in [0,10]$ : $[1, 1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$ . OEIS no parece tener una entrada relacionada.

---

Edición: Para evitar confusiones, aquí hay algunos ejemplos que utilizan sólo números enteros distintos, que creo que son óptimos:

0: {}                    {{}}
1: {0}                   {{0}}
2: {-1,1}                {{-1,1}}
3: {-1,0,1}              {{0},{-1,1}}
4: {-2,-1,1,2}           {{-2,2},{-1,1}}
5: {-2,-1,0,1,2}         {{0},{-2,2},{-1,1}}
6: {-3,-2,-1,1,2,3}      {{-3,3},{-2,2},{-1,1},{-3,1,2},{-2,-1,3}}
7: {-6,-4,-1,1,2,3,5}    {{-1,1},{-6,1,5},{-4,-1,5},{-4,1,3},{-6,-1,2,5},{-6,1,2,3},{-4,-1,2,3},{-6,-4,2,3,5}}
8: {-8,-7,-3,1,2,4,5,6}  {{-8,2,6},{-7,1,6},{-7,2,5},{-3,1,2},{-8,-3,5,6},{-8,1,2,5},{-7,-3,4,6},{-7,1,2,4},{-8,-7,4,5,6},{-8,-3,1,4,6},{-8,-3,2,4,5},{-7,-3,1,4,5}}

Answer 1

Si entiendo bien la pregunta, lo siguiente podría dar respuestas asintóticas de tamaño exponencial..

1) Subsumas de una suma finita y conjuntos extremos de vértices del hipercubo, por Dezső Miklós, Horizons of Combinatorics, Bolyai Society Mathematical studies Vol 17, 2008.

disponible en el enlace de Springer. Un enlace a algunas diapositivas: http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf

2) Otros trabajos sobre el problema de Littlewood-Offord también podrían ser relevantes.

Answer 2

Este es un ejemplo que muestra que el límite va a ser de naturaleza exponencial.

Escoge $k > 0$ un número entero grande para enfatizar. Elija su conjunto favorito $F$ de $k$ enteros positivos distintos. Formar el conjunto $S$ de todas las sumas formadas por la suma de un subconjunto propio y no vacío de $F$ . Para su conjunto favorito $F$ , $S$ puede ser de tamaño $2^k$ para mi conjunto favorito $F$ siendo el primero $k$ enteros positivos, $S$ tiene un tamaño máximo de $k+1$ elegir 2 .

Utilicemos un $F$ tal que $S$ tiene un tamaño polinómico en $k$ . Ahora crea $M$ que es el negativo de cada número en $S$ . Por último, crea el multiconjunto $U$ que tiene una copia de $M$ y suficientes copias de $F$ (incluyendo una copia fraccionada si es necesario, pero creo que una no lo es) para tener $U$ suma a 0. $U$ tiene un tamaño polinómico en $k$ y al menos $2^k$ opciones obvias para subconjuntos mínimos que suman 0. Así que conjeturo un límite inferior de la forma $2^{g(n)}$ , donde $g(n)$ es $O(n^{1/3})$ y $n$ es el tamaño del multiconjunto.

Es probable que puedas ajustar esto para obtener límites precisos, pero si estás en el comienzo, creo que tienes que prepararte para un potencial tiempo de ejecución exponencial para tu algoritmo.

Gerhard "Ask Me About System Design" Paseman, 2011.12.08

Answer 3

Como sugiere Christian, puede que quieras empezar por mirar el El problema de Littlewood-Offord . Aquí hay una versión escalada del resultado de Erdős que podría ser más relevante para su problema:

"Si $a_1, \dots a_n$ son todos distintos de cero, entonces para cualquier $c$ sub-suma que es igual a $c$ es como máximo $\binom{n}{\lfloor n/2\rfloor}$ el límite que se alcanza cuando todos los $a_i$ son iguales a $1$ . y $c=\lfloor n/2 \rfloor $ ".

Supongamos, sin pérdida de generalidad, que todos sus $a_i$ son distintos de cero (cualquier $a_i$ que es igual a $0$ no aparecen en ninguno de sus subconjuntos de todos modos). Entonces ese límite superior sigue siendo válido en este caso, y es aproximadamente $C2^n/\sqrt{n}$ para grandes $n$ .

Para un límite inferior, utilizaremos la siguiente construcción: Supongamos que tenemos un conjunto $S$ de enteros positivos tal que la suma de todos los elementos de $S$ es $k$ y tienes muchos subconjuntos que suman $c$ . Entonces dejamos que

$$S'=S \cup \{-c\} \cup \{c-k\}.$$

Para cada subconjunto de $S$ sumando a $c$ hay un subconjunto correspondiente de $S'$ formado por la adición de $-c$ . Este subconjunto no tiene ningún subconjunto más pequeño que sume $0$ porque $S$ consistía enteramente en números enteros positivos.

Lo que da este límite inferior depende de cómo se cuenten los subconjuntos. Por ejemplo, si $n$ es incluso el multiconjunto $$[1,1,\dots,1,-\frac{n}{2}, -\frac{n}{2}]$$ con $n-2$ tiene $2\binom{n-2}{n/2-1}$ submultisets de la forma $[1,1,\dots,1, -\frac{n}{2}]$ sumando a $0$ . Para grandes $n$ esto es un factor de $2$ del límite inferior.

Si se considera que estos subconjuntos son todos idénticos, entonces se puede empezar con $S=\{1,2,\dots,n-2\}$ . Puede comprobar que para los grandes $n$ este conjunto tiene aproximadamente $C\frac{2^{n-2}}{n^{3/2}}$ subconjuntos que suman el mismo valor para algunos $C$ (la idea es que si se toma un subconjunto aleatorio la desviación estándar de su suma es sólo de orden $n^{3/2}$ ). Así que puedes empezar con esto como tu $S$ y obtener un límite inferior que es aproximadamente $2^n n^{-3/2}$ para grandes $n$ .