DIMACS TR: 98-21

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

Author: Sarmad Abbasi


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