Degree and Sensitivity

Hao Huang's proof of the sensitivity conjecture that I posted on last week relied on a 1992 result of Gotsman and Linial. Let's talk about that result.

Consider the set S={-1,1}ⁿ. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x₁,…,x_n) and y = (y₁,…,y_n) in S if there is exactly one i such that x_i ≠ y_i. Every vertex has degree n.

We say a vertex x is odd if x has an odd number of -1 coordinates, even otherwise. Every edge joins an odd and even vertex.

Let f be a function mapping S to {-1,1}. The sensitivity of f on x is the number of i such that f(x₁,…,x_i,…,x_n) ≠ f(x₁,…,-x_i,…,x_n). The sensitivity of f is the maximum over all x in S of the sensitivity of f on x.

Let g be the same function as f except that we flip the value on all odd vertices. Notice now that the sensitivity of f on x is the number of i such that g(x₁,…,x_i,…,x_n) = g(x₁,…,-x_i,…,x_n).

Let G be the induced subgraph of vertices of x such that g(x)=-1 and H be induced subgraph on the set of x such that g(x)=1. The sensitivity of f is the maximum number of neighbors of any vertex in G or H.

Consider f as a multilinear polynomial over the reals. The sensitivity conjecture states there is some α>0 such that if f has degree n then f has sensitivity at least n^α.

Note g(x₁,…,x_n)=f(x₁,…,x_n)x₁⋯x_n. If f has a degree n term, the variables in that term cancel out on S (since x_i²=1) and the constant of the degree n term of f becomes the constant term of g. The constant term is just the expected value, so f has full degree iff g is unbalanced.

GL Assumption: Suppose you have a partition of the hypercube into sets A and B with |A| ≠ |B|, and let G and H be the induced subgraphs of A and B. Then there is some constant α>0 such that there is a node of A or B with at least n^α neighbors.

The above argument, due to Gotsman and Linial, shows that the GL assumption is equivalent to the sensitivity conjecture.

Huang proved that given any subset A of the vertices of a hypercube with |A|>2ⁿ/2 the induced subgraph has a node of degree at least n^1/2. Since either A or B in the GL assumption has size greater than 2ⁿ/2, Huang's result gives the sensitivity conjecture.