Nikolaos Fountoulakis
Publications and preprints
- Local majority dynamics on preferential attachement graphs, (joint with M. Abdullah and M. Bode), submitted.
- Typical distances in a geometric model for complex networks, (joint with M. Abdullah and M. Bode), submitted.
- 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.
- The probability that the hyperbolic random graph is connected, (joint with M. Bode and T. Müller), accepted by Random Structures and Algorithms.
- Bootstrap percolation and the geometry of complex networks (joint with E. Candellero), accepted by Stochastic Processes and their Applications.
- A phase transition on the evolution of bootstrap percolation processes on preferential attachment graphs, (joint with M.Abdullah) submitted.
- Bootstrap percolation in inhomogeneous random graphs (joint with H.Amini and K. Panagiotou) submitted .
- Clustering and the hyperbolic geometry of complex networks (joint with E. Candellero), accepted by Internet Mathematics.
(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.), LNCS 8882, 2014, pp. 1-12.)
- On a geometrization of the Chung-Lu model for complex netoworks, Journal of Complex Networks 3(3) (2015), 361-387.
- Bootstrap percolation in power-law random graphs, (joint with H. Amini) J. Stat. Phys. 155 (2014), 72-92.
- Largest sparse subgraphs of random graphs, (joint with R. Kang and C. McDiarmid), European J. Combin. 35 (2014), 232-244.
- 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. 462-474.
- On the insertion time of Cuckoo hashing (joint with K. Panagiotou and A. Steger), SIAM Journal on Computing 42 (2013), 2156-2181.
- Rumor spreading on random regular graphs and expanders, (joint with K. Panagiotou), Random Structures and Algorithms 41 (2013), 201-220.
- Sharp load thresholds for Cuckoo hashing, (joint with K. Panagiotou), Random Structures and Algorithms 41 (2012), 306-333.
- Ultra-fast rumor spreading in social networks (joint with K.Panagiotou and T.Sauerwald),
In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 2012, pp. 1642-1660.
- The multiple-orientability thresholds of random hypergraphs
(joint with M. Koshla and K. Panagiotou), In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, U.S.A., 2011, pp.1222-1236.
- 3-Connected Cores in Random Planar Graphs,(joint with K. Panagiotou), Combinatorics, Probability and Computing 20(3) (2011), 381-412.
- 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. 560-573.
- 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. 348-359.
- 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. 2552-2560.
-
The t-stability number of a random graph, (joint with
C.J.H. McDiarmid and R. Kang), The Electronic Journal of Combinatorics R(59), 2010.
-
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. 529-530.
-
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. 639-645
-
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), 1964-1991.
-
Embeddings and Ramsey numbers
of sparse k-uniform hypergraphs
(joint with O.J. Cooley, D. Kühn and D. Osthus),
Combinatorica 29 (2009), 263-297.
- Minors in random
regular graphs (joint with D. Kühn and D. Osthus), Random Structures and Algorithms 35 (2009), 444-463.
- 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), 127-141.
-
3-Uniform 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), 484-505.
- 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), 68-86.
-
Percolation on sparse random graphs with given degree sequence,
Internet Mathematics 4 (2007), 329-356.
- Faster Mixing and Small Bottlenecks , (joint with B. A. Reed), Probability Theory and Related Fields 137 (2007), 475-486.
- Upper bounds on the non-3-colourability threshold of random graphs (joint with C.J.H. McDiarmid), Discrete Mathematics and Theoretical Computer Science 5 (2002), 205-226.
- On the structure of the core of sparse random graphs, preprint.