Professor Catherine Greenhill

Professor

D.Phil., University of Oxford, 1996.
M.Sc. (Research) in Combinatorics, University of Queensland, 1992.
B.Sc. (Hons) in Pure Mathematics, University of Queensland, 1991.

Science

School of Mathematics & Statistics

I started my academic career as an undergraduate at the University of Queensland, before obtaining my doctorate from the University of Oxford (1992). I held postdoctoral positions at the University of Leeds and at the University of Melbourne, before joining ��¼� in 2002. Today I am a Professor and head of the Combinatorics group in the School of Mathematics and Statistics, ��¼� Sydney. My research interests lie in asymptotic, probabilistic and algorithmic combinatorics. I was elected as a Fellow of the Australian Academy of Science in 2022. My work lies at the interface between discrete mathematics, theoretical computer science and probability, and has been applied by researchers in various areas including physics, computer science and statistics.

Phone

9385 7105

E-mail

c.greenhill@unsw.edu.au

Location

School of Mathematics and Statistics ��¼� Sydney NSW 2052, AUSTRALIA The Red Centre Room 5105

Books | 2002

Greenhill CS, 2002, Proceedings of FPSAC 2002, Brak R; Foda O; Greenhill C; Guttmann T; Owczarek A, (eds.), The University of Melbourne, Melbourne
Book Chapters | 2021

Greenhill C, 2021, 'Generating Graphs Randomly', in Surveys in Combinatorics 2021,

Book Chapters | 2013

Bright DA; Greenhill C; Levenkova N, 2013, 'Dismantling criminal networks: Can node attributes play a role?', in Crime and Networks, pp. 148 - 162,

Book Chapters | 2013

Bright DA; Greenhill C; Levenkova N, 2013, 'Dismantling criminal networks: can node attributes play a role?', in Morselli C (ed.), Crime and Networks, Routledge, pp. 148 - 162,

Book Chapters | 1999

Dyer M; Greenhill C, 1999, 'Random walks on combinatorial objects', in Lamb JD; Preece DA; Preece DA (ed.), Surveys in Combinatorics, Cambridge University Press, Cambridge, pp. 101 - 136
Journal articles | 2025

Pitman A; Saribatir E; Greenhill C; Green S; Pitman S, 2025, 'Assessing the risk of climate change to a business', ,

Journal articles | 2024

Pitman AJ; Saribatir E; Greenhill C; Green S; Pitman SJ; Fiedler T, 2024, 'Linking physical climate risk with mandatory business risk disclosure requirements', Environmental Research Letters, 19,

Journal articles | 2023

Greenhill C; Isaev M; Makai T; McKay BD, 2023, 'Degree sequences of sufficiently dense random uniform hypergraphs', Combinatorics Probability and Computing, 32, pp. 183 - 224,

Journal articles | 2023

Greenhill C; Mans B; Pourmiri A, 2023, 'Balanced allocation on hypergraphs', Journal of Computer and System Sciences, 138,

Journal articles | 2022

Ayre P; Coja-Oghlan A; Greenhill C, 2022, 'Lower Bounds on the Chromatic Number of Random Graphs', Combinatorica, 42, pp. 617 - 658,

Journal articles | 2022

Erdős PL; Greenhill C; Mezei TR; Miklós I; Soltész D; Soukup L, 2022, 'The mixing time of switch Markov chains: A unified approach', European Journal of Combinatorics, 99,

Journal articles | 2022

Greenhill C, 2022, 'Spanning trees in random regular uniform hypergraphs', Combinatorics, Probability and Computing, 31, pp. 29 - 53,

Journal articles | 2021

Aldosari HS; Greenhill C, 2021, 'The average number of spanning hypertrees in sparse uniform hypergraphs', Discrete Mathematics, 344, pp. 112192,

Journal articles | 2021

Chen C; Greenhill C, 2021, 'Threshold functions for substructures in random subsets of finite vector spaces', JOURNAL OF COMBINATORICS, 12, pp. 157 - 183

Journal articles | 2021

Chen C; Greenhill C, 2021, 'Threshold functions for substructures in random subsets of finite vector spaces', Journal of Combinatorics, 12, pp. 157 - 183,

Journal articles | 2021

Dyer M; Greenhill C; Kleer P; Ross J; Stougie L, 2021, 'Sampling hypergraphs with given degrees', Discrete Mathematics, 344, pp. 112566,

Journal articles | 2021

Dyer M; Greenhill C; Müller H, 2021, 'Counting independent sets in graphs with bounded bipartite pathwidth', Random Structures and Algorithms, 59, pp. 204 - 237,

Journal articles | 2021

