39
$\begingroup$

Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)


Consider a square planar grid. (The vertices are pair of points in the plane with integer coordinates and two vertices are adjacent if they agree in one coordinate and differ by one in the other.)

Give every edge a length one with probability a half and length two with probability a half.

Consider a shortest path between the origin and the vertex $(n,0)$.

Show that with probability that tends to one as $n$ tends to infinity the shortest path will not contain the "middle edge" on the x-axis inbetween the orgin and $(n,0)$. (Namely, the edge between the vertices $(\lfloor\frac{n}{2}\rfloor,0)$ and $(\lfloor\frac{n}{2}\rfloor+1,0)$.)


This question is in the category of "a missing lemma". It is not really a full fledged open problem but rather a statement which looks correct that was needed in some paper and resisted proof. Of course, some such "lemmas" turn out to be very difficult, but sometimes maybe a simple argument was simply missed. The relevant paper is

  • Itai Benjamini, Gil Kalai, and Oded Schramm, First Passage Percolation Has Sublinear Distance Variance, Ann. Probab. 31(4) (2003) pp 1970-1978, doi:10.1214/aop/1068646373, arXiv:math/0203262.

While MO have chosen to accept one answer, and there were some nice suggestions, the problem is still wide open.

$\endgroup$
5
  • 3
    $\begingroup$ Nitpicking: is it "a shortest path" or "the shortest path"? Do you want to show there is a shortest path avoiding the given edge, or that all shortest paths avoid the given edge. $\endgroup$
    – Boris Bukh
    Dec 23, 2009 at 11:26
  • $\begingroup$ That's really a shame, Gil. Have you tried installing jsMath along with the fonts? It's not supposed to be necessary but perhaps it'll help. $\endgroup$
    – Alon Amit
    Dec 23, 2009 at 18:00
  • $\begingroup$ Boris, I suppose I just want to show that there is a shortest path avoiding this middle edge. Alon, jsMath? where $\endgroup$
    – Gil Kalai
    Dec 23, 2009 at 18:50
  • $\begingroup$ Boris: That's not nitpicky, it's actually an important point. If the distribution of passage times is continuous, then with probability one, there is a unique minimizing path between any two points. Here, since the distribution has atoms, with positive probability, there are multiple shortest paths. $\endgroup$ Dec 26, 2009 at 2:02
  • $\begingroup$ I am not sure if a bounty is an effective tool for an open problem that might be hard. Maybe it will lead to having another round of thoughts about it, which I feel, in good conscious, that the problem deserves $\endgroup$
    – Gil Kalai
    Jan 23, 2010 at 16:51

9 Answers 9

7
$\begingroup$

It seems that this problem was recently solved by Ahlberg and Hoffman. https://arxiv.org/abs/1609.02447

$\endgroup$
1
  • $\begingroup$ Dear Matt, Wonderful! $\endgroup$
    – Gil Kalai
    Jan 23, 2017 at 10:04
7
$\begingroup$

Gil: This is a type of problem that I know little about so here I am thinking out loud about problems that seem natural to ask about this situation. It is hard to believe that people have not already thought about these questions and perhaps answered them. Where would I look to find out more?

You write you are interested in a "square planar grid." So I took this to mean that you were thinking about the points of a "square grid graph" with lx1 squares as the cells that goes from (0,0) to (n,n) and where weights were going to be assigned to the edges of size 1 or 2.

The paths that you are talking about need not be constrained to move up and to the right but it might be interesting to contrast the behavior of general shortest paths with those that move up and to the right. It would also seem to be of interest to see what happens if one selects half of the edges at random and makes them all length 1 edges and makes all the others of length 2. Since there are 4n edges this means 2n are 1's and 2n are 2's. Furthermore, If we insist that paths move up and to the right, such paths all have length 2n, so "very shortest" paths would consist only on 1's.

In both settings:

a. What is the probability there is a shortest path to (n,n) consisting of all 1's?

b. What can be said about the expected value of the length of a shortest path to (n, n)? What can be said about the expected number of paths of this value?

c. When one insists that each of the two lengths appear equally often how many different ways can this happen? (One can also ask how many of these are different up to symmetry of the "colored" graph, treating the lengths as two colors.) One could count in the general case too but the up and to the right case seems more interesting here.

