Return to Question

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

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

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?

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

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^{g - cg/\log d}$ subsets of that form. Are there any stronger results (say, that there are at most $2^{cg/\log d}$ such subsets?

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?