TY - JOUR
T1 - The multiplication table problem for bipartite graphs
AU - Narayanan, Bhargav P.
AU - Sahasrabudhe, Julian
AU - Tomon, István
N1 - Publisher Copyright:
© 2016, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.
PY - 2017/10/1
Y1 - 2017/10/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84991716221&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84991716221&partnerID=8YFLogxK
U2 - 10.1007/s00493-016-3322-0
DO - 10.1007/s00493-016-3322-0
M3 - Article
AN - SCOPUS:84991716221
SN - 0209-9683
VL - 37
SP - 991
EP - 1010
JO - Combinatorica
JF - Combinatorica
IS - 5
ER -