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, Alan Frieze (Ph.D. advisor), Cecilia Holmgren, Svante Janson, Fiona Skerman.


  • 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. Frieze]
  • On random k-out sub-graphs of large graphs (pdf)
    Random Structures and Algorithms
    [Co-author: A. Frieze]
  • Minimum-cost matching in a random graph with random costs (pdf)
    SIAM Journal on Discrete Mathematics
    [Co-author: A. Frieze]
  • On edge disjoint spanning trees in a randomly weighted complete graph
    To appear in Combinatorics, Probability and Computing
    [Co-author: A. 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