***********************************
* 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)