What is the Poincare Inequality, Really?

This post is a cry for help.

OK, it's more of a request for information. First, let me explain what I know, which I hope will be enough to be an informative post about graph expansion in its own right.

I've been reading off and on about Fourier analysis of Boolean functions for awhile, and recently in the context of Property Testing towards giving the talk I posted, where it is really the elegant way of analyzing the linearity test. Afterwards I was doing some random online course exercises, and stumbled on a good one here, by Ryan O'Donnell.

Here's a proof for exercise 1, whose statement I'll rephrase:

'Poincare Inequality': Let (A, B) be a partition of the Boolean n-cube into two sets. Let p be the fraction of the cube's edges going between A and B (vertices are connected by an edge if at Hamming distance 1). Then,

p >= 2|A|*|B|/(n*2^{2n}).

First, what does this say? If the cube were a 'totally random' graph, and A, B were a 'totally random' partition of the vertices, we'd expect a 2|A|*|B|/2^{2n} fraction of the edges to go between A and B.

So, while ill-chosen partitions of the cube can induce sparser cuts than randomly chosen partitions of random graphs, Poincare says these can only be sparser by at most a factor of n. In this sense, the cube is robustly interconnected; not on a par with strong expanders, but to a nontrivial extent. An example that shows the inequality can be approximately tight is to let A be the vectors with first coordinate 0.
(Note: this is the 'extremal example' for edge expansion on the cube, whereas letting A be the set of vectors with Hamming weight at most k gives extremal examples for 'vertex expansion'... for more on the latter, see my June 2006 post.)


Proof: Pick x, y uniformly at random from the cube. The probability q that one is in A,the other in B (we don't care which one is in A) is exactly 2|A|*|B|/2^{2n}.

On the other hand, choose also a random monotone path P between x and y. The probability that x, y lie in these distinct sets is at most the probability that at least one of the edges on P goes between A and B (call this a 'mixed edge'), since the first event implies the second.

The path has edge length at most n, and each individual edge that appears is uniformly randomly distributed over all edges of the cube (though there is dependence in the joint distribution), so there is a mixed edge with probability at most n*p--here we are using the union bound.

So q = 2|A|*|B|/2^{2n} <= n*p, or

p <= 2|A|*|B|/(n*2^{2n}). QED.


What was interesting about this proof for me was that I had used the same idea once before, to show a seemingly different type of result to the extent that

"If an n-by-n 0/1 matrix is 'reasonably balanced' between 0s and 1s, it has either 'many' only-slightly-less-balanced rows, or 'many' only-slightly-less-balanced columns."

(It's easy to see you must allow this choice of rows-or-columns in the statement.)

Looking back at that proof, which was just the one I described but now with length-2 paths instead of length-n ones and n-element hyperedges in place of edges, I realized that result too was 'about' (hyper-)graph expansion. The proof technique also could apply to cases where the edges along the random path are not uniformly distributed, but merely almost-uniform.

I also know, however, that Poincare was working in a very different mathematical milieu, one which, while aware of the importance of isoperimetric inequalities (as this sort of thing can be considered, and the most famous historical example of which being the result that circles have minimal perimeter among planar figures of a given area), was not to my knowledge pursuing expander graphs per se. So what was the larger 'story' of which Poincare's Inequality originally played a part?

Update: My question about the inequality still stands; however, I've found work in the literature that puts my proof of the inequality in perspective. The argument looks to be a simple variant of something called the 'canonical paths' technique, that has successfully shown the good expansion properties (or the weighted version, 'conductance') for much more complex structures; Jerrum and Sinclair are two prominent names in this area, and Jerrum wrote an excellent chapter in 'Probabilistic Methods for Algorithmic Discrete Mathematics' which has been getting me up to speed in this area. I hope to post more about this soon.