The bipartite case of the Bollob\'as and Koml\'os conjecture states that for every $\Delta_0, \gamma >0$ there is an $\alpha = \alpha(\Delta_0, \gamma) >0$ such that the following statement holds:
If $G$ is any graph with minimum degree at least
$${ n \over 2} + \gamma n,$$
then $G$ contains as subgraphs all $n$ vertex bipartite graphs, $H,$ satisfying
$$ \Delta(H) \leq \Delta_0 \mbox{ and } b(H) \leq \alpha n.$$
Here $b(H),$ the bandwidth of $H$, is the smallest $b$ such that the vertices of $H$ can be ordered as $v_1, \ldots, v_n$ such that $ v_i \sim_H v_j$ implies $|i-j| \leq b$.
This conjecture has been proved in [1]. In this note we show that
this conjecture is tight in the sense that as $\gamma \rightarrow 0$ then
$\alpha \rightarrow 0$. More precisely, we show that for any
$\gamma \leq { 1 \over 100}$ there is a $\Delta_0$ such that that
$\alpha(\Delta_0, \gamma) \leq 4 \gamma $.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-21.ps.gz
DIMACS Home Page