{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T13:57:31Z","timestamp":1758808651351},"reference-count":11,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2018,10,29]],"date-time":"2018-10-29T00:00:00Z","timestamp":1540771200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p>We study a synchronous process called <jats:italic>dispersion<\/jats:italic>. Initially <jats:italic>M<\/jats:italic> particles are placed at a distinguished <jats:italic>origin vertex<\/jats:italic> of a graph <jats:italic>G<\/jats:italic>. At each time step, at each vertex <jats:italic>v<\/jats:italic> occupied by more than one particle at the beginning of this step, each of these particles moves to a neighbor of <jats:italic>v<\/jats:italic> chosen independently and uniformly at random. The process ends at the first step when no vertex is occupied by more than one particle. For the complete graph <jats:italic>K<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, for any constant <jats:italic>\u03b4<\/jats:italic>\u2009&gt;\u20091, with high probability, if <jats:italic>M<\/jats:italic>\u2009\u2264\u2009<jats:italic>n<\/jats:italic>\/2(1\u2009\u2212\u2009<jats:italic>\u03b4<\/jats:italic>), the dispersion process finishes in <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20822-math-0001.png\" xlink:title=\"urn:x-wiley:rsa:media:rsa20822:rsa20822-math-0001\" \/> steps, whereas if <jats:italic>M<\/jats:italic>\u2009\u2265\u2009<jats:italic>n<\/jats:italic>\/2(1\u2009+\u2009<jats:italic>\u03b4<\/jats:italic>), the process needs <jats:italic>e<\/jats:italic><jats:sup>\u03a9(<jats:italic>n<\/jats:italic>)<\/jats:sup> steps to complete, if ever. A lazy variant of the process exhibits analogous behavior but at a higher threshold, thus allowing faster dispersion of more particles. For paths, trees, grids, hypercubes, and Abelian Cayley graphs of large enough size, we give bounds on the time to finish and the maximum distance traveled from the origin as a function of <jats:italic>M<\/jats:italic>.<\/jats:p>","DOI":"10.1002\/rsa.20822","type":"journal-article","created":{"date-parts":[[2018,10,29]],"date-time":"2018-10-29T17:52:33Z","timestamp":1540835553000},"page":"561-585","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Dispersion processes"],"prefix":"10.1002","volume":"53","author":[{"given":"Colin","family":"Cooper","sequence":"first","affiliation":[{"name":"Department of Informatics King's College London London UK"}]},{"given":"Andrew","family":"McDowell","sequence":"additional","affiliation":[{"name":"Department of Informatics King's College London London UK"}]},{"given":"Tomasz","family":"Radzik","sequence":"additional","affiliation":[{"name":"Department of Informatics King's College London London UK"}]},{"given":"Nicol\u00e1s","family":"Rivera","sequence":"additional","affiliation":[{"name":"Department of Informatics King's College London London UK"}]},{"given":"Takeharu","family":"Shiraga","sequence":"additional","affiliation":[{"name":"Department of Information and System Engineering Chuo University Tokyo Japan"}]}],"member":"311","published-online":{"date-parts":[[2018,10,29]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0125-1"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2013.9"},{"key":"e_1_2_8_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700322"},{"key":"e_1_2_8_5_1","first-page":"95","article-title":"A growth model, a game, an algebra, Lagrange inversion, and characteristic classes","volume":"49","author":"P. Diaconis","year":"1991","journal-title":"Rend. Sem. Mat. Univ. Pol. Torino"},{"key":"e_1_2_8_6_1","volume-title":"An introduction to probability theory and its applicationsProtect","author":"Feller W.","year":"1968"},{"key":"e_1_2_8_7_1","unstructured":"A. M.FriezeandW.Pegden(2017). A note on dispersing particles on a line. arXiv: 1711.02192."},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989542"},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02985833"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03990-8"},{"key":"e_1_2_8_11_1","volume-title":"Lectures given at the School and Conference on Probability Theory, Trieste","author":"Liggett T.","year":"2002"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(70)90034-4"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20822","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T18:23:59Z","timestamp":1693679039000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,29]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1002\/rsa.20822"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20822","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,29]]},"assertion":[{"value":"2017-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}