20
$\begingroup$

Represent the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ points as in the figures below for example. How to calculate the number of circuits that visit a chosen point in this rectangle? What is the most visited point on this rectangle?

enter image description here

Making the question more precise we fix the settings below.

  • A circuitc $c$ in rectangle $R_{n\times n}$ is defined as a sequence of distinct points $x_{i_1j_1}, x_{i_2j_2},x_{i_2j_2},\ldots, x_{i_{m-1}j_{m-1}}$ and a point $x_{i_{m}j_{m}}=x_{i_{1}j_{1}}$ in $R_{n\times n}$ such that $|i_{k}-i_{k+1}|+|j_{k}-j_{k+1}|=1$ for $k=1,\ldots, m-1$.

  • A circuit $c=\{x_{i_1j_1}, x_{i_2j_2},x_{i_2j_2},\ldots, x_{i_{m-1}j_{m-1}},x_{i_{m}j_{m}}\}$ visit a point $x_{ij}$ if $x_{ij}\in c$.

  • Let $N_n(x_{ij})$ the total circuits in $R_{n\times n}$ who visit the point $x_{ij}$ .

Question. How to calculate the value of $N_n(x_{ij})$? If we draw a circuit randomly which point $x_{ij}$ has the highest probability to be visited?

Calculations case $n = 1,2,3$ are trivial. I'm trying to calculate the number $N_n(x_{ij})$ by a recursive procedure which reduces the calculation for the case $n$ to $n-1$. But I think the use of this recursion depends on some well-crafted trick that escaped my attempts.

$\endgroup$
5
  • 1
    $\begingroup$ The following result might be helpful. Theorem: Let $G:=(V,E)$ be a graph and consider its adjacency matrix $A_G$. For all $k\in \mathbb N$, the number of paths of lenght $k$ from node $v_i$ to $v_j$is the the entry $i,j$ of the matrix $A^k_G$, for any $i,j\in \{m\in \mathbb N\colon m\leq |V|\}$. See the proof here. A couple of keyterms are adjacency matrix and number of paths. $\endgroup$
    – Git Gud
    Dec 24, 2013 at 13:55
  • $\begingroup$ @GitGud This is the classic solution to the problem of the most visited point. In this case I would have to calculate the number of two distinct paths connecting two points. It seems to be a promising approach. But I have not had progress with this approach. $\endgroup$
    – Elias Costa
    Dec 24, 2013 at 13:57
  • $\begingroup$ I have a suggestion but it might be also hard to calculate. Instead of counting paths on this graph, count the number of coloring the squares in a continuous way. It is obvious that there is an upper bound of $2^{(n-1)(n-1)}$. $\endgroup$
    – mnz
    Mar 3, 2014 at 15:20
  • $\begingroup$ I think the way to approach it might be to relate the probability of each node's appearance in a circuit with its neighbors. Or maybe look at the probability of each edge appearing in a circuit instead. $\endgroup$
    – NovaDenizen
    Jul 23, 2014 at 2:46
  • $\begingroup$ see also another related question here. $\endgroup$
    – Elias Costa
    May 2, 2015 at 15:04

1 Answer 1

Reset to default
1
$\begingroup$

I think it' strictly linked to the self-avoiding path problem (which is slightly different as the circuit doesn't necessary ends where it started); there is also a detailed study , and a partial solution to what you called $N_n(x_{\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor})$, all circuits which visit the origin. Anyway until now, any solution has been found. It can be an idea to consider a circuit that starts from $x_{ab}$ and arrives to $x_{cd}$, and then consider the reverse paths (from $x_{cd}$ to $x_{ab}$), remembering not to count the reverse paths which intersect the first one, as to create an Hamilton path.

$\endgroup$
3
  • $\begingroup$ "Anyway until now, [no?] solution has been found."? $\endgroup$
    – Teepeemm
    Jun 8, 2014 at 20:15
  • $\begingroup$ @Teepeemm No, no solution was found. $\endgroup$
    – Elias Costa
    Sep 13, 2014 at 20:42
  • $\begingroup$ "remembering not to count the reverse paths which intersect the first one": you say that like it was easy! $\endgroup$
    – TonyK
    Oct 27, 2014 at 15:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .