2
$\begingroup$

Consider the set of all non-intersecting walks of length $n$ on a $d$ dimensional lattice starting at the origin. Now group the members of this set into conformations, where members $x_i$ and $x_j$ belong to the same conformation if they have the same set of nearest neighbors. Let $C(n,d)$ denote the cardinality of the number of unique conformations.

Does anyone have any insight to the bounds of $C(n,d)$ or prior work that deals with this question?

[Please feel free on rephrasing/clarifying the question with more mathematical rigor]

Edit: As a concrete example consider the case where $d=2, n=4$, small enough that I can enumerate all the cases here. Using 0 as the origin, _ as an empty lattice site the paths can be enumerated as:

[Nearest neighbor set: Empty]

0123

[Nearest neighbor set: Empty]

__3
012

[Nearest neighbor set: Empty]

_3
_2
01

[Nearest neighbor set: Empty]

_23
01_

[Nearest neighbor set: (0,3)]

32
01

Since there are two different configurations, $C(4,2)=2$. It's easy to work out $C(5,2)=4$ as the only possible combinations are $[ [], [(0,4)], [(1,4)], [(0,3)] ]$. For $C(6,2)=6$ the possible combinations are (assuming I haven't missed any): $[ [], [(0,5),(1,4)], [(2,5)],[(0,5),(2,5)],[(0,3)],[(0,3),(2,5)]] ]$.

Edit++: Douglas rightly pointed out that $[(1,4)]$ can not possibly belong to the set $C(4,2)$ due to a simple parity argument. Leaving the original up to keep the thread continuity.

$\endgroup$
4
  • 1
    $\begingroup$ What does it mean for two non-intersecting walks to have "the same set of nearest neighbors"? $\endgroup$
    – Yemon Choi
    Apr 21, 2010 at 19:22
  • $\begingroup$ For instance, can you give me a concrete example (with d=2, say) where two paths are supposed to have EXACTLY the same set of nearest neighbours? $\endgroup$
    – Yemon Choi
    Apr 21, 2010 at 20:01
  • $\begingroup$ hi Hooked, I think I am not understanding what you are calling nearest neighbors of a random walk. Suppose that we have a non-intersect walk $\omega=\{v_0,\{v_0,v_1\},v_1,\{v_1,v_2\},\ldots,\{v_{n-1},v_n\},v_n\}$. We can think about it as a graph, I will call it $G$. My question is: what are you calling nearest neighbors pairs of $\omega$ ? Are they the set of pairs $\{v_i,v_j\}\notin E(G)$, satisfying $\|v_i-v_j\|_1=1$ ? ($E(G)$, as usual, is the edge set of $G$ and $\|(z_1,\ldots,z_d)\|_1=\sum_{j=1}^d|z_j|$ $\endgroup$
    – Leandro
    Apr 22, 2010 at 2:48
  • $\begingroup$ Perhaps more simply, two nodes are nearest neighbors on a unit lattice if the Cartesian distance between them is one (with the provision that node $n_i$ is not a nearest neighbor to nodes $n_{i-1}$ or $n_{i+1}$. So no, I don't think this makes it a graph in the usual sense. $\endgroup$
    – Hooked
    Apr 22, 2010 at 4:17

1 Answer 1

1
$\begingroup$

For ease of notation, I'm going to use $C(n,d)$ as the set (and not include the empty set in $C(n,d)$) and $|C(n,d)|$ as the cardinality. Unless I'm mistaken, for $n=5$ we have $|C(5,2)|=2$. The only paths that have neighbours are these (or symmetrically equivalent):

012  .01  014
.43  432  .23

So $C(5,2)=\big\{\{0,3\},\{1,4\}\big\}$, which disagrees with your value.

The important observation here is that we can't have $\{0,4\}$ because of a parity argument. That is, the symbol next to 0 must always be odd. In fact, neighbours $\{a,b\}$ are always going to have opposite parity. We will now prove by induction that \[C(n,d)=\big{{a,b} \subset {0,1,\ldots,n-1}:|a-b| \geq 3 \text{ and } a \not\equiv b \pmod 2\big} \quad (1)\] when $d \geq 2$ for all $n \geq 1$.

EDIT: There's actually an easy construction that $\{a,b\} \in C(n,d)$ provided $|a-b| \geq 3$ and $a \not\equiv b \pmod 2$. Assuming $a < b$:

a-1 a-2 a-3 ... 0
a   a+1 a+2 ... a+(b-a-1)/2
b   b-1 b-2 ... a+(b-a+1)/2
b+1 b+2 b+3 ... n-1

Note: my original "proof" (below) is invalid as we might not be able to "append $n$" without creating an intersecting walk.

Proof: We just proved that $C(n,d)$ is a subset of the right-hand-side in (1). So we now need to show that $C(n,d)$ is a superset of of the right-hand-side in (1).

It's true when $n \leq 4$, so take $n>4$. Assume (1) is true for parameters $(n-1,d)$. Then $C(n-1,d) \subset C(n,d)$ (by appending an $n$ to each path) and $C(n-1,d)+1 \subset C(n,d)$ (by adding $1$ to each element in the path and appending $0$). This resolves the cases $\{a,b\}$ when $|a-b| < n$.

So it is sufficient to show that $\{0,n-1\} \in C(n,d)$ provided $n \equiv 0 \pmod 2$. But this is easy to prove by construction, for example:

0   1   .. n/2-1
n-1 n-2 .. n/2

Done.

$\endgroup$
2
  • $\begingroup$ This is what I get for editing a post right before I leave! I am quite mistaken that ${0,4}$ belongs to the set $C(5,2)$ and your parity argument seems quite valid. The tricky part to the problem comes from the fact that not every combination of ${a,b}$ can work at once. Consider $C(6,2)$ with possible values of ${0,3} {0,5} {1,4} {2,5}$. Not all $2^4$ combination are possible since a walk the has the 0 node touching both the 3 and 5 node can not possibly have the 2 node touching the 5 node. The question maybe better as which of these $2^4$ combination's are valid non-intersecting paths? $\endgroup$
    – Hooked
    Apr 22, 2010 at 0:27
  • $\begingroup$ The post above striped out the curly braces and my rep is to low to edit the comment - Please pretend that the exist around the 0,3 and 0,5 etc... $\endgroup$
    – Hooked
    Apr 22, 2010 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.