The link hypergraph L_G of a graph G is the 3-uniform hypergraph obtained by adding a new vertex v to V(G) and inserting v into every edge of G. Solving a problem of Erdős and Hajnal from 1972, we give a new probabilistic construction proving that the Ramsey number of L_{K_3} (with 4 vertices and 3 edges) against the clique satisfies r(L_{K_3}, K_n^(3)) = 2^{Theta(n logn)}. Our construction generalizes to give r(L_G, K_n^(3)) = 2^{Theta(n logn)} for all non-bipartite graphs G, as well as a new proof of the fact that r(K_n^(3), K_n^(3)) > 2^{cn^2}, which matches the best known lower bound up to the value of c.

Joint work with Jacob Fox.