Nikolaos Fountoulakis
Reader in Probabilistic Combinatorics
Email: n dot fountoulakis at bham dot ac.uk
Phone: +44 121 414 6188
Fax: +44 121 414 3389
 Random discrete structures
 Stochastic processes on graphs
 Probabilistic combinatorics
Preprints
Journal articles
 Bootstrap percolation in inhomogeneous random graphs (joint with H.Amini and K. Panagiotou), Advances in Applied Probability, to appear.
 Condensation phenomena in preferential attachment trees with neighbourhood influence (joint with T. Iyer), Electronic Journal of Probability27 (2022), 49pp.
 Dynamical models for random simplicial complexes, (joint with T. Iyer, C. Mailler and H. Sulzbach), Annals of Applied Probability 32 (2022), 28602913. pdf
 The modularity of random graphs on the hyperbolic plane (with J. Chellig and F. Skerman), Journal of Complex Networks 10 (2022), 32 pp.
 Algebraic and combinatorial expansion in random simplicial complexes (joint with M. Przykucki), Random Structures and Algorithms 60 (2022), 339366.
 Percolation on random graphs with a fixed degree sequence, (joint with F. Joos and G. Perarnau), SIAM Journal on Discrete Mathematics 36 (2022), 146 .
 Best response dynamics on random graphs (joint wiht J. Chellig and C. Durbac), Games and Economic Behavior 131 (2022), 141170.
 Clustering in a hyperbolic model of complex networks (joint with P. vd Hoorn, T. Müller and M. Schepers), Electronic Journal of Probability 26 (2021), 132pp.
 Hamilton cycles and perfect matchings in the KPKVB model, (joint with D. Mietchse, T. Müller and M. Schepers), Stochastic Processes and their Applications 131 (2021), 340358.
 Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs (joint with M. Kang and T. Makai), Random Structures and Algorithms 57 (4) (2020), 11341156
 Limit theory for the number of isolated and extreme points in hyperbolic random graphs (joint with J. Yukich), Electronic Journal of Probability 25 (2020), paper no. 141, 51 pages (electronic)
 A phase transition on the evolution of bootstrap processes in inhomogeneous random graphs, (joint with M. Kang, C. Koch and T. Makai), Annals of Applied Probability 28 (2018), 9901051.
 Law of large numbers for the largest component in a hyperbolic model of complex networks, (joint with T. Müller), Annals of Applied Probability 28 (2018), 607650.
 A phase transition on the evolution of bootstrap percolation processes on preferential attachment graphs, (joint with M.Abdullah), Random Structures and Algorithms 52 (2018), 379418.
 Typical distances in a geometric model for complex networks, (joint with M. Abdullah and M. Bode), Internet Mathematics 1 (2017), 38 pages (electronic).
 The probability of connectivity in a hyperbolic model of complex networks, (joint with M. Bode and T. Müller), Random Structures and Algorithms 49(1) (2016), 6594.
 Clustering and the hyperbolic geometry of complex networks (joint with E. Candellero), Internet Mathematics 12(12) (2016), 253.
