MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $Q_d$ be the d-dimensional hypercube - the graph with vertex set $\{0,1\}^d$ and edges joining two vertices that differ in exactly one coordinate. Say a subset $A$ of vertices is 2-connected if for each $x,y \in A$ there exists a $x=x_{0}, x_{1}, ..., x_{k} = y$ such that $x_{i} \in A$ and $d(x_{i},x_{i+1}) \leq 2$.

My question is: Suppose we take a 2-connected set $A$ and look at the set $N(A) = \{ x \in V(Q_d) : xEy \}$, i.e., the set of vertices that are next to a vertex in $A$. Is there an upper bound on the number of subsets $A$ with $|A| = a$ and $|N(A)| = n$?

Related results: It can be shown, by considering a tree, that there are at most $2^{a \log d}$ subsets. Sapozhenko introduced techniques to show that there are at most $2^{n - cn/\log d}$ subsets of that form. Are there any stronger results (say, that there are at most $2^{cn/\log d}$ such subsets)?

I'm interested in results as $d \to \infty$ and for $2^{d/\log^2 d} \leq a \leq \alpha^d$ for some fixed $1 < \alpha < 2$, and for $a \leq n \leq a\log d$. (Sapozhenko's results give an upper bound for any $a$ and any $n$)

share|cite|improve this question
You write $|N(A)|=n$, but the bounds you indicate do not depend on $n$ -- can you explan? Also, what is $g$ and what range of $d,a,...$ are you interested in? – Seva Jun 10 '11 at 18:32
Sorry - I edited the post. I'm interested in $2^{d/\log^2 d} \leq a \leq c^d$ (for some fixed $1 < c < 2$), and I'm looking for asymptotics in $d$. – John Jun 11 '11 at 2:17
Since you have not said what approaches you have tried, let me suggest one. N(A) should be connected as a graph when A is 2-connected. Find an estimate E(n) for connected subgraphs of size n, and then find an average estimate S(m,a) for 2-connected subgraphs of size a of graphs counted by E(m). Hopefully what you want will be close to S(n,a) - S(n-1,a), perhaps with a weighting factor. Gerhard "Ask Me About System Design" Paseman, 2011.06.10 – Gerhard Paseman Jun 11 '11 at 2:48
Is this use of the term "2-connected" standard? – Douglas Zare Jun 11 '11 at 3:18
In this context, my guess is 2-connected has a definition different from other parts of graph theory, because here A 2-connected does not mean A connected. Gerhard "Ask Me About System Design" Paseman, 2011.06.10 – Gerhard Paseman Jun 11 '11 at 4:47

The tree based estimate for connected (or 2-connected) sets should be fairly close to the truth for sets of size $\alpha^d$ with $\alpha<\surd{2}$. This is essentially a birthday effect, since up to that size the a typical tree embedded in the cube will not have much overlap. For larger $\alpha$, the tree bound will not be as good, but still should give you the right order of magnitude.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.