Let $A$ be a connected subset of $\mathbb{Z}^d$ having finite cardinality $n$ and containing the origin. I need a good upper bound which depends only on $n$ for the number of connected subsets of $A$ containing the origin.

Can one provide an upper bound which grows slower than $O( exp(c \cdot n) )$ for any $c >0$?

Comment: The number of connected sets of cardinality $k$ intersecting the origin grows as $C^k$ for some $C>0$ (see also Number of connected sets of size $k$ containing a given vertex on $\mathbb{Z}^d$ ). I am now asking for the total number of connected sets intersecting the origin and contained in $A$, as a function of the cardinality of $A$.

Definition of connected set: A set $A \subset \mathbb{Z}^d$ is connected if, for any $x, y \in A$, there exists a path on nearest neighbors which is entirely contained in $A$ and which connects $x$ and $y$.

  • $\begingroup$ What is the topology on $\Bbb{Z}^d$ that you are considering? Because in the standard one, the only connected sets are the singletons... $\endgroup$ – Nitrogen Jan 11 '16 at 18:00
  • $\begingroup$ Please see my edit. Thanks for the question. $\endgroup$ – QuantumLogarithm Jan 11 '16 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.