Corentin Faipeur

On considère l'hypercube ${0,1}^n$, avec les arêtes reliant deux sommets lorsque toutes les composantes sont égales sauf une. Dans ce graphe, le nombre maximum de points deux à deux non reliés est $2^{n-1}$ : un exemple de telle partie est donné par l'ensemble des n-uplets sont la somme des coordonnées est paire. On ne peut pas faire plus sinon on peut trouver dans la partie deux sommets de la forme $(x_1,...,x_{n-1},0)$ et $(x_1,...,x_{n-1},1)$.

Hao Huang a montré que pour toute partie à $2^{n-1}+1$ éléments, le degré maximum est au moins égal à la racine carrée de $n$.

Ce résultat a des répercussions intéressantes en théorie des fonctions booléennes, montrant l'équivalence de certaines mesures de complexité.