## DIMACS TR: 98-21

## How tight is the Bollobás-Komlós Conjecture?

### Author: Sarmad Abbasi

**
ABSTRACT
**

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