Consider the set S={-1,1}

^{n}. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x

_{1},…,x

_{n}) and y = (y

_{1},…,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

_{1},…,x

_{i},…,x

_{n}) ≠ f(x

_{1},…,-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

_{1},…,x

_{i},…,x

_{n}) = g(x

_{1},…,-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

_{1},…,x

_{n})=f(x

_{1},…,x

_{n})x

_{1}⋯x

_{n}. If f has a degree n term, the variables in that term cancel out on S (since x

_{i}

^{2}=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

^{n}/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

^{n}/2, Huang's result gives the sensitivity conjecture.

## No comments:

## Post a Comment