The Directed Spanning Forest is almost surely a tree

-

English
14 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
The Directed Spanning Forest is almost surely a tree David Coupier, Viet Chi Tran January 31, 2011 Abstract 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. 2 Keywords: Stochastic geometry; Directed Spanning Forest; Percolation. AMS Classification: 60D05 1 Introduction Let us consider a homogeneous Poisson point process N (PPP) on R2 with intensity 1. The plane R2 is equipped with its canonical orthonormal basis (O, ex, ey) where O denotes the origin (0, 0). In the sequel, the ex and ey coordinates of any given point of R2 are respectively called its abscissa and its ordinate, and often denoted by (x, y). From the PPP N , Baccelli and Bordenave [3] defined the Directed Spanning Forest (DSF) with direction ex as a random graph whose vertex set is N and whose edge set satisfies: the ancestor of a point X ? N is the

  • dsf

  • introduction let

  • radius √

  • let n?

  • directed spanning

  • infinite paths

  • there exists


Subjects

Informations

Published by
Reads 9
Language English
Report a problem
TheDirectedSpanningForestisalmostsurelyatreeDavidCoupier,VietChiTranJanuary31,2011AbstractWeconsidertheDirectedSpanningForest(DSF)constructedasfollows:givenaPoissonpointprocessNontheplane,theancestorofeachpointisthenearestvertexofNhavingastrictlylargerabscissa.WeprovethattheDSFisactuallyatree.Contrarytootherdirectedforestsoftheliterature,noMarkovianprocesscanbeintroducedtostudythepathsinourDSF.Ourproofisbasedonacomparisonargumentbetweensurfaceandperimeterfrompercolationtheory.WethenshowthatthisresultstillholdswhenthepointsofNbelongingtoanauxiliaryBooleanmodelareremoved.Usingtheseresults,weprovethatthereisnobi-infinitepathsintheDSF.Keywords:Stochasticgeometry;DirectedSpanningForest;Percolation.AMSClassification:60D051IntroductionLetusconsiderahomogeneousPoissonpointprocessN(PPP)onR2withintensity1.TheplaneR2isequippedwithitscanonicalorthonormalbasis(O,ex,ey)whereOdenotestheorigin(0,0).Inthesequel,theexandeycoordinatesofanygivenpointofR2arerespectivelycalleditsabscissaanditsordinate,andoftendenotedby(x,y).FromthePPPN,BaccelliandBordenave[3]definedtheDirectedSpanningForest(DSF)withdirectionexasarandomgraphwhosevertexsetisNandwhoseedgesetsatisfies:theancestorofapointXNisthenearestpointofNhavingastrictlylargerabscissa.Intheirpaper,theDSFappearsasanessentialtoolfortheasymptoticanalysisoftheRadialSpanningTree(RST).Indeed,theDSFcanbeseenasthelimitoftheRSTfarawayfromitsroot.EachvertexXoftheDSFalmostsurely(a.s.)hasauniqueancestor(butmayhaveseveralchildren).So,theDSFcanhavenoloop.Thisisaforest,i.e.aunionofoneormoredisjointtrees.ThemostnaturalquestiononemightaskabouttheDSFiswhethertheDSFisatree.Theansweris“yes”withprobability1.Theorem1.TheDSFconstructedonthehomogeneousPPPNisa.s.atree.Letusremarkthattheisotropyandthescale-invarianceofthePPPNimplythatTheorem1stillholdswhenthedirectionexisreplacedwithanygivenuR2andforanygivenvalueoftheintensityofN.Theorem1meansthata.s.thepathsintheDSF,withdirectionexandcomingfromanytwopointsX,YN,eventuallycoalesce.Inotherwords,anytwopointsX,YNhaveacommonancestorsomewhereintheDSF.ThiscanbeseenonsimulationsofFigure1.1