The Multiplication Table Problem for Bipartite Graphs

3 May 2016
Bhargav Narayanan

Given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs? This question is a natural graph-theoretic generalisation of the 'multiplication table problem' of Erdős:  Erdős’s problem of estimating the number of distinct products a.b with a, b in [n] is precisely the problem under consideration when the graph in question is the complete bipartite graph K_{n,n}.

Based on joint work with J. Sahasrabudhe and I. Tomon.

  • Combinatorial Theory Seminar