Huang, an assistant professor in the math department at Emory, settled an open question about the hypercube. The hypercube is a graph on N=2n 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 n1/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.ReplyDelete
a bit of a stretch to call this adult, a kid.ReplyDelete
Thanks for your ready to read explanationReplyDelete