Dense minors and bipartite independence numbers

Abstract

A graph $G$ is $m$-joined if there is an edge between every two disjoint $m$-sets of vertices. In this paper, we prove that for any $\epsilon >0$ and sufficiently large $m,n\in \mathbb{N}$ with $m\le n^{1-\epsilon }$, every $n$-vertex $m$-joined graph $G$ contains a minor with density $\hat{I}\text{c◯}\left(\frac{n}{\sqrt{m}}\right)$, which is best possible up to a constant factor. When $m\ge n^{1-\epsilon }$, we further show that $G$ contains a clique minor of order $\hat{I}\text{c◯}\left(\frac{n}{\sqrt{m\log m}}\right)$.