Skip to main content
added 329 characters in body
Source Link
Joonas Ilmavirta
  • 8.1k
  • 5
  • 39
  • 66

This answer has two main points:

  1. If you find a good upper bound in the case $j=1$, you will get a reasonable bound for small $j$.
  2. You cannot get polynomial bounds with respect to $n,m,k$ for any $j\geq1$. (The hope for polynomial bounds was expressed in a comment.)

Let $N(n,m,k;j)$ denote the number of choices on the $n\times m\times k$ block producing at most $j$ connected components. If we make $i$ choices with a single connected component and put then on top of each otherthem together (take the pointwise maximum if you regard each choice as a function taking values in the 0–1 model$\{0,1\}$), we get a situation with at most $i$ connected components. This construction yields at most $N(n,m,k;1)^i/i!$ choices for each $i$, so we get the estimate $$ N(n,m,k;j) \leq \sum_{i=0}^j \frac1{i!} N(n,m,k;1)^i. $$ (Actually $N(n,m,k;1)-1$ would also work since it is the amount of choices with exactly one component, but this difference is very small.) My intuition is that this estimate is fairly good when $j$ is very small. For large $j$ it is not very tight, since $N(n,m,k;\infty)=2^{nmk}$ but the estimate gives $e^{N(n,m,k;1)}$ which is way bigger. Thus to estimate $N(n,m,k;j)$ for small $j$ the key thing is to estimate $N(n,m,k;1)$ well.

You cannot get upper bounds for $N(n,m,k;1)$ which are polynomial in $n,m,k$. Let me write $[a,b]=\{a,a+1,\dots,b\}$ for integers $a<b$. Take any function $f:[1,m]\times[1,k]\to[1,n]$. Assign the value $1$ to the cell $(a,b,c)\in[1,n]\times[1,m]\times[1,k]$ iff $a\leq f(b,c)$. (Imagine the graph of the function $f$.) Now there is exactly one connected component of $1$s, and different choices of $f$ give different choices for the $1$s. Therefore $N(n,m,k;j)\geq N(n,m,k;1)\geq n^{mk}$ for $j\geq1$, so there is no polynomial bound.

As I mentioned in a comment above, naive arguments give the bounds $$ \sum_{i=0}^j{nmk\choose i} \leq N(n,m,k;j) \leq 2^{nmk}. $$ (Choose only at most $j$ points or make any choice at all to get these bounds.)

As a summary, you have these bounds when $j\geq1$: This is very coarse$$ \max\left\{\sum_{i=0}^j{nmk\choose i},n^{mk},m^{nk},k^{nm}\right\} \leq N(n,m,k;j) \leq \min\left\{2^{nmk},\sum_{i=0}^j \frac1{i!} N(n,m,k;1)^i\right\}. $$ These bounds are not optimal, but gives somegive an idea of the growth rate for any $j$.

This answer has two points:

  1. If you find a good upper bound in the case $j=1$, you will get a reasonable bound for small $j$.
  2. You cannot get polynomial bounds with respect to $n,m,k$.

Let $N(n,m,k;j)$ denote the number of choices on the $n\times m\times k$ block producing at most $j$ connected components. If we make $i$ choices with a single connected component and put then on top of each other (take the pointwise maximum in the 0–1 model), we get a situation with at most $i$ connected components. This construction yields at most $N(n,m,k;1)^i/i!$ choices for each $i$, so we get the estimate $$ N(n,m,k;j) \leq \sum_{i=0}^j \frac1{i!} N(n,m,k;1)^i. $$ (Actually $N(n,m,k;1)-1$ would also work since it is the amount of choices with exactly one component, but this difference is very small.) My intuition is that this estimate is fairly good when $j$ is very small. For large $j$ it is not very tight, since $N(n,m,k;\infty)=2^{nmk}$ but the estimate gives $e^{N(n,m,k;1)}$ which is way bigger. Thus to estimate $N(n,m,k;j)$ for small $j$ the key thing is to estimate $N(n,m,k;1)$ well.

You cannot get upper bounds for $N(n,m,k;1)$ which are polynomial in $n,m,k$. Let me write $[a,b]=\{a,a+1,\dots,b\}$ for integers $a<b$. Take any function $f:[1,m]\times[1,k]\to[1,n]$. Assign the value $1$ to the cell $(a,b,c)\in[1,n]\times[1,m]\times[1,k]$ iff $a\leq f(b,c)$. (Imagine the graph of the function $f$.) Now there is exactly one connected component of $1$s, and different choices of $f$ give different choices for the $1$s. Therefore $N(n,m,k;j)\geq N(n,m,k;1)\geq n^{mk}$ for $j\geq1$, so there is no polynomial bound.

As I mentioned in a comment above, naive arguments give the bounds $$ \sum_{i=0}^j{nmk\choose i} \leq N(n,m,k;j) \leq 2^{nmk}. $$ (Choose only at most $j$ points or make any choice at all to get these bounds.) This is very coarse, but gives some idea of the growth rate for any $j$.

