Jane (Pu) Gao

Jane Gao

    Assistant Professor

    Department of Combinatorics and Optimization
    University of Waterloo

    Office: MC 6012
    Phone: 1 (519) 888 4567 (37529)
    Email: pu dot gao at uwaterloo dot ca


Random graph theory, asymptotic graph enumeration, theoretical computer science, randomized algorithms and stochastic processes.



  1. P. Gao.  
    Triangles and subgraph probabilities in random regular graphs.

  2. P. Gao.  
    Kim-Vu's sandwich conjecture is true for all d=Ω((log n)^7).

  3. P. Gao and Y. Ohapkin.  
    Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity.

  4. P. Gao, B. Kaminski, C. MacRury and P. Pralat.  
    Hamilton cycles in the semi-random graph process.

  5. L. Brick, P. Gao and A. Southwell.  
    The threshold of symmetry in random graphs with specified degree sequences.

  6. P. Gao, R. Ramadurai, I. Wanless and N. Wormald.  
    Counterexamples on matchings in hypergraphs and full rainbow matchings in graphs.

  7. P. Gao.  
    Analysis of the parallel peeling algorithm: a short proof.

Published or accepted

  1. P. Gao and C. Greenhill.  
    Mixing time of the switch Markov chain and stable degree sequences.
         Discrete Applied Mathematics, accepted.

  2. M. Anastos, A. Frieze, and P. Gao.  
    Hamiltonicity of random graphs in the stochastic block model.
         SIAM Journal on Discrete Mathematics, accepted.

  3. P. Gao, R. van der Hofstad, A. Southwell and C. Stegehuis.  
    Counting triangles in power-law uniform random graphs.
         Elec. J. Combinatorics, 27(3), (2020), P3.19.

  4. P. Gao, R. Ramadurai, I. Wanless and N. Wormald.  
    Full rainbow matchings in graphs and hypergraphs.
         Combinatorics, Probability and Computing, accepted.

  5. A. Coja-Oghlan, A. Ergur, P. Gao, S. Hetterich, M. Rolvien.  
    The rank of sparse random matrices.
         Proc. SODA 2020 (extended abstract).
         A preliminary version titled "The rank of random matrices over finite fields" can be found [here].

  6. P. Gao, M. Isaev and B. McKay.  
    Sandwiching random regular graphs between binomial random graphs.
         Proc. SODA 2020 (extended abstract).

  7. P. Gao and C. Greenhill.  
    Uniform generation of spanning regular subgraphs of a dense graph.
         Electronic Journal of Combinatorics, accepted.

  8. A. Arman, P. Gao, N. Wormald.  
    Fast uniform generation of random graphs with given degree sequences.
         FOCS2019, pp. 1371-1379.
         Random Struct. Algorithms, accepted.

  9. P. Ayre, A. Coja-Oghlan, P. Gao, N. Müller.  
    The satisfiability threshold for random linear equations.
         Combinatorica, accepted.

  10. P. Gao and N. Wormald.  
    Uniform generation of random graphs with power-law degree sequences.
         SODA 2018: 1741-1758 (Extended abstract).

  11. P. Gao.  
    The stripping process can be slow: part II.
         Siam Journal on Discrete Mathematics, accepted.

  12. P. Gao, X. Perez-Gimenez and C. M. Sato.   
    Arboricity and spanning-tree packing of random graphs.
         Random Struct. Algorithms, accepted.
         Extended abstract published in SODA 2014, 317-326.   [conference version]

  13. P. Gao and N. Wormald.   
    Uniform generation of random regular graphs.
         Siam Journal of Computing, 46(4): 1395-1427.
         Extended abstract published in Proc. FOCS 2015, 1218-1230.   [conference version]

  14. P. Gao and M. Molloy.  
    Inside the clustering window for random linear equations.
        Random Struct. Algorithms52(2): 197-218 (2018)

  15. P. Gao and M. Molloy.  
    The stripping process can be slow: part I.
        Random Struct. Algorithms, accepted.

  16. P. Gao and C. M. Sato.  
    A transition of limiting distributions of large matchings in random graphs.
        Journal of Combinatorial Theory, Series B, 116: 57-86, 2016.

  17. P. Gao.  
    On the geometric Ramsey numbers of trees.
        Discrete Mathematics, 339(1): 375-381, 2016.

  18. P. Gao and N. Wormald.  
    Enumeration of graphs with a heavy-tailed degree sequence.
        Advances in Mathematics, 287: 412-450, 2016.

  19. J. Cibulka, P. Gao, M. Krcal, T. Valla and P. Valtr.  
    On the geometric Ramsey number of outerplanar graphs.
        Discrete & Computational Geometry, 53(1): 64-79, 2015.
        Extended abstract published in Eurocomb 2013, 171-176.

  20. P. Gao, N. C. Wormald.  
    Orientability thresholds of random hypergraphs.
        Combinatorics, Probability & Computing 24(5): 774-824 (2015).
        Extended abstract (titled: Load balancing and orientability thresholds of random hypergraphs) published in Proc. STOC 2010, 97-104.   [conference version]

  21. P. Gao.  
    The first k-regular subgraph is large.
        Combinatorics, Probability & Computing, 23(3): 412-433 (2014).

  22. P. Gao.   
    Sandwiching a densest subgraph by consecutive cores.
       [ pdf]
         Random Struct. Algorithms, 47(2): 341-360, 2015.

  23. E. Ebrahimzade, F. Farczadi, P. Gao, A. Mehrabian, C. Sato, N. Wormald and J. Zung.   
    On the longest path and the diameter in random Apollonian networks.
         Random Struct. Algorithms, 45(4): 703-725, 2014.
         Extended abstract published in Electronic Notes in Discrete Mathematics, 43, 355-365.    [conference version]

  24. P. Gao.  
    Uniform generation of d-factors in dense host graphs.
        Graphs Combin. 30 (2014), no. 3, 581-589.

  25. P. Gao.  
    Distributions of sparse spanning subgraphs in random graphs.
        SIAM Journal on Discrete Mathematics, 27 (2013), no. 1, 386-401.

  26. P. Gao.  
    Distribution of the number of spanning regular subgraphs in random graphs.
        Random Struct. Algorithms 43 (2013), no. 3, 338-353.

  27. P. Gao, Y. Su and N. C. Wormald.  
    Induced subgraphs in sparse random graphs with given degree sequence
         European Journal of Combinatorics, 33(6): 1142-1166 (2012).

  28. P. Gao.  
    The connectivity of the random regular graphs generated by the pegging algorithm
         J. Graph Theory, 65(3), 185-197, 2010.

  29. P. Gao, N. C. Wormald.  
    Rate of convergence of the short cycle distribution in random regular graphs generated by pegging.
         Elec. J. Combinatorics, Volumn 16(1)(2009), R44, 17 pp.

  30. P. Gao, N. C. Wormald.  
    Short cycle distributions in random regular graphs recursively generated by pegging.
         Random Struct. Algorithms 34(1): 54-86 (2009).