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
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 .
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.
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
On Russo’s approximate zero-one law (Ann of Probability, 1994)
Eight very recommended papers by Talagrand and Talagrand’s prize money problems
Michel Talagrand page: Become RICH with my prizes
An incomplete larger picture