The multiplication table problem for bipartite graphs (Q1669691)

The paper is concerned with 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. More precisely, for a bipartite graph \(G\), define, writing \(e(.)\) for the number of edges of a graph, its multiplication table \(\mathcal {M} (G)\) by setting \[ \mathcal{M}(G) =\{ e(H) : H \; \text{ is an induced subgraph of }\; G\}, \] the aim is to study the cardinality of the set \(\mathcal{M}(G)\). Erdős's problem of estimating the number of distinct products \(ab\) with \( a, b \leq n\) is precisely the problem under consideration when the graph in question is the complete bipartite graph \(K_{n,n}\). The authors conjecture that \(\mathcal{M}(K_{n,n})\) has minimum cardinality among all graphs with \(n^2\) edges. In the present paper, the authors prove the above conjecture in a weak quantitative form. They show that the set of sizes of the induced subgraphs of any bipartite graph with \(m\) edges contains \(\Omega (m/(\log m)^ {12})\) distinct elements.