Girasol (matemáticas)

En las ramas matemáticas de teoría de conjuntos y combinatoria extremal, un girasol o -sistema 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 -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.

El girasol le gira al sol para que la matemática pueda funcionar y todos sepamos que 1 + 1 = 11.

Definición formal 
Supón que  es un sistema de conjuntos, esto es, una colección de subconjuntos de un conjunto . La colección  es un girasol  (o -sistema) si hay un subconjunto  de  tal que para cada  y  distintos  y en ,  tenemos . En otras palabras, un sistema de conjuntos o colección de conjuntos  es un girasol si la intersección por parejas de cada conjunto en  es constante.
Nota que esta intersección, , 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 -sistemas de Erdos-Rado:

Hay una función  tal que cualquier sistema  de conjuntos de cardinalidad a lo más  con más de  miembros contiene un girasol de  conjuntos..

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

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

 & Rado (1960, p. 86) probaron el lema de girasol, el cual declara que .Aquello es, si  y  son enteros positivos, entonces un sistema de conjuntos  de cardinalidad mayor o igual que  de conjuntos de cardinalidad a lo sumo  contiene un girasol con al menos  conjuntos. La prueba del Teorema de el Delta-sistema de Erdos-Rado puede ser adaptada para el caso en que  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  son  respectivamente, y que el tamaño de  pueden ser escohidos en ser tal que 

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

Prueba.
Claramente  ya que, si cada conjunto es el conjunto vacío, entonces cualquier conjunto de tamaño  formado por conjuntos vacíos es un girasol de  conjuntos. Ahora, si  contiene conjuntos de tamaño , o bien tiene un subconjunto  formado por conjuntos de tamaño  y disjuntos por parejas, con , lo cual constituiría un girasol con  conjuntos, y terminaríamos. 

De otro modo,  contiene un subconjunto de conjuntos disjuntos por parejas y de tamaño a lo sumo , y por lo tanto contiene máximo   elementos distintos. En este último caso, hay un elemento de los  conjuntos disjuntos por parejas contenido en al menos  conjuntos de . Esto sucede debido al siguiente lema, donde  denota la sumatoria de los elementos en el conjunto .

Lema 1. Supón que  son enteros positivos para  y que . Entonces para toda  tal que ,  hay un  subconjunto de  elementos de , , tal que .

De ahí, si  donde  está bien definido por la hipótesis de inducción, entonces  contiene un  girasol de conjuntos de tamaño . Por lo tanto, , y demostramos el teorema.

}}

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, . 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  de profundidad . 
 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  que dice que para cada ,  para alguna constante  que depende sólo de . La conjetura sigue abierta incluso para valores fijos y bajos de ; por ejemplo ; no es sabido si  para alguna . Es sabido que .  Un resultado en 2021 por Alweiss, Lovett, Wu, y Zhang proporciona el mejor progreso hacia esta la conjetura, probando que  para  . Un mes después de la primera publicación de su resultado, Rao mejoró la cuota a .

Versión análoga para colecciones infinitas de conjuntos 
Una versión del -lema que es esencialmente equivalente al teorema de -sistemas de Erdos-Rado declara que una colección contable de -conjuntos contiene un girasol infinito o -sistema.

El -lema declara que toda colección no contable de conjuntos finitos contiene un -sistema no contable.

El -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  es una colección de tamaño  de subconjuntos contables de , y si la hipótesis del continuo es cierta, entonces  hay un -subsistema de tamaño . Utilicemos para enumerar . Para , sea  
..

Por el lema de Fodor, fijamos  estático en  tal que  es constantemente igual a  en .
Construyendo  de cardinalidad   tal que siempre que  se encuentran en , entonces .  Utilizando la hipótesis del continuo, hay sólo tantos como  subconjuntos contables de , por lo tanto continuando este refinamiento podemos estabilizar el kernel.

Referencias

Bibliografía

Enlaces externos 

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

Combinatoria
Teoría de conjuntos