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
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
Pingback: Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand | Combinatorics and more