100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Corentin Faipeur

preuve de la conjecture de sensitivité par Hao Huang
Mardi, 15 Juin, 2021 - 15:30
Résumé : 

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é.

Thème de recherche : 
Probabilités
Salle : 
16
logo uga logo cnrs