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

Speaker: Jaehoon Kim (KAIST)

Thursday 30th November, 3:00 in Fine Hall 224.

Title: A bandwidth theorem for graph transversals.

Given a collection G=(G(1),.., G(h)) of graphs on the same vertex set V of 
size n, an h-edge graph H on the vertex set V is a G-transversal if there 
exists a bijection l: E(H)->[h] such that e is in E(G(l(e)) for each edge e 
of H. The conditions on the minimum degree d(G)= min_{i in [h]} d(G_i) for 
finding a spanning G-transversal isomorphic to a graph H have been actively 
studied when H is a Hamilton cycle, an F-factor, a spanning tree with maximum 
degree o(n/log n) and a power of a Hamilton cycle, etc. We determined the 
asymptotically tight threshold on d(G) for finding a G-transversal isomorphic 
to H when H is a general n-vertex graph with bounded maximum degree and
o(n)-bandwidth. This provides a transversal generalization of the celebrated
Bandwidth theorem by Bottcher, Schacht and Taraz. This is joint work with
Debsoumya Chakraborti, Seonghyuk Im and Hong Liu.

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

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