Gao P; Greenhill C, 2021, 'Mixing time of the switch Markov chain and stable degree sequences', Discrete Applied Mathematics, 291, pp. 143 - 162,

Journal articles | 2021

Greenhill C; Isaev M; McKay BD, 2021, 'Subgraph counts for dense random graphs with specified degrees', Combinatorics Probability and Computing, 30, pp. 460 - 497,

Journal articles | 2020

Altman D; Greenhill C; Isaev M; Ramadurai R, 2020, 'A threshold result for loose Hamiltonicity in random regular uniform hypergraphs', Journal of Combinatorial Theory Series B, 142, pp. 307 - 373,

Journal articles | 2019

Aldosari HS; Greenhill C, 2019, 'Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges', European Journal of Combinatorics, 77, pp. 68 - 77,

Journal articles | 2019

Ayre P; Coja-Oghlan A; Greenhill C, 2019, 'Hypergraph coloring up to condensation', Random Structures and Algorithms, 54, pp. 615 - 652,

Journal articles | 2019

Ayre P; Greenhill C, 2019, 'Rigid colorings of hypergraphs and contiguity', SIAM Journal on Discrete Mathematics, 33, pp. 1575 - 1606,

Journal articles | 2019

Cooper C; Dyer M; Greenhill C; Handley A, 2019, 'The flip Markov chain for connected regular graphs', Discrete Applied Mathematics, 254, pp. 56 - 79,

Journal articles | 2019

Cooper C; Dyer M; Greenhill C, 2019, 'Triangle-creation processes on cubic graphs', ,

Journal articles | 2019

Dyer M; Greenhill C; Müller H, 2019, 'Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth', Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, 11789 LNCS, pp. 298 - 310,

Journal articles | 2019

Erdős PL; Greenhill CS; Mezei TR; Miklós I; Soltész D; Soukup L, 2019, 'Mixing time of the swap Markov chain and P-stability', Acta Mathematica Universitatis Comenianae, 88, pp. 659 - 665

Journal articles | 2019

Gao P; Greenhill C, 2019, 'Uniform generation of spanning regular subgraphs of a dense graph', Electronic Journal of Combinatorics, 26,

Journal articles | 2018

Greenhill C; Sfragara M, 2018, 'The switch Markov chain for sampling irregular graphs and digraphs', Theoretical Computer Science, 719, pp. 1 - 20,

Journal articles | 2017

Bright D; Greenhill C; Britz T; Ritter A; Morselli C, 2017, 'Criminal network vulnerabilities and adaptations', Global Crime, 18, pp. 424 - 441,

Journal articles | 2017

Greenhill C; Isaev M; Kwan M; McKay BD, 2017, 'The average number of spanning trees in sparse graphs with given degrees', European Journal of Combinatorics, 63, pp. 6 - 25,

Journal articles | 2016

Blinovsky V; Greenhill C, 2016, 'Asymptotic enumeration of sparse uniform hypergraphs with given degrees', European Journal of Combinatorics, 51, pp. 287 - 296,

Journal articles | 2016

Blinovsky V; Greenhill C, 2016, 'Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees', ELECTRONIC JOURNAL OF COMBINATORICS, 23

Journal articles | 2015

Bright DA; Greenhill C; Reynolds M; Ritter A; Morselli C, 2015, '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, pp. 262 - 278,

Journal articles | 2015

Bright DA; Greenhill C; Ritter A; Morselli C, 2015, 'Networks within networks: using multiple link types to examine network structure and identify key actors in a drug trafficking operation', Global Crime, 16, pp. 219 - 237,

Journal articles | 2015

Dyer M; Frieze A; Greenhill C, 2015, 'On the chromatic number of a random hypergraph', Journal of Combinatorial Theory Series B, 113, pp. 68 - 122,

Journal articles | 2014

Bordewich M; Greenhill C; Patel V, 2014, 'Mixing of the Glauber dynamics for the ferromagnetic Potts model', Random Structures & Algorithms, pp. n/a - n/a,

Journal articles | 2014

Dyer M; Greenhill C; Ullrich M, 2014, 'Structure and eigenvalues of heat-bath Markov chains', Linear Algebra and Its Applications, 454, pp. 57 - 71,

Journal articles | 2014

Greenhill C; Kwan M; Wind D, 2014, 'On the number of spanning trees in random regular graphs', Electronic Journal of Combinatorics, 21,

Journal articles | 2013

Greenhill C; Mckay BD, 2013, 'Asymptotic enumeration of sparse multigraphs with given degrees', SIAM Journal on Discrete Mathematics, 27, pp. 2064 - 2089,

Journal articles | 2012

Cooper C; Dyer M; Greenhill C, 2012, 'Corrigendum: Sampling regular graphs and a peer-to-peer network', Corrigendum: Sampling regular graphs and a peer-to-peer network,

