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 $\mathrm{\ell }\times \mathrm{\ell }$ grid minor is exponential in $\mathrm{\ell }$. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A \emph{grid-like-minor of order} $\mathrm{\ell }$ in a graph $G$ is a set of paths in $G$ whose intersection graph is bipartite and contains a $K_{\mathrm{\ell }}$-minor. For example, the rows and columns of the $\mathrm{\ell }\times \mathrm{\ell }$ grid are a grid-like-minor of order $\mathrm{\ell }+1$. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least $c{\mathrm{\ell }}^4\sqrt{\log \mathrm{\ell }}$ has a grid-like-minor of order $\mathrm{\ell }$. As an application of this result, we prove that the cartesian product $G\mathrm{\square }{K}_2$ contains a $K_{\mathrm{\ell }}$-minor whenever $G$ has treewidth at least $c{\mathrm{\ell }}^4\sqrt{\log \mathrm{\ell }}$.