Polynomial treewidth forces a large grid-like-minor

Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an ℓ×ℓℓ×ℓ grid minor is exponential in ℓℓ. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A grid-like-minor of order  ℓℓ in a graph GG is a set of paths in GG whose intersection graph is bipartite and contains a KℓKℓ-minor. For example, the rows and columns of the ℓ×ℓℓ×ℓ grid are a grid-like-minor of order ℓ+1ℓ+1. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least cℓ4logℓ has a grid-like-minor of order ℓℓ. As an application of this result, we prove that the Cartesian product G□K2 contains a KℓKℓ-minor whenever GG has treewidth at least cℓ4logℓ.