Tournesol (mathématiques)
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/e/ec/Sonnenblume_02_KMJ.jpg/220px-Sonnenblume_02_KMJ.jpg)
En mathématiques, dans les domaines de la théorie des ensembles et de la combinatoire extrémale, un tournesol ou système est une famille d'ensembles dont les paires d'éléments distincts ont toutes la même intersection[1]. Cette intersection commune est appelée le noyau du tournesol.
Présentation
[modifier | modifier le code]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 - 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[2],[3].
Définition formelle
[modifier | modifier le code]Soit une famille de parties d'un ensemble . La famille est appelée un tournesol (ou -system ) s'il existe un sous-ensemble de tel que pour toute paire d'éléments distincts et de , on a ; est appelé le noyau de . Un élément de figure donc soit dans toute partie de , soit dans une seule.
Dans la définition, le noyau peut être vide, autrement dit, une famille de sous-ensembles disjoints deux-à-deux est également un tournesol.
Lemme et conjecture du tournesol
[modifier | modifier le code]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 est suffisamment grande pour contenir nécessairement un tournesol. Formellement, on considère la fonction
qui, pour des entiers non négatifs , dénote est le plus petit entier tel qu'une famille de taille dont chaque ensemble a au plus éléments contient un tournesol de taille .
Lemme du tournesol
[modifier | modifier le code]Un résultat fondamental et simple à établir dû à Erdős et deRado[4], 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
Ainsi, pour des entiers et , toute une famille d'ensembles de cardinalité supérieure ou égale à composée d'ensembles de cardinalité contient un tournesol avec au moins éléments.
Lemme du tournesol de Erdős et Rado — Pour tout , , il existe un entier tel qu'un famille d'ensembles à éléments et de taille supérieure à contient un tournesol de taille . De plus, on a
.
Conjecture du tournesol de Erdős-Rado
[modifier | modifier le code]La conjecture du tournesol est l'une des nombreuses variantes de la conjecture de Erdős & Rado concernant la majoration de la fonction . La conjecture énonce que, pour chaque , on a
pour une constante dépendant uniquement de . La conjecture est ouverte même pour des petites valeurs ; ainsi pour , on ne sait pas si pour une constante [5]. Un article de 2021 de Alweiss, Lovett, Wu et Zhang donne la majoration pour [6],[7]. Un mois après la publication de la première version de son article, Rao a précisé la majoration de la constante : [8]. La borne plus précise est [9].
Bornes inférieures du tournesol
[modifier | modifier le code]Erdős et Rado ont prouvé la borne inférieure suivante sur , qui revient à prouver que le lemme original du tournesol est optimal en .
- Pour tout et , on a .
Un résultat plus précis est le inégalité suivante :
Applications du lemme du tournesol
[modifier | modifier le code]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 de circuits monotones, un résultat qui à l'époque était tout noouveau 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 de profondeur . 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[10].
Références
[modifier | modifier le code]- (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).
- Le terme original pour ce concept est « -system ». Le nom « tournesol », qui a peut-être été introduit par Deza et Frankl (1981), l'a remplacé progressivement.
- Gil Kalai, « Extremal Combinatorics III: Some Basic Theorems », Combinatorics and more, .
- Terence Tao, « The sunflower lemma via Shannon entropy », What's new, .
- Erdős et Rado 1960, p. 86
- Abbott, Hanson et Sauer (1972).
- Alweiss et al. (2020).
- Kevin Hartnett, « Mathematicians Begin to Tame Wild ‘Sunflower’ Problem », Quanta Magazine - Illuminating Science,
- Rao (2020).
- Bell, Chueluecha et Warnke (2021).
- Flum et Grohe (2006).
Bibliographie
[modifier | modifier le code]- [2072] Harvey Leslie Abbott, Denis Hanson et Norbert Sauer, « Intersection theorems for systems of sets », Journal of Combinatorial Theory, série A, vol. 12, no 3, , 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, , 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, no 7, , 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, no 03, , 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, no 3, , 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, no 1, , 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 », , 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, no 1, , p. 187–202 (DOI 10.1007/s00493-023-00012-z)
- [2003] Thomas Jech, Set Theory, Springer, coll. « Springer Monographs in Mathematics », , 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, , 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, (ISBN 978-0-444-85401-8)
- [2020] Anup Rao, « Coding for Sunflowers », Discrete Analysis, vol. 2020, no 2, , article no 11887 (DOI 10.19086/da.11887
, lire en ligne)
- [2023] Anup Rao, « Sunflowers: from soil to oil », Bull. Amer. Math. Soc., vol. 60, no 1, , 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, , p. 399–400
- [2020]Terence Tao, « The sunflower lemma via Shannon entropy », What's new (personal blog), (lire en ligne)
Liens externes
[modifier | modifier le code]