On Directed Random Graphs and Greedy Walks on Point Processes

Abstract

Assigning irandomly itwo ior more imarks ito ithe ipoints iof ithe iPoisson iprocess ion ithe iline newlinemimics ithe igreedy iwalk ion ia istrip; ibypassed ipoints icorrespond ito the ipoints iwith imultiple newlineimarks ion ithe iline. iAn iexplanation iis ithat the igreedy iwalk ineeds ito ipass iseveral itimes newlineiover ithe ipoint iwithimultiple imarks ito idelete iall imarks, isimilarly ias ithe igreedy iwalk ion newlinethe istrip imight ipass iseveral itimes iaround ithe ipoint ibefore iit iis finally ivisited. Conjecture newlineithat iwhenever ithe ipoints of ia iPoisson iprocess iare iassigned itwo ior imore imarks iwith newlineipositive probability, ithe igreedy iwalk ivisits iall ipoints iof ithe ipoint iprocess. In iPaper iIV iwe newlineistudy ithe igreedy iwalk ion itwo ihomogeneous Poisson iprocesses iplaced ion itwo iparallel newlineilines iat idistance ir. iThis can ibe icompared ito ia istrip ior ithe iline iwith i double imarks, newlinebecause ithe igreedy iwalk imight ipass ion ione iline, ileaving isome iof the ipoints ion ithe iother newlineiline iunvisited. iThose iunvisited ipoints icause the iwalk ito ireturn itowards ithe istarting ipoint. newlineAs they play an important role in the proofs, we give a brief overview of point processes in Section newline1.1. The first two papers included in the thesis study models of directed random graphs, which are newlineintroduced in Section 1.2. In Paper I we look at the longest path in a long and thin rectangle and newlineprove that the length of such a path, properly rescaled and centered, converges to the Tracy-Widom newlinedistribution. To be able to show this, we observe that there are special points in the graphs called skeleton points, which are defined in Section 1.3. The Tracy-Widom distribution is newlinedescribed in Section 1.4. The last three papers study greedy walks defined on various point processesing