***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Xiaoyu He (Stanford)

Thursday 12th December, 3:00 in Fine Hall 224.

Title: Ramsey numbers of link hypergraphs

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.

		----------------------------------

Next week: holidays

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)