Paul Balister

Former Professor

Phone
901.678.3138
Office
Dunn Hall 331
Faculty Picture

Current Affiliation

University of Oxford, UK
Email: Paul.Balister@wadham.ox.ac.uk.

Research Interests

Probabilistic combinatorics, random geometric graphs

Managing editor

Combinatorics, Probability & Computing

Publications with links

  1. Paul Balister, Béla Bollobás, Alan Stacey. Upper bounds for the critical probability of oriented percolation in two dimensions, Proc. Royal Soc. London Ser. A 440 (1993), no. 1908, 201–220.
  2. Paul Balister, Béla Bollobás, Alan Stacey. Improved upper bounds for the critical probability of oriented percolation in two dimensions. Random Structures & Algorithms 5 (1994), no. 4, 573–589.
  3. Paul Balister, Susan Howson. Note on Nakayama's lemma for compact Λ-Modules. Asian J. Math. 1 (1997), no. 2, 224–229.
  4. Paul Balister. Characteristic distributions for non-torsion Λ-modules. Elliptic Curves, Modular Forms and Fermat's Last Theorem (Hong Kong, 1993), Series in Number Theory, Vol I, 2nd Edition, 141–151, International Press Inc, Cambridge MA, (1997).
  5. Paul Balister, Béla Bollobás, Alan Stacey. Counting boundary paths for oriented percolation clusters. Random Structures & Algorithms 14 (1999), no. 1, 1–28.
  6. Paul Balister, Béla Bollobás, Alan Stacey. Dependent percolation in two dimensions. Probability Theory and Related Fields 117 (2000), no. 4, 495–513.
  7. Paul Balister, Béla Bollobás, Oliver Riordan, Alex Scott. Alternating knot diagrams, Euler circuits and the interlace polynomial. European Journal of Combinatorics 22 (2001), no. 1, 1–4.
  8. Paul Balister. On the Alspach conjecture. Combinatorics, Probability and Computing 10 (2001), no. 2, 95–125.
  9. Paul Balister. Packing circuits into Kn. Combinatorics, Probability and Computing 10 (2001), no. 6, 463–499.
  10. Robert Kozma, Paul Balister, Béla Bollobás, and Walter Freeman. Dynamical percolation models of phase transitions in the cortex, Proceedings: NOLTA 2001 Nonlinear Theory and its Applications. Miyagi, Japan. Oct 28 – Nov 1, 2001. Vol I 55–58.
  11. Paul Balister. Vertex-distinguishing edge colorings of random graphs. Random Structures & Algorithms 20 (2002), no. 1, 89–97.
  12. Paul Balister, Richard Schelp, Miklos Simonovits. A note on Ramsey size-linear graphs. Journal of Graph Theory 39 (2002), no. 1, 1–5.
  13. Paul Balister, Béla Bollobás, Richard Schelp. Vertex-distinguishing colorings of graphs with Δ(G)=2. Discrete Mathematics 252 (2002), no. 1–3, 17–29.
  14. Paul Balister, Béla Bollobás, Jonathan Cutler, Luke Pebody. The interlace polynomial of graphs at −1. European Journal of Combinatorics 23 (2002), no. 7, 761–767.
  15. Paul Balister, Yair Caro, Cecil Rousseau, Raphael Yuster. Zero-sum square matrices. European Journal of Combinatorics 23 (2002), no. 5, 489–497.
  16. Paul Balister, Béla Bollobás, Anthony Quas. Entropy along convex shapes, random tilings and shifts of finite type. Illinois Journal of Math. 46 (2002), no. 3, 781–795.
  17. Robert Kozma, Paul Balister, Béla Bollobás. Self-organized development of behaviors in spatio-temporal dynamical systems. International Joint Conference on Neural Networks IJCNN 2002, World Congress on Computational Intelligence WCCI 2002, Honolulu, Hawaii, May 12–17, 2002, pp.2261–2265.
  18. Paul Balister, Oliver Riordan, Richard Schelp. Vertex-distinguishing edge colorings of graphs. Journal of Graph Theory 42 (2003), no. 2, 95–109.
  19. Paul Balister, Béla Bollobás, Oliver Riordan, Richard Schelp. Graphs with large maximum degree containing no odd cycles of a given length. Journal of Combin. Theory B 87 (2003), no. 2, 366–373.
  20. Paul Balister. Packing digraphs with directed closed trails. Combinatorics, Probability and Computing 12 (2003), no. 1, 1–15.
  21. Paul Balister. Packing closed trails into dense graphs. Journal of Combin. Theory B 88 (2003), no.1, 107–118.
  22. Paul Balister, Alexandr Kostochka, Hao Li, Richard Schelp. Balanced edge colorings. Journal of Combin. Theory B 90 (2004), no. 1, 3–20.
  23. Paul Balister, Ervin Győri, Jenö Lehel, Richard Schelp. Longest paths in circular arc graphs. Combinatorics, Probability and Computing 13 (2004), no. 3, 311–317.
  24. Paul Balister, Béla Bollobás, Mark Walters. Continuum percolation with steps in an annulus. Annals of Applied Probability 14 (2004), no. 4, 1869–1879.
  25. Robert Kozma, Marko Puljic, Paul Balister, Béla Bollobás, Walter Freeman. Neuropercolation: A random cellular automata approach to spatio-temporal neurodynamics. Proc. ACRI 2004. Lecture Notes in Computer Science, vol. 3305, pp. 435–443.
  26. Paul Balister, Béla Bollobás, Anthony Quas. Percolation in Voronoi tilings. Random Structures & Algorithms 26 (2005), no. 3, 310–318.
  27. Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters. Connectivity of random k-nearest-neighbour graphs. Advances in Applied Probability 37 (2005), no. 1, 1–24.
  28. Paul Balister, Béla Bollobás, Mark Walters. Continuum percolation in the square and the disc. Random Structures & Algorithms 26 (2005), no. 4, 392–403.
  29. Robert Kozma, Marko Puljic, Paul Balister, Béla Bollobás, Walter Freeman. Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions. Biological Cybernetics 92 (2005), no. 6, 367–379.
  30. Paul Balister, Jenö Lehel, Richard Schelp. Ramsey unsaturated and saturated graphs. Journal of Graph Theory 51 (2006), no. 1, 22–32.
  31. Paul Balister, András Gyárfás, Jenö Lehel, Richard Schelp. Mono-multi bipartite Ramsey numbers, designs, and matrices. Journal of Combin. Theory A 113 (2006), no. 1, 101–112.
  32. Paul Balister, Béla Bollobás. Pair dominating graphs. European Journal of Combinatorics 27 (2006), no. 2, 322–328.
  33. Paul Balister, Béla Bollobás, Robert Kozma. Large deviations for mean field models of probabilistic cellular automata. Random Structures & Algorithms 29 (2006), no. 3, 399–415.
  34. Paul Balister, Ervin Győri, Jenö Lehel, Richard Schelp. Adjacent vertex distinguishing edge-colorings. SIAM Journal of Discrete Math. 21 (2007), no. 1, 237–250.
  35. Paul Balister, Béla Bollobás. Counting regions with bounded surface area. Communication in Mathematical Physics 273 (2007), no. 2, 305–315.
  36. Paul Balister, Béla Bollobás, Stefanie Gerke. The generalized Randić index of trees. Journal of Graph Theory 56 (2007), no. 4, 270–286.
  37. Paul Balister, Béla Bollobás, Santosh Kumar, Amites Sarkar. Reliable Density Estimates for Coverage and Connectivity in Thin Strips of Finite Length. ACM MobiCom 2007, 75–86.
  38. Paul Balister, Béla Bollobás, Stefanie Gerke. Connectivity of addable graph classes. Journal of Combin. Theory B 98 (2008), no. 3, 577–584.
  39. Paul Balister, Béla Bollobás, Stefanie Gerke. Sequences with changing dependencies. SIAM Journal of Discrete Math. 22 (2008), no. 3, 1149–1154.
  40. Paul Balister, Ervin Győri, Jenö Lehel, Richard Schelp. Connected graphs without long paths. Discrete Math. 308 (2008), no. 19, 4487–4494.
  41. Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters. Connectivity of a Gaussian network. International Journal of Ad Hoc and Ubiquitous Computing 3 (2008), no. 3, 204–213.
  42. Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters. Highly connected random geometric graphs. Discrete Appl. Math. 157 (2009), no. 2, 309–320.
  43. Paul Balister, Stefanie Gerke, Gregory Gutin. Convex sets in acyclic digraphs. Order 26 (2009), no. 1, 95–100.
  44. Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters. A critical constant for the k-nearest-neighbour model. Advances in Applied Probability 41 (2009), no. 1, 1–12.
  45. Paul Balister, Béla Bollobás, Mark Walters. Random transceiver networks. Advances in Applied Probability 41 (2009), no. 2, 323–343.
  46. Paul Balister, Jeffrey Wheeler. The Erdős–Heilbronn problem for finite groups. Acta Arithmetica 140 (2009), no. 2, 105–118.
  47. Paul Balister, Stefanie Gerke, Gregory Gutin, Adrian Johnstone, Joseph Reddington, Elizabeth Scott, Arezou Soleimanfallah, Anders Yeo. Algorithms for generating convex sets in acyclic digraphs. Journal of Discrete Algorithms 7 (2009), no. 4, 509–518.
  48. Paul Balister, Béla Bollobás, Amites Sarkar. Percolation, connectivity, coverage and colouring of random geometric graphs. Handbook of Large-Scale Random Networks 117–142, Bolyai Society Mathematical Studies 18, Springer, Berlin, (2009). Editors: Béla Bollobás, Robert Kozma, Dezső Miklós.
  49. Paul Balister, Zizhan Zheng, Santosh Kumar, Prasun Sinha. Trap Coverage: Allowing Coverage Holes of Bounded Diameter in Wireless Sensor Networks. INFOCOM 2009, 136–144.
  50. Paul Balister, Santosh Kumar. Random vs. Deterministic Deployment of Sensors in the Presence of Failures and Placement Errors. INFOCOM 2009, 2896–2900.
  51. Paul Balister, Steven Kalikow, Amites Sarkar. The Linus sequence. Combinatorics, Probability and Computing 19 (2010), no. 1, 21–46.
  52. Paul Balister, Béla Bollobás. Bond percolation with attenuation in high dimensional Voronoĭ tilings. Random Structures & Algorithms 36 (2010), no. 1, 5–10.
  53. Paul Balister, Béla Bollobás, J. Robert Johnson, Mark Walters. Random majority percolation. Random Structures & Algorithms 36 (2010), no. 3, 315–340.
  54. Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters. Sentry selection in wireless networks. Advances in Applied Probability 42 (2010), no. 1, 1–25.
  55. Paul Balister, Béla Bollobás, Stefanie Gerke. Connectivity of random addable graphs. Advances in discrete mathematics and applications: Mysore, 2008, 125–132, Ramanujan Math. Soc. Lect. Notes Ser., 13, Ramanujan Math. Soc., Mysore, 2010.
  56. Paul Balister, Ervin Győri, Richard Schelp. Coloring vertices and edges of a graph by nonempty subsets of a set. European J. Combin. 32 (2011), no. 4, 533–537.
  57. Paul Balister, Balázs Patkós. Random partial orders defined by angular domains. Order 28 (2011), no. 2, 341–355.
  58. Paul Balister, Béla Bollobás, Animashree Anandkumar, Alan Willsky. Energy-latency tradeoff for in-network function computation in random networks. INFOCOM 2011, 1575–1583.
  59. Paul Balister, Béla Bollobás. Critical probabilities of 1-independent percolation models. Combin. Probab. Comput. 21 (2012), no. 1–2, 11–22.
  60. Paul Balister, Béla Bollobás. Projections, entropy and sumsets. Combinatorica 32 (2012), no. 2, 125–141.
  61. Paul Balister, Randall McCutcheon. A concentration function estimate and intersective sets from matrices. Israel J. Math. 189 (2012), 413–436.
  62. Paul Balister, Béla Bollobás. Percolation in the k-nearest neighbor graph. In Recent Results in Designs and Graphs: a Tribute to Lucia Gionfriddo, Quaderni di Matematica, Volume 28. Editors: Marco Buratti, Curt Lindner, Francesco Mazzocca, and Nicola Melone, (2013), 83–100. Supporting code and results.
  63. Paul Balister, Béla Bollobás, Jenö Lehel, Michał Morayne. Repeated degrees in random uniform hypergraphs. SIAM J. Discrete Math. 27 (2013), no. 1, 145–154.
  64. Paul Balister, Béla Bollobás. Interference Percolation. Random Structures & Algorithms 44 (2014), no. 4, 399–418.
  65. Paul Balister, Béla Bollobás. Random union-closed families. Number theory, analysis, and combinatorics, 1–9, De Gruyter Proc. Math., De Gruyter, Berlin, 2014.
  66. Paul Balister, Béla Bollobás, Zoltán Füredi, John Thompson. Minimal symmetric differences of lines in projective planes. Journal of Combinatorial Designs, 22 (2014), no. 10, 435–451.
  67. Paul Balister, Stefanie Gerke. Controllability and matchings in random bipartite graphs. Surveys in combinatorics 2015, 119–145, London Math. Soc. Lecture Note Ser., 424, Cambridge Univ. Press, Cambridge, 2015.
  68. Paul Balister, Béla Bollobás, Michał Przykucki, Paul Smith. Subcritical U-bootstrap percolation models have non-trivial phase transitions. Trans. Amer. Math. Soc. 368 (2016), no. 10, 7385–7411.
  69. Paul Balister, Béla Bollobás, Jenö Lehel, Michał Morayne. Random Hypergraph Irregularity. SIAM J. Discrete Math. 30 (2016), no. 1, 465–473.
  70. Paul Balister, Béla Bollobás, Karen Gunderson. Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs. European J. Combin. 57 (2016), 85–93.
  71. Paul Balister, Béla Bollobás, Zoltán Füredi, Imre Leader, Mark Walters. Subtended Angles. Israel Journal of Mathematics 214 (2016), no. 2, 995–1012.
  72. Paul Balister, Béla Bollobás, Amites Sarkar. Barrier coverage. Random Structures & Algorithms 49 (2016), no. 3, 429–478.
  73. Paul Balister, Béla Bollobás, Paul Smith. The time of bootstrap percolation in two dimensions Probab. Theory Relat. Fields 166 (2016) no. 1–2, 321–364.
  74. Paul Balister, Stefanie Gerke, Andrew McDowell. Adversarial resilience of matchings in bipartite random graphs. Journal of Combinatorics 8 (2017), no. 1, 79–92.
  75. Paul Balister, Amy Shaw, Béla Bollobás, Bhargav P. Narayanan. Catching a fast robber on the grid. J. Combin. Theory Ser. A 152 (2017), 341–352
  76. Paul Balister, Béla Bollobás, Martin Haenggi, Amites Sarkar, Mark Walters. Sentry Selection in Sensor Networks: Theory and Algorithms. International Journal of Sensor Networks. 24 (2017), 139–148.
  77. Paul Balister, Hao Li, Richard Schelp. Decompositions of graphs into cycles with chords. J. Combin. Theory Ser. B 128 (2018), 47–65. Supplemental material.
  78. Paul Balister, Béla Bollobás, Jonathan D. Lee, Bhargav P. Narayanan. Line Percolation. Random Structures & Algorithms 52 (2018), 597–616.
  79. Paul Balister, Béla Bollobás, Robert Morris. The sharp threshold for making squares. Annals of Math. 188 (2018), no. 1, 49–143.
  80. Paul Balister, József Balogh, Enrico Bertuzzo, Béla Bollobás, Guido Caldarelli, Amos Maritan, Rossana Mastrandrea, Robert Morris, Andrea Rinaldo. River landscapes and optimal channel networks. Proc. Natl. Acad. Sci. USA 115 (2018), 6548–6553.
  81. Paul Balister, Béla Bollobás, Karen Gunderson, Imre Leader, Mark Walters. Random Geometric Graphs and Isometries of Normed Spaces. Transactions of the American Mathematical Society 370 (2018) 7361–7389.
  82. Paul Balister, Ali Doğan. On the edge spectrum of saturated graphs for paths and stars. Journal of Graph Theory 89 (2018), 364–385.
  83. Paul Balister, Béla Bollobás, Jonathan Lee, Bhargav Narayanan. Coalescence on the real line. Transactions of the American Mathematical Society 371 (2019), 1583–1619.
  84. Paul Balister, Béla Bollobás, Jonathan Lee, Robert Morris, Oliver Riordan. A note on Linnik's Theorem on quadratic non-residues. Arch. Math. (Basel) 112 (2019), 371–375.
  85. Paul Balister, Béla Bollobás, Julian Sahasrabudhe, Alexander Veremyev. Dense subgraphs in random graphs Discrete Appl. Math. 260 (2019), 66–74.
  86. Paul Balister, Béla Bollobás, Bhargav Narayanan. Reconstructing random jigsaws. Multiplex and multilevel networks 31–50, Oxford Univ. Press, Oxford, 2019.
  87. Paul Balister, Stefanie Gerke. The asymptotic number of prefix normal words. Theoretical Compututer Science 784 (2019), 75–80.
  88. Paul Balister. Branching Processes.
  89. Phoebus Chen, Karl H. Johansson, Paul Balister, Béla Bollobás, Shankar Sastry. Multi-path Routing Metrics for Reliable Wireless Mesh Routing Topologies.
  90. Paul Balister, Béla Bollobás, Oliver Riordan. Essential enhancements revisited.
  91. Paul Balister, Béla Bollobás, Karen Gunderson. Limited packings of closed neighbourhoods in graphs.
  92. Paul Balister, Béla Bollobás, Svante Janson. Consistent random vertex-orderings of graphs.
  93. Paul Balister, Chaoming Song, Oliver Riordan, Béla Bollobás, Albert-Laszlo Barabasi. Topological Phase Transitions in Spatial Networks.
  94. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba. On the Erdős Covering Problem: the density of the uncovered set.
  95. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba. The Erdős–Selfridge problem with square-free moduli, Supplemental material.
  96. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba. The structure and number of Erdős covering systems.
  97. Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba. Flat Littlewood Polynomials Exist.
  98. Paul Balister. Bounds on Rudin--Shapiro polynomials of arbitrary degree.

Orcid ID: 0000-0003-2696-0352

Current grant:
NSF DMS 1855745 (June 2019 – May 2022).