Girasol (matemáticas)

En las ramas matemáticas de teoría de conjuntos y combinatoria extremal, un girasol o ${\displaystyle \Delta }$-sistema^[1]​ es una colección de conjuntos cuya intersección por parejas es constante. Esta intersección constante se denomina el centro del girasol.

La pregunta de investigación principal que surge con relación a los girasoles es: bajo qué condiciones existe un girasol grande (un girasol con muchos conjuntos) en una colección dada de conjuntos? El ${\displaystyle \Delta }$-lema, lema de girasol, culminando en la conjetura del girasol dan condiciones sucesivamente más débileslas cuales implicarían la existencia de un girasol grande en una colección de conjuntos dada, este último siendo uno de los problemas abiertos más famosos en la combinatoria extremal.^[2]​

Definición formal

Supón que ${\displaystyle W}$ es un sistema de conjuntos, esto es, una colección de subconjuntos de un conjunto ${\displaystyle U}$. La colección ${\displaystyle W}$ es un girasol (o ${\displaystyle \Delta }$-sistema) si hay un subconjunto ${\displaystyle S}$ de ${\displaystyle U}$ tal que para cada ${\displaystyle A}$ y ${\displaystyle B}$ distintos y en ${\displaystyle W}$, tenemos ${\displaystyle A\cap B=S}$. En otras palabras, un sistema de conjuntos o colección de conjuntos ${\displaystyle W}$ es un girasol si la intersección por parejas de cada conjunto en ${\displaystyle W}$ es constante. Nota que esta intersección, ${\displaystyle S}$, puede ser vacía; una colección de subconjuntos disjuntos por parejas es también un girasol. De modo parecido, una colección de conjuntos, cada uno conteniendo los mismos elementos es también un girasol trivialmente.

Teorema de sistemas delta y lema del girasol

Un resultado básico y sencillo de Erdos y Rado afirma:

Teorema de ${\displaystyle \Delta }$-sistemas de Erdos-Rado:

Hay una función ${\displaystyle f(k,r)}$ tal que cualquier sistema ${\displaystyle W}$ de conjuntos de cardinalidad a lo más ${\displaystyle k}$ con más de ${\displaystyle f(k,r)}$ miembros contiene un girasol de ${\displaystyle r}$ conjuntos..

Prueba. Supón que existe un sistema de conjuntos ${\displaystyle W}$ tal que existen ${\displaystyle k>0}$ y ${\displaystyle r>0}$ tal que para cualquier cardinalidad del sistema de conjuntos ${\displaystyle W}$, no existe ningún girasol de ${\displaystyle r}$ conjuntos en ${\displaystyle W}$. Escogemos que ${\displaystyle W}$ sea infinito. Ya que ${\displaystyle W}$ no contiene ningún girasol de medida ${\displaystyle r}$, en ${\displaystyle W}$ puede haber como máximo ${\displaystyle r-1}$ conjuntos disjuntos por parejas, ya que ${\displaystyle r}$ conjuntos disjuntos por parejas constituirían un girasol. Sea ${\displaystyle K_{a_{0}}}$ el conjunto máximo de subconjuntos disjuntos por parejas de ${\displaystyle W}$; ${\displaystyle K_{a_{0}}}$ es de cardinalidad como máximo ${\displaystyle r-1}$. Sigue que cada conjunto en ${\displaystyle W}$ fuera de ${\displaystyle K_{a_{0}}}$ cruza con al menos uno puesto en ${\displaystyle K_{a_{0}}}$. De otra manera, supongamos que hay un conjunto en ${\displaystyle W}$ fuera de ${\displaystyle K_{a_{0}}}$ el cual no se interseca con ningún conjunto en ${\displaystyle K}$; entonces, sería disjunto por pareja con cualquier conjunto en ${\displaystyle K}$ y entonces con los ${\displaystyle r-1}$ conjuntos de ${\displaystyle K}$, y esto último formaría un girasol con ${\displaystyle r}$ conjuntos, lo cual contradice la suposición.

