Huang, an assistant professor in the math department at Emory, settled an open question about the hypercube. The hypercube is a graph on N=2

^{n}vertices where each vertex corresponds to an n-bit string and their are edges between vertices corresponding to strings that differ in a single bit. Think of the set of the strings of odd parity, N/2 vertices with no edges between them. Add any other vertex and it would have n neighbors. Huang showed that no matter how you placed those N/2+1 vertices in the hypercube, some vertex will have at least n

^{1/2}neighbors. By an old result of Gotsman and Linial, Huang's theorem implies the sensitivity conjecture.

I won't go through the shockingly simple proof, the paper is well written, or you can read the blogs I linked to above or even just Ryan O'Donnell's tweet.

I have nothing more to say than wow, just wow.

The hypercube is an n-cube, not a graph. The 1-skeleton of the hypercube is a graph.

ReplyDeletea bit of a stretch to call this adult, a kid.

ReplyDeleteThanks for your ready to read explanation

ReplyDelete