Tom Bohman Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA 15213 USA Email: tbohman Telephone: 412 268 2545 Classes: Spring 2013 21-737: Probabilistic Combinatorics Links ACO Seminar Journal of Combinatorics SIAM Journal on Discrete Mathematics Advances in Applied Mathematics Julius Ashkin Teaching Award ACO Homepage Random Structures and Algorithms 2009 FriezeFest 2005

Image courtesy of Misha Lavrov

Publications

Synopses of selected papers

• Evolution of SIR epidemics on random graphs with a fixed degree sequence (with M. Picollelli) , Random Structures and Algorithms , to appear.
  
  
• On the independence numbers of the cubes of odd cycles (with R. Holzman and V. Natarajan) , submitted.
  
  
• Karp-Sipser on random graphs with a fixed degree sequence (with A. Frieze), Combinatorics, Probability and Computing, 20 (2011), 721-741.
  
  
• Ramsey games with giants (with A. Frieze, M. Krivelevich, P. Loh, B. Sudakov) , Random Structures and Algorithms, 38 (2011), 1-32.
  
  
• A note on the random greedy triangle-packing algorithm (with A. Frieze and E. Lubetzky) , Journal of Combinatorics, 1 (2010), 477-488.
  
  
• The Saturation Function of Complete Partite Graphs, (with M. Fonoberova and O. Pikhurko) , Journal of Combinatorics , 1 (2010), 149-170.
  
  
• Hypergraphs with independent neighborhoods (with D. Mubayi, O. Pikhurko and A. Frieze) , Combinatorica , 30 (2010), 277-293. .
  
  
• The early evolution of the H-free process (with P. Keevash) , Inventiones Mathematicae 181 (2010), 291--336.
  
  
• Anti-Ramsey properties of random graphs (with A. Frieze, O. Pikhurko and C. Smythe) , Journal of Combinatorial Theory B 100 (2010), 299-312.
  
  
• Coloring H-free hypergraphs (with D. Mubayi and A. Frieze) , Random Structures and Algorithms 36 (2010) 11-25.
  
  
• Hamilton cycles in 3-out (with A. Frieze) , Random Structures and Algorithms , 35 (2009) 393-417.
  
                      The program for the numerical computations.
  
  
• Erdos-Ko-Rado in Random Hypergraphs (with J. Balogh and D. Mubayi) , Combinatorics, Probability and Computing, 18 (2009) 629-646.
  
  
• Maximum independent sets in certain powers of odd cycles (with R. Holzman and V. Natarajan) Electronic Journal of Combinatorics, 16 (2009) N26.
  
  
• The Triangle-Free Process , Advances in Mathematics , 221 (2009) 1653-1677.
  
  
• The game chromatic number of random graphs (with A. Frieze and B. Sudakov), Random Structures and Algorithms, 32 (2008) 223-235.
  
  
• Product rule wins a competitive game (with A. Beveridge, A. Frieze and O. Pikhurko), Proceedings of the AMS, 135 (2007) 3061-3071.
  
  
• First order definability of trees and sparse random graphs (with A. Frieze, T. Luczak, O. Pikhurko, C. Smyth, J. Spencer and O. Verbitsky), Combinatorics, Probability and Computing, 16 (2007) 375-400.
  
  
• Creating a giant component (with D. Kravitz) , Combinatorics, Probability and Computing, 15 (2006) 489-511.
  
  
• A phase transition for avoiding a giant component (with J. H. Kim) , Random Structures and Algorithms, 28 (2006) 195-214.
  
  
• Linear versus hereditary discrepancy (with R. Holzman) , Combinatorica, 25 (2005) 39-47.
  
  
• A limit theorem for the Shannon capacities of odd cycles II, Proceedings of the AMS, 133 (2005) 537-543.
  
  
• Avoidance of a giant component in half the edge set of a random graph (with Alan Frieze and Nick Wormald), Random Structures and Algorithms, 25 (2004) 432-449.
  
                      The program for the numerical computations.
  
  
• On the irregularity strength of trees (with David Kravitz), Journal of Graph Theory, 45 (2004) 241-254.
  
  
• Adding random edges to dense graphs (with A. Frieze, M. Krivelevich and R. Martin), Random Structures and Algorithms, 24 (2004) 105-117.
  
  
• On Randomly Generated Intersecting Hypergraphs (with C.Cooper, A. Frieze, R. Martin, and M. Ruszinko), Electronic Journal of Combinatorics , 10(1) (2003) R29.
  
  
• A nontrivial lower bound on the Shannon capacities of the complements of odd cycles (with R. Holzman) IEEE Transactions on Information Theory , 49 (2003) 721-722.
  
  
• A note on G-intersecting families (with R. Martin) , Discrete Mathematics, 260 (2003) 183-188.
  
  
• A limit theorem for the shannon capacities of odd cycles I, Proceedings of the AMS , 131 (2003) 3559-3569.
  
  
• How many random edges make a dense graph Hamiltonian? (with A. Frieze and R. Martin) , Random Structures and Algorithms, 22 (2003) 33-42.
  
  
• On a list coloring conjecture of Reed (with R. Holzman) , Journal of Graph Theory, 41 (2002) 106-109.
  
  
• On partitions of discrete boxes (with N. Alon, R. Holzman and D. Kleitman) , Discrete Mathematics, 257 (2002) 255-258.
  
  
• Arc-disjoint paths in expander digraphs (with A. Frieze) , Proceedings of FOCS 2001, 558-567.
  
                      Journal Version, SIAM Journal on Computing, 32 (2003) 326-344.
  
  
• Avoiding a giant component (with A. Frieze) , Random Structures and Algorithms, 19 (2001) 75-85.
  
  
• Six lonely runners (with R. Holzman and D. Kleitman), Electronic Journal of Combinatorics, 8(2) (2001) R3.
  
  
• G-intersecting families (with A. Frieze, M. Ruszinko and L. Thoma) , Combinatorics, Probability and Computing, 10 (2001) 367-384.
  
  
• Vertex covers by edge disjoint cliques (with A. Frieze, M. Ruszinko and L. Thoma), Combinatorica, 21 (2001) 171-197.
  
  
• Min-wise independent linear permutations (with C. Cooper and A. Frieze), Electronic Journal of Combinatorics 7 (2000) R26.
  
  
• A note on sparse random graphs and cover graphs (with A. Frieze, M. Ruszinko and L. Thoma), Electronic Journal of Combinatorics, 7 (2000) R19.
  
  
• 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 construction for sets of integers with distinct subset sums, Electronic Journal of Combinatorics, 5 (1998) R3.
  
  
• A sum packing problem of Erdos and the Conway Guy Sequence, Proceedings of the AMS, 124 (1996) 3627-3636.