Mignonne, allons voir si Newroz...

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 :

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.

Exemple de diagramme de Venn à 2 ensembles

Exemple de diagramme de Venn à 3 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, 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

A gauche, le diagramme d'Euler correspondant au syllogisme
A droite, le diagramme de Venn du même syllogisme

Il faudra attendre un siècle pour que l'anglais John Venn modernise les diagrammes d'Euler. Avec lui, les patates ne sont jamais imbriquées ou disjointes, toutes les possibilités apparaissant a priori. Les cas impossibles sont simplement grisés (dans le cas précédent, on a grisé la partie correspondant aux bonnes comédies romantiques sans Hugh Grant, puisqu'elles n'existent pas).

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ⁿ 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. A partir de 4, les choses se compliquent. Plusieurs écoles s'affrontent :

D'un côté, on peut suivre la méthode 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. La méthode fonctionne plutôt bien (peut-être existe-t-il un diagramme de Venn dont le graphe dual n'est pas hamiltonien ?), mais conduit à des résultats un peu brouillons...

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

L'autre méthode, avec bien plus de symétries, est celle de Anthony Edwards. On part d'un plan coupé par deux axes perpendiculaires (diagramme de Venn à 2 ensembles), puis on ajoute un 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.

Diagrammes de Venn à 3, 4, 5 et 6 ensembles. Point positif : il y a un peu plus de symétrie.

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, un bon diagramme de Venn est un diagramme symétrique. 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 soucis, mais les choses se gâtent pour n=4. Cela dit, avec 5 ellipses, on obtient assez facilement un diagramme symétrique :

Diagramme de Venn (simple) symétrique pour n=5

Et pour n=4 ? Quand on essaye, on tombe toujours sur un diagramme de la forme ci-dessous. Un tel diagramme n'est pas de Venn, puisque certaines régions sont manquantes (par exemple, il n'y a pas de région seulement rouge et verte).

Raisonnons autrement. Dans un diagramme de Venn symétrique à n patates, il y a 2ⁿ régions. Parmi elles, il y en a C(n,k) correspondant à l'intersection de k patates, réparties équitablement sur les n patates. Il faut donc que C(n,k) soit divisible par n, ce qui n'arrive que lorsque n est un nombre premier.

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)

Maintenant que l'on sait que des diagrammes symétriques à 7, 11, 13 ou 17 pétales peuvent exister, il faut les trouver. C'est ce qui a été fait par Edward en 1996 (7 pétales), par Hamburger, Petruska et Sali en 2004 (11 pétales) et par Killian, Ruskey, Savage et Weston en 2006 (généralisation).

Adelaide, l'un des 23 diagrammes symétriques à 7 pétales

Un diagramme symétrique pour n=11.

Finalement
Il reste tout de même un soucis majeur : ce dernier diagramme est affreusement laid, la faute à sa non simplicité. Le problème, c'est que lorsque deux courbes se croisent, elles sont rarement les seules. Un diagramme de Venn à 11 ensembles devrait avoir 2046 (2¹¹-2) intersections, celui-ci n'en a que 1837.

On dit qu'un diagramme de Venn est simple quand les intersections ne se font jamais entre plus de deux courbes. Avant le mois de juillet, personne ne savait si un diagramme simple existait pour n=11. C'est désormais chose faite : il existe !

Désormais, la question se pose pour n=13...

---

Sources :

A New Rose : The First Simple Symmetric 11-Venn Diagram, l'article original de Ruskey et Mamakani.
A New Rose : The First Simple Symmetric 11-Venn Diagram, la version simplifiée de l'article, avec plus d'images et moins d'équations (d'où provient l'image de Newroz)
A Survey of Venn Diagrams, le site de très complet de Ruskey et Weston (d'où proviennent les deux derniers diagrammes)
Le tag "venn-diagram" sur tumblr, le plein d'humour à base de diagrammes de Venn

Autres images : xkcd, xkcd, wikicommons

Comments

[Guillaum]

Très intéressant ! Toutefois je pense que le potentiel comique des diagrammes de Venn à 11 pétales est assez limité. (Ce strip de xckd sur les sites universitaires est tellement vrai mais TELLEMENT vrai !)

[RuBisCO]

En tout cas, c'est magnifique ! Bien plus beau que les rosaces de primaires !