Photo by erwanhesry from unsplash
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?… Click to show full 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 ≤ 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.
Keywords:
bipartite;
multiplication table;
problem;
table problem
Journal Title: Combinatorica
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Combinatorica
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!