Para ${\displaystyle W}$ arbitrariamente grande, existe un elemento ${\displaystyle a_{1}}$ en los conjuntos en ${\displaystyle K_{a_{0}}}$ tal que una infinidad de conjuntos en ${\displaystyle W}$ contendrán a ${\displaystyle a}$ por el Principio de Casillas inverso. Quitamos el elemento común de todos estos conjuntos y denotamos este sistema de conjuntos por ${\displaystyle K_{a_{1}}}$. Ya que por suposición, no existe ningún girasol con ${\displaystyle r}$ conjuntos, hay como máximo ${\displaystyle r-1}$ conjuntos disjuntos en ${\displaystyle K_{a_{1}}}$. De otra manera, aquellos ${\displaystyle r}$ conjuntos formarían un girasol y el conjunto de intersección del girasol sería ${\displaystyle {a}}$. Construimos ${\displaystyle K_{a_{k}}}$ a partir de ${\displaystyle K_{a_{k-1}}}$removiendo ${\displaystyle {a_{k}}}$ de la infinidad de conjuntos en ${\displaystyle K_{a_{k-1}}}$ que contienen a ${\displaystyle a_{k}}$, donde ${\displaystyle a_{k}}$ es un elemento de los (máximo) ${\displaystyle r-1}$ ${\displaystyle k}$-conjuntos contenidos en ${\displaystyle K_{a_{k-1}}}$. ${\displaystyle K_{a_{k}}}$ es ahora un conjunto infinito de conjuntos vacíos, implicando que existe un conjunto infinito de ${\displaystyle k}$-conjuntos idénticos en ${\displaystyle W}$, lo que es una contradicción. Esto completa la prueba.

Erdős y Rado (1960) & Rado (1960, p. 86) probaron el lema de girasol, el cual declara que ${\displaystyle f(k,r)\leq k!(r-1)^{k+1}}$.Aquello es, si ${\displaystyle k}$ y ${\displaystyle r}$ son enteros positivos, entonces un sistema de conjuntos ${\displaystyle W}$ de cardinalidad mayor o igual que ${\displaystyle k!(r-1)^{k+1}}$ de conjuntos de cardinalidad a lo sumo ${\displaystyle k}$ contiene un girasol con al menos ${\displaystyle r}$ conjuntos. La prueba del Teorema de el Delta-sistema de Erdos-Rado puede ser adaptada para el caso en que ${\displaystyle W}$ tiene tamaño finito para probar el lema, en particular, observando que el número total de elementos en los conjuntos de los conjuntos maximales disjuntos por parejas en ${\displaystyle K_{a_{0}},K_{a_{1}},\ldots ,K_{a_{k-1}},K_{a_{k}}}$ son ${\displaystyle (r-1)k,(r-1)(k-1),\ldots ,r}$ respectivamente, y que el tamaño de ${\displaystyle K_{a_{i}}}$ pueden ser escohidos en ser tal que ${\displaystyle K_{a_{i-1}}/[(r-1)(k-i)]}$

Lo siguiente da una prueba directa inductiva del lema del girasol de Erdos-Rado.

Prueba. Claramente ${\displaystyle f(0,r)\leq r-1}$ ya que, si cada conjunto es el conjunto vacío, entonces cualquier conjunto de tamaño ${\displaystyle r}$ formado por conjuntos vacíos es un girasol de ${\displaystyle r}$ conjuntos. Ahora, si ${\displaystyle F}$ contiene conjuntos de tamaño ${\displaystyle k+1}$, o bien tiene un subconjunto ${\displaystyle K}$ formado por conjuntos de tamaño ${\displaystyle (k+1)}$ y disjuntos por parejas, con ${\displaystyle |K|\geq r}$, lo cual constituiría un girasol con ${\displaystyle r}$ conjuntos, y terminaríamos.