$\endgroup$
4
  • 4
    $\begingroup$ To whomever gave this post a negative vote: Shame on you. This post does not answer the question Gil asked, but so what? It is exploratory and raises some interesting ideas; perhaps one of those could lead to a correct answer. Posts like this are exactly what MathOverflow needs. $\endgroup$ Dec 26, 2009 at 1:57
  • 1
    $\begingroup$ Joe, it is a very good idea to consider paths from (0,0) to (n,n) and to consider also the case where you only go north and east. This restricted model is called "directed percolation". As far as I know the lemma is not known for directed percolation. There is one version where the distribution of edge length is exponential and you want the path of MAXIMUM length where this model is understood very well and is strongly connected to maximum eigenvalues of random symmetric matrices, largest monotone subsequences etc. $\endgroup$
    – Gil Kalai
    Dec 26, 2009 at 19:27
  • $\begingroup$ It may be possible that for this version (directed percolation; exponential lengths, maximum path), the detailed understanding of the model may lead to a proof of the lemma; but I am not sure even about it. (There are hopes, but no proofs for universality: that various models will behave in some sense the same way.) Strangely, I dont know the answer for a) off-hand. Nice question. $\endgroup$
    – Gil Kalai
    Dec 26, 2009 at 19:34
  • 5
    $\begingroup$ @Tom. I think you are wrong --- if someone read it and find it not helpful then it is right thing to vote down. (BTW, it was not me) $\endgroup$ Jan 27, 2010 at 19:37
7
$\begingroup$

Gil, as you said, this is one of those typical FPP problems which seems obvious but is hard to prove. What have you tried already? It'd be helpful to know of some naïve attempts which didn't work.

Here are my thoughts:

