David Galvin's Research

IN PROCESS 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 process

  1. Matchings and Independent Sets of a Fixed Size in Regular Graphs, PDF
    (with Teena Carroll and Prasad Tetali, submitted)
  2. A threshold phenomenon for random independent sets in the discrete hypercube, PDF
    (submitted)
  3. Independent sets of a fixed size in the discrete hypercube, PDF
    (in preparation, July 16 2008 revision)

Papers appeared/appearing

  1. Sampling independent sets in the discrete torus, PDF
    (to appear in Random Structures and Algorithms)
  2. Sampling 3-colourings of regular bipartite graphs, PDF
    (Electronic Journal of Probability 12 (2007) 481-497)
  3. 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)
  4. Bounding the partition function of spin systems, PDF
    (Electronic Journal of Combinatorics 13 No. 1 (2006) R72)
  5. 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)
  6. 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)
  7. 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)
  8. On phase transition in the hard-core model on Z^d, PDF
    (with Jeff Kahn, Combinatorics, Probability and Computing 13 (2004) 137-164)
  9. Slow mixing of the Glauber Dynamics for the hard-core model on the Hamming cube (short summary), PDF
    (with Prasad Tetali, Proceedings of the Fifteenth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA 2004), 459-460)
  10. On homomorphisms from the Hamming cube to Z, PDF
    (Israel Journal of Mathematics 138 (2003) 189-213)
  11. Two problems involving the notion of phase transition, PDF
    (PhD thesis written under the direction of Jeff Kahn)

Miscellaneous papers

  1. Independent sets in the discrete hypercube, PDF
    (a exposition of A. A. Sapozhenko's proof that the number of independent sets in the discrete hypercube Qd is asympototically 2e1/222d-1)
  2. [4]^2 Tic-Tac-Toe is a draw, PDF
  3. Erdos's proof of Bertrand's postulate, PDF
    (a exposition of Erdos's elementary proof that there is always a prime between n and 2n)

Back to my home page