{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:58Z","timestamp":1759063798407,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T00:00:00Z","timestamp":1108425600000},"content-version":"unspecified","delay-in-days":45,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>We consider several extremal problems concerning representations of graphs as <jats:italic>distance graphs<\/jats:italic> on the integers. Given a graph <jats:inline-formula>$G=(V,E)$<\/jats:inline-formula>, we wish to find an injective function <jats:inline-formula>$\\phi:V\\to{\\mathbb Z}^+=\\{1,2,\\dots\\}$<\/jats:inline-formula> and a set <jats:inline-formula>${\\mathcal D}\\subset{\\mathbb Z}^+$<\/jats:inline-formula> such that <jats:inline-formula>$\\{u,v\\}\\in E$<\/jats:inline-formula> if and only if <jats:inline-formula>$|\\phi(u)-\\phi(v)|\\in{\\mathcal D}$<\/jats:inline-formula>.<\/jats:p>\n\t  <jats:p>Let <jats:inline-formula>$s(n)$<\/jats:inline-formula> be the smallest <jats:inline-formula>$N$<\/jats:inline-formula> such that any graph <jats:inline-formula>$G$<\/jats:inline-formula> on <jats:inline-formula>$n$<\/jats:inline-formula> vertices admits a representation <jats:inline-formula>$(\\phi_G,{\\mathcal D}_G)$<\/jats:inline-formula> such that <jats:inline-formula>$\\phi_G(v)\\leq N$<\/jats:inline-formula> for all <jats:inline-formula>$v\\in V(G)$<\/jats:inline-formula>. We show that <jats:inline-formula>$s(n)=(1+o(1))n^2$<\/jats:inline-formula> as <jats:inline-formula>$n\\to\\infty$<\/jats:inline-formula>. In fact, if we let <jats:inline-formula>$s_r(n)$<\/jats:inline-formula> be the smallest <jats:inline-formula>$N$<\/jats:inline-formula> such that any <jats:inline-formula>$r$<\/jats:inline-formula>-regular graph <jats:inline-formula>$G$<\/jats:inline-formula> on <jats:inline-formula>$n$<\/jats:inline-formula> vertices admits a representation <jats:inline-formula>$(\\phi_G,{\\mathcal D}_G)$<\/jats:inline-formula> such that <jats:inline-formula>$\\phi_G(v)\\leq N$<\/jats:inline-formula> for all <jats:inline-formula>$v\\in V(G)$<\/jats:inline-formula>, then <jats:inline-formula>$s_r(n)=(1+o(1))n^2$<\/jats:inline-formula> as <jats:inline-formula>$n\\to\\infty$<\/jats:inline-formula> for any <jats:inline-formula>$r=r(n)\\gg\\log n$<\/jats:inline-formula> with <jats:inline-formula>$rn$<\/jats:inline-formula> even for all <jats:inline-formula>$n$<\/jats:inline-formula>.<\/jats:p>\n\t  <jats:p>Given a graph <jats:inline-formula>$G=(V,E)$<\/jats:inline-formula>, let <jats:inline-formula>$D_{\\rm e}(G)$<\/jats:inline-formula> be the smallest possible cardinality of a set <jats:inline-formula>${\\mathcal D}$<\/jats:inline-formula> for which there is some <jats:inline-formula>$\\phi\\:V\\to{\\mathbb Z}^+$<\/jats:inline-formula> so that <jats:inline-formula>$(\\phi,{\\mathcal D})$<\/jats:inline-formula> represents <jats:inline-formula>$G$<\/jats:inline-formula>. We show that, for almost all <jats:inline-formula>$n$<\/jats:inline-formula>-vertex graphs <jats:inline-formula>$G$<\/jats:inline-formula>, we have <jats:disp-formula>\\begin{equation*} D_{\\rm e}(G)\\geq\\frac{1}{2}\\binom{n}{2}-(1+o(1))n^{3\/2}(\\log n)^{1\/2}, \\end{equation*}<\/jats:disp-formula> whereas for some <jats:inline-formula>$n$<\/jats:inline-formula>-vertex graph <jats:inline-formula>$G$<\/jats:inline-formula>, we have <jats:disp-formula>\\begin{equation*} D_{\\rm e}(G)\\geq\\binom{n}{2}-n^{3\/2}(\\log n)^{1\/2+o(1)}.\\end{equation*}<\/jats:disp-formula> Further extremal problems of similar nature are considered.<\/jats:p>","DOI":"10.1017\/s0963548304006637","type":"journal-article","created":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T12:56:08Z","timestamp":1108472168000},"page":"107-131","source":"Crossref","is-referenced-by-count":5,"title":["Distance Graphs on the Integers"],"prefix":"10.1017","volume":"14","author":[{"given":"M.","family":"FERRARA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"KOHAYAKAWA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"R\u00d6DL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2005,2,15]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:16:45Z","timestamp":1750454205000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006637\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":0,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["S0963548304006637"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006637","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}