Vi studerar egenskaper hos flera slumpmässiga promenader på en graf under olika antaganden om interaktion mellan partiklarna. För att ge exakta resultat gör vi analysen för slumpmässiga regelbundna grafer. Omslagstiden för en slumpmässig gång på en slumpmässig r-regelbunden graf studerades i [6], där det visades med hög sannolikhet (whp), att för r ≥ 3 är omslagstiden asymptotisk till r n n, där r = (r − 1)/(r − 2). I detta papper bevisar vi följande (whp) resultat, som uppstår från studien av flera slumpmässiga promenader på en slumpmässig regelbunden graf G. För k oberoende promenader på G, omslagstiden C G (k) är asymptotic till C G /k, där C G är omslagstiden för en enda promenad. För de flesta startpositioner, det förväntade antalet steg innan någon av promenaderna möts är  på r n/ k 2. Om promenaderna kan kommunicera när de möts på en vertex, visar vi att för de flesta startpositionerna, den förväntade tiden för k promenader att sända en enda bit information till varandra är asymptotic till 2 ln k k  och r n, som k, n → ∞. Vi etablerar också egenskaper hos promenader där det finns två typer av partiklar, rovdjur och byten, eller där partiklar interagerar när de möts på en vertex genom sammansmältning, eller genom att förinta varandra. Till exempel, den förväntade utrotningstiden för k explosiva partiklar (k jämn) tenderar att (2 ln 2) till r n som k → ∞. Fallet med sammansmältningspartiklar, där en partikel ursprungligen är placerad vid varje vertex, motsvarar en röstmodell som definieras enligt följande: Inledningsvis har varje vertex en distinkt åsikt, och vid varje steg ändrar varje vertex sin uppfattning till en slumpmässig granne. Den förväntade tiden för ett unikt yttrande är densamma som den förväntade tiden för alla partiklar att sammanfalla, vilket är asymptotiskt till 22 r n.
Senare, författarna till REF studerade meet-exchange för fallet med slumpmässiga regelbundna grafer och k  till n ε slumpmässiga promenader.
Multiple Random Walks in Random Regular Graphs
{'venue': 'in SIAM J. Discrete Math', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}