Recouvrir les sommets de l’hypercube
Quand on raisonne sur les coordonnées, la géométrie plane (avec abscisse et ordonnée) et la géométrie dans l’espace (avec abscisse, ordonnée et cote) se généralisent facilement à la géométrie à n dimensions. En deux dimensions, les points dont les coordonnées ne sont que des 0 et des 1 forment un carré. Dans l’espace, les sommets, notés 000, 100, 110, 010, 001, 101, 111 et 011, forment un cube. Dans l’espace à n dimensions, on obtient un hypercube, qu’on notera Hn. On peut aussi considérer des hyperplans, qui sont alors tout simplement les ensembles de points décrits par des équations de la forme a1 x1 + a2 x2 + … +an xn = b.
Le cadre étant fixé, un petit jeu occupe les matheux depuis un moment : recouvrir des ensembles de points avec un minimum d’hyperplans, et en particulier des ensembles constitués de certains sommets de l’hypercube. En 1993, l’Israélien Noga Alon et le Hongrois Zoltán Füredi ont démontré que recouvrir tous les sommets de l’hypercube sauf l’origine (celui dont toutes les coordonnées sont nulles, parfois noté 0n ) nécessite exactement n hyperplans. On peut en effet choisir tous les hyperplans d’équation xi = 1. La difficulté est de comprendre pourquoi cela n’est pas ...
Lire la suite