¿Cuáles son las estimaciones conocidas para el máximo $M$ para los que existen subconjuntos $A_1,\dots,A_M$ en $\{1,\dots,n\}$ tal que no existan índices diferentes $i,j,k$ para lo cual $A_i\subset A_j\cup A_k$ ?
No es difícil demostrar algunos límites exponenciales $c_1^n<M<c_2^n$ para algunos $1<c_1<c_2<2$ ¿pero tal vez se conozca el exponente agudo?
Hasta donde yo sé, los únicos límites de este problema en la literatura se encuentran en el antiguo artículo de Erdos, Frankl y Füredi . Véase el teorema 2. Si nos fijamos en el Reseña de MathSciNet sobre dicho artículo encontrará artículos que hacen referencia a este documento. Tal vez algunos puedan serle útiles.
También hay un artículo de seguimiento de los mismos autores en familias que no contienen conjuntos $A,B_1,\dotsc,B_r$ tal que $A\subset B_1\cup\dotsb\cup B_r$ .
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.
2 votos
Utiliza $k$ dos veces para cosas diferentes, máximo $N$ sería mejor. :)
1 votos
¿Cómo se llega a su límite inferior $c_1^n$ ? No encuentro nada mejor que lineal, por ejemplo $A_i=\{i\}$ .
2 votos
Elegir, por ejemplo, subconjuntos $A_1,\dots,A_M$ de tamaño $n/4$ al azar. La probabilidad de cualquier suceso $A_i\subset A_j\cup A_k$ es exponencialmente pequeño en $n$ por lo que para $c_1$ cercano a 1 con probabilidad positiva de que no ocurra ningún suceso. Esto puede mejorarse optimizando el tamaño y utilizando el lema local de Lovász.
0 votos
Ah, ya veo, por ejemplo $f(9)\ge12$ que se obtiene tomando los 9 conjuntos 123,234,... (cíclicamente) más los 3 conjuntos 147,258,369. ¡Interesante!