Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic   if there is a bijection l:V(G)∪E(G)→[n+m]l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab)l(a)+l(b)+l(ab), ab∈E(G)ab∈E(G), are the same. We present new lower and upper bounds on M(n)M(n), the maximum size of an edge-magic graph of order n  , being the first to show an upper bound of the form M(n)⩽(1-ε)n2. Concrete estimates for εε can be obtained by knowing s(k,n)s(k,n), the maximum number of distinct pairwise sums that a k  -subset of [n][n] can have.So, we also study s(k,n)s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n)s(k,n). For example, our estimates(k,n)⩽n+k214-1(π+2)2+o(1)implies a new bound on the maximum size of quasi-Sidon sets, a problem posed by Erdős and Freud [On sums of a Sidon-sequence, J. Number Theory 38 (1991) 196–205].