A bandwidth theorem for graph transversals

Thời gian: 14:00 đến 16:30 Ngày 17/03/2023

Địa điểm: Trực tuyến

Tóm tắt:

Speaker: Jaehoon Kim (Korea Advanced Institute of Science and Technology, Korea)

Abstract: Given a collection $\mathcal{G}=(G_1,\dots, 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 $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow [h]$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The conditions on the minimum degree $\delta(\mathcal{G})=\min_{i\in[h]}\{ \delta(G_i)\}$ for finding a spanning $\mathcal{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 $\delta(\mathcal{G})$ for finding a $\mathcal{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 B\"ottcher, Schacht and Taraz. This is joint work with Debsoumya Chakraborti, Seonghyuk Im and Hong Liu

ZOOM link: https://us02web.zoom.us/j/87167950828?pwd=UFpHTkcwaDZWTndsRGloRE5yN2tIdz09

Zoom Meeting ID: 871 6795 0828

Passcode: 352266

Website Seminar: https://sites.google.com/view/ktv-seminar/