Un bijou (algèbre linéaire/ théorie des graphes)

Lucas

Bonjour
L'article avait fait beaucoup de bruit il y a quelques années mais je ne me souviens pas qu'on en ait parlé ici. En 2019 Hao Huang a publié une preuve élémentaire (essentiellement en 1 page !) ici : https://arxiv.org/abs/1907.00847 du résultat suivant.

Dans l'hypercube discret $\{0,1\}^n$ formé de $2^n$ sommets il est possible de colorier $2^{n-1}$ sommets en rouge de sorte que 2 sommets rouges ne soient jamais voisins (je vous laisse trouver comment). Par contre si on colorie $2^{n-1} +1$ sommets en rouge alors il existe un sommet qui a au moins $\sqrt{n}$ voisins rouges. Ceci résout un vieux problème en maths discrètes : la "sensitivity conjecture".

Je viens de lire l'article et c'est un vrai bijou. Ça n'utilise que des outils d'algèbre linéaire de L2, si on admet le théorème d' "entrelacement de Cauchy", qui est moins trivial. Depuis D.Knuth a réécrit une preuve la preuve sans utiliser d'entrelacement :
https://www-cs-faculty.stanford.edu/~knuth/papers/huang.pdf  (cela obscurcit peut-être l'argument de Huang).

L'idée absolument magnifique de Huang est de considérer la matrice d'adjacence de l'hypercube, mais en remplaçant certains $1$ par des $-1$. Ceci écarte violemment les valeurs propres, et ça suffit à conclure.

Je recommande cette très saine lecture à ceux et celles qui ici qui souhaitent apprendre des jolies maths et voir à quoi ressemble un article de recherche.