most recent 30 from http://mathoverflow.net 2013-05-26T00:09:21Z http://mathoverflow.net/feeds/user/15706 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/63789/probability-of-a-random-walk-crossing-a-straight-line/67459#67459 John 2011-06-10T18:00:57Z 2011-06-10T18:00:57Z

<p>An upper estimate is given in Appendix A of "The Probabilistic Method" by Alon/Spencer. This gives $P(S_n > a) &lt; e^{-a^2/2n}$ for $a > 0$ (Theorem A.1.1). There are lots of bounds like this one, if you are interested in simple upper bounds.</p>

http://mathoverflow.net/questions/67451/number-of-2-connected-subsets-in-the-hypercube John 2011-06-11T11:31:58Z 2011-06-11T11:31:58Z

2-connected isn't entirely standard - I've also seen `2-linked' used for the concept of 2-connected described here. You're right that 2-connected doesn't imply connected here. As to an approach, I tried (following the lead of Sapozhenko) to find a small set of subsets which appropriately approximate any given 2-connected set of size a with neighborhood of size n, and then for each approximating set I tried to bound the number of a that could approximated by this particular approximating set. This leads to the $2^{n - cn/\log d}$ result.

http://mathoverflow.net/questions/67451/number-of-2-connected-subsets-in-the-hypercube John 2011-06-11T02:17:20Z 2011-06-11T02:17:20Z

Sorry - I edited the post. I'm interested in $2^{d/\log^2 d} \leq a \leq c^d$ (for some fixed $1 &lt; c &lt; 2$), and I'm looking for asymptotics in $d$.

http://mathoverflow.net/questions/63789/probability-of-a-random-walk-crossing-a-straight-line/67459#67459 John 2011-06-10T18:02:26Z 2011-06-10T18:02:26Z

Sorry - I didn't read the 'exists' part of your question carefully, so this isn't quite what you're looking for. It is a bound for a particular $n$, though.