The multiplication table problem for bipartite graphs

Abstract

We investigate the following generalisation of the 'multiplication table problem' of Erdős: given a bipartite graph with $m$ edges, how large is the set of sizes of its induced subgraphs? Erdős's problem of estimating the number of distinct products $ab$ with $a,b\le n$ is precisely the problem under consideration when the graph in question is the complete bipartite graph $K_{n,n}$. In this note, we prove that the set of sizes of the induced subgraphs of any bipartite graph with $m$ edges contains $\Omega (m/(\log m{)}^{12})$ distinct elements.

21 pages, fixed misprints, Combinatorica