Tom Bohman

Classes: Spring 2008

21-228: Discrete Mathematics

---

Links

FriezeFest 2005

ACO Homepage

David Griffeath's Primordial Soup Kitchen

Electronic Journal of Combinatorics

Publications

• Hamilton cycles in 3-out (with A. Frieze) , submitted.
  
                      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.
  
  
• Product rule wins a competitive game (with A. Beveridge, A. Frieze and O. Pikhurko), Proceedings of the American Mathematical Society , to appear.
  
  
• The game chromatic number of random graphs (with A. Frieze and B. Sudakov), Random Structures and Algorithms , to appear.
  
  
• 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 , to appear.
  
  
• 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.