De otro modo, ${\displaystyle F}$ contiene un subconjunto de conjuntos disjuntos por parejas y de tamaño a lo sumo ${\displaystyle r-1}$, y por lo tanto contiene máximo ${\displaystyle (r-1)(k+1)}$ elementos distintos. En este último caso, hay un elemento de los ${\displaystyle \leq r}$ conjuntos disjuntos por parejas contenido en al menos ${\displaystyle |F|/(r-1)(k+1)}$ conjuntos de ${\displaystyle F}$. Esto sucede debido al siguiente lema, donde ${\displaystyle \Sigma (C)}$ denota la sumatoria de los elementos en el conjunto ${\displaystyle C}$.

Lema 1. Supón que ${\displaystyle A=(a_{1},....,a_{n})}$ son enteros positivos para ${\displaystyle n>0}$ y que ${\displaystyle \Sigma (A)=m}$. Entonces para toda ${\displaystyle k}$ tal que ${\displaystyle n\geq k>0}$, hay un subconjunto de ${\displaystyle k}$ elementos de ${\displaystyle A}$, ${\displaystyle B}$, tal que ${\displaystyle \Sigma (B)\geq m/k}$.

De ahí, si ${\displaystyle |F|\geq (r-1)(k+1)f(k,r)}$ donde ${\displaystyle f(k,r)}$ está bien definido por la hipótesis de inducción, entonces ${\displaystyle F}$ contiene un ${\displaystyle r}$ girasol de conjuntos de tamaño ${\displaystyle k+1}$. Por lo tanto, ${\displaystyle f(k+1,r)\leq f(k,r)(r-1)(k+1)}$, y demostramos el teorema.

}}^[2]​

Aplicaciones del lema de girasol

El lema de girasol tiene aplicaciones numerosas en informática teórica. Por ejemplo,

• En 1986, Razborov utilizó el lema de girasol para probar que el lenguaje Clique requería circuitos monótonos de longitud superpolinomial, es decir, ${\displaystyle n^{log(n)}}$. Esto fue un resultado impactante en teoría de complejidad de circuitos en su tiempo.
• Håstad, Jukna, y Pudlák lo utilizaron para probar cuotas mínimas para circuitos ${\displaystyle AC_{0}}$ de profundidad ${\displaystyle 3}$.
• También ha sido aplicado en el estudio de la complejidad parametrizada del problema de conjunto de pegado, para diseñar algoritmos tractables de parámetro fijo para encontrar conjuntos pequeños de elementos que contienen al menos un elemento de una familia dada de conjuntos.[4]

Conjetura de girasol de Erdős-Rado

La conjetura de girasol es una de varias variaciones de la conjetura de Erdős y Rado (1960, p. 86) que dice que para cada ${\displaystyle r>2}$, ${\displaystyle f(k,r)\leq C^{k}}$ para alguna constante ${\displaystyle C>0}$ que depende sólo de ${\displaystyle r}$. La conjetura sigue abierta incluso para valores fijos y bajos de ${\displaystyle r}$; por ejemplo ${\displaystyle r=3}$; no es sabido si ${\displaystyle f(k,3)\leq C^{k}}$ para alguna ${\displaystyle C>0}$. Es sabido que ${\displaystyle 10^{.5k}\leq f(k,3)}$.^[3]​ Un resultado en 2021 por Alweiss, Lovett, Wu, y Zhang proporciona el mejor progreso hacia esta la conjetura, probando que ${\displaystyle f(k,r)\leq C^{k}}$ para ${\displaystyle C=(\log k)^{1+o(1)}(r-1)}$.^[4]​^[5]​ . Un mes después de la primera publicación de su resultado, Rao mejoró la cuota a ${\displaystyle C=(\log k)(r-1)}$.

Versión análoga para colecciones infinitas de conjuntos