This answer has two main points:

  1. If you find a good upper bound in the case $j=1$, you will get a reasonable bound for small $j$.
  2. You cannot get polynomial bounds with respect to $n,m,k$ for any $j\geq1$. (The hope for polynomial bounds was expressed in a comment.)

Let $N(n,m,k;j)$ denote the number of choices on the $n\times m\times k$ block producing at most $j$ connected components. If we make $i$ choices with a single connected component and put them together (take the pointwise maximum if you regard each choice as a function taking values in $\{0,1\}$), we get a situation with at most $i$ connected components. This construction yields at most $N(n,m,k;1)^i/i!$ choices for each $i$, so we get the estimate $$ N(n,m,k;j) \leq \sum_{i=0}^j \frac1{i!} N(n,m,k;1)^i. $$ (Actually $N(n,m,k;1)-1$ would also work since it is the amount of choices with exactly one component, but this difference is very small.) My intuition is that this estimate is fairly good when $j$ is very small. For large $j$ it is not very tight, since $N(n,m,k;\infty)=2^{nmk}$ but the estimate gives $e^{N(n,m,k;1)}$ which is way bigger. Thus to estimate $N(n,m,k;j)$ for small $j$ the key thing is to estimate $N(n,m,k;1)$ well.

You cannot get upper bounds for $N(n,m,k;1)$ which are polynomial in $n,m,k$. Let me write $[a,b]=\{a,a+1,\dots,b\}$ for integers $a<b$. Take any function $f:[1,m]\times[1,k]\to[1,n]$. Assign the value $1$ to the cell $(a,b,c)\in[1,n]\times[1,m]\times[1,k]$ iff $a\leq f(b,c)$. (Imagine the graph of the function $f$.) Now there is exactly one connected component of $1$s, and different choices of $f$ give different choices for the $1$s. Therefore $N(n,m,k;j)\geq N(n,m,k;1)\geq n^{mk}$ for $j\geq1$, so there is no polynomial bound.

As I mentioned in a comment above, naive arguments give the bounds $$ \sum_{i=0}^j{nmk\choose i} \leq N(n,m,k;j) \leq 2^{nmk}. $$ (Choose only at most $j$ points or make any choice at all to get these bounds.)

As a summary, you have these bounds when $j\geq1$: $$ \max\left\{\sum_{i=0}^j{nmk\choose i},n^{mk},m^{nk},k^{nm}\right\} \leq N(n,m,k;j) \leq \min\left\{2^{nmk},\sum_{i=0}^j \frac1{i!} N(n,m,k;1)^i\right\}. $$ These bounds are not optimal, but give an idea of the growth rate.

Source Link
Joonas Ilmavirta
  • 8.1k
  • 5
  • 39
  • 66

This answer has two points:

  1. If you find a good upper bound in the case $j=1$, you will get a reasonable bound for small $j$.
  2. You cannot get polynomial bounds with respect to $n,m,k$.

Let $N(n,m,k;j)$ denote the number of choices on the $n\times m\times k$ block producing at most $j$ connected components. If we make $i$ choices with a single connected component and put then on top of each other (take the pointwise maximum in the 0–1 model), we get a situation with at most $i$ connected components. This construction yields at most $N(n,m,k;1)^i/i!$ choices for each $i$, so we get the estimate $$ N(n,m,k;j) \leq \sum_{i=0}^j \frac1{i!} N(n,m,k;1)^i. $$ (Actually $N(n,m,k;1)-1$ would also work since it is the amount of choices with exactly one component, but this difference is very small.) My intuition is that this estimate is fairly good when $j$ is very small. For large $j$ it is not very tight, since $N(n,m,k;\infty)=2^{nmk}$ but the estimate gives $e^{N(n,m,k;1)}$ which is way bigger. Thus to estimate $N(n,m,k;j)$ for small $j$ the key thing is to estimate $N(n,m,k;1)$ well.

You cannot get upper bounds for $N(n,m,k;1)$ which are polynomial in $n,m,k$. Let me write $[a,b]=\{a,a+1,\dots,b\}$ for integers $a<b$. Take any function $f:[1,m]\times[1,k]\to[1,n]$. Assign the value $1$ to the cell $(a,b,c)\in[1,n]\times[1,m]\times[1,k]$ iff $a\leq f(b,c)$. (Imagine the graph of the function $f$.) Now there is exactly one connected component of $1$s, and different choices of $f$ give different choices for the $1$s. Therefore $N(n,m,k;j)\geq N(n,m,k;1)\geq n^{mk}$ for $j\geq1$, so there is no polynomial bound.

As I mentioned in a comment above, naive arguments give the bounds $$ \sum_{i=0}^j{nmk\choose i} \leq N(n,m,k;j) \leq 2^{nmk}. $$ (Choose only at most $j$ points or make any choice at all to get these bounds.) This is very coarse, but gives some idea of the growth rate for any $j$.