Tom
Bohman
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh
PA 15213
USA
Email: tbohman
Telephone: 412 268 2545
Classes: Spring 2015
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
A note on the random greedy independent set algorithm
(with P. Bennett), submitted.
Dynamic concentration of the triangle-free process
(with P. Keevash), submitted.
A natural barrier in random greedy hypergraph matching
(with P. Bennett), submitted.
A greedy algorithm for finding a large 2-matching on a random cubic graph
(with D. Bal, P. Bennett, and A. Frieze), submitted.
Random triangle removal
(with A. Frieze and E. Lubetzky), submitted.
On the independence numbers of the cubes of odd cycles (with R. Holzman and V. 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.