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



Research

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

Publications

Preprints
  1. P. Gao, J. Mausberg, and P. Nelson.   
    Evolution of random representable matroids: minors, circuits, connectivity and the critical number.       [arxiv]

  2. A. Frieze, P. Gao, C. MacRury, P. Pra?at, G. Sorkin.   
    Building Hamiltonian cycles in the semi-random graph process in less than 2n rounds.       [arxiv]

  3. P. Gao and H. Koerts.  
    On the pre- and post-positional semi-random graph processes.       [arxiv]

  4. P. Gao and P. Nelson.  
    Minors of matroids represented by sparse random matrices over finite fields.       [arxiv]

  5. P. Gao and Y. Ohapkin.  
    Embedding theorems for random graphs with specified degrees.       [arxiv]

  6. P. Gao, M. Isaev and B. McKay.  
    Kim-Vu's sandwich conjecture is true for d>=log^4 n.       [arxiv]

  7. P. Gao, R. Ramadurai, I. Wanless and N. Wormald.  
    Counterexamples on matchings in hypergraphs and full rainbow matchings in graphs.       [arxiv]

  8. P. Gao.  
    Analysis of the parallel peeling algorithm: a short proof.       [arxiv]

Published or accepted
  1. A. Coja-Oghlan, P. Gao, M. Hahn-Klimroth, J. Lee, N. Müller, and M. Rolvien.  
    The full rank condition for sparse random matrices.       [arxiv]
         Combinatorics, Probability, and Computing, 2023 (accepted).

  2. P. Gao, C. MacRury and P. Pralat.  
    Perfect Matchings in the Semi-random Graph Process.       [arxiv]
    3.      SIAM J. Discret. Math. 36(2): 1274-1290, 2022.

  3. A. Arman, P. Gao and N. Wormald.  
    Linear-time uniform generation of random sparse contingency tables with specified marginals.       [arxiv]
         Annals of Applied Probability, 2021 (accepted).


  4. P. Gao.  
    Triangles and subgraph probabilities in random regular graphs.       [arxiv]
         Elec. J. Comb, 2023 (accepted).


  5. Pu Gao, Calum MacRury, and Pawel Pralat.  
    A fully adaptive strategy for Hamiltonian cycles in the semi-random graph process.       [arxiv]
         Proc. RANDOM 2022.

  6. P. Gao, M. Isaev and B. McKay.  
    Sandwiching dense random regular graphs between binomial random graphs.       [download]
         Probability Theory and Related Fields, 2022.
         (This article contains the dense sandwiching part of this, with several corrections.)

  7. P. Gao and Y. Ohapkin.  
    Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity.       [arxiv]
         Random Struct. Algorithms, accepted.

  8. L. Brick, P. Gao and A. Southwell.  
    The threshold of symmetry in random graphs with specified degree sequences.       [arxiv]
         SIAM Journal on Discrete Mathematics, accepted.

  9. P. Gao.  
    The number of perfect matchings, and the nesting properties, of random regular graphs.       [arxiv]
         Random Struct. Algorithms, accepted.

  10. P. Gao, B. Kaminski, C. MacRury and P. Pralat.  
    Hamilton cycles in the semi-random graph process.       [arxiv]
        European Journal of Combinatorics 99 (2022): 103423.

  11. P. Gao and C. Greenhill.  
    Mixing time of the switch Markov chain and stable degree sequences.       [arxiv]
        Discrete Applied Mathematics 291 (2021): 143-162.

  12. M. Anastos, A. Frieze, and P. Gao.  
    Hamiltonicity of random graphs in the stochastic block model.       [arxiv]
         SIAM Journal on Discrete Mathematics 35.3 (2021): 1854-1880.

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

  14. P. Gao, R. Ramadurai, I. Wanless and N. Wormald.  
    Full rainbow matchings in graphs and hypergraphs.       [arxiv]
         Combinatorics, Probability and Computing (2021): 1-19.

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

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

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

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

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

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

  21. P. Gao.  
    The stripping process can be slow: part II.       [arxiv]
         Siam Journal on Discrete Mathematics, accepted.

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

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

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

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

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

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

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

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

  30. P. Gao, N. C. Wormald.  
    Orientability thresholds of random hypergraphs.       [arxiv]
        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]

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

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

  33. 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.       [arxiv]
         Random Struct. Algorithms, 45(4): 703-725, 2014.
         Extended abstract published in Electronic Notes in Discrete Mathematics, 43, 355-365.    [conference version]

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

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

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

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

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

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

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

Theses