Tom Bohman

Classes: Fall 2009

21-701: Discrete Mathematics

---

Links

Random Structures and Algorithms 2009

ACO Homepage

David Griffeath's Primordial Soup Kitchen

Electronic Journal of Combinatorics

FriezeFest 2005

Publications

Synopses of selected papers

• Ramsey games with giants (with A. Frieze, M. Krivelevich, P. Loh, B. Sudakov) , submitted.
  
  
• The early evolution of the H-free process (with P. Keevash) , submitted.
  
  
• Coloring H-free hypergraphs (with D. Mubayi and A. Frieze) , submitted.
  
  
• On the independence numbers of the cubes of odd cycles (with R. Holzman and V. Natarajan) , submitted.
  
  
• Hypergraphs with independent neighborhoods (with D. Mubayi, O. Pikhurko and A. Frieze) , Combinatorica , to appear.
  
  
• Hamilton cycles in 3-out (with A. Frieze) , Random Structures and Algorithms , to appear.
  
                      The program for the numerical computations.
  
  
• Karp-Sipser on random graphs with a fixed degree sequence (with A. Frieze) , submitted.
  
  
• Anti-Ramsey properties of random graphs (with A. Frieze, O. Pikhurko and C. Smythe) , submitted.
  
  
• Erdos-Ko-Rado in Random Hypergraphs (with J. Balogh and D. Mubayi) , Combinatorics, Probability and Computing, 18 (2009) 629-646.
  
  
• Maximum independdent 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.