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.

Un tournesol mathématique peut être représenté comme une fleur. Le noyau du tournesol est la partie brune au milieu, et chaque élément du tournesol est l'union d'un pétale et du noyau.

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}.$

.

Démonstration

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.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sunflower (mathematics) » (voir la liste des auteurs).

Bibliographie

• [2072] Harvey Leslie Abbott, Denis Hanson et Norbert Sauer, « Intersection theorems for systems of sets », Journal of Combinatorial Theory, série A, vol. 12, n^o 3,‎ 1972, p. 381–389 (DOI 10.1016/0097-3165(72)90103-3).
• [2020] Ryan Alweiss, Shachar Lovett, Kewen Wu et Jiapeng Zhang, « Improved bounds for the sunflower lemma », Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery,‎ juin 2020, p. 624–630 (ISBN 978-1-4503-6979-4, DOI 10.1145/3357713.3384234, arXiv 1908.08483, S2CID 201314765)
• [2021] (en) Tolson Bell, Suchakree Chueluecha et Lutz Warnke, « Note on Sunflowers », Discrete Mathematics, vol. 344, n^o 7,‎ 2021, p. 112367 (DOI 10.1016/j.disc.2021.112367, MR 4240687, arXiv 2009.09327, S2CID 221818818)

• [2023 Domagoj Bradač, Matija Bucić et Benny Sudakov, « Turán numbers of sunflowers », Proceedings of the American Mathematical Society, vol. 151, n^o 03,‎ mars 2023, p. 961–975 (DOI 10.1090/proc/16160)

• [1981] Michel Deza et Péter Frankl, « Every large set of equidistant (0,+1,–1)-vectors forms a sunflower », Combinatorica, vol. 1, n^o 3,‎ 1981, p. 225–231 (ISSN 0209-9683, DOI 10.1007/BF02579328, MR 637827, S2CID 14043028)
• [1960] Paul Erdős et R. Rado, « Intersection theorems for systems of sets », Journal of the London Mathematical Society (Second Series), vol. 35, n^o 1,‎ 1960, p. 85–90 (ISSN 0024-6107, DOI 10.1112/jlms/s1-35.1.85, MR 0111692)
• [2006] Jörg Flum et Martin Grohe, « A Kernelization of Hitting Set », EATCS Ser. Texts in Theoretical Computer Science, Springer « Parameterized Complexity Theory »,‎ 2006, p. 210–212 (ISBN 978-3-540-29952-3, DOI 10.1007/3-540-29953-X, MR 2238686)
• [2023] Jacob Fox, János Pach et Andrew Suk, « Sunflowers in Set Systems of Bounded Dimension », Combinatorica, vol. 43, n^o 1,‎ 1^er février 2023, p. 187–202 (DOI 10.1007/s00493-023-00012-z)
• [2003] Thomas Jech, Set Theory, Springer, coll. « Springer Monographs in Mathematics », 2003, 769 p. (ISBN 3-540-44085-2)
• [2023] Peter Frankl, Janos Pach et Dömötör Pálvölgyi, « Odd-Sunflowers », European Conference on Combinatorics, Graph Theory and Applications,‎ 28 août 2023, p. 441–449 (DOI 10.5817/CZ.MUNI.EUROCOMB23-061, lire en ligne)
• [1980] Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, North-Holland, 1980 (ISBN 978-0-444-85401-8)
• [2020] Anup Rao, « Coding for Sunflowers », Discrete Analysis, vol. 2020, n^o 2,‎ 25 février 2020, article n^o 11887 (DOI 10.19086/da.11887 , lire en ligne)
• [2023] Anup Rao, « Sunflowers: from soil to oil », Bull. Amer. Math. Soc., vol. 60, n^o 1,‎ 2023, p. 29–38 (DOI 10.1090/bull/1777 , lire en ligne)
• [1946] Nikolaĭ Aleksandrovich Shanin, « A theorem from the general theory of sets », C. R. (Doklady) Acad. Sci. URSS (New Series), vol. 53,‎ 1946, p. 399–400
• [2020]Terence Tao, « The sunflower lemma via Shannon entropy », What's new (personal blog),‎ 2020 (lire en ligne)

Liens externes

• Thiemann, René. The Sunflower Lemma of Erdős and Rado (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)