MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]


[Nearest neighbor set: Empty]


[Nearest neighbor set: Empty]


[Nearest neighbor set: Empty]


[Nearest neighbor set: (0,3)]


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.

share|cite|improve this question
What does it mean for two non-intersecting walks to have "the same set of nearest neighbors"? – Yemon Choi Apr 21 '10 at 19:22
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? – Yemon Choi Apr 21 '10 at 20:01
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|$ – Leandro Apr 22 '10 at 2:48
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. – Hooked Apr 22 '10 at 4:17

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


share|cite|improve this answer
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? – Hooked Apr 22 '10 at 0:27
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... – Hooked Apr 22 '10 at 0:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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