David Galvin's Research

My research is in discrete probability, combinatorics and graph theory; in particular, extremal enumerative problems, set partitions, and the applications of combinatorial ideas to the study of phase transitions in statistical physics models and long-range correlations in discrete random structures. You can find a 2019 summary of my recent research here. This page contains links to the journal versions of all my papers, or to the arXiv version (if available) if the paper has not yet appeared in a journal, or is not intended for journal publication.

Publications

    Unsubmitted

  1. Trees with non log-concave independent set sequences, arXived

    2. Submitted

  2. Counting independent sets in regular graphs with bounded independence number (with P. Marmorino), arXived
  3. Independent set sequence of some linear hypertrees (with C. Sharpe), arXived
  4. The domination polynomial of powers of paths and cycles (with Y. Zhang), arXived

    5. 2024

  5. Generalized Tuza's conjecture for random hypergraphs (with A. Basit), SIAM Journal on Discrete Mathematics 38 (2024), 2005-2288
  6. Reciprocals of thinned exponential series (with J. Engbers and C. Smyth), Australasian Journal of Combinatorics 89 (2024), 61-96
  7. On the zeroes of hypergraph independence polynomials (with G. McKinley, W. Perkins, M. Sarantis and P. Tetali), Combinatorics, Probability and Computing 33 (2024), 65-84

    8. 2023

  8. Totally non-negativity of a family of change-of-basis matrices (with Y. Zhang), Linear Algebra and its Applications 676 (2023), 88-103.

    9. 2022

  9. Enumerating Threshold Graphs and Some Related Graph Classes (with G. Wesley and B. Zacovic), Journal of Integer Sequences 25 (2022), Article 22.2.7
  10. Independent set and matching permutations (with T. Ball, C. Hyry and K. Weingartner), Journal of Graph Theory 99 (2022), 40-57.

    11. 2021

  11. On the independent set sequence of a tree (with A. Basit), Electronic Journal of Combinatorics 28 (2021), Article P3.23.

    12. 2020

  12. Cutting lemma and Zarankiewicz's problem in distal structures (with A. Chernikov and S. Starchenko), Selecta Mathematica (New Series), 26 (2020), article 25.
  13. Total non-negativity of some combinatorial matrices (with A. Pacurar), Journal of Combinatorial Theory Series A 172 (2020), Article 105179.

    14. 2019

  14. Phase Coexistence for the Hard-Core Model on Z^2 (with A. Blanca, Y. Chen, D. Randall and P. Tetali), Combinatorics, Probability and Computing, 28 (2019), 1-22. . The data sets used in this paper are available here
  15. The game of plates and olives (with T. Carroll), Electronic Journal of Combinatorics 26 (2019), P1.18.
  16. Restricted Stirling and Lah number matrices and their inverses (with J. Engbers and C. Smyth), Journal of Combinatorial Theory Series A 161 (2019), 271-298.
  17. Independent sets in the discrete hypercube, arXiv-only expository article.

    18. 2018

  18. The independent set sequence of some families of trees (with J. Hilyard), Australasian Journal of Combinatorics 70 (2018), 236-252.

    19. 2017

  19. Extremal H-colorings of trees and 2-connected graphs (with J. Engbers), Journal of Combinatorial Theory Series B 122 (2017), 800-814.

    20. 2016

  20. Guest editors' foreword (with D. Chakrabarty), Theory of Computing 12 (2016), Article 8 (Special issue: APPROX-RANDOM 2014)
  21. On the independence ratio of distance graphs (with J. Carraher, S. Hartke, J. Radcliffe and D. Stolee), Discrete Mathematics 339 (2016), 3058-3072.
  22. Asymptotic normality of some graph sequences, Graphs and Combinatorics 32 (2016), 639-647.

    23. 2015

  23. Phase coexistence and torpid mixing in the 3-coloring model on Z^d (with J. Kahn, D. Randall and G. Sorkin), SIAM Journal of Discrete Mathematics 29 (2015), 1223-1244.
  24. Counting colorings of a regular graph, Graphs and Combinatorics 31 (2015), 629--638.
  25. Combinatorially interpreting generalized Stirling numbers (with J. Engbers and J. Hilyard), European Journal of Combinatorics 43 (2015), 32--54.

    26. 2014

  26. Three tutorial lectures on entropy and counting, (notes prepared to accompany a series of tutorial lectures given at the 1st Lake Michigan Workshop on Combinatorics and Graph Theory, Western Michigan University, March 15--16 2014), arXiv-only expository article.
  27. Counting independent sets of a fixed size in graphs with given minimum degree (with J. Engbers), Journal of Graph Theory 76 (2014), 149--168.

    28. 2013

  28. Phase Coexistence and Slow Mixing for the Hard-Core Model on Z^2 (with A. Blanca, D. Randall and P. Tetali), Lecture Notes in Computer Science 8096 (Proceedings of APPROX/RANDOM 2013) (2013), 379--394. The data sets used in this paper are available here
  29. Stirling numbers of forest and cycles (with Do Trong Thanh), Electronic Journal of Combinatorics 20 (2013), #P73.
  30. Maximizing H-colorings of a regular graph, Journal of Graph Theory 73 (2013), 66--84.

    31. 2012

  31. H-coloring tori (with J. Engbers), Journal of Combinatorial Theory Series B 102 (2012), 1110--1133.
  32. The independent set sequence of regular bipartite graphs, Discrete Mathematics 312 (2012), 2881--2892.
  33. H-colouring bipartite graphs (with John Engbers), Journal of Combinatorial Theory Series B 102 (2012), 726--742.
  34. Reverse Mathematics and infinite traceable graphs (with P. Cholak and R. Solomon), Mathematical Logic Quarterly 58 (2012), 18--28.

    35. 2011

  35. Two problems on independent sets in graphs, Discrete Mathematics 311 (2011), 2105--2112.
  36. The multi-state hard core model on a regular tree (with Fabio Martinelli, Kavita Ramanan and Prasad Tetali), SIAM Journal of Discrete Mathematics 25 (2011), 894--916.
  37. The number of independent sets in a graph with small maximum degree (with Yufei Zhao), Graphs and Combinatorics 27 (2011), 177--186. The java programs used in this paper (source files, compiled programs and documentation) are available here in a compressed (zipped) folder.
  38. A threshold phenomenon for random independent sets in the discrete hypercube, Combinatorics, Probability and Computing 20 (2011), 27--51.

    39. 2009

  39. An upper bound for the number of independent sets in regular graphs, Discrete Mathematics 309 (2009), 6635--6640.
  40. Matchings and Independent Sets of a Fixed Size in Regular Graphs (with Teena Carroll and Prasad Tetali), Journal of Combinatorial Theory Series A 116 (2009), 1219--1227).

    41. 2008

  41. Sampling independent sets in the discrete torus, Random Structures and Algorithms 33 (2008), 356--376.

    42. 2007

  42. Sampling 3-colourings of regular bipartite graphs, Electronic Journal of Probability 12 (2007), 481--497.
  43. Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus (with Dana Randall), Proceedings of the Eighteenth Annual ACM--SIAM Symposium on Discrete Algorithms (2007), 376--384

    44. 2006

  44. Bounding the partition function of spin systems, Electronic Journal of Combinatorics 13 (2006), #R72
  45. Slow mixing of Glauber Dynamics for the hard-core model on regular bipartite graphs (with Prasad Tetali), Random Structures and Algorithms 28 (2006) 427--443.
  46. Global connectivity from local geometric constraints for sensor network with various wireless footprints (with Raissa D'Souza, Cris Moore and Dana Randall), Proceedings of the Fifth International Conference on Information Processing in Sensor Networks (2006), 19--26.

    47. 2004

  47. On weighted graph homomorphisms (with Prasad Tetali), DIMACS series in discrete mathematics and theoretical computer science 63 (Graphs, Morphisms and Statistical Physics) (2004), 97--104 (scanned copy).
  48. On phase transition in the hard-core model on Z^d (with Jeff Kahn), Combinatorics, Probability and Computing 13 (2004), 137--164.
  49. Slow mixing of the Glauber Dynamics for the hard-core model on the Hamming cube (with Prasad Tetali), Proceedings of the Fifteenth Annual ACM--SIAM Symposium on Discrete Algorithms (2004), 459--460.
  50. Entropy and graph homomorphisms, Oberwolfach reports 1 (2004), 30--32.

    51. 2003

  51. On homomorphisms from the Hamming cube to Z, Israel Journal of Mathematics 138 (2003), 189--213 (the figures in the journal version were not scanned correctly).

    52. 2002

  52. Two problems involving the notion of phase transition, ProQuest Dissertations and Theses, Ph.D. thesis

Miscellaneous other papers

  1. Ramanujan Graphs (Essay for Part III of Mathematical Tripos, University of Cambridge, June 1996)
  2. [4]^2 Tic-Tac-Toe is a draw
  3. Erdos's proof of Bertrand's postulate (an exposition of Erdos's elementary proof that there is always a prime between n and 2n)
  4. Ultrafilters, with applications to analysis, social choice and combinatorics (an introduction to the basics of ultrafilters, with some applications)
  5. A topological approach to evasiveness (an introduction to the use of topological ideas in the study of evasive properties, based on a paper by Kahn, Saks and Sturtevant)
  6. Bregman's theorem and extensions (an exposition of Radhakrishnan's entropy proof of Bregman's theorem, and some results and conjectures around the theorem)

Back to my home page