most recent 30 from http://mathoverflow.net 2013-05-25T22:17:09Z http://mathoverflow.net/feeds/question/67451 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67451/number-of-2-connected-subsets-in-the-hypercube John 2011-06-10T15:48:46Z 2011-06-11T19:32:19Z

<p>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 <em>2-connected</em> 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$.</p> <p>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$?</p> <p>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)?</p> <p>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 &lt; \alpha &lt; 2$, and for $a \leq n \leq a\log d$. (Sapozhenko's results give an upper bound for any $a$ and any $n$)</p>

http://mathoverflow.net/questions/67451/number-of-2-connected-subsets-in-the-hypercube/67534#67534 Omer 2011-06-11T19:32:19Z 2011-06-11T19:32:19Z

<p>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&lt;\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.</p>