random graphs and algorithms | Algorithms at UNSW

This research area studies properties of random graphs and related structures, and evaluates random processes, such as Markov chains. This informs on typical properties of graph families, and running time analyses of randomized algorithms.

selected papers

JEMS

Anita Liebenau, and Nick Wormald

Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph

Journal of the European Mathematical Society, 2024

DOI Bib

@article{HarveyH21,
  author = {Liebenau, Anita and Wormald, Nick},
  title = {Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph},
  journal = {Journal of the European Mathematical Society},
  volume = {26},
  number = {1},
  pages = {1 -- 40},
  year = {2024},
  doi = {10.4171/JEMS/1355}
}

SODA

Catherine S. Greenhill

The switch Markov chain for sampling irregular graphs (Extended Abstract)

In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, 2015

DOI Bib

@inproceedings{Greenhill15,
  author = {Greenhill, Catherine S.},
  editor = {Indyk, Piotr},
  title = {The switch Markov chain for sampling irregular graphs (Extended Abstract)},
  booktitle = {Proceedings of the Twenty-Sixth Annual {ACM-SIAM} Symposium on Discrete
                    Algorithms, {SODA} 2015, San Diego, CA, USA, January 4-6, 2015},
  pages = {1564--1572},
  publisher = {{SIAM}},
  year = {2015},
  url = {https://doi.org/10.1137/1.9781611973730.103},
  doi = {10.1137/1.9781611973730.103}
}

JCTB

Martin E. Dyer, Alan M. Frieze, and Catherine S. Greenhill

On the chromatic number of a random hypergraph

Journal of Combinatorial Theory, Series B, 2015

DOI Bib

@article{DyerFG15,
  author = {Dyer, Martin E. and Frieze, Alan M. and Greenhill, Catherine S.},
  title = {On the chromatic number of a random hypergraph},
  journal = {Journal of Combinatorial Theory, Series {B}},
  volume = {113},
  pages = {68--122},
  year = {2015},
  url = {https://doi.org/10.1016/j.jctb.2015.01.002},
  doi = {10.1016/J.JCTB.2015.01.002}
}