16 novembre 2012

1 commentaire — commenter cet article

Mignonne, allons voir si Newroz...

Les diagrammes de Venn symétriques et simples existent pour n=11 !

El Jj

Une première version de cet article a été publiée sur le blog de l’auteur.

Ils l’ont fait ! La question était ouverte depuis les années 60, et pourtant, ils sont parvenus à le débusquer ! Les diagrammes de Venn symétriques et simples à 11 ensembles existent bel et bien ! Les deux mathématiciens canadiens Khalegh Mamakani et Frank Ruskey sont très fiers de vous présenter leur bébé. Voici Newroz :

PNG - 68.3 ko
Newroz
Newroz : 11 pétales, 2046 intersections, né le 27 juillet 2012

Au commencement

Les diagrammes de Venn, tout le monde connaît : deux patates (ou plus) qui s’entrecroisent pour représenter l’intersection d’ensembles. En théorie, on devrait l’utiliser pour se représenter mentalement les lois de De Morgan, mais dans la pratique, on s’en sert surtout pour asseoir la supériorité de l’humour à base de mathématiques [1].

PNG - 17.7 ko
Exemple de diagramme de Venn à 3 ensembles
JPEG - 73.4 ko
Exemple de diagramme de Venn à 2 ensembles

Leonhard Euler n’avait pas tout ça en tête quand il a utilisé pour la première fois au XVIIIe siècle des patates pour étudier systématiquement les syllogismes. Un syllogisme c’est un raisonnement logique, par exemple :

« Toute bonne comédie romantique est anglaise.
Or tout bon film anglais met en vedette Hugh Grant.
Donc toute bonne comédie romantique met en vedette Hugh Grant. »

Pour représenter graphiquement les syllogismes, Euler a mis en place un système de diagramme. A chaque type de syllogisme correspond un diagramme d’Euler.

PNG - 13.9 ko
Le diagramme d’Euler correspondant au syllogisme ci-dessus
Ce syllogisme se traduit par trois cercles imbriqués.

Il faudra attendre un siècle (1880) pour que l’anglais John Venn modernise le travail d’Euler. Plutôt que d’avoir autant de diagrammes que de syllogismes, Venn propose un diagramme unique permettant de représenter tous les syllogismes : trois cercles qui s’entrecroisent en formant 7 régions. Les régions correspondant à des cas impossibles sont simplement grisées.

PNG - 18.7 ko
Le diagramme de Venn correspondant au syllogisme ci-dessus
Seules trois régions ne sont pas grisées, ce sont les régions correspondant à des situations possibles.

Il faut aussi citer Lewis Caroll (celui qui a écrit Alice au Pays des Merveilles), qui a lui aussi mis son grain de sel dans les représentations graphiques des syllogismes.

Ensuite

Pour faire un bon diagramme de Venn, il faut donc $n$ patates (une région du plan délimitée par une courbe fermée sans point double) qui s’entrecroisent et

  • qui forment $2^n$ régions (connexes)
  • que toutes les intersections envisageables soient présentes.

Pour 0, 1, 2 ou 3 patates, on a les diagrammes en tête. À partir de 4, les choses se compliquent. Plusieurs écoles s’affrontent :

D’un côté, on peut suivre la méthode originale de Venn : on construit le diagramme à $n+1$ ensembles à partir de celui à $n$ ensembles en traçant une courbe qui coupe en deux chacune des régions (il existe de nombreuses façons de construire cette courbe, conduisant à des diagrammes différents). La méthode fonctionne plutôt bien [2], mais conduit à des résultats quelque peu brouillons...

PNG - 58.7 ko
Diagrammes de Venn à respectivement 3, 4 et 5 ensembles
Les courbes ajoutées coupent en deux chacune des régions du diagramme précédent.

L’autre méthode, avec bien plus de symétries, est celle de Anthony Edwards (en 1989). On part d’un plan coupé par deux axes perpendiculaires (diagramme de Venn à 2 ensembles), puis on ajoute un premier cercle (diagramme à 3 ensembles). Chaque nouvelle courbe serpente autour de ce cercle, en le traversant à chaque nouvelle région. Cette fois-ci, la méthode est universelle, et produit des résultats visuellement intéressants.

PNG - 47.5 ko
Diagrammes de Venn à 3, 4, 5 et 6 ensembles
Construits selon la méthode d’Edwards, le résultat final est bien plus symétrique.

Après

Il y a quand même quelque chose de gênant dans les diagrammes ayant plus de 3 ensembles : toutes les courbes ne sont pas identiques ! Or, pour avoir un résultat esthétique, les diagrammes de Venn se doivent d’être symétriques. Il faudrait pour cela que chaque courbe soit l’image de la précédente par une rotation.
Avec $n=1$, $n=2$ ou $n=3$, il n’y a pas de souci, mais les choses se gâtent pour $n=4$. Cela dit, avec 5 ellipses, on obtient assez facilement un diagramme symétrique :

PNG - 29.2 ko
Diagramme de Venn (simple) symétrique pour n=5
Ce diagramme est symétrique : les cinq ellipses sont superposables, chacune étant l’image d’une autre par une rotation (de 72°)

Et pour $n=4$ ? Quand on essaye, on tombe systématiquement sur un diagramme de la forme ci-dessous, qui persiste à ne pas être de Venn.

