CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Tom Bohman, Alexander M. Knaster Professor, Department Head
Ph.D., Rutgers University
Office: Wean Hall 6113
Phone: 412-268-2545
Personal web site


My field of research is extremal and probabilistic combinatorics, and I work on discrete mathematical problems inspired by a diverse collection of perspectives. These include mathematical disciplines as well as information theory (which has a very strong connection with extremal set theory), statistical physics and theoretical computer science. Recently, I have been interested in the Shannon capacities of odd cycles, 'guided' versions of the standard random graph model, randomized network algorithms, list-coloring problems for graphs, and hypergraph discrepancy.

Selected Publications:

  • Avoiding a giant component (with A. Frieze), Random Structures and Algorithms, to appear.
  • Six lonely runners (with R. Holzman and D. Kleitman), Electronic Journal of Combinatorics, to appear.
  • On partitions of discrete boxes (with N. Alon, R. Holzman and D. Kleitman), Discrete Mathematics, to appear.
  • Random threshold growth dynamics (with J. Gravner), Random Structures and Algorithms 15 (1999), 93111.
  • Discrete threshold growth dynamics are omnivorous for box neighborhoods, Transactions of the AMS 351 (1999), 947983.
  • A sum packing problem of Erdos and the Conway Guy Sequence, Proceedings of the AMS 124 (1996), 36273636.