David Galvin's Research

IN PREPARATION SUBMITTED APPEARED/APPEARING MISCELLANEOUS

My research is in discrete probability, combinatorics and graph theory; in particular, applications of combinatorial ideas to the study of phase transitions in statistical mechanics, algorithms in theoretical computer science and performance analysis of communications networks

Papers in preparation

  1. Phase coexistence and torpid mixing in the 3-coloring model on Z^d,
    (with J. Kahn, D. Randall and G. Sorkin)
  2. Phase coexistence for the hard-core model on Z^2,
    (with D. Randall and P. Tetali)
  3. Counting colorings of a regular graph, PDF

Papers submitted

  1. Counting independent sets of a fixed size in graphs with given minimum degree, PDF
    (with J. Engbers)
  2. Stirling numbers of forest and cycles, PDF
    (with Do Trong Thanh)
  3. The independent set sequence of regular bipartite graphs, PDF

Papers appeared/appearing

  1. H-coloring tori, PDF
    (with J. Engbers), to appear in Journal of Combinatorial Theory Series B
  2. Maximizing H-colorings of regular graphs, PDF
    to appear in Journal of Graph Theory
  3. H-colouring bipartite graphs, PDF
    (with John Engbers), Journal of Combinatorial Theory Series B 102 (2012) 726–742
  4. Reverse Mathematics and infinite traceable graphs, PDF
    (with P. Cholak and R. Solomon), Mathematical Logic Quarterly 58 (2012) 18-28
  5. Two problems on independent sets in graphs, PDF
    (Discrete Mathematics 311 (2011) 2105-2112)
  6. The multi-state hard core model on a regular tree, PDF
    (with Fabio Martinelli, Kavita Ramanan and Prasad Tetali, SIAM Journal of Discrete Mathematics 25 (2011) 894-916)
  7. The number of independent sets in a graph with small maximum degree, PDF
    (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.
  8. A threshold phenomenon for random independent sets in the discrete hypercube, PDF
    (Combinatorics, Probability and Computing 20 (2011) 27-51)
  9. An upper bound for the number of independent sets in regular graphs, PDF
    (Discrete Mathematics 309 (2009) 6635-6640)
  10. Matchings and Independent Sets of a Fixed Size in Regular Graphs, PDF
    (with Teena Carroll and Prasad Tetali, Journal of Combinatorial Theory Series A 116 (2009) 1219-1227)
  11. Sampling independent sets in the discrete torus, PDF
    (Random Structures and Algorithms 33 No. 3 (2008) 356-376)
  12. Sampling 3-colourings of regular bipartite graphs, PDF
    (Electronic Journal of Probability 12 (2007) 481-497)
  13. Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus PDF
    (with Dana Randall, Proceedings of the Eighteenth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA 2007), 376-384)
  14. Bounding the partition function of spin systems, PDF
    (Electronic Journal of Combinatorics 13 No. 1 (2006) R72)
  15. Global connectivity from local geometric constraints for sensor network with various wireless footprints, PDF
    (with Raissa D'Souza, Cris Moore and Dana Randall, Proceedings of the Fifth International Conference on
    Information Processing in Sensor Networks     (IPSN 2006), 19-26)
  16. Slow mixing of Glauber Dynamics for the hard-core model on regular bipartite graphs, PDF
    (with Prasad Tetali, Random Structures and Algorithms 28 (2006) 427-443)
    Summary appears as
    Slow mixing of the Glauber Dynamics for the hard-core model on the Hamming cube, PDF
    (Proceedings of the Fifteenth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA 2004), 459-460)
  17. On weighted graph homomorphisms, PDF
    (with Prasad Tetali, In Graphs, Morphisms and Statistical Physics,
    DIMACS series in discrete mathematics and theoretical computer science    , J. Nestril and P. Winkler editors (2004).
    Summary appears as
    Entropy and graph homomorphisms,
    (Oberwolfach reports 1 No. 1 (2004) 30-32)
  18. On phase transition in the hard-core model on Z^d, PDF
    (with Jeff Kahn, Combinatorics, Probability and Computing 13 (2004) 137-164)
  19. On homomorphisms from the Hamming cube to Z, PDF
    (Israel Journal of Mathematics 138 (2003) 189-213)

Miscellaneous papers

  1. Two problems involving the notion of phase transition, PDF
    (PhD thesis written under the direction of Jeff Kahn, Rutgers University, October 2002)
  2. Ramanujan Graphs,
    (Essay for Part III of Mathematical Tripos, University of Cambridge, June 1996)
  3. Independent sets in the discrete hypercube, PDF
    (an exposition of A. A. Sapozhenko's asymptotic count of the number of independent sets in the discrete hypercube)
  4. [4]^2 Tic-Tac-Toe is a draw, PDF
  5. Erdos's proof of Bertrand's postulate, PDF
    (an exposition of Erdos's elementary proof that there is always a prime between n and 2n)
  6. Ultrafilters, with applications to analysis, social choice and combinatorics, PDF
    (an introduction to the basics of ultrafilters, with some applications)
  7. A topological approach to evasiveness, PDF
    (an introduction to the use of topological ideas in the study of evasive properties, based on a paper by Kahn, Saks and Sturtevant)
  8. Bregman's theorem and extensions, PDF
    (an exposition of Radhakrishnan's entropy proof of Bregman's theorem, and some results and conjectures around the theorem)

Back to my home page