Journal articles | 2012

Greenhill CS; McKay BD, 2012, 'Counting loopy graphs with given degrees', Linear Algebra and its Applications, 436, pp. 901 - 926,

Journal articles | 2011

Greenhill CS, 2011, 'A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs', Electronic Journal of Combinatorics, 18, pp. #234 (49pp)

Journal articles | 2010

Canfield ER; Gao Z; Greenhill CS; McKay BD; Robinson RW, 2010, 'Asymptotic enumeration of correlation-immune boolean functions', Cryptography and Communications, 2, pp. 111 - 126

Journal articles | 2010

Greenhill CS; Janson S; Rucinski A, 2010, 'On the number of perfect matchings in random lifts', Combinatorics Probability and Computing, 19, pp. 791 - 817,

Journal articles | 2009

Greenhill CS; McKay BD, 2009, 'Random dense bipartite graphs and directed graphs with specified degrees', Random Structures and Algorithms, 35, pp. 222 - 249

Journal articles | 2008

Canfield E; Greenhill CS; McKay BD, 2008, 'Asymptoic enumeration of dense 0-1 matrices with specified line sums', Journal of Combinatorial Theory Series A, 115, pp. 32 - 66

Journal articles | 2008

Cavenagh N; Greenhill CS; Wanless IM, 2008, 'The cycle structure of two rows in a random Latin square', Random Structures and Algorithms, 33, pp. 286 - 309

Journal articles | 2008

Greenhill CS; Holt F; Wormald NC, 2008, 'Expansion properties of a random regular graph after random vertex deletions', European Journal of Combinatorics, 29, pp. 1139 - 1150,

Journal articles | 2008

Greenhill CS; McKay BD, 2008, 'Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums', Advances in Applied Mathematics, 41, pp. 459 - 481

Journal articles | 2007

Cooper C; Dyer M; Greenhill CS, 2007, 'Sampling regular graphs and a peer-to-peer network', Combinatorics Probability and Computing, 16, pp. 557 - 593

Journal articles | 2006

Gerke S; Greenhill CS; Wormald NC, 2006, 'The generalized acyclic edge chromatic number of random regular graphs', Journal of Graph Theory, 53, pp. 101 - 125

Journal articles | 2006

Greenhill CS; McKay BD; Wang XJ, 2006, 'Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums', Journal of Combinatorial Theory Series A, 113, pp. 291 - 324

Journal articles | 2006

Greenhill CS; Rucinski A, 2006, 'Neighbour-distinguishing edge colourings of random regular graphs', Electronic Journal of Combinatorics, 13

Journal articles | 2005

Brinkmann G; Greenberg S; Greenhill CS; McKay BD; Thomas R; Wollan P, 2005, 'Generation of simple quadrangulations of the sphere', Discrete Mathematics, 305, pp. 33 - 54

Journal articles | 2005

Cooper C; Dyer M; Greenhill C, 2005, 'Sampling regular graphs and a peer-to-peer network', Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 980 - 988

Journal articles | 2005

Greenhill CS; Pikhurko O, 2005, 'Bounds on the generalised acyclic chronatic numbers of bounded degree graphs', Graphs and Combinatorics, 21, pp. 407 - 419

Journal articles | 2004

Greenhill C; Kim JH; Wormald NC, 2004, 'Hamiltonian decompositions of random bipartite regular graphs', Journal of Combinatorial Theory Series B, 90, pp. 195 - 222,

Journal articles | 2004

Greenhill CS; Dyer M, 2004, 'Corrigendum: The complexity of counting graph homomorphisms (Vol 17, pg 260, 2000)', Random Structures and Algorithms, 25, pp. 346 - 352

Journal articles | 2004

Greenhill CS; Rucinski A; Wormald NC, 2004, 'Random hypergraph processes with degree restrictions', Graphs and Combinatorics, 20, pp. 319 - 332

Journal articles | 2003

Dyer M; Goldberg LA; Greenhill C; Jerrum M, 2003, 'The relative complexity of approximate counting problems', Algorithmica New York, 38, pp. 471 - 500,

Journal articles | 2003

Greenhill C; Ruciski A; Wormald N, 2003, 'Connectedness of the Degree Bounded Star Process', Combinatorics, Probability and Computing, 12, pp. 269 - 283,

Journal articles | 2002

Dyer M; Goldberg LA; Greenhill C; Istrate G; Jerrum M, 2002, 'Convergence of the iterated prisoner's dilemma game', Combinatorics Probability and Computing, 11, pp. 135 - 147,

Journal articles | 2002