PNG - 19.5 ko
Diagramme (simple) symétrique pour n=4
Ce diagramme n’est pas de Venn, certaines régions ne sont pas présentes (par exemple, aucune région seulement jaune et bleue)

On peut en fait le démontrer : pour $n=4$, un diagramme de Venn symétrique est composé de $2^4=16$ régions. Mais puisque le diagramme est symétrique, chaque région est l’image d’une autre par une rotation de 90° : elles sont donc toutes présentes en 4 exemplaires. Parmi celles-ci, $C(4,2)=6$ correspondent à l’intersection de 2 ensembles [3]. Puisque 6 n’est pas un multiple de 4, un tel diagramme ne peut pas exister.

En fait, pour qu’un diagramme de Venn puisse être symétrique, il faut impérativement que le nombre d’ensembles $n$ soit un nombre premier (2, 3, 5, 7, 11 ...).

Démonstration générale

Dans un diagramme de Venn symétrique à $n$ ensembles, il y a $2^n$ régions. Le diagramme étant symétrique, chaque région est l’image d’une autre par une même rotation (d’angle $\frac{360°}{n}$), ce qui implique qu’elles sont toutes présentes en $n$ exemplaires (à l’exception de la région extérieure et de celle du centre). De plus, il y a $C(n,k)$ régions qui correspondent à l’intersection de $k$ ensembles (regroupées donc par groupes de $n$ régions identiques). Autrement dit, il faut que tous les $C(n,k)$ soient divisibles par $n$, ce qui n’arrive que lorsque $n$ est un nombre premier [4].

Bref : si un diagramme de Venn à $n$ ensembles est symétrique, alors $n$ est premier. (Et on oublie les diagrammes symétriques à 4 ou 42 ensembles)

Puisqu’il n’y a pas d’obstruction pour l’existence des diagrammes symétriques à 7, 11, 13 ou 17 pétales, il faut les trouver. C’est ce qui a été fait par Edward en 1996 (7 pétales), par Hamburger en 2002 (11 pétales) et par Killian, Ruskey, Savage et Weston en 2006 (généralisation à tout nombre premier de pétales).

GIF - 16.9 ko
Adelaïde
L’un des 23 diagrammes symétriques à 7 pétales, qui tient son nom de la ville australienne dans laquelle il a été découvert.
GIF - 82.3 ko
Le diagramme de Hamburger
Diagramme de Venn symétrique (non simple) à 11 ensembles découvert par Peter Hamburger en 2002.

Aujourd’hui

Mais le travail n’est pas tout à fait complet, il reste un souci majeur : ce dernier diagramme est affreusement laid ! La faute à sa non-simplicité. On dit qu’un diagramme est simple quand il n’existe aucun point où 3 courbes (ou plus) se croisent. Dans le diagramme de Hamburger, il existe des points où les 11 courbes se croisent. Alors qu’un diagramme de Venn à 11 ensembles devrait avoir 2046 ($=2^{11}-2$) intersections, celui-ci n’en a que 462. Avant aujourd’hui, les meilleurs diagrammes à 11 ensembles atteignaient péniblement les 1837 intersections.

Mais ça, c’était avant la découverte de Mamakani et Ruskey ! En se lançant dans une recherche informatique minutieuse, ils ont réussi à fabriquer le premier diagramme de Venn symétrique et simple à 11 ensembles, montrant au passage que de tels diagrammes existent bel et bien. [5]

Mais la recherche n’est pas close. Le problème qui se posait pour $n=11$ se pose maintenant pour $n=13$. Existe-t-il un diagramme de Venn symétrique et simple à 13 pétales ? La question est ouverte.

PNG - 83.4 ko
Newroz
Contemplez-le une dernière fois !
P.S. :

PS1 : Et si certains souhaitent relire le poème de Ronsard...

PS2 : La rédaction d’Images des maths et l’auteur remercient, pour leur relecture attentive, les relecteurs dont le nom ou le pseudonyme est le suivant : flandrin, Nicolas Chatal, Jean-Baptiste, projetmbc.

Notes

[1Cette première illustration est le travail de l’excellent xkcd.

[2Il n’a cependant pas été démontré que l’on peut toujours construire cette courbe.

[3Ici, C(4,2) représente le nombre de façons de choisir 2 éléments dans un ensemble de 4. Voir l’article Wikipédia.

[4On peut s’en convaincre en regardant les premières lignes du triangle de Pascal : si $n$ et $k$ sont premiers entre eux, alors $C(n,k)$ est divisible par $n$, et réciproquement.

[5Si vous voulez davantage d’explications, je vous renvoie vers l’article original de Mamakani et Ruskey et le site de Ruskey.

Crédits images

Newroz — http://webhome.cs.uvic.ca/ ruskey/Publications/Venn11/Venn11.html
Exemple de diagramme de Venn à 3 ensembles — http://xkcd.com/112/
Le diagramme de Hamburger — Frank Ruskey and Mark Weston, http://www.theory.cs.uvic.ca/ cos/venn/VennEJC.html
Adelaïde — Frank Ruskey and Mark Weston, http://www.theory.cs.uvic.ca/ cos/venn/VennEJC.html
Newroz — http://arxiv.org/abs/1207.6452

Affiliation de l'auteur

Commentaires sur l'article

Pour citer cet article : El Jj, « Mignonne, allons voir si Newroz... »Images des Mathématiques, CNRS, 2012.

En ligne, URL : http://images.math.cnrs.fr/Mignonne-allons-voir-si-Newroz.html

Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :