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

Posted on September 22, 2019 by Gil Kalai

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

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

Paata Ivanishvili says:

September 22, 2019 at 4:07 pm

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.

Reply
- Gil Kalai says:
  
  September 22, 2019 at 4:50 pm
  
  Dear Paata, this is very interesting!, thanks.
  
  Reply
Pingback: Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google). | Combinatorics and more

	Gil Kalai on Gérard Cornuéjols’s bake…
	Abstractness on Amazing: Karim Adiprasito prov…
	Gil Kalai on The story of Poincaré and his…
	Peter Shor on The story of Poincaré and his…
	Gil Kalai on What do Firms Want?
	Gil Kalai on Noisy quantum circuits: how do…
	World News OK, WTF I… on Quantum computers: amazing pro…
	Quantum computers: a… on The story of Poincaré and his…
	Craig on The story of Poincaré and his…
	Gil Kalai on The story of Poincaré and his…
	Craig on The story of Poincaré and his…
	Rao on The story of Poincaré and his…