20 mars 2011

2 messages - Retourner à l'article
  • Le lemme des Mariages

    le 21 mars 2011 à 15:29, par Maxime Bourrigan

    Merci, Frédéric, pour ce bel article.

    J’ai une question à propos du lemme des mariages, qui vient d’une interférence avec un truc de Dijkstra au sujet du principe des tiroirs que j’ai lu il y a peu : http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html

    Dans ce texte, Dijkstra dit en substance qu’une partie de l’émerveillement produit par une preuve utilisant le principe des tiroirs sous sa forme classique (Si on a plus de chaussettes que de tiroirs, un tiroir accueillera plusieurs chaussettes) vient du fait que la formulation, même si elle est très plaisante, nécessite un gros effort intellectuel pour être appliquée. Essentiellement, il faut pas mal de temps pour comprendre qui vont être les tiroirs et qui les chaussettes avant d’appliquer le principe. Dijkstra dit alors que le principe des tiroirs a une forme différente, qu’il appelle « purifiée », beaucoup moins « catchy » mais beaucoup plus efficace : dans une collection de nombres, le maximum est supérieur à la moyenne.

    Je me demandais si une chose similaire pouvait être faite avec le lemme des mariages : les remarques de Dijkstra semblent s’y appliquer tout aussi bien. La formulation est incisive, basée sur une métaphore forte, les preuves l’utilisant héritent souvent d’une patine d’élégance et l’appliquer demande un peu d’astuce, comme le suggère ta devinette. Penses-tu qu’il existe une version « purifiée » du lemme des mariages ? Cela semble d’autant plus crédible qu’il semble relié à un grand nombre de résultats en combinatoire, dans des contextes variés : théorème de König sur les graphes bipartis, de Dilworth sur les ensembles ordonnés, etc.

    Et encore bravo !

    Répondre à ce message
  • Le lemme des Mariages

    le 27 mars 2011 à 21:26, par Frédéric Le Roux

    Bonjour Maxime,

    merci pour ton commentaire. Je dois dire que je tiens beaucoup aux images en maths, et que je préfère penser à des tiroirs ou à des mariages qu’à des nombres. Je n’ai pas vraiment l’impression que j’aurais plus de facilité à appliquer la formulation de Dijkstra : ça dépend probablement du problème (et aussi de la forme d’esprit de celui qui s’y attaque). Le fait de penser à des carrés, ou à des cartes à jouer, comme à des filles ou des garçons, ça demande un gros effort d’abstraction ; mais je ne sais pas si l’effort est moindre si on essaie d’appliquer la formulation purement ensembliste du Lemme.

    Pour moi, l’émerveillement vient plutôt du fait que le même énoncé peut s’appliquer à des objets très différents, quelle que soit la formulation de cet énoncé.

    Frédéric

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.