Take all the naturals and for each pair (i, j) with i j with fixed probability p, thus obtaining an infinite DAG (directed acyclic graph) G. Let T be the transitive reduction of G (which is unique). How does the length of the shortest path *in T* from node h to node k (if any) grow with their 'numeric distance' (k - h)?
(The *longest* path from h to k should grow linearly with their numeric distance.)
The work by Beardwood, Halton and Hammersely (the link to which I present below) may be relevant to this question. My knowledge of this work is indirect: through the review article by Frisch and Hammersley (Percolation Processes and Related Topics - the link to which I also present below), in turn through the book Graph Theory and Theoretical Physics, by Harary (Academic Press, London, 1967).
While looking for the above-mentioned paper by Beardwood et al., I discovered a paper by L. Few (The Shortest Path and the Shortest Road though n Points. Mathematika 2, 141-144 (1955)) in which he cites the earliest work on the subject matter as being by Verblunsky (Math, Zeitschrift 46, 83-85 (1940)).
http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2049460&fileId=S0305004100034095
http://epubs.siam.org/doi/abs/10.1137/0111066
Dear Behnam Farid, thank you for the pointers. The first paper refers to distance in the plane, while I need graph distance. The Frish and Hammersley paper looks more general, and I am trying to get a copy... Thanks a lot.
Tommaso
You are welcome Tommaso. My sense is that the first paper is also relevant to your problem. Lattices, graphs and matrices (think of e.g. the incidence matrix) can all be brought into connection with each other. My own entry into the subject matter is by the way of (sparse) matrices.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Bioinformatics