Claim: There exists non-random $\lambda$ such that, with probability one, for large n, all shortest paths between $0$ and $(n,0)$ meet $\lambda n + o(n)$ edges. (this is a LLN-type theorem so it shouldn't be hard to prove; e.g., via energy-entropy methods, since your passage time distributions are bounded)

Thus one can consider the probability space $\Omega_n$ consisting of all paths between $0$ and $(n,0)$ which meet $\lambda n + o(n)$ edges. A shortest path is a random variable $X_n$ on this space with a certain probability distribution.

Claim: There exists $\sigma$ such that $|\Omega_n| \approx \sigma^n$. (should be easy: $\log|\Omega_n|$ is probably subadditive)

Let $\Omega_n'$ be the subspace of paths which meet the middle edge, so that $|\Omega_n'| \approx \sigma^{n/2} + \sigma^{n/2}$.

Suppose that there exists $p > 0$ such that the shortest path between $0$ and $(n,0)$ meets the middle edge with probability at least $p$. (*)

Here is the part which I'm struggling to quantify. Intuitively, the distribution of $X_n$ should be smeared smoothly over $\Omega_n$. Certainly the mean is a horizontal line segment, but even paths which veer quite far away aren't unreasonable. However, if (*) holds, with probability at least $p$, $X_n$ concentrates on the much smaller subspace $\Omega_n'$. This seems wrong.

Perhaps all I've done is to translate one "obvious" statement into another. Hopefully this helps a bit. Good luck!

$\endgroup$
1
  • $\begingroup$ Tom, Interseting suggestion. I dont remember so much what we tried. At the end we managed to go around this lemma. $\endgroup$
    – Gil Kalai
    Dec 26, 2009 at 19:38
5
$\begingroup$

If the limit of geodesics from $0$ to $(n,0)$ exists almost surely, then this question is answered by showing that this limiting geodesic is not a doubly-infinite geodesic (bigeodesic). Under the assumption that the limit shape boundary is differentiable, Jack Hanson and I can show that this limit exists and is not a bigeodesic. Therefore we can prove that if the limit shape is differentiable, then $\mathbb{P}(0 \text{ is in the geodesic from }(-n,0) \text{ to }(n,0)) \to 0$.

It is part of a more general statement. Suppose that the limit shape boundary is differentiable in direction $\theta$, call $S_\theta$ the sector of angles corresponding to contact points of the limit shape with the unique supporting line in direction $\theta$, and assume that the boundary is differentiable at the endpoints of this sector. Then for each direction $\theta$, almost surely, if $(x_n)$ is a sequence of points directed in $S_\theta$, then for each $x$, the finite geodesics from $x$ to $x_n$ have a limit and it is directed in $S_\theta$. Furthermore, all infinite geodesics in this sector coalesce, and there are no bigeodesics with one end directed in this sector. This implies that the related disordered ferromagnet has no ground state pair with interface directed in $S_\theta$.

$\endgroup$
1
4
$\begingroup$

Gil, thanks for bumping this post. I think I've got a new idea for you, but it's not a proof yet. Let $\gamma_n$ be a minimizing geodesic between $(-n,0)$ and $(n,0)$, and let $\gamma^{\pm}_n$ be a minimizing geodesic betwen $(\pm n, 0)$ and the origin.

Denote by $d(\gamma_n)$ the maximal Euclidean distance from the geodesic $\gamma_n$ to the straight line path between $(-n,0)$ and $(n,0)$, and define $d(\gamma^\pm_n)$ similarly for $\gamma^\pm_n$. By the definition of the transversal fluctuation exponent $\xi$, $d(\gamma^\pm_n)$ scales like $n^\xi$ and $d(\gamma_n)$ scales like $(2n)^\xi$.

Since $\tfrac 1 2$ is less than the critical probability for oriented bond percolation in two dimensions $\approx .633$, a theorem of Licea-Newman-Piza applies and there is a rigorous lower bound $$\xi \ge 1/3$$ for your model. (cf. Theorem 4.3 in Howard - Models of First-Passage Percolation)

Suppose that $\gamma_n = \gamma^-_n \cup \gamma^+_n$ (i.e. the geodesic $\gamma_n$ meets the origin), so that $$2^\xi n^\xi \approx d(\gamma_n) = \max\{d(\gamma^-_n), d(\gamma^+_n)\} \approx n^\xi, $$ which suggests a contradiction since $2^\xi > 1$ by the lower bound $\xi \ge 1/3$.

Here's why it doesn't work. The exponent $\xi$ is precisely defined as the minimal power of $n$ such that the following hold: $$\lim_{n\to\infty} \mathbb P\left[d(\gamma^\pm_n) \le n^\xi \right] = 1 \qquad \mathrm{and} \qquad \lim_{n\to\infty} \mathbb P\left[d(\gamma_n) \le (2n)^\xi \right] = 1.$$ Since the $\approx$ signs above are really inequalities, there is no contradiction above.

$\endgroup$
1
  • 1
    $\begingroup$ That's very interesting. I did not know that there is a (provable) lower bound for xsi and this certainly looks very relevant. (In fact stronger than my question...) $\endgroup$
    – Gil Kalai
    Apr 28, 2010 at 6:08
2
$\begingroup$

Here is a sketch of a germ of an idea that might work. But don't take it too seriously.

Consider the space $E_k$ of grid paths from $(0,0)$ to $(2k+1,0)$ with nonnegative $x_2$-coordinate and Euclidean length $2k+3$. Associate such paths with functions in the obvious way. Now there are $\binom{2k+2}{2}$ such paths, $2\binom{k+1}{2}$ (i.e., proportionally just less than one half) of which contain the middle edge. Now there exists an assignment of edge lengths and corresponding coefficients $\{a_j\}_{j=1}^k \in \{0,1\}^k$ s.t. the sum $\gamma = \sum_{j=1}^k a_j \gamma_j$ is a shortest path (provided we require a nonnegative $x_2$-coordinate).

If the $a_j$ and $\gamma_j$ are selected uniformly at random, then the probability that the middle edge will be contained in $\gamma$ is asymptotically $2^{-k/2}$.

$\endgroup$
2
$\begingroup$

Talking about naive attempts, I thought maybe a simple solution along these lines could be found, but I couldn't:

I denote by $p_k(n,2r)$ the probability that a shortest path from the origin to $(n,2r)$ contains the segment $(\lfloor \frac{n}{2}\rfloor,k)$ to $(\lfloor \frac{n}{2}\rfloor +1,k)$. A simple observation is that $p_k(n,2k)=p_k(n,0)$ (consider reflecting the path on the line $y=k$ in the region $x > \lfloor \frac{n}{2}\rfloor$). The idea is to show that $p_k(n,2k)$ is close to $p_0(n,0)$ for small $k$. One can do this maybe by considering a new rectangular grid spanned by $(1,\frac{2k}{n})$ and $(-\frac{2k}{n},1)$ (with suitable edge weight distribution) and trying to find the new $p_0'(n,0)$ which should be a good approximation of $p_k(n,2k)$.

Now if one can find a slowly decreasing function $f$ so that $p_k(n,2k)\approx f(p_0(n,0))$ in the range, say $|k|\le \sqrt{n}$ then $$1=\sum_{k=-\infty}^{\infty}p_k(n,0)=\sum_{k=-\infty}^{\infty}p_k(n,2k)\approx \int_{-\sqrt{n}}^{\sqrt{n}}f(p)dp \geq c\sqrt{n}p_0(n,0)$$ for some constant $c$. If $\lim_{n\to \infty}p_0(n,0)>0$ then the above inequality is obviously false for large enough $n$.

ETA: I realize this approach works if we were able to prove $$\liminf_{n\to \infty} p_{0}(n,0)=\liminf_{n\to \infty} p_k(n,0)$$ for any fixed $k$.

$\endgroup$
2
$\begingroup$

UPDATE: Fixed typing error in 2nd paragraph (greater than -> less than or equal to)

UPDATE2: Fixed typing errors pointed out by Gil Kalai

UPDATE3: I put off the detailed version from my webpage

UPDATE4: The solution is wrong, as pointed out to me by Nathanaël Berestycki. It is of course not enough to consider only the path that goes directly from the origin to (n,0). I didn't read the problem properly. Sorry.

I don't know whether this problem is still open, but I think I have found an elementary proof for the original question. It is almost too simple to be true, but I don't see any mistake. Here's the sketch:

All numbers here are natural numbers between $0$ and $n$, and $n$ is sufficiently large. Fix a (large) $K$. Let $x_l$ be the smallest $x < n/3$, such that for all $1\le j \le K$, the length of the path $(x,0)\rightarrow (x,j) \rightarrow (x+K,j)$ is less than or equal to the length of the path $(x,0)\rightarrow (x+K,0)$. The arrow indicates that we take the direct path. For definiteness, set $x_l = \lfloor n/3 \rfloor + 1$ if such a number does not exist, but note that it exists with probability going to one as $n\rightarrow \infty$. Note further that since we took the smallest $x$ with the above property, conditioned on $x_l$, the lengths of the edges to the right of the vertical line $x=x_l+K$ are still independent, of the same law as before, and independent of the configuration to the left of this vertical line.

Now define $x_r$ by mirroring the above definition at the line $x=n/2$ (the largest $x>2n/3$, such that ....)

Then, the paths $(x_l+K,j)\rightarrow(x_r-K,j)$ are independent for $0\le j\le K$, hence, with probability going to $K/(K+1)$, there exists $1\le j \le K$, such that the path $(x_l+K,j)\rightarrow(x_r-K,j)$ is shorter than $(x_l+K,0)\rightarrow(x_r-K,0)$.

Combining the above observations, with probability $K/(K+1) + o(1)$, there exist $x_l < n/3$, $x_r>2n/3$ and $1\le j \le K$ such that the path $(0,0) \rightarrow (x_l,0)\rightarrow (x_l,j)\rightarrow (x_r,j) \rightarrow (x_r,0) \rightarrow (n,0)$ is shorter than the path $(0,0) \rightarrow (n,0)$. Letting first $n\rightarrow \infty$, then $K\rightarrow\infty$ finishes the proof.

$\endgroup$
7
  • $\begingroup$ Dear Pascal, it is a bit too sketchy for me to follow but it looks promising! (Also I supppose the vertical line is x=x_l+K). $\endgroup$
    – Gil Kalai
    Sep 25, 2011 at 13:26
  • $\begingroup$ @Gil: Thanks for having a look at the proof and pointing out the typos. I'd be glad to write down a detailed version, if the problem still interests you. $\endgroup$ Sep 25, 2011 at 17:22
  • $\begingroup$ Dear Pascal, yes definitely it is an interesting problem on its own, several people tried to prove it (including us) and it has some applications regarding geodesics in the random metric described by FPP. $\endgroup$
    – Gil Kalai
    Sep 25, 2011 at 19:51
  • $\begingroup$ Dear Pascal, the conjecture is from 2002 by Benjamini, Schramm and myself in the paper cited in the question itself .front.math.ucdavis.edu/0203.5262 . It is mentioned at the bottom of page 2 and the top of page 5. Actually on page 5 a slightly stronger version that we needed is mentioned and maybe your method apply there too. $\endgroup$
    – Gil Kalai
    Sep 26, 2011 at 12:10
  • $\begingroup$ OK, I'll have a look at it and see if the method can be applied to the stronger statement. $\endgroup$ Sep 26, 2011 at 12:59
1
$\begingroup$

Midway Problem (a reformulation only)

This is not an Answer. Start with a 2n x2n grid graph. all edges length one, all even pairs linked.

The "both even" numbered vertices are "the original graph". Add (x odd, y even) vertices half the time. Add (x even, y odd) vertices the time. The (odd, odd) vertices are always out. Seems a decent starting point. Point Midway is now (n+1, 0), and in the graph half of the time.

The two questions may then be:

Strongest question, as n grows: Show with probability approaching one that the set of all shortest paths between (0,0) and (2n,0) almost never contains Midway.

Weaker question, as n grows: Show with probability approaching one that there is a shortest path
between (0,0) and (2n,0) that does not contain Midway.

They may even have different answers, unless the shortest path has "uniqueness" properties. So again, this is not an answer.

But, the fractions are gone, and the edge lengths are all one!

Apologies for the initial typo. Is this variation more accessible?
The Far Corner variant of Midway, with an exclusion somewhere, may be easier for purists; but again, I do not know the answer (Nor even close). Propertys of shortest path sets from (0,0) to (2n,2n) may shed light on the axial case. Some small variety of forbidden minor, behaving as Midway, may be worthy of considering. I would try constant sized cycles.

$\endgroup$
1
  • 1
    $\begingroup$ That's an interesting variation of the problem that might be easier. When you say add (x odd y even) hald the time do you mean with probability 1/2? I suppose also the (x even y odd) vertices are also added half the time. that's interesting. $\endgroup$
    – Gil Kalai
    Jan 31, 2010 at 16:52

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.