Bandwidth theorem for random graphs

Abstract: A graph

G

is said to have extit{bandwidth} at most

b

, if there exists a labeling of the vertices by

1, 2, ..., n

, so that

| i - j | l e q b

whenever

i, j

is an edge of

G

. Recently, B"{o}ttcher, Schacht, and Taraz verified a conjecture of Bollob'{a}s and Koml'{o}s which says that for every positive

r, D e l t a, g a m m a

, there exists

such that if

H

is an

n

-vertex

r

-chromatic graph with maximum degree at most

D e l t a

which has bandwidth at most

, then any graph

G

on

n

vertices with minimum degree at least

(1 - 1 / r + g a m m a) n

contains a copy of

H

for large enough

n

. In this paper, we extend this theorem to dense random graphs. For bipartite

H

, this answers an open question of B"{o}ttcher, Kohayakawa, and Taraz. It appears that for non-bipartite

H

the direct extension is not possible, and one needs in addition that some vertices of

H

have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed

r

-chromatic graph

H_{0}

which one can find in a spanning subgraph of

G (n, p)

with minimum degree

(1 - 1 / r + g a m m a) n p

.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Bandwidth theorem for random graphs