Tony Johansson

Department of Mathematics
Uppsala University

email: tony.johansson AT math DOT uu DOT se
(You can contact me in English or Swedish)


I am a postdoc in the Analysis and Probabiliy Theory group. My main research interests are random graphs and randomized algorithms.

Co-authors: Xing Shi Cai, Colin Cooper, Alan Frieze (Ph.D. advisor), Cecilia Holmgren, Svante Janson, Fiona Skerman.


  • Specialkurs i Matematik II, VT 2018


  • On the insertion time of random walk cuckoo hashing (pdf)
    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
    [Co-author: A. M. Frieze]
  • On random k-out sub-graphs of large graphs (pdf)
    Random Structures and Algorithms
    [Co-author: A. M. Frieze]
  • Minimum-cost matching in a random graph with random costs (pdf)
    SIAM Journal on Discrete Mathematics
    [Co-author: A. M. Frieze]
  • On edge disjoint spanning trees in a randomly weighted complete graph (pdf)
    Combinatorics, Probability and Computing
    [Co-author: A. M. Frieze]


  • The cover time of a biased random walk on a random cubic graph
    [Co-authors: C. Cooper, A. M. Frieze]
  • Inversions in split trees and conditional Galton--Watson trees
    [Co-authors: X. S. Cai, C. Holmgren, S. Janson, F. Skerman]
  • Deletion of oldest edges in a preferential attachment graph