The 2D‐directed spanning forest is almost surely a tree. Issue 1 (5th February 2012)

• Record Type: Journal Article
• Authors: Coupier, David; Tran, Viet Chi
• Is Part Of: Random structures & algorithms. Volume 42:Issue 1(2013)
• Page Start: 59
• Page End: 72
• Publication Date: 2012-02-05
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20400
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We consider the Directed Spanning Forest (DSF) constructed as follows: given a Poisson point process N on the plane, the ancestor of each point is the nearest vertex of N having a strictly larger abscissa. We prove that the DSF is actually a tree. Contrary to other directed forests of the literature, no Markovian process can be introduced to study the paths in our DSF. Our proof is based on a comparison argument between surface and perimeter from percolation theory. We then show that this result still holds when the points of N belonging to an auxiliary Boolean model are removed. Using these results, we prove that there is no bi‐infinite paths in the DSF. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012</p> </abstract>