On the Bollobás–Eldridge Conjecture for Bipartite Graphs

Source abstract

Let G be a simple graph on n vertices. A conjecture of Bollobás and Eldridge [5] asserts that if $\delta (G)\geq \frac{kn-1}{k+1}$ then G contains any n vertex graph H with Δ( H ) = k . We prove a strengthened version of this conjecture for bipartite, bounded degree H , for sufficiently large n . This is the first result on this conjecture for expander graphs of arbitrary (but bounded) degree. An important tool for the proof is a new version of the Blow-Up Lemma.