# Tournesol (mathématiques)

En mathématiques, dans les domaines de la théorie des ensembles et de la combinatoire extrémale, un tournesol ou système $\Delta$ est une famille d'ensembles dont les paires d'éléments distincts ont toutes la même intersection. Cette intersection commune est appelée le noyau du tournesol.

## Présentation

Le nom veut rappeler la similitude visuelle avec le tournesol botanique : lorsqu'on dispose les éléments d'un tournesol en un diagramme de Venn, les éléments du noyau sont regroupés au centre du diagramme et les éléments non partagés sont répartis selon un motif circulaire autour des éléments partagés. Dans le diagramme de Venn, les sous-ensembles en forme de lobe qui encerclent les éléments communs prennent l'apparence des pétales d'une fleur de tournesol.
La recherche concernant les tournesols portent sur la question suivante : dans quelles conditions existe-t-il un « gros » tournesol (un tournesol avec de nombreuses parties) dans une famille donnée d'ensembles ? Le lemme -$\Delta$ ou lemme du tournesol et la conjecture du tournesol d'Erdős-Rado tournent autour de cette question ; ils donnent des conditions successivement plus faibles pour l'existence d'un gros tournesol dans une famille donnée ; la conjecture du tournesol est l'un des problèmes ouverts les plus typiques de la combinatoire extrémale$^,$.

## Définition formelle

Soit ${\cal {F}}$ une famille de parties d'un ensemble $U$. La famille ${\cal {F}}$ est appelée un tournesol (ou $\Delta$-system ) s'il existe un sous-ensemble $S$ de $U$ tel que pour toute paire d'éléments distincts $A$ et $B$ de ${\cal {F}}$, on a $A\cap B=S$; $S$ est appelé le noyau de ${\cal {F}}$. Un élément de $U$ figure donc soit dans toute partie de ${\cal {F}}$, soit dans une seule.
Dans la définition, le noyau $S$ peut être vide, autrement dit, une famille de sous-ensembles disjoints deux-à-deux est également un tournesol.

## Lemme et conjecture du tournesol

L'étude des tournesols se concentre généralement sur la taille de la famille, en particulier on cherche à savoir quand une famille donnée ${\cal {F}}$ est suffisamment grande pour contenir nécessairement un tournesol. Formellement, on considère la fonction
    $f(k,r)$
qui, pour des entiers non négatifs $k,r$, dénote le plus petit entier $n$ tel qu'une famille ${\cal {F}}$ de taille $n$ dont chaque ensemble a au plus $k$ éléments contient un tournesol de taille $r$.

### Lemme du tournesol

Un résultat fondamental et simple à établir dû à Erdős et Rado, le théorème du système Delta, dit qu'un tel système existe. Erdős et Rado ont prouvé le lemme du tournesol, qui donne la majoration suivante
    $f(k,r)\leq k!(r-1)^{k}.$
Ainsi, pour des entiers $k$ et $r$, toute une famille d'ensembles ${\cal {F}}$ de cardinalité supérieure ou égale à $k!(r-1)^{k}$ composée d'ensembles de cardinalité $k$ contient un tournesol avec au moins $r$ éléments.
Lemme du tournesol de Erdős et Rado — Pour tout $k>0$, $r>0$, il existe un entier $f(k,r)$ tel qu'un famille ${\cal {F}}$ d'ensembles à $k$ éléments et de taille supérieure à $f(k,r)$ contient un tournesol de taille $r$. De plus, on a
    $f(k,r)\leq k!(r-1)^{k}.$
Soit ${\cal {F}}$ une famille d'ensembles à $k$ éléments qui ne contient pas de noyau de taille $r$. Soit $A_{1},A_{2},\dots ,A_{t}$ une sous-famille d'ensembles deux-à-deux disjoints de ${\cal {F}}$. Comme une famille d'ensembles deux-à-deux disjoints est un tournesol, on a $t<r$. Soit
    $A=\cup _{i=1}^{t}A_{i}$ .
Pour tout $a\in A$, on considère la famille
    ${\cal {F}}_{a}=\{S\backslash \{a\}:S\in {\cal {F}},a\in S\}$.
La taille $A$ est au plus $(r-1)k$ et la taille de chaque ${\cal {F}}_{a}$ est au plus $f(k-1,r)$, car un tournesol dans ${\cal {F}}_{a}$ est aussi un tournesol dans ${\cal {F}}$. On obtient
    $f(k,r)\leq (r-1)kf(k-1,r)$
d'où la majoration
    $f(k,r)\leq (r-1)^{k}\times k!$.

### Conjecture du tournesol de Erdős-Rado

La conjecture du tournesol est l'une des nombreuses variantes de la conjecture de Erdős & Rado concernant la majoration de la fonction $f(k,r)$. La conjecture énonce que, pour chaque $r>2$, on a
    $f(k,r)\leq C^{k}$
pour une constante $C>0$ dépendant uniquement de $r$ . La conjecture est ouverte même pour des petites valeurs $r$ ; ainsi pour $r=3$, on ne sait pas si $f(k,3)\leq C^{k}$ pour une constante $C>0$. Un article de 2021 de Alweiss, Lovett, Wu et Zhang donne la majoration $f(k,r)\leq C^{k}$ pour $C=O(r^{3}\log(k)\log \log(k))$$^,$. Un mois après la publication de la première version de son article, Rao a précisé la majoration de la constante : $C=O(r\log(rk))$. La borne plus précise est $C=O(r\log k)$.

### Bornes inférieures du tournesol

Erdős et Rado ont prouvé la borne inférieure suivante sur $f(k,r)$, qui revient à prouver que le lemme original du tournesol est optimal en $r$ .
    Pour tout $r$ et $k$, on a $(r-1)^{k}\leq f(k,r).$.
Un résultat plus précis est le inégalité suivante :
    $f(a+b,r)\geq (f(a,r)-1)(f(b,r)-1)$

## Applications du lemme du tournesol

Le lemme du tournesol a des applications en informatique théorique . Par exemple, en 1986, Alexandre Razborov a utilisé le lemme du tournesol pour prouver que le langage Clique exigeait un nombre $n^{\log(n)}$ de circuits monotones, un résultat qui à l'époque était tout nouveau dans la théorie de la complexité des circuits . Håstad, Jukna et Pudlák l'ont utilisé pour prouver les limites inférieures sur les circuits $AC_{0}$ de profondeur $3$. Il a également été appliqué dans la complexité paramétrée du problème de couverture par ensembles, pour donner des algorithmes traitables à paramètres fixes pour trouver de petits ensembles d'éléments contenant au moins un élément d'une famille d'ensembles donnée.