How tight is the Bollobás-Komlós conjecture? (Q1576569): Difference between revisions

The bipartite case of the Bollobás-Komlós conjecture states that for every \(\Delta_0\), \(r>0\) there is an \(\alpha= \alpha(\Delta_0, r)> 0\) such that the following statement holds: If \(G\) is any graph with minimum degree at least \({n\over 2}+ rn\), then \(G\) contains as subgraphs all \(n\) vertex bipartite graphs, \(H\), satisfying \(\Delta(H)\leq\Delta_0\) 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,v_2,\dots, v_n\) such that \(v_i\sim_Hv_j\) implies \(|i-j|\leq b\). This conjecture has been proved by the author in the submitted paper ``Embedding low bandwidth bipartite graphs.'' The author proves the following theorem: For any \(0< r\leq{1\over 100}\) there is a \(\Delta_0\) such that following statement holds for infinitely many \(n\): there is a graph \(\text{BK}_{n,r}\) on \(n\) vertices with minimum degree at least \({n\over 2}+ rn\) and a bipartite graph, \(H\), on \(n\) vertices with \(\Delta(H)\leq \Delta_0\) and \(b(H)< 4rn\). Yet \(H\) is not a subgraph of \(\text{BK}_{n,r}\).