The multiplication table problem for bipartite graphs

Bhargav P. Narayanan, Julian Sahasrabudhe, István Tomon

Research output: Contribution to journalArticlepeer-review


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 ≤ n is precisely the problem under consideration when the graph in question is the complete bipartite graph Kn,n. In this note, we prove that the set of sizes of the induced subgraphs of any bipartite graph with m edges contains Ω(m/(logm)12) distinct elements.

Original languageEnglish (US)
Pages (from-to)991-1010
Number of pages20
Issue number5
StatePublished - Oct 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'The multiplication table problem for bipartite graphs'. Together they form a unique fingerprint.

Cite this