Dense edge-magic graphs and thin additive bases (Q2501547): Difference between revisions

An \((n,m)\)-graph is edge-magic if there is a labeling \(\ell:V(G)\cup E(G) \rightarrow \{1,2,\dots,n+m \}\) such that all the sums \(\ell(a) + \ell(ab) + \ell(b)\) are the same. Also, \(\mathcal{M}(n)\) is the maximum number of edges that a graph with \(n\) vertices can have. The paper presents new bounds on \(\mathcal{M}(n)\), namely: \[ \frac{2}{7} n^{2} + \mathrm{O}(n) \leq \mathcal{M}(n) \leq (0.489 \ldots +\mathrm{o}(1))n^{2} \] These calculations lead to a new bound on \(s(k,n)\), the maximum number of distinct pairwise sums that a \(k\)-subset of \(\{1,2, \dots , n\}\) can have, namely: \[ s(k,n) \leq n + k^{2} \left( \frac{1}{4}-\frac{1}{(\pi+2)^{2}} + \mathrm{o}(1)\right) \] These results have applications to the theory of quasi-Sidon sets as well.