A bandwidth theorem for graph transversals

Jaehoon Kim, KAIST
Fine Hall 224

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.