Supongamos que $S$ es un conjunto con $n$ elementos. ¿Cuál es el valor máximo de $m$ tal que existe una colección $\{A_k\}_{k=1,\dots m}$ de subconjuntos de $S$ de manera que cada $A_i$ no es la unión de otros elementos de $\{A_k\}_{k=1,\dots m}$ ?
¿Existe una fórmula elegante para este número?
Esto es sólo una respuesta parcial: da una construcción que da un límite inferior y produce exactamente todas las soluciones máximas para $n \in [0, 4]$ . Asumo para facilitar el etiquetado que $S_n = [1, n]$ .
Para $n=0$ tomamos el subconjunto no vacío de $2^{\{\}}$ es decir $\{\emptyset\}$ .
Para $n > 0$ tomamos una solución máxima para $n-1$ y colindan con $\{ s \subseteq S_n : n \in s \wedge |s| = k\}$ , eligiendo $k$ para maximizar el resultado. Esto significa que cuando $n-1$ es incluso tomamos $k-1 = \frac{n-1}{2}$ y cuando se trata de impar tomamos $k-1 = \frac{n-1 \pm 1}{2}$ .
El número de conjuntos así producidos es una suma parcial de $1, \binom{0}{0}, \binom{1}{0}, \binom{2}{1}, \binom{3}{1}, \binom{4}{2}, \binom{5}{2}, \ldots$ . Esta suma parcial está en OEIS como A072100 .
Está dentro del ámbito de la fuerza bruta verificar si el valor dado para $n=5$ está apretado o no. Para $n=6$ Dudo que sea verificable por fuerza bruta.
Anexo Živković, Familias extremas que no contienen dos conjuntos y su unión , Linear Algebra and its Applications 436.4 (2012) pp845-849 demuestra un límite más ajustado:
$$m \ge 2^{\lceil n/2 \rceil - 3} - 2 + \sum_{k=0}^{n-1}\binom{k}{\lceil k/2 \rceil}$$
y hace referencia a Kleitman (creo que Propiedades extremas de colecciones de subconjuntos que no contienen dos conjuntos y su unión J. Combin. Theory Ser. A 20 (1976) pp390-392, pero la referencia es vaga y no tengo acceso al documento para verificarlo) para
$$m \ge \binom{n}{\lceil n/2 \rceil} + \left\lceil \frac1n \binom{n}{\lceil n/2 \rceil - 1}\right\rceil$$
que es mayor para los grandes incluso $n$ .
Esto se planteó como un problema abierto en la página 161 de Mitchell, Turan's graph theorem and maximum independent sets in Brandt semigroups, que son las páginas 151-162 de Isabel M Araujo et al., eds., Proceedings of the Workshop Semigroups and Languages, 2004: "Dejemos $X$ denotan el conjunto de subconjuntos de un $n$ conjunto de elementos. ¿Cuál es la cardinalidad máxima de un subconjunto $Y$ de $X$ con la propiedad de que ningún conjunto en $Y$ es la unión de otros conjuntos en $Y$ ?"
No hay más discusión sobre el problema en el documento.
Está disponible un pdf del documento aquí .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
