Publications
Here is a list of my submitted papers, journal papers and conference papers, plus some miscellaneous things at the end. You can download almost all of the submitted and journal papers in PDF form. There may be some differences from the final journal version.
Preprints
[56] Peter Ayre and Catherine Greenhill,
Rigid colourings of hypergraphs and contiguity,
Preprint (submitted), 2018.
arxiv:1808.04060 [math.CO]
[55] Pu Gao and Catherine Greenhill,
Uniform generation of spanning regular subgraphs of a dense graph,
Preprint (submitted), 2018.
arxiv:1807.00964 [math.CO]
[54] Haya S. Aldosari and Catherine Greenhill,
Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges,
Preprint (submitted), 2018.
arxiv:1805.04991 [math.CO]
[53] Changhao Chen and Catherine Greenhill,
Threshold functions for patterns in random subsets of finite vector spaces, Preprint (submitted), 2018.
arxiv:1805.03778 [math.CO]
[52] Catherine Greenhill, Mikhail Isaev and Brendan McKay,
Subgraph counts for dense random graphs with specified degrees,
Preprint (submitted), 2018.
arxiv:1801.09813 [math.CO]
[51] Daniel Altman, Catherine Greenhill, Mikhail Isaev and Reshma Ramadurai,
A threshold result for loose Hamiltonicity in random regular uniform hypergraphs, Preprint (submitted), 2017.
arxiv:1611.09423 [math.CO]
I would like to dedicate the above paper to all refugees and asylum seekers
who the Australian Government have
imprisoned in offshore detention on Manus Island and Nauru. Many people in offshore detention have been there
since mid-2013 (much longer than the 3 years it took myself and my co-authors to complete this paper). These are human beings: innocent men, women and children who have committed no crime. Seeking asylum is a human right. I am disgusted with successive Australian governments for their cruel policies of mandatory detention and offshore detention of people who seek our help. Australia is a signatory to the UN Refugee Convention. We should respect international law and human rights. I call on the Australian government to #CloseTheCamps #BringThemHere #SafetyForAll (3 February 2017) |
Journal papers, and the occasional book chapter
[50] Peter Ayre, Amin Coja-Oghlan and Catherine Greenhill,
Hypergraph coloring up to condensation,
Random Structures & Algorithms (to appear).
arxiv:1508.01841 [math.CO]
[49] Colin Cooper, Martin Dyer, Catherine Greenhill and Andrew Handley,
The flip Markov chain for connected regular graphs,
Discrete Applied Mathematics (to appear).
arxiv:1701.03856 [cs.DM]
[48] Catherine Greenhill and Matteo Sfragara,
The switch Markov chain for sampling irregular graphs and digraphs, Theoretical Computer Science 719 (2018), 1 - 20.
arxiv:1701.07101 [cs.DM]
[47] David A. Bright, Catherine Greenhill, Thomas Britz, Alison Ritter and Carlo Morselli, Criminal network vulnerabilities and adaptations, Global Crime 18(4) (2017), 424 - 441.
[46] Catherine Greenhill, Mikhail Isaev, Matthew Kwan and Brendan McKay,
The average number of spanning trees in sparse graphs with given degrees,
European Journal of Combinatorics 63 (2017), 6 - 25.
arxiv:1606.01586 [math.CO]
[45] Vladimir Blinovsky and Catherine Greenhill,
Asymptotic enumeration of sparse
uniform linear hypergraphs with given degrees,
Electronic Journal of Combinatorics 23(3) (2016), #P3.17.
arxiv:1409.1314 [math.CO]
[44] Vladimir Blinovsky and Catherine Greenhill,
Asymptotic enumeration of sparse
uniform hypergraphs with given degrees,
European Journal of Combinatorics 51 (2016), 287 - 296.
arxiv:1306.2012 [math.CO]
(A slight gap in one of the proofs is plugged here.)
[43] Magnus Bordewich, Catherine Greenhill and Viresh Patel,
Mixing of the Glauber dynamics for
the ferromagnetic Potts model, Random Structures & Algorithms 48 (2016), 21 - 52.
arxiv:1305.0776 [cs.DM]
[42] David A. Bright, Catherine Greenhill, Alison Ritter and Carlo Morselli, Networks within networks: Using multiple link types to examine network structure and identify key actors in a drug trafficking operation, Global Crime 16(3) (2015), 219 - 237.
[41] David A. Bright, Catherine Greenhill, Michael Reynolds, Alison Ritter and Carlo Morselli, The use of actor-level attributes and centrality measures to identify key actors: a case study of an Australian drug trafficking network, Journal of Contemporary Criminal Justice 31 (2015), 262 - 278.
[40] Martin Dyer, Alan Frieze and Catherine Greenhill,
On the chromatic number of a random hypergraph,
Journal of Combinatorial Theory (Series B) 113 (2015), 68 - 122.
arXiv:1208.0812 [cs.DM]
[39] Martin Dyer, Catherine Greenhill and Mario Ullrich,
Structure and eigenvalues of heat-bath Markov chains,
Linear Algebra and its Applications 454 (2014), 57 - 71.
arxiv:1301.4055 [math.CO]
[38] Catherine Greenhill, Matthew Kwan and David Wind,
On the number of spanning trees in random regular graphs,
Electronic Journal of Combinatorics 21(1) (2014), #P1.45.
arxiv:1309.6710 [math.CO]
[37] Catherine Greenhill and Brendan McKay,
Asymptotic enumeration of sparse multigraphs with given degrees,
SIAM Journal on Discrete Mathematics 27 (2013), 2064 - 2089.
arxiv:1303.4218 [math.CO]
[36] David A. Bright, Catherine Greenhill and Natalya Levenkova, Dismantling criminal networks: can node attributes play a role?, in Crime and Networks (C. Morselli, ed.), Criminology and Justice Studies Series, Routledge, London, 2013, pp. 148 - 162.
[35] Catherine Greenhill and Brendan D. McKay,
Counting loopy graphs with given degrees,
Linear Algebra and its Applications 436
(2012), 901 - 926.
arXiv:1103.0080 [math.CO]
[34] Catherine Greenhill,
A polynomial bound on the mixing time of a Markov chain for
sampling regular directed graphs,
Electronic Journal of Combinatorics 18(1) (2011), #P234.
arXiv:1105.0457 [math.CO]
(Note, in this paper I stated that Lemma 1.3 is new, when in fact it is precisely the result
stated on p.702 of Diaconis and Saloffe-Coste's 1993 paper "Comparison
theorems for reversible Markov chains". I sincerely apologise for this error.)
[33] Catherine Greenhill, Svante Janson and
Andrzej Ruciński,
On the number of perfect matchings in random lifts,
Combinatorics, Probability and Computing 19 (2010),
791 - 817.
arXiv:0907.0958 [math.CO]
(The Maple file
used for the calculations is also available.)
[32] E. Rodney Canfield, Zhicheng Gao, Catherine Greenhill,
Brendan D. McKay and Robert W. Robinson,
Asymptotic enumeration of correlation-immune boolean functions,
Cryptography and Communications 2 (2010), 111 - 126.
arXiv:0909.3321 [math.CO]
[31] Catherine Greenhill and Brendan D. McKay,
Random dense bipartite graphs and directed graphs with specified
degrees, Random Structures & 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 J. Cavenagh, Catherine Greenhill and Ian M. Wanless, The cycle structure of two rows in a random latin square, Random Structures & 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] E. Rodney Canfield, Catherine Greenhill and Brendan D. 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.
arXiv:1203.6111 [math.CO]
There was a technical error in the proof of one of the lemmas
in this paper, which can be corrected at the cost of an
extra factor in the mixing time of the switch chain.
The details are here:
Colin Cooper, Martin Dyer and Catherine Greenhill,
Corrigendum: Sampling regular graphs and a peer-to-peer network,
2012.
[25] Catherine Greenhill and Andrzej Ruciński, 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 Ruciński 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 Ruciński 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 & 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 & 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 & 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 & 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
[7] Catherine Greenhill, The switch Markov chain for sampling irregular graphs, in 26th Annual ACM-SIAM Symposium on Discrete Algorithms, New York-Philadelphia (2015), 1564 - 1572.
[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
An article for Parabola 51 (2015) on "Now I know: Solving logical puzzles using graphs". (Parabola is a mathematical magazine for NSW schools.)
Don't make your Markov chain lazy! See this note on
Making Markov chains less lazy which advertises
a method of Diaconis and Saloff-Coste that you should try instead.
Also available at arxiv:1203.6668 [math.CO].
An article for Parabola 47 (2011) on "Sudoku, logic and proof". (Parabola is a mathematical magazine for NSW schools.)
Two articles for Parabola 41 (2005), for their issue dedicated to George Szekeres: "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.
An article on "The cycle double cover conjecture" for the Australian Mathematical Society Gazette 32 (2005), as part of their series on "Millenium Problems".