4 citations · 4 across the 4 of their papers we have counts for
6 papers · 1 filter
Ramsey games with giants
Tom Bohman, Alan Frieze, Michael Krivelevich +2
The classical result in the theory of random graphs, proved by Erdos and Renyi in 1960, concerns the threshold for the appearance of the giant component in the random graph process…
A note on embedding hypertrees
Po-Shen Loh
A classical result from graph theory is that every graph with chromatic number χ> t contains a subgraph with all degrees at least t, and therefore contains a copy of every t-edge t…
Large induced trees in K_r-free graphs
Jacob Fox, Po-Shen Loh, Benny Sudakov
For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. In this paper, we study the problem of bounding t(G) for graphs which do n…
Avoiding small subgraphs in Achlioptas processes
Michael Krivelevich, Po-Shen Loh, Benny Sudakov
For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is aske…
Independent transversals in locally sparse graphs
Po-Shen Loh, Benny Sudakov
Let G be a graph with maximum degree Δwhose vertex set is partitioned into parts V(G) = V_1 \cup ... \cup V_r. A transversal is a subset of V(G) containing exactly one vertex from…
On the strong chromatic number of random graphs
Po-Shen Loh, Benny Sudakov
Let G be a graph with n vertices, and let k be an integer dividing n. G is said to be strongly k-colorable if for every partition of V(G) into disjoint sets V_1 \cup ... \cup V_r,…