(a short version has appeared in Proceedings of the 11th International Workshop on Algorithms and Models for the Web graph (WAW'14) (A. Bonato et al. Eds.), Lecture Notes in Computer Science 8882, 2014, pp. 112.)
 Multiple orientability thresholds for random hypergraphs (joint with M. Khosla and K. Panagiotou),
Combinatorics, Probability and Computing 25(6) (2016), 870908.
 Bootstrap percolation and the geometry of complex networks (joint with E. Candellero), Stochastic Processes and their Applications 126(1) (2016), 234264.
 On the largest component of a hyperbolic model of complex networks, (joint with M. Bode and T. Müller), Electronic Journal of Combinatorics 22 (3) (2015), 3.24.
 On a geometrization of the ChungLu model for complex networks, Journal of Complex Networks 3(3) (2015), 361387.
 On the averagecase complexity of parametrised clique, (joint with T. Friedrich and D. Hermelin), Theoretical Computer Science 576 (2015), 1829.
 Bootstrap percolation in powerlaw random graphs, (joint with H. Amini) J. Stat. Phys. 155 (2014), 7292.
 Largest sparse subgraphs of random graphs, (joint with R. Kang and C. McDiarmid), European J. Combin. 35 (2014), 232244.
 On the insertion time of Cuckoo hashing (joint with K. Panagiotou and A. Steger), SIAM Journal on Computing 42 (2013), 21562181.
 Rumor spreading on random regular graphs and expanders, (joint with K. Panagiotou), Random Structures and Algorithms 41 (2013), 201220.
 Sharp load thresholds for Cuckoo hashing, (joint with K. Panagiotou), Random Structures and Algorithms 41 (2012), 306333.
 3Connected Cores in Random Planar Graphs,(joint with K. Panagiotou), Combinatorics, Probability and Computing 20(3) (2011), 381412.

The tstability number of a random graph, (joint with
C.J.H. McDiarmid and R. Kang), The Electronic Journal of Combinatorics R(59), 2010.

Quasirandom rumor spreading on the complete graph is as
fast as randomized rumor spreading, (joint with A. Huber), SIAM Journal on Discrete Mathematics 23 (2009), 19641991.

Embeddings and Ramsey numbers
of sparse kuniform hypergraphs
(joint with O.J. Cooley, D. Kühn and D. Osthus),
Combinatorica 29 (2009), 263297.
 Minors in random
regular graphs (joint with D. Kühn and D. Osthus), Random Structures and Algorithms 35 (2009), 444463.
 The order of the largest complete minor in a random graph
(joint with D. Kühn and D. Osthus), Random Structures and Algorithms 33 (2008), 127141.

3Uniform hypergraphs of bounded degree have linear Ramsey numbers
(joint with O.J. Cooley, D. Kühn and D. Osthus),
Journal of Combinatorial Theory B 98(2008), 484505.
 The evolution of the mixing rate of a simple random walk on
the giant component of a random graph ,
(joint with B. A. Reed), Random Structures and Algorithms
33 (2008), 6886.

Percolation on sparse random graphs with given degree sequence,
Internet Mathematics 4 (2007), 329356.
 Faster Mixing and Small Bottlenecks , (joint with B. A. Reed), Probability Theory and Related Fields 137 (2007), 475486.
 Upper bounds on the non3colourability threshold of random graphs (joint with C.J.H. McDiarmid), Discrete Mathematics and Theoretical Computer Science 5 (2002), 205226.
Refereed conferences
 Local majority dynamics on preferential attachement graphs (full version), (joint with M. Abdullah and M. Bode), Proceedings of the 11th International Workshop on Algorithms and Models for the Web graph (WAW'14) (A. Bonato et al. Eds.), Lecture Notes in Computer Science 9479, 2015, pp. 95106.
 What I tell you three times in true: bootstrap percolation in small worlds, (joint with H. Amini), In Proceedings of
the 8th Workshop on Internet and Network Economics (WINE '12) (P. Goldberg, Ed.), Lecture Notes in Computer Science, 7695, 2012, pp. 462474.
 Ultrafast rumor spreading in social networks (joint with K.Panagiotou and T.Sauerwald),
In Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 2012, pp. 16421660.
 The multipleorientability thresholds of random hypergraphs
(joint with M. Koshla and K. Panagiotou), In Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, U.S.A., 2011, pp.12221236.
 Rumor spreading on random regular graphs and expanders, (joint with K. Panagiotou), In Proceedings of
RANDOM 2010, Leture Notes in Computer Science 6302, Springer, 2010, pp. 560573.
 Orientability of random hypergraphs and the power of multiple choices ,
(joint with K.Panagiotou) In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Lecture Notes in Computer Science 6198, Springer, 2010, pp. 348359.
 Reliable broadcasting on random networks and the effect of
density , (joint with A.Huber and K.Panagiotou)
In Proceedings of IEEE INFOCOM 2010, 2010, pp. 25522560.

Brief announcement:The speed of broadcasting in random networks:
density does not matter, (joint with A. Huber and K. Panagiotou),
In Proceedings of the 23rd International Symposium on Distributed
Computing (DISC 2009), Lecture Notes in Computer Science 5805, Springer, 2009, pp. 529530.

A general critical condition for the emergence of a giant component in random graphs with given degrees,
(joint with B. Reed) In Proceedings of EUROCOMB 2009,
Electronic Notes in Discrete Mathematics 34, 2009, pp. 639645
Edited volumes
 Combinatorics (2AC)

Statistics (2S)

Stochastic Processes (4SP)

September 2008  March 2011, Research fellow, MaxPlanckInstitut Informatik, Germany.
 May 2006  September 2008, Research fellow, School
of Mathematics ,
University of Birmingham, UK.
 August 2003  July 2004, Research fellow,
School of Computer Science , McGill University, Canada.
 Some of my collaborators:
M. Kang ,
R. Kang,
T. Müller,
G. Perarnau,
F. Joos,
K. Panagiotou,
D. Kühn,
,
D. Osthus , B. Reed ,
C. McDiarmid.