1
$\begingroup$

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$)

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$
    – Seva
    Commented Jun 10, 2011 at 18:32
  • $\begingroup$ 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$. $\endgroup$
    – John
    Commented Jun 11, 2011 at 2:17
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jun 11, 2011 at 2:48
  • $\begingroup$ Is this use of the term "2-connected" standard? $\endgroup$
    – Douglas Zare
    Commented Jun 11, 2011 at 3:18
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jun 11, 2011 at 4:47

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .