5
$\begingroup$

Consider an oriented graph (e.g. a finite part of the standard grid with some random orientations).

Each minute the following operation takes place: we choose uniformly randomly an ordered pair $(A,B)$ of vertices of the graph, and if there is an oriented path from $A$ to $B$ then we say “success”, take it and invert all the directions of the edges on this path (one can take a random path, or a shortest one). If there is no such a path, we say “failure”.

I guess it might be a classical problem in statistical physics. Anyway, do you have any advice on how to compute the probability of “success” after many steps? Does it converge for any initial directions of the edges? I can imagine two versions of the problem:

(less interesting) compute the probability of the existence of an oriented path between two random vertices on the whole ensemble of edge orientations.

(more interesting) We perform the above operation many many times, what is the frequency of success?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is it supposed that the size of the oriented graph goes to $\infty$, as in the stat. phys. limit? $\endgroup$
    – LeechLattice
    Commented Feb 7, 2019 at 8:13
  • $\begingroup$ @Bullet51 for example. I will be happy if there is a solution in any setup: fixed big graph, a scaling limit of graphs, whatever. One can even change the rule of choosing or reversing orientations. $\endgroup$
    – Nikita Kalinin
    Commented Feb 7, 2019 at 8:35
  • 2
    $\begingroup$ You can view this as a Markov Chain on the set of all 2^#edges possible configurations. All states are positive recurrent as you could for example switch one edge twice. Hence it follows that there is a unique equilibrium. I am not sure if this equilibrium is the equidistribution over all states. If we allow multiple edges between the same vertices its not. Consider for example the graph with 2 vertices and 2 edges between them. The equilibrium will then be more towards the case that the two edges point in the same direction. $\endgroup$
    – user100927
    Commented Feb 7, 2019 at 9:57

1 Answer 1

Reset to default
1
$\begingroup$

Consider the dual of the square lattice, which is formed from the square lattice by placing one vertex in the center of each square and joining vertices with an edge when their corresponding squares in the square lattice share an edge.$^{[1]}$

It's easy to see that the edges in the original graph are perpendicular with those in the dual graph. That is to say, if we turn the arrows in the original orientation $R$ 90° left, we will get a orientation in the dual lattice $R'$.

If $R$ is vertically blocked, $R'$ must be horizontally connected, and vice versa. enter image description here

($R$ is shown in blue, and $R'$ in red)

By symmetry, the probability for one side to be connected to its opposite in an $n×n$ square is $1/2$, independent of $n$. Thus, the proof techniques from $[1]$ follows, and it can be argued that the probability of the less interesting problem tends to $0$ for $n→\infty$.

[1] http://www.ams.org/publicoutreach/feature-column/fcarc-percolation

Improve this answer
$\endgroup$
2
  • $\begingroup$ "the probability of the less interesting problem tends to 0.." why? How it is related to percolations? $\endgroup$
    – Nikita Kalinin
    Commented Feb 8, 2019 at 6:47
  • $\begingroup$ The less interesting problem is really about the connected component of an oriented grid graph, having similar connection properties with the bond percolation graph of a square lattice with prob. $1/2$, hence [1] follows. As the point $A$ can be surrounded with concentric annuli, each reducing the prob. for it to be untraped by a factor of $1+\epsilon$, the prob. for $A$ to be connected with $B$ tends to $0$ as $A$ and $B$ are sufficiently distant. $\endgroup$
    – LeechLattice
    Commented Feb 8, 2019 at 8:46

You must log in to answer this question.

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