The Sensitivity Conjecture is true

You need to know: For the Theorem: Graph, induced subgraph, degree of a vertex of a graph, notation \Delta(H) for the maximum degree of graph H. In addition, you may want to go the original paper (or online) and learn what is the Sensitivity Conjecture to fully appreciate the context.

Background: The n-dimensional hypercube graph is the graph Q^n, whose vertex set consists of vectors (x_1, x_2, \dots, x_n) such that each x_i is either 0 or 1, and two vectors are adjacent if they differ in exactly one coordinate.

The Theorem: On 1st July 2019, Hao Huang submitted to arxiv a paper in which he proved that for every integer n\geq 1, and every (2^{n-1}+1)-vertex induced subgraph H of Q^n, one has \Delta(H) \geq \sqrt{n}.

Short context: The inequality \Delta(H) \geq \sqrt{n} in the Theorem is the best possible, in sense that it is tight when n is a perfect square. The Theorem confirms a conjecture of Gotsman and Linial made in 1992, who proved that their conjecture, if true, would imply the celebrated Sensitivity Conjecture, one of the famous conjectures in theoretical computer science. The Theorem confirms the Gotsman-Linial conjecture and hence the Sensitivity Conjecture.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Leave a comment