Faculty Tom Bohman, Alexander M. Knaster Professor and Department Head
Ph.D., Rutgers University
E-mail: dept.head@math.cmu.edu
Office: Wean Hall 6204/6105
Phone: 412-268-2545
Personal web site

Research:

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), 93–111.
• Discrete threshold growth dynamics are omnivorous for box neighborhoods, Transactions of the AMS 351 (1999), 947–983.
• A sum packing problem of Erdos and the Conway Guy Sequence, Proceedings of the AMS 124 (1996), 3627–3636.