Una versión del ${\displaystyle \Delta }$-lema que es esencialmente equivalente al teorema de ${\displaystyle \Delta }$-sistemas de Erdos-Rado declara que una colección contable de ${\displaystyle k}$-conjuntos contiene un girasol infinito o ${\displaystyle \Delta }$-sistema.

El ${\displaystyle \Delta }$-lema declara que toda colección no contable de conjuntos finitos contiene un ${\displaystyle \Delta }$-sistema no contable.

El ${\displaystyle \Delta }$-lema es una herramienta combinatoria procedente de la teoría de conjuntos utilizada en pruebas para mostrar cuotas superiores para el tamaño de una colección de elementos incompatibles disjuntos por parejas en un poset forzado. Por ejemplo, puede ser utilizado como uno de los ingredientes en una prueba que muestra que es compatible con los axiomas de Zermelo–Fraenkel que establecen que la hipótesis del continuo es falsa. Esto fue introducido por Shanin (1946).

Si ${\displaystyle W}$ es una colección de tamaño ${\displaystyle \omega _{2}}$ de subconjuntos contables de ${\displaystyle \omega _{2}}$, y si la hipótesis del continuo es cierta, entonces hay un ${\displaystyle \Delta }$-subsistema de tamaño ${\displaystyle \omega _{2}}$. Utilicemos ${\displaystyle \langle A_{\alpha }:\alpha <\omega _{2}\rangle }$para enumerar ${\displaystyle W}$. Para ${\displaystyle \operatorname {cf} (\alpha )=\omega _{1}}$, sea .${\displaystyle f(\alpha )=\sup(A_{\alpha }\cap \alpha )}$.

Por el lema de Fodor, fijamos ${\displaystyle S}$ estático en ${\displaystyle \omega _{2}}$ tal que ${\displaystyle f}$ es constantemente igual a ${\displaystyle \beta }$ en ${\displaystyle S}$. Construyendo ${\displaystyle S'\subseteq S}$ de cardinalidad ${\displaystyle \omega _{2}}$ tal que siempre que ${\displaystyle i<j}$ se encuentran en ${\displaystyle S'}$, entonces ${\displaystyle A_{i}\subseteq j}$. Utilizando la hipótesis del continuo, hay sólo tantos como ${\displaystyle \omega _{1}}$ subconjuntos contables de ${\displaystyle \beta }$, por lo tanto continuando este refinamiento podemos estabilizar el kernel.

Referencias

Bibliografía

• Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (June 2020), «Improved bounds for the sunflower lemma», Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, pp. 624-630, ISBN 978-1-4503-6979-4, doi:10.1145/3357713.3384234 .
• Deza, M.; Frankl, P. (1981), «Every large set of equidistant (0,+1,–1)-vectors forms a sunflower», Combinatorica 1 (3): 225-231, ISSN 0209-9683, doi:10.1007/BF02579328 .
• Erdős, Paul; Rado, R. (1960), «Intersection theorems for systems of sets», Journal of the London Mathematical Society, Second Series 35 (1): 85-90, ISSN 0024-6107, doi:10.1112/jlms/s1-35.1.85 .
• Flum, Jörg; Grohe, Martin (2006), «A Kernelization of Hitting Set», Parameterized Complexity Theory, EATCS Ser. Texts in Theoretical Computer Science, Springer, pp. 210-212, doi:10.1007/3-540-29953-X .
• Jech, Thomas (2003), Set Theory, Springer .
• Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs, North-Holland, ISBN 978-0-444-85401-8 .
• Shanin, N. A. (1946), «A theorem from the general theory of sets», C. R. (Doklady) Acad. Sci. URSS, New Series 53: 399-400 .
• Tao, Terence (2020), The sunflower lemma via Shannon entropy, What's new (personal blog) .

Enlaces externos

• Thiemann, René. El Lema de Girasol de Erdős y Rado (desarrollo de prueba formal en Isabelle/HOL, Archivo de Pruebas Formales)