A bandwidth theorem for graph transversals

Publication date: 19 February 2023

Abstract: Given a collection

m a t h c a l G = (G_{1}, d o t s, 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

m a t h c a l G

-transversal if there exists a bijection

l a m b d a : E (H) i g h t a r r o w [h]

such that

e i n E (G_{l a m b d a (e)})

for each

e i n E (H)

. The conditions on the minimum degree

d e l t a (m a t h c a l G) = m i n_{i i n [h]} d e l t a (G_{i})

for finding a spanning

m a t h c a l 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 / l o g n)

and a power of a Hamilton cycle, etc. In this paper, we determined the asymptotically tight threshold on

d e l t a (m a t h c a l G)

for finding a

m a t h c a l 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 page was built for publication: A bandwidth theorem for graph transversals