Dyer M; Greenhill C; Molloy M, 2002, 'Very Rapid Mixing of the Glauber Dynamics for Proper Colorings on Bounded-Degree Graphs', Random Structures and Algorithms, 20, pp. 98 - 114,

Journal articles | 2002

Greenhill C; Janson S; Kim J; Wormald N, 2002, 'Permutation Pseudographs and Contiguity', Combinatorics, Probability and Computing, 11,

Journal articles | 2000

Dyer M; Goldberg LA; Greenhill C; Jerrum M; Mitzenmacher M, 2000, 'Extension of path coupling and its application to the Glauber dynamics for graph colourings', Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 616 - 624

Journal articles | 2000

Dyer M; Greenhill C, 2000, 'Complexity of counting graph homomorphisms', Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 246 - 255

Journal articles | 2000

Dyer M; Greenhill C, 2000, 'On Markov Chains for Independent Sets', Journal of Algorithms, 35, pp. 17 - 49,

Journal articles | 2000

Dyer M; Greenhill C, 2000, 'Polynomial-time counting and sampling of two-rowed contingency tables', Theoretical Computer Science, 246, pp. 265 - 278,

Journal articles | 2000

Dyer M; Greenhill C, 2000, 'The complexity of counting graph homomorphisms', Random Structures and Algorithms, 17, pp. 260 - 289, http://dx.doi.org/10.1002/1098-2418(200010/12)17:3/4<260::aid-rsa5>3.0.co;2-w

Journal articles | 2000

Dyer M; Leslie Goldberg A; Greenhill C; Jerrum M; Mitzenmacheru M, 2000, 'An extension of path coupling and its application to the glauber dynamics for graph colorings', SIAM Journal on Computing, 30, pp. 1962 - 1975,

Journal articles | 2000

Greenhill C, 2000, 'The complexity of counting colourings and independent sets in sparse graphs and hypergraphs', Computational Complexity, 9, pp. 52 - 72,

Journal articles | 1999

Bubley R; Dyer M; Greenhill C; Jerrum M, 1999, 'On approximately counting colorings of small degree graphs', SIAM Journal on Computing, 29, pp. 387 - 400,

Journal articles | 1999

Greenhill C, 1999, 'An algorithm for recognising the exterior square of a matrix', Linear and Multilinear Algebra, 46, pp. 213 - 244,

Journal articles | 1998

Dyer M; Greenhill C, 1998, 'A genuinely polynomial-time algorithm for sampling two-rowed contingency tables', , pp. 339 - 350,

Journal articles | 1998

Dyer M; Greenhill C, 1998, 'A more rapidly mixing Markov chain for graph colorings', Random Structures and Algorithms, 13, pp. 285 - 317, http://dx.doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<285::aid-rsa6>3.0.co;2-r

Journal articles | 1995

Greenhill CS; Street AP, 1995, 'Smallest defining sets of some small t-designs and relations to the Petersen graph', Utilitas Mathematica, 48, pp. 5 - 31

Journal articles | 1995

Greenhill CS, 1995, 'Theoretical and Experimental Comparison of Efficiency of Finite Field Extensions', Journal of Symbolic Computation, 20, pp. 419 - 429,

Journal articles | 1993

Greenhill CS, 1993, 'An algorithm for finding smallest defining sets of t-designs', Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 39 - 60
Working Papers | 2021

Greenhill C; Isaev M; Makai T; McKay BD, 2021, Degree sequences of sufficiently dense random uniform hypergraphs, ,
Preprints | 2025

Chatterjee A; Coja-Oghlan A; Greenhill C; Pfenninger V; Rolvien M; Zakharov P; Zampetakis K, 2025, The random $k$-SAT Gibbs uniqueness threshold revisited,

Preprints | 2024

Greenhill C; Makai T, 2024, Enumeration of dihypergraphs with specified degrees and edge types,

Preprints | 2023

Cooper C; Dyer M; Greenhill C, 2023, Triangle processes on graphs with given degree sequence,

Preprints | 2023

Delcourt M; Greenhill C; Isaev M; Lidický B; Postle L, 2023, Decomposing random regular graphs into stars,

Preprints | 2022

Greenhill C, 2022, Generating graphs randomly, ,

Conference Papers | 2021

Cooper C; Dyer M; Greenhill C, 2021, 'A Triangle Process on Regular Graphs', in Flocchini P; Moura L (ed.), Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, Springer Nature, ELECTR NETWORK, pp. 310 - 323, presented at 32nd International Workshop on Combinatorial Algorithms (IWOCA), ELECTR NETWORK, 05 July 2021 - 07 July 2021,

Preprints | 2020

Dyer M; Greenhill C; Kleer P;

���������¼�

Follow

Professor Catherine Greenhill

Follow me

��¼