Thursday, July 11, 2019

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}n. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x1,…,xn) and y = (y1,…,yn) in S if there is exactly one i such that xi ≠ yi. 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(x1,…,xi,…,xn) ≠ f(x1,…,-xi,…,xn). 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(x1,…,xi,…,xn) = g(x1,…,-xi,…,xn).

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(x1,…,xn)=f(x1,…,xn)x1⋯xn. If f has a degree n term, the variables in that term cancel out on S (since xi2=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|>2n/2 the induced subgraph has a node of degree at least n1/2. Since either A or B in the GL assumption has size greater than 2n/2, Huang's result gives the sensitivity conjecture.

No comments:

Post a Comment