{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T18:17:43Z","timestamp":1693419463501},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T00:00:00Z","timestamp":1544486400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>We show that a coupling of non-colliding simple random walkers on the complete graph on <jats:italic>n<\/jats:italic> vertices can include at most <jats:italic>n<\/jats:italic> - log <jats:italic>n<\/jats:italic> walkers. This improves the only previously known upper bound of <jats:italic>n<\/jats:italic> - 2 due to Angel, Holroyd, Martin, Wilson and Winkler (<jats:italic>Electron. Commun. Probab.<\/jats:italic><jats:bold>18<\/jats:bold> (2013)). The proof considers couplings of i.i.d. sequences of Bernoulli random variables satisfying a similar avoidance property, for which there is separate interest.<\/jats:p>","DOI":"10.1017\/s0963548318000500","type":"journal-article","created":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T08:02:03Z","timestamp":1544515323000},"page":"325-334","source":"Crossref","is-referenced-by-count":1,"title":["An Upper Bound on the Size of Avoidance Couplings"],"prefix":"10.1017","volume":"28","author":[{"given":"ERIK","family":"BATES","sequence":"first","affiliation":[]},{"given":"LISA","family":"SAUERMANN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,12,11]]},"reference":[{"key":"S0963548318000500_ref13","unstructured":"Tsianos K. I. (2013) The role of the network in distributed optimization algorithms: Convergence rates, scalability, communication\/computation tradeoffs and communication delays. PhD thesis, McGill University."},{"key":"S0963548318000500_ref12","unstructured":"Tetali P. and Winkler P. (1993) Simultaneous reversible Markov chains. In Combinatorics: Paul Erd\u0151s is Eighty, Vol. 1, J\u00e1nos Bolyai Mathematical Society, pp. 433\u2013451."},{"key":"S0963548318000500_ref10","unstructured":"Infeld E. J. (2016) Uniform avoidance coupling, design of anonymity systems and matching theory. PhD thesis, Dartmouth College."},{"key":"S0963548318000500_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000195"},{"key":"S0963548318000500_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/0406029"},{"key":"S0963548318000500_ref6","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdt067"},{"key":"S0963548318000500_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP723"},{"key":"S0963548318000500_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008732"},{"key":"S0963548318000500_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20368"},{"key":"S0963548318000500_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v18-2275"},{"key":"S0963548318000500_ref11","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v14-1417"},{"key":"S0963548318000500_ref3","unstructured":"Basu R. , Sidoravicius V. and Sly A. (2014) Scheduling of non-colliding random walks. arXiv:1411.4041"},{"key":"S0963548318000500_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-006-0008-3"},{"key":"S0963548318000500_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<58::AID-RSA5>3.0.CO;2-E"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T23:38:35Z","timestamp":1555025915000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000500\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,11]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000500"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000500","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,11]]}}}