{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T00:06:57Z","timestamp":1763338017914},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T00:00:00Z","timestamp":1540252800000},"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,1]]},"abstract":"<jats:p>Consider a uniform random rooted labelled tree on <jats:italic>n<\/jats:italic> vertices. We imagine that each node of the tree has space for a single car to park. A number <jats:italic>m<\/jats:italic> \u2264 <jats:italic>n<\/jats:italic> of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider <jats:italic>m<\/jats:italic> = \u230a\u03b1 <jats:italic>n<\/jats:italic>\u230b and let <jats:italic>A<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>,\u03b1<\/jats:sub> denote the event that all \u230a\u03b1 <jats:italic>n<\/jats:italic>\u230b cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if \u03b1 \u2264 1\/2, we have <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548318000457_inline1\" \/><jats:tex-math>$\\mathbb{P}({A_{n,\\alpha}}) \\to {\\sqrt{1-2\\alpha}}\/{(1-\\alpha})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, whereas if \u03b1 &gt; 1\/2 we have <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548318000457_inline2\" \/><jats:tex-math>$\\mathbb{P}({A_{n,\\alpha}}) \\to 0$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton\u2013Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(\u03b1) number of cars arrive at each vertex. Let <jats:italic>X<\/jats:italic> be the number of cars which visit the root of the tree. We show that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548318000457_inline3\" \/><jats:tex-math>$\\mathbb{E}{[X]}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions.<\/jats:p>","DOI":"10.1017\/s0963548318000457","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T07:30:08Z","timestamp":1540279808000},"page":"23-45","source":"Crossref","is-referenced-by-count":19,"title":["Parking on a Random Tree"],"prefix":"10.1017","volume":"28","author":[{"given":"CHRISTINA","family":"GOLDSCHMIDT","sequence":"first","affiliation":[]},{"given":"MICHA\u0141","family":"PRZYKUCKI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,10,23]]},"reference":[{"key":"S0963548318000457_ref5","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1215\/ijm\/1258059469","article-title":"Random walk on the incipient infinite cluster on trees","volume":"50","author":"Barlow","year":"2006","journal-title":"Illinois J. Math."},{"key":"S0963548318000457_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v6-96"},{"key":"S0963548318000457_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2016.03.001"},{"key":"S0963548318000457_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964810000136"},{"key":"S0963548318000457_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02124750"},{"key":"S0963548318000457_ref16","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.6.2620"},{"key":"S0963548318000457_ref1","unstructured":"Abraham R. and Delmas J.-F. (2015) An introduction to Galton\u2013Watson trees and their local limits. Lecture notes available at arXiv:1506.05571."},{"key":"S0963548318000457_ref2","unstructured":"Addario-Berry L. (2013) The local weak limit of the minimum spanning tree of the complete graph. arXiv:1301.1667"},{"key":"S0963548318000457_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20011"},{"key":"S0963548318000457_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4108-9_19"},{"key":"S0963548318000457_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700016517"},{"key":"S0963548318000457_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589"},{"key":"S0963548318000457_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0114101"},{"key":"S0963548318000457_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009188"},{"key":"S0963548318000457_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000142"},{"key":"S0963548318000457_ref11","first-page":"425","article-title":"Subdiffusive behavior of random walk on a random cluster","volume":"22","author":"Kesten","year":"1986","journal-title":"Ann. Inst. H. Poincar\u00e9 Probab. Statist."},{"key":"S0963548318000457_ref10","unstructured":"Jones O. (2018) Runoff on rooted trees. arXiv:1807.08803"},{"key":"S0963548318000457_ref17","first-page":"1","article-title":"Parking functions and noncrossing partitions","volume":"4","author":"Stanley","year":"1997","journal-title":"Electron. J. Combin."},{"key":"S0963548318000457_ref4","volume-title":"Probability on Discrete Structures","author":"Aldous","year":"2004"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T20:25:28Z","timestamp":1555100728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000457\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,23]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["S0963548318000457"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000457","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,23]]}}}