Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.

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 Q_n be the n-dimensional Hamming cube and N=2^n. We prove that the number of maximal independent sets in Q_n is asymptotically 2n2^{N/4},
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 Q_n.

An isoperimetric inequality for the Hamming cube and some consequences

Abstract: (Slightly modified.)

Our basic result, an isoperimetric inequality for Hamming cube Q_n, can be written:
\int h_A^\beta d\mu \ge 2 \mu(A)(1-\mu(A)).
Here \mu is uniform measure on V={0,1}^n(=V(Q_n)); \beta=log_2(3/2); and, for S\subset V and x\in V, h_S(x) is zero if x \notin S, and h_S(x) is the number of neighbors of a not in S, if x \in S. (where d_T(x) is the number of neighbors of x in T).

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 Q_n is (1+o(1))2n\exp_2[2^{n-2}] 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 n-cube. The maximal size of an independent set is 2^{n-1} and you may recall that the recently solved (by Hao Huang) sensitivity conjecture asked for the properties of an induced subgraph on 2^{n-1}+1 vertices.

How many independent sets are there? Well, we can consider all the subsets of the two independent sets of size 2^{n-1} so this gives us 2\cdot 2^{2^{n-1}}.  Korshunov and Sapozhenko proved in 1983 that the number is 2\sqrt e(1+o(1))2^{2^{n-1}}, 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 2 \sqrt e term comes from.

Now, lets talk about maximal independent sets.  The Kahn-Park asymptotic formula 2n2^{N/4} 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 n-elemet set by Korshunov (1980) and by Sapozhenko (1991).

Talagrand’s inequality and the Kahn-Park inequality.

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

Recall that \mu 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

\int h_A(x) d\mu \ge 2 \mu(A)(1-\mu(A))

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

Talagrand proved that \int h_A^{1/2}(x) d\mu \ge \sqrt 2 \mu(A)(1-\mu(A)). 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 \beta=log_2(3/2)= .585.... Kahn and Park proved that

\int h_A^{\beta}(x) d\mu \ge 2 \mu(A)(1-\mu(A))

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 A, so \int h_A^{\beta}(x) d\mu is 1/2 for every \beta and this equals 2 \mu(A) (1-\mu (A)). When A is a codimension 2 subcube,  $h_A$ is constant 2 on A. Now, by the definition of $\beta$,  2^\beta = 3/2. Thus, \int h_A^{\beta}(x) d\mu=\frac {1}{4} \frac {3}{2}=\frac{3}{8} and 2 \mu(A) (1-\mu (A))=2 \frac {1}{4} \frac{3}{4}=\frac{3}{8}, 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

Advertisements
This entry was posted in Combinatorics and tagged , , . Bookmark the permalink.

3 Responses to Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.

  1. Paata Ivanishvili says:

    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.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s