Three isoperimetric papers by Michel Talagrand (see the end of the post)

Discrete isoperimetric relations are of great interest on their own and today I want to tell you about a new isoperimetric inequality by Jeff Kahn and Jinyoung Park which leads to a solution to an old problem on the number of maximal independent sets. (I am thankful to Nathan Keller who told me about the new papers on the arXiv and to Jeff and Jinyoung who told me about the results a few months ago.)

Unrelated news: In connection with some a forthcoming announcement by Google regarding quantum computers, Scott Aaronson commented on his blog ” *Gil Kalai’s blog will indeed be an extremely interesting one to watch … you might get to witness the real-time collapse of a worldview! 😉” *Thanks for the publicity, Scott! Stay tuned, folks! For my current worldview see this post.

## Two papers by Jeff Kahn and Jinyoung Park

The number of maximal independent sets in the Hamming cube

**Abstract:** Let be the *n*-dimensional Hamming cube and . We prove that the number of maximal independent sets in is asymptotically ,

as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl.

The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in .

An isoperimetric inequality for the Hamming cube and some consequences

**Abstract:** (Slightly modified.)

Our basic result, an isoperimetric inequality for Hamming cube , can be written:

.

Here is uniform measure on and, for and , is zero if , and is the number of neighbors of not in , if . (where is the number of neighbors of in ).

This implies inequalities involving mixtures of edge and vertex boundaries, with related stability results, and suggests some more general possibilities. One application, a stability result for the set of edges connecting two disjoint subsets of V of size roughly |V|/2, is a key step in showing that the number of maximal independent sets in is This asymptotic statement, whose proof will appear separately, was the original motivation for the present work.

## Discussion

### Counting independent sets in graphs and hypergraphs and related things.

Asymptotic enumeration of independent sets (and number of colorings) in various graph is a big topic with very remarkable techniques and methods, and there are quite a few results when the graph in question is that of the discrete -cube. The maximal size of an independent set is and you may recall that the recently solved (by Hao Huang) sensitivity conjecture asked for the properties of an induced subgraph on vertices.

How many independent sets are there? Well, we can consider all the subsets of the two independent sets of size so this gives us . Korshunov and Sapozhenko proved in 1983 that the number is , and here is a link to a paper of Galvin describing a beautiful proof by Sapozhenko for this result. As an exercise you can try to figure out where the term comes from.

Now, lets talk about maximal independent sets. The Kahn-Park asymptotic formula is very clean: try to figure the lower bound!

Two related results in this spirit: Erdos, Kleitman and Rothschild (1976): triangle-free graphs are almost always bipartite. The solution of Dedekind’s problem on the number of antichains of subsets of an -elemet set by Korshunov (1980) and by Sapozhenko (1991).

### Talagrand’s inequality and the Kahn-Park inequality.

Let be a subset of the vertices of the discrete -cube. For every vertex in we define as the number of neighbors of that are not in . We define if does not belong to . ( is a variation on the sensitivity function of .)

Recall that denote the uniform probability measure on the discrete cube. A classic discrete isoperimetric inequality that goes back (in a stronger form) to Harper and others asserts that

(The left hand side is 1/2 times the average sensitivity aka total influence of .)

Talagrand proved that . This result is sharp up to some multiplicative constant both for subcubes and for Hamming balls. We discussed Talagrand’s result in this post.

Let . Kahn and Park proved that

Note that the exponent is higher than Talagrand’s exponent. The new inequality is sharp on the nose for subcubes of codimension one and two. **Let’s check it**: for codimension 1, $h_A$ is constant 1 on , so is 1/2 for every and this equals . When is a codimension 2 subcube, $h_A$ is constant 2 on . Now, by the definition of $\beta$, . Thus, and , **walla!**

For the relation between the Kahn-Park isoperimetric inequality and the Kahn-Park theorem on counting maximal independent sets I refer you to the original paper. The two papers are beautifully written.

## Three pictures of some important isoperimetric results by Talagrand

Here are drawings and links regarding Talagrand’s three isoperimetric papers and subsequent papers, and I hope to come back to discuss them in the future.

Three important papers on discrete isoperimetric inequalities by Talagrand

Concentration of measure and isoperimetric inequalities in product spaces (Publ IHES 1995)

On Russo’s approximate zero-one law (Ann of Probability, 1994)

Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem (GAFA, 1993)

Eight very recommended papers by Talagrand and Talagrand’s prize money problems

Michel Talagrand page: Become RICH with my prizes

An incomplete larger picture

Dear Gil,

I think the Talagrand’s inequality with better constant (with root 3 instead of root 2) was proved in the paper of Bobkov–Gotze

http://www-users.math.umn.edu/~bobko001/papers/1999_PTRF_BG.pdf

This is in Lemma 2.2 for p=q=1/2.

Dear Paata, this is very interesting!, thanks.

Pingback: Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google). | Combinatorics and more