Alexander E. Holroyd

Email: a.e.holroyd at bristol dot ac dot uk
Bootstrap Percolation

Stable Marriage Poisson-Lebesgue

Random Sorting Networks

B-M-L Traffic Model

I'm in the School of Mathematics at the University of Bristol, UK. I also have affiliations with the Mathematics Departments at the Universities of British Columbia and Washington, and the Pacific Institute for Mathematical Sciences.

Research Interests: Probability theory, with emphasis on discrete spatial models, including cellular automata, percolation, matching, coupling.

Papers:

[88] A. E. Holroyd and J. B. Martin. Galton-Watson games. 2019. [ PDF ]
[87] O. Angel and A. E. Holroyd. Perfect shuffling by lazy swaps. Electron. Commun. Probab., 23(47), 2018. [ PDF ]
[86] O. Angel, A. E. Holroyd, T. Hutchcroft, and A. Levy. Mallows permutations as stable matchings. 2018. [ PDF ]
[85] A. E. Holroyd, T. Hutchcroft, and A. Levy. Finitely dependent cycle coloring. Electron. Commun. Probab., 23(64), 2018. [ PDF ]
[84] A. E. Holroyd, J. B. Martin, and Y. Peres. Stable matchings in high dimensions via the Poisson-weighted infinite tree. Ann. Inst. Henri Poincaré Probab. Stat., 2017. [ PDF ]
[83] A. E. Holroyd, T. Hutchcroft, and A. Levy. Mallows permutations and finite dependence. Ann. Probab., 2017. [ PDF ]
[82] J. Gravner, A. E. Holroyd, and D. Sivakoff. Polluted bootstrap percolation in three dimensions. 2017. [ PDF ]
[81] A. E. Holroyd, A. Levy, M. Podder, and J. Spencer. Second order logic on random rooted trees, 2017. [ PDF ]
[80] J. Gravner and A. E. Holroyd. Polluted bootstrap percolation with threshold two in all dimensions. Probab. Theory Related Fields, 2017. [ PDF ]
[79] O. Angel, D. Dauvergne, A. E. Holroyd, and B. Virág. The local limit of random sorting networks. Ann. Inst. Henri Poincaré Probab. Stat., 2017. [ PDF ]
[78] S. C. Billey, A. E. Holroyd, and B. J. Young. A bijective proof of Macdonald's reduced word formula. FPSAC, 2017. [ PDF ]
[77] L. Nachmanson, A. Nocaj, S. Bereg, L. Zhang, and A. Holroyd. Node overlap removal by growing a tree. J. Graph Algorithms Appl., 21(5):857-872, 2017. [ PDF ]
[76] S. Chawla, N. R. Devanur, A. E. Holroyd, A. R. Karlin, J. B. Martin, and B. Sivan. Stability of service under time-of-use pricing. STOC - -Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 184-197, 2017. [ PDF ]
[75] M. Deijfen, A. E. Holroyd, and J. B. Martin. Friendly Frogs, Stable Marriage, and the Magic of Invariance. Amer. Math. Monthly, 124(5):387-402, 2017. [ PDF ]
[74] A. E. Holroyd. Perfect snake-in-the-box codes for rank modulation. IEEE Trans. Inform. Theory, 63(1):104-110, 2017. [ PDF ]
[73] A. E. Holroyd, L. Levine, and P. Winkler. Abeilan logic gates. Combinatorics, Probability and Computing, 2017. [ PDF ]
[72] A. E. Holroyd, O. Schramm, and D. B. Wilson. Finitary coloring. Ann. Probab., 45(5):2867-2898, 2017. [ PDF ]
[71] A. E. Holroyd. One-dependent coloring by finitary factors. Ann. Inst. Henri Poincaré Probab. Stat., 53(2):753-765, 2017. [ PS | PDF ]
[70] G. Amir, O. Angel, and A. E. Holroyd. Multicolor Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat., 2016. [ PDF ]
[69] A. E. Holroyd and Z. Li. Constrained percolation in two dimensions. 2016. [ PDF ]
[68] S. Bereg, A. E. Holroyd, L. Nachmanson, and S. Pupyrev. Representing Permutations with Few Moves. SIAM J. Discrete Math., 30(4):1950-1977, 2016. [ PDF ]
[67] R. Basu, A. E. Holroyd, J. B. Martin, and J. Wästlund. Trapping games on random boards. Ann. Appl. Probab., 26(6):3727-3753, 2016. [ PDF ]
[66] A. E. Holroyd and T. M. Liggett. Finitely dependent coloring. Forum Math. Pi, 4:e9, 43, 2016. [ PS | PDF ]
[65] S. Pupyrev, L. Nachmanson, S. Bereg, and A. E. Holroyd. Edge routing with ordered bundles. Comput. Geom., 52:18-33, 2016. (Full version). [ PDF ]
[64] L. Nachmanson, R. Prutkin, B. Lee, N. H. Riche, A. E. Holroyd, and X. Chen. GraphMaps: Browsing Large Graphs as Interactive Maps, pages 3-15. Springer International Publishing, 2015. [ PDF ]
[63] A. E. Holroyd, I. Marcovici, and J. B. Martin. Percolation games, probabilistic cellular automata, and the hard-core model. 2015. [ PDF ]
[62] A. E. Holroyd and J. B. Martin. Poisson allocations with bounded connected cells. Electron. Commun. Probab., 20(69), 2015. [ PDF ]
[61] A. E. Holroyd and T. M. Liggett. Symmetric 1-dependent colorings of the integers. Electron. Commun. Probab., 20(31), 2015. [ PS | PDF ]
[60] J. Gravner and A. E. Holroyd. Percolation and disorder-resistance in cellular automata. Ann. Probab., 43(4):1731-1776, 2015. [ PS | PDF ]
[59] A. E. Holroyd, Y. Peres, and J. E. Steif. Wald for non-stopping times: the rewards of impatient prophets. Electron. Commun. Probab., 19(78), 2014. [ PDF ]
[58] G. R. Grimmett, A. E. Holroyd, and Y. Peres. Extendable self-avoiding walks. Ann. Inst. Henri Poincaré D, 1(1):61-75, 2014. [ PS | PDF ]
[57] G. R. Grimmett, A. E. Holroyd, and G. Kozma. Percolation of finite clusters and infinite surfaces. Mathematical Proceedings of the Cambridge Philosophical Society, 156:263-279, 3 2014. [ PDF ]
[56] A. E. Holroyd and J. Martin. Stochastic domination and comb percolation. Electron. J. Probab., 19:no. 5, 1-16, 2014. [ PS | PDF ]
[55] O. Angel, A. E. Holroyd, G. Kozma, J. Wästlund, and P. Winkler. The phase transition for dyadic tilings. Trans. Amer. Math. Soc., 366(2):1029-1046, 2014. [ PS | PDF ]
[54] S. Bereg, A. E. Holroyd, L. Nachmanson, and S. Pupyrev. Drawing permutations with few corners. In Graph drawing, volume 8242 of Lecture Notes in Comput. Sci., pages 484-495. Springer, Cham, 2013. [ PDF ]
[53] K. Bringmann, A. E. Holroyd, K. Mahlburg, and M. Vlasenko. k-run overpartitions and mock theta functions. Q. J. Math., 64(4):1009-1021, 2013. [ PS | PDF ]
[52] O. Angel, A. E. Holroyd, J. Martin, D. B. Wilson, and P. Winkler. Avoidance coupling. Electron. Commun. Probab., 18:no. 58, 13, 2013. [ PS | PDF ]
[51] A. E. Holroyd and T. Soo. Insertion and deletion tolerance of point processes. Electron. J. Probab., 18:no. 74, 24, 2013. [ PS | PDF ]
[50] O. Angel, V. Gorin, and A. E. Holroyd. A pattern theorem for random sorting networks. Elec. J. Probab., 17(99), 2012. [ PS | PDF ]
[49] S. Pupyrev, L. Nachmanson, S. Bereg, and A. E. Holroyd. Edge routing with ordered bundles. In Graph drawing, volume 7034 of Lecture Notes in Comput. Sci., pages 136-147. Springer, Heidelberg, 2012. (Extended abstract). [ PDF ]
[48] O. Angel and A. E. Holroyd. Recurrent rotor-router configurations. J. Comb., 3(2):185-194, 2012. [ PS | PDF ]
[47] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215-245, 2012. [ PDF ]
[46] G. R. Grimmett and A. E. Holroyd. Geometry of Lipschitz percolation. Ann. Inst. Henri Poincaré Probab. Stat., 45(2):309-326, 2012. [ PS | PDF ]
[45] G. R. Grimmett and A. E. Holroyd. Lattice embeddings in percolation. Ann. Probab., 40(1):146-161, 2012. [ PS | PDF ]
[44] J. Gravner, A. E. Holroyd, and R. Morris. A sharper threshold for bootstrap percolation in two dimensions. Probab. Theory Related Fields, 153(1-2):1-23, 2012. [ PS | PDF ]
[43] M. Deijfen, O. Häggström, and A. E. Holroyd. Percolation in invariant Poisson graphs with i.i.d. degrees. Arkiv för matematik, 50(1):41-58, 2012. [ PS | PDF ]
[42] R. A. Woodgate and A. E. Holroyd. Correction of Teledyne acoustic doppler current profiler (ADCP) bottom-track range measurements for instrument pitch and roll. 2011. [ PDF ]
[41] A. E. Holroyd. Some circumstances where extra updates can delay mixing. J. Stat. Phys., 145(6):1649-1652, 2011. [ PS | PDF ]
[40] M. Deijfen, A. E. Holroyd, and Y. Peres. Stable Poisson graphs in one dimension. Elec. J. Probab., 16(44):1238-1253, 2011. [ PS | PDF ]
[39] O. Angel and A. E. Holroyd. Rotor walks on general trees. SIAM J. Discrete Math., 25(1):423-446, 2011. [ PS | PDF ]
[38] O. Angel, A. E. Holroyd, and T. Soo. Deterministic thinning of finite Poisson processes. Proc. Amer. Math. Soc., 139(2):707-720, 2011. [ PS | PDF ]
[37] A. E. Holroyd. Geometric properties of Poisson matchings. Probab. Theory Related Fields, 150(3-4):511-527, 2011. [ PS | PDF ]
[36] J. van den Berg, M. R. Hilário, and A. E. Holroyd. Escape of resources in a distributed clustering process. Electronic Communications in Probability, 15(40):442-448, 2010. [ PS | PDF ]
[35] A. Holroyd, F. Ruskey, and A. Williams. Faster generation of shorthand universal cycles for permutations. In Computing and combinatorics, volume 6196 of Lecture Notes in Comput. Sci., pages 298-307. Springer, Berlin, 2010. [ PS | PDF ]
[34] N. Dirr, P. W. Dondl, G. R. Grimmett, A. E. Holroyd, and M. Scheutzow. Lipschitz percolation. Elec. Comm. Probab., 15:14-21, 2010. [ PS | PDF ]
[33] G. R. Grimmett and A. E. Holroyd. Plaquettes, spheres, and entanglement. Electronic Journal of Probability, 15(45):1415-1428, 2010. [ PS | PDF ]
[32] O. Angel and A. E. Holroyd. Random subnetworks of random sorting networks. Elec. J. Combinatorics, 17(1):N23, 2010. [ PS | PDF ]
[31] A. E. Holroyd and J. Propp. Rotor walks and Markov chains. In Algorithmic Probability and Combinatorics, volume 520 of Contemporary Mathematics, pages 105-126. Amer. Math. Soc., 2010. [ PS | PDF ]
[30] O. Angel, A. E. Holroyd, J. B. Martin, and J. Propp. Discrete low-discrepancy sequences. 2009. [ PS | PDF ]
[29] A. E. Holroyd, R. Lyons, and T. Soo. Poisson splitting by factors. Annals of Probability, 2009. [ PS | PDF ]
[28] A. E. Holroyd and T. Soo. A nonmeasurable set from coin flips. Amer. Math. Monthly, 116(10):926-928, 2009. [ PS | PDF ]
[27] C. Hoffman, A. E. Holroyd, and Y. Peres. Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math., 61(6):1279-1299, 2009. [ PS | PDF ]
[26] O. Angel, A. Holroyd, and D. Romik. The oriented swap process. Ann. Probab., 37(5):1970-1998, 2009. [ PS | PDF ]
[25] A. E. Holroyd, R. Pemantle, Y. Peres, and O. Schramm. Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):266-287, 2009. [ PS | PDF ]
[24] J. Gravner and A. E. Holroyd. Local bootstrap percolation. Electron. J. Probab., 14:no. 14, 385-399, 2009. [ PS | PDF ]
[23] C. Cotar, A. E. Holroyd, and D. Revelle. A percolating hard sphere model. Random Structures Algorithms, 34(2):285-299, 2009. [ PS | PDF ]
[22] A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp, and D. B. Wilson. Chip-firing and rotor-routing on directed graphs. In In and out of equilibrium. 2, volume 60 of Progr. Probab., pages 331-364. Birkhäuser, Basel, 2008. [ PS | PDF ]
[21] A. E. Holroyd. Partition identities and the coin exchange problem. J. Combin. Theory Ser. A, 115(6):1096-1101, 2008. [ PS | PDF ]
[20] J. Gravner and A. E. Holroyd. Slow convergence in bootstrap percolation. Ann. Appl. Probab., 18(3):909-928, 2008. [ PS | PDF ]
[19] A. E. Holroyd. Astonishing cellular automata. Bulletin du Centre de Recherches Mathematiques, 13(1):10-13, 2007. [ PS | PDF ]
[18] O. Angel, A. E. Holroyd, D. Romik, and B. Virág. Random sorting networks. Adv. Math., 215(2):839-868, 2007. [ PS | PDF ]
[17] N. Harvey, A. E. Holroyd, Y. Peres, and D. Romik. Universal finitary codes with exponential tails. Proc. Lond. Math. Soc. (3), 94(2):475-496, 2007. [ PS | PDF ]
[16] C. Hoffman, A. E. Holroyd, and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab., 34(4):1241-1272, 2006. [ PS | PDF ]
[15] A. E. Holroyd. The metastability threshold for modified bootstrap percolation in d dimensions. Electron. J. Probab., 11:no. 17, 418-433 (electronic), 2006. [ PS | PDF ]
[14] O. Angel, A. E. Holroyd, and J. B. Martin. The jammed phase of the Biham-Middleton-Levine traffic model. Electron. Comm. Probab., 10:167-178 (electronic), 2005. [ PS | PDF ]
[13] A. E. Holroyd and Y. Peres. Extra heads and invariant allocations. Ann. Probab., 33(1):31-52, 2005. [ PS | PDF ]
[12] A. E. Holroyd, T. M. Liggett, and D. Romik. Integrals, partitions, and cellular automata. Trans. Amer. Math. Soc., 356(8):3349-3368 (electronic), 2004. [ PS | PDF ]
[11] A. E. Holroyd. Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Related Fields, 125(2):195-224, 2003. [ PS | PDF ]
[10] A. E. Holroyd and Y. Peres. Trees and matchings from point processes. Electron. Comm. Probab., 8:17-27 (electronic), 2003. [ PS | PDF ]
[9] A. E. Holroyd. Knotted paths in percolation. J. Statist. Phys., 109(1-2):325-330, 2002. [ PS | PDF ]
[8] A. E. Holroyd. Inequalities in entanglement percolation. J. Statist. Phys., 109(1-2):317-323, 2002. [ PS | PDF ]
[7] A. E. Holroyd. Entanglement and rigidity in percolation models. In In and out of equilibrium (Mambucaba, 2000), volume 51 of Progr. Probab., pages 299-307. Birkhäuser, Boston, MA, 2002. [ PS | PDF ]
[6] A. E. Holroyd and T. M. Liggett. How to find an extra head: optimal random shifts of Bernoulli and Poisson random fields. Ann. Probab., 29(4):1405-1425, 2001. [ PS | PDF ]
[5] A. E. Holroyd. Rigidity percolation and boundary conditions. Ann. Appl. Probab., 11(4):1063-1078, 2001. [ PS | PDF ]
[4] G. R. Grimmett and A. E. Holroyd. Entanglement in percolation. Proc. London Math. Soc. (3), 81(2):485-512, 2000. [ PS | PDF ]
[3] A. E. Holroyd. Existence of a phase transition for entanglement percolation. Math. Proc. Cambridge Philos. Soc., 129(2):231-251, 2000. [ PS | PDF ]
[2] A. E. Holroyd. Percolation Beyond Connectivity. PhD thesis, University of Cambridge, 1999.
[1] A. E. Holroyd. Existence and uniqueness of infinite components in generic rigidity percolation. Ann. Appl. Probab., 8(3):944-973, 1998. [ PS | PDF ]

PhD Students:

Terry Soo (graduated November 2010 from University of British Columbia; now at University of Kansas).
Avi Levy (University of Washington; graduated Spring 2017).

Interns mentored: Vadim Gorin (2009), Riddhi Basu (2013), Tom Hutchcroft (2015,2016), Avi Levy (2016).