14:30
The Multiplication Table Problem for Bipartite Graphs
Abstract
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.