Girasol (matemàtiques)

Archiu:Sonnenblume AC KMJ.jpg

Un girasol matemàtic pot ser visualisat com una flor. El centre del girasol és la part marró en el mig, i cada conjunt del girasol és l'unió d'un pétal i el centre.

En les branques matemàtiques de teoria de conjunts i combinatòria extremal, un girasol o $\Delta$-sistema és una colecció de conjunts que la seua intersecció per parelles és constant. Esta intersecció constant es denomina el centre del girasol.

La pregunta d'investigació principal que sorgix con relación a els girasols és: baix quines condicions existix un girasol gran (un girasol en molts conjunts) en una colecció donada de conjunts? El $\Delta$-lema, lema de girasol, culminant en la conjectura del girasol donen condicions successivament més débileslas cuales implicarien l'existència d'un girasol gran en una colecció de conjunts donada, este últim sent un dels problemes oberts més famosos en la combinatòria extremal.

Definició formal

Supon que $W$ és un sistema de conjunts, açò és, una colecció de subconjunts d'un conjunt $U$. La colecció $W$ és un girasol (o $\Delta$-sistema) si hi ha un subconjunt $S$ de $U$ tal que per a cada $A$ i $B$ distints i en $W$, tenim $A\cap B=S$. En atres paraules, un sistema de conjunts o colecció de conjunts $W$ és un girasol si l'intersecció per parelles de cada conjunt en $W$ és constant. Nota que esta intersecció, $S$, pot ser buida; una colecció de subconjunts disjuntos per parelles és també un girasol. De modo paregut, una colecció de conjunts, cada u contenint els mateixos elements és també un girasol trivialmente.

Teorema de sistemes delta i lema del girasol

Un resultat bàsic i senzill de Erdos i Rado afirma:

Teorema de $\Delta$-sistemes de Erdos-Rado:

Hi ha una funció $f(k,r)$ tal que qualsevol sistema $W$ de conjunts de cardinalidad a lo més $k$ en més de $f(k,r)$ membres conté un girasol de $r$ conjunts..

Prova. Supon que existix un sistema de conjunts $W$ tal que existixen $k>0$ i $r>0$ tal que per a qualsevol cardinalidad del sistema de conjunts $W$, no existix cap girasol de $r$ conjunts en $W$. Triem que $W$ siga infinit. Ya que $W$ no conté cap girasol de mida $r$, en $W$ pugues haver com a màxim $r-1$ conjunts disjuntos per parelles, ya que $r$ conjunts disjuntos per parelles constituirien un girasol. Siga $K_{a_0}$ el conjunt màxim de subconjunts disjuntos per parelles de $W$; $K_{a_0}$ és de cardinalidad com a màxim $r-1$. Seguix que cada conjunt en $W$ anara de $K_{a_0}$ creua en a lo manco un lloc en $K_{a_0}$. D'una atra manera, supongam que hi ha un conjunt en $W$ anara de $K_{a_0}$ el qual no es interseca en cap conjunt en $K$; llavors, seria disjunto per parella en qualsevol conjunt en $K$ i llavors en els $r-1$ conjunts de $K$, i açò últim formaria un girasol en $r$ conjunts, la qual cosa contradiu la suposició.

Per a $W$ arbitrariamente gran, existix un element $a_1$ en els conjunts en $K_{a_0}$ tal que una infinitat de conjunts en $W$ contindran a $a$ pel Principi de Casillas invers. Llevem l'element comú de tots estos conjunts i denotem este sistema de conjunts per $K_{a_1}$. Ya que per suposició, no existix cap girasol en $r$ conjunts, hi ha com a màxim $r-1$ conjunts disjuntos en $K_{a_1}$. D'una atra manera, aquells $r$ conjunts formarien un girasol i el conjunt d'intersecció del girasol seria $a$. Construïm $K_{a_k}$ a partir de $K_{a_{k-1}}$removent $a_k$ de l'infinitat de conjunts en $K_{a_{k-1}}$ que contenen a $a_k$, a on $a_k$ és un element dels (màxim) $r-1$ $k$-conjunts continguts en $K_{a_{k-1}}$. $K_{a_k}$ és ara un conjunt infinit de conjunts buits, implicant que existix un conjunt infinit de $k$-conjunts idèntics en $W$, lo que és una contradicció. Açò completa la prova.

Erdős y Rado (1960) & Rado (1960, p. 86) varen provar el lema de girasol, el qual declara que $f(k,r)\le k!(r-1{)}^{k+1}$.Allò és, si $k$ i $r$ són sancers positius, llavors un sistema de conjunts $W$ de cardinalidad major o igual que $k!(r-1{)}^{k+1}$ de conjunts de cardinalidad com a molt $k$ conté un girasol en a lo manco $r$ conjunts. La prova de la Teorema de la Delta-sistema de Erdos-Rado pot ser adaptada per al cas en que $W$ té tamany finito per a provar el lema, en particular, observant que el número total d'elements en els conjunts dels conjunts maximales disjuntos per parelles en $K_{a_0},K_{a_1},\dots ,K_{a_{k-1}},K_{a_k}$ són $(r-1)k,(r-1)(k-1),\dots ,r$ respectivament, i que el tamany de $K_{a_i}$ poden ser escohidos en ser tal que $K_{a_{i-1}}/[(r-1)(k-i)]$

Lo següent dona una prova directa inductiva del lema del girasol de Erdos-Rado.

Prova. Clarament $f(0,r)\le r-1$ ya que, si cada conjunt és el conjunt buit, llavors qualsevol conjunt de tamany $r$ format per conjunts buits és un girasol de $r$ conjunts. Ara, si $F$ conté conjunts de tamany $k+1$, o be té un subconjunt $K$ format per conjunts de tamany $(k+1)$ i disjuntos per parelles, en $|K|\ge r$, la qual cosa constituiria un girasol en $r$ conjunts, i terminaríem.

D'un atre modo, $F$ conté un subconjunt de conjunts disjuntos per parelles i de tamany com a molt $r-1$, i per lo tant conté màxim $(r-1)(k+1)$ elements distints. En este últim cas, hi ha un element dels $\le r$ conjunts disjuntos per parelles contingut en a lo manco $|F|/(r-1)(k+1)$ conjunts de $F$. Açò succeïx pel següent lema, a on $\Sigma (C)$ denota la sumatoria dels elements en el conjunt $C$.

Lema 1. Supon que $A=(a_1,\mathrm{....},a_n)$ són sancers positius per a $n>0$ i que $\Sigma (A)=m$. Llavors per a tota $k$ tal que $n\ge k>0$, hi ha un subconjunt de $k$ elements de $A$, $B$, tal que $\Sigma (B)\ge m/k$.

D'ahí, si $|F|\ge (r-1)(k+1)f(k,r)$ a on $f(k,r)$ està ben definit per l'hipòtesis d'inducció, llavors $F$ conté un $r$ girasol de conjunts de tamany $k+1$. Per lo tant, $f(k+1,r)\le f(k,r)(r-1)(k+1)$, i vàrem demostrar la teorema.

}}