Catherine Greenhill

Publications

I've split the papers into submitted papers, journal papers and conference papers, and some miscellaneous things at the end. You can download all the submitted and journal papers in PDF form (except for the really early design theory ones which are lost in the mists of time). There may be some differences from the final journal version.

Preprints

[33] E. Rodney Canfield, Zhicheng Gao, Catherine Greenhill, Brendan D. McKay and Robert W. Robinson, Asymptotic enumeration of correlation-immune boolean functions (submitted). arXiv:0909.3321 [math.CO]

Journal papers

[32] Catherine Greenhill, Svante Janson and Andrzej Rucinski, On the number of perfect matchings in random lifts, Combinatorics, Probability and Computing (to appear). arXiv:0907.0958 [math.CO]
(The Maple file used for the calculations is also available.)

[31] Catherine Greenhill and Brendan D. McKay, Random dense bipartite graphs and directed graphs with specified degrees, Random Structures and Algorithms 35 (2009), 222 - 249. arXiv:math/0701600 [math.CO] (The arXiv version contains some proof details which are omitted from the journal version. This paper evolved from an earlier one with the title "Asymptotic enumeration of dense 0-1 matrices with specified line sums and forbidden positions".)

[30] Catherine Greenhill and Brendan D. McKay, Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums, Advances in Applied Mathematics 41 (2008), 459 - 481. arXiv:0707.0340 [math.CO]

[29] Nicholas Cavenagh, Catherine Greenhill and Ian Wanless, The cycle structure of two rows in a random latin square, Random Structures and Algorithms 33 (2008), 286 - 309.

[28] Catherine Greenhill, Fred B. Holt and Nicholas Wormald, Expansion properties of a random regular graph after random vertex deletions, European Journal of Combinatorics 29 (2008), 1139 - 1150. arXiv:math/0701863 [math.CO]

[27] Rodney Canfield, Catherine Greenhill and Brendan McKay, Asymptotic enumeration of dense 0-1 matrices with specified line sums, Journal of Combinatorial Theory (Series A) 115 (2008), 32 - 66. arXiv:math/0606496 [math.CO]

[26] Colin Cooper, Martin Dyer and Catherine Greenhill, Sampling regular graphs and a peer-to-peer network, Combinatorics, Probability and Computing 16 (2007), 557 - 593.

[25] Catherine Greenhill and Andrzej Rucinski, Neighbour-distinguishing edge colourings of random regular graphs, Electronic Journal of Combinatorics 13 (2006), #R77.

[24] Stefanie Gerke, Catherine Greenhill and Nicholas Wormald, The generalised acyclic edge chromatic number of random regular graphs, Journal of Graph Theory 53 (2006), 101 - 125.

[23] Catherine Greenhill, Brendan D. McKay and Xiaoji Wang, Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, Journal of Combinatorial Theory (Series A) 113 (2006), 291 - 324.

[22] Catherine Greenhill and Oleg Pikhurko, Bounds on the generalised acyclic chromatic numbers of bounded degree graphs, Graphs and Combinatorics 21 (2005), 407 - 419.

[21] Gunnar Brinkmann, Sam Greenberg, Catherine Greenhill, Brendan D. McKay, Robin Thomas and Paul Wollan, Generation of simple quadrangulations of the sphere, Discrete Mathematics 305 (2005), 33 - 54.

[20] Catherine Greenhill, Andrzej Rucinski and Nicholas C. Wormald, Random hypergraph processes with degree restrictions, Graphs and Combinatorics 20 (2004), 319 - 332.

[19] Catherine Greenhill, Jeong Han Kim and Nicholas C. Wormald, Hamiltonian decompositions of random bipartite regular graphs, Journal of Combinatorial Theory (Series B) 90 (2004), 195 - 222.

[18] Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum, On the relative complexity of approximate counting problems, Algorithmica 38 (2003), 471 - 500.

[17] Catherine Greenhill, Andrzej Rucinski and Nicholas C. Wormald, Connectedness of the degree bounded star process, Combinatorics, Probability and Computing 12 (2003), 269 - 283.

[16] Catherine Greenhill, Svante Janson, Jeong Han Kim and Nicholas C. Wormald, Permutation pseudographs and contiguity, Combinatorics, Probability and Computing 11 (2002), 273 - 298.

[15] Martin Dyer, Catherine Greenhill and Mike Molloy, Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs, Random Structures and Algorithms, 20 (2002), 98 - 114.

[14] Martin Dyer, Gabriel Istrate, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum, Convergence of the Iterated Prisoner's Dilemma game, Combinatorics, Probability and Computing, 11 (2002), 135 - 147.

[13] Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum and Michael Mitzenmacher, An extension of path coupling and its application to the Glauber dynamics for graph colourings, SIAM Journal on Computing, 30 (2001), 1962 - 1975.

[12] Martin Dyer and Catherine Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables, Theoretical Computer Science 246 (2000), 265 - 278.

[11] Catherine Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, Computational Complexity 9 (2000), 52 - 73.

[10] Martin Dyer and Catherine Greenhill, The complexity of counting graph homomorphisms, Random Structures and Algorithms, 17 (2000), 260 - 289.
There was a small gap in a proof in this paper, which Leslie Goldberg pointed out to us. This gap is corrected here:
Martin Dyer and Catherine Greenhill, Corrigendum: The complexity of counting graph homomorphisms, Random Structures and Algorithms 25 (2004), 346 - 352.

[9] Martin Dyer and Catherine Greenhill, On Markov chains for independent sets, Journal of Algorithms 35 (2000), 17 - 49.

[8] Catherine Greenhill, An algorithm for recognising the exterior square of a multiset, LMS Journal of Computation and Mathematics 3 (2000), 96 - 116.

[7] Martin Dyer and Catherine Greenhill, Random walks on combinatorial objects, in Surveys in Combinatorics 1999 (J. D. Lamb and D A. Preece, eds.), London Mathematical Society Lecture Note Series vol. 267, Cambridge University Press, Cambridge, 1999, pp. 101 - 136.

[6] Catherine Greenhill, An algorithm for recognising the exterior square of a matrix, Linear and Multilinear Algebra 46 (1999), 213 - 244.

[5] Russ Bubley, Martin Dyer, Catherine Greenhill and Mark Jerrum, On approximately counting colourings of small degree graphs, SIAM Journal on Computing 29 (1999), 387 - 400.

[4] Martin Dyer and Catherine Greenhill, A more rapidly mixing Markov chain for graph colourings, Random Structures and Algorithms 13 (1998), 285 - 317.

[3] Catherine S. Greenhill, Theoretical and experimental comparison of efficiency of finite field extensions, Journal of Symbolic Computation 20 (1995), 419 - 429.

[2] Catherine Suzanne Greenhill and Anne Penfold Street, "Smallest defining sets of small t-designs and relations to the Petersen graph", Utilitas Mathematica 48 (1995), 5 - 31.

[1] Catherine Suzanne Greenhill, "An algorithm for finding smallest defining sets of t-designs", Journal of Combinatorial Mathematics and Combinatorial Computing 14 (1993), 39 - 60.

Conference Papers

[6] Colin Cooper, Martin Dyer and Catherine Greenhill, "Sampling regular graphs and a peer-to-peer network", in 16th Annual ACM-SIAM Symposium on Discrete Algorithms, New York-Philadelphia (2005), pp. 980 - 988.

[5] Martin Dyer and Catherine Greenhill, "The complexity of counting graph homomorphisms (Extended abstract)", in The 11th Annual ACM-SIAM Symposium on Discrete Algorithms, New York-Philadelphia (2000), pp. 246 - 255.

[4] Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum and Michael Mitzenmacher, "An extension of path coupling and its application to the Glauber dynamics for graph colourings (Extended abstract)", in The 11th Annual ACM-SIAM Symposium on Discrete Algorithms , New York-Philadelphia (2000), pp. 616 - 624.

[3] Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum, "On the relative complexity of approximate counting problems", in The 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Springer-Verlag Lecture Notes in Computer Science vol. 1913, Springer-Verlag, Berlin, 2000, pp. 108 - 119.

[2] Martin Dyer and Catherine Greenhill, "A genuinely polynomial-time Markov chain for sampling two-rowed contingency tables", in 25th International Colloquium on Automata, Languages and Programming, EATCS, Aalborg, Denmark (1998), pp. 339 - 350.

[1] Russ Bubley, Martin Dyer and Catherine Greenhill, "Beating the $2\Delta$ bound for approximately counting colourings: a computer-assisted proof of rapid mixing", in The 9th Annual ACM-SIAM Symposium on Discrete Algorithms, New York-Philadelphia (1998), pp. 355 - 363.

Edited books

Richard Brak, Omar Foda, Catherine Greenhill, Tony Guttmann and Aleksander Owczarek (eds.), Proceedings of FPSAC 2002, The University of Melbourne, Melbourne, 2002 (ISBN: 0 7340 2215 8).

Miscellaneous

Two articles for Parabola 41 (2005), for their issue dedicated to George Szekeres. (Parabola is a mathematical magazine for NSW schools.) The articles were "The cycle double cover conjecture" and "Ramsey Numbers". Also wrote a commentary on two "Unsolved Problems" which George Szekeres had described to Parabola readers in very early issues.

Article on "The cycle double cover conjecture" for the Australian Mathematical Society Gazette 32 (2005), as part of their series on "Millenium Problems".

Book review for the Australian Mathematical Society Gazette 31 (2004). (Reviewed the book "Combinatorics and Graph Theory" by Harris, Hirst and Mossinghoff, Springer, New York, 2000.)