Tom Bohman Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213 USA Email: tbohman Telephone: 412 268 2545 Classes: Spring 2025 21-484: Graph Theory Links Random Structures & Algorithms Conference 2009 2011 2013 2015 2017 2019 2022 2023 RS&A Journal Journal of Combinatorics Advances in Applied Mathematics ACO Seminar ACO Homepage Julius Ashkin Teaching Award

Image courtesy of Misha Lavrov

Publications

Preprints available on the arXiv.


• A construction for Boolean cube Ramsey numbers (with Fei Peng), Order , to appear.
  
  
• Independent sets in hypergraphs omitting an intersection (with Xizhi Liu and Dhruv Mubayi), Random Structures & Algorithms, 61 (2022), no. 3, 493-519.
  
  
• Coprime matchings and lonely runners (with Fei Peng), Mathematika, 68 (2022), no. 3, 784-804.
  
  
• Dynamic concentration of the triangle-free process (with Peter Keevash), Random Structures & Algorithms, 58 (2021), no. 2, 221-293.
  
  
• Large girth approximate Steiner triple systems (with Lutz Warnke), Journal of the London Mathematical Society, 100 (2019), no. 3, 895-913.
  
  
• A natural barrier in random greedy hypergraph mathcing (with Patrick Bennett), Combinatorics, Probability and Computing 28 (2019), no. 6, 816-825.
  
  
• Independence number of graphs with a prescribed number of cliques (with Dhruv Mubayi), Electronic Journal of Combinatorics (2019), no. 2, Paper No. 2.25, 7pp.
  
  
• A greedy algorithm for finding a large 2-mathcing in a random cubic graph (with Deepak Bal, Patrick Bennett and Alan Frieze), Journal of Graph Theory 88 (2018), no. 3, 440-481.
  
  
• More on the bipartite decomposition of random graphs (with Noga Alon and Hao Huang), Journal of Graph Theory 84 (2017), no. 1, 45-52.
  
  
• The independent neighborhoods process (with Dhruv Mubayi and Michael Picollelli), Israel Journal of Mathematics 214 (2016), no. 1, 333-357.
  
  
• A note on the random greedy independent set algorithm (with Patrick Bennett), Random Structures & Algorithms, 49 (2016), no. 3, 479-502.
  
  
• Random triangle removal (with Alan Frieze and Eyal Lubetzky), Advances in Mathematics, 280 (2015), 379-438.
  
  
• On the independence numbers of the cubes of odd cycles (with Ron Holzman and Venkatesh Natarajan), Electronic Journal of Combinatorics , 20 (2013), P10.
  
  
• Evolution of SIR epidemics on random graphs with a fixed degree sequence (with M. Picollelli), Random Structures and Algorithms, 41 (2012), 179-214.
  
  
• Turán densities of some hypergraphs related to K_k^k+1 (with J, Balogh, B. Bollobas and Y. Zhao), SIAM Journal on Discrete Mathematics, 26 (2012), 1609-1617.
  
  
• Random greedy triangle-packing beyond the 7/4 barrier (with A. Frieze and E. Lubetzky), manuscript (2011).
  
  
• 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.