I learned from a colleague at JD.com that a professor Huang Hao from Emory math department made breakthrough just weeks ago in the following conjecture of Gotsman and Linial:
Given any induced subgraph of the hypercube graph , with , its maximum degree is at least . This by itself is already a big deal since the previous best result by famous people like Fan Chung was on the order of , and presumably not obvious either.
Since the prof is Chinese, it was well advertised in the Chinese blogging community, though not to the extent of Yitang Zhang’s prime gap result.
The connection to other areas of complexity theory is even more remarkable, and well-exposed in the author’s original paper. In fact, I found that the subsequent advertising blogs by other mathematicians and journalists to be largely not adding much expository value.
A notion of complexity is given by the so-called sensitivity . For a boolean function , where viewed as a set, the sensitivity function is defined by , where stands for the binary vector with the -th coordinate flipped. In other words, point-wise sensitivity is the number of ways the function can be perturbed by a single coordinate, or more metaphorically, the co-dimension of its null tangent space at . Global sensitivity of is simply . This is a natural measure of complexity of since if is constant, sensitivity is clearly . But maybe it’s not fundamental enough to let us tackle P versus NP because for a simple function like the parity function , already achieves maximum sensitivity.
Now the connection between sensitivity and maximum degree is proved by Gotsman and Linial in a quarter-page proof, so I encourage everyone to read it. But here is my digested version:
The following two statements are equivalent:
- The max degree of and the induced subgraph on is bounded below by , provided .
- The sensitivity of a boolean function with satisfies where is the degree of , viewed as a polynomial. More precisely, .
To see the equivalence, simply consider the indicator function of with domain , multiplied by the parity function . The degree of at is clearly related to its sensitivity at . Indeed the parity makes so that neighbors in the original graph change the function value.
The requirement of corresponds to , which in turn corresponds to . The rest should be pretty straightforward.
Statement 2 can be equivalently relaxed to the case where . The reason, as pointed out to me by Gil Kalai, is that given a function of degree , there is a monomial of exactly variables. Let . Then has degree and sensitivity less than or equal to that of . But has full degree (equal to the dimension of its domain), so 2 applies. And we get
I will devote another post for Huang’s actual proof.