DISTANCE GRAPHS ON THE INTEGERS

M. FERRARA, Y. KOHAYAKAWA, AND V. RÖDL

Dedicated to the memory of Professor Walter Deuber on the occasion of his 60th birthday

Abstract. We consider several extremal problems concerning representations of graphs as distance graphs on the integers. Given a graph G = (V, E), we wish to find an injective function φ: V → ℤ^{+} = {1, 2, … } and a set D ⊂ ℤ^{+} such that {u, v} ∈ E if and only if |φ(u) − φ(v)| ∈ D.

Let s(n) be the smallest N such that any graph G on n vertices admits a representation (φ_{G}, D_{G}) such that φ_{G}(v) ≤ N for all v ∈ V (G). We show that s(n) = (1 + o(1))n^{2} as n → ∞. In fact, if we let s_{r}(n) be the smallest N such that any r-regular graph G on n vertices admits a representation (φ_{G}, D_{G}) such that φ_{G}(v) ≤ N for all v ∈ V (G), then s_{r}(n) = (1 + o(1))n^{2} as n → ∞ for any r = r(n) ≫ log n with rn even for all n.

Given a graph G = (V, E), let D_{e}(G) be the smallest possible cardinality of a set D for which there is some φ: V → ℤ^{+} so that (φ, D) represents G. We show that, for almost all n-vertex graphs G, we have

D_{e}(G) ≥ \frac{1}{2} \binom{n}{2} − (1 + o(1))n^{3/2}(log n)^{1/2},

whereas for some n-vertex graph G, we have

D_{e}(G) ≥ \binom{n}{2} − n^{3/2}(log n)^{1/2+o(1)}.

Further extremal problems of similar nature are considered.

1. Introduction and statement of the main results

We are interested in representing a graph G = (V, E) by assigning to each vertex v ∈ V an integer φ(v) so that we can then distinguish those pairs of vertices u, v that are edges from those that are not simply by

Date: 8 January 2004. 1991 Mathematics Subject Classification. Primary: 05C62. Secondary: 11B75. Key words and phrases. Sidon sets, geometric representations of graphs. Most of this work was done while the second author was visiting the Department

of Mathematics and Computer Science, Emory University, whose support he gratefully acknowledges. The second author is also partially supported by MCT/CNPq (ProNEx Project Proc. CNPq 664107/1997–4) and by CNPq (Proc. 300334/93–1 and 468516/2000– 0). The third author was partially supported by NSF Grant 0071261. The collaboration of the Brazilian author and the US authors is supported by a CNPq/NSF cooperative grant (910064/99–7, 0072064).

|φ(u) − φ(v)|. In other words, for each graph G = (V, E) we wish to find a function φ: V → ℤ^{+} = {1, 2, … } and a set D ⊂ ℤ^{+} so that {u, v} ∈ E if and only if |φ(u) − φ(v)| ∈ D.

We shall investigate numerical parameters associated with such representations (φ, D) of G. A basic question is to determine or estimate the smallest possible value for max{φ(v): v ∈ V (G)} for a given graph G, when we let φ and D vary freely. We denote this value by s(G) (see (5)). Let s(n) = max_{G} s(G), where the maximum is taken over all n-vertex graphs. One of our results shows that s(n) = (1 + o(1))n^{2} (see Theorem 4).

We shall also investigate the size of the sets D that we need, both for individual graphs and when considering all graphs on a fixed number of vertices. Other parameters pertaining to the function φ, which may be of some interest on their own, will also be considered (see Lemmas 12 and 13).

We are grateful to B. Bollobás and O. Pikhurko for letting us know that problems and results of nature similar to the ones considered here appear in [6] and [17].

Finally, we observe that the subject of this paper may be thought of as a particular case of the problem of representing graphs as induced subgraphs of Cayley graphs (see, e.g., Babai and Sós [2] and the references therein). At least to some extent, this paper shows that the specific case of representing graphs as induced subgraphs of Cayley graphs on the integers is already of some interest.

1.1. Definitions. We shall consider integer functions

φ: [n] → ℤ^{+}  (1)

with domain [n] = {1, …, n}. In what follows, the asymptotics will be with respect to n → ∞. A map φ as in (1) defines an equivalence relation

∼_{φ}  (2)

on \binom{[n]}{2}, the edge set of the complete graph K_{n} with vertex set [n], given by

{i, j} ∼_{φ} {k, ℓ} ⟺ |φ(i) − φ(j)| = |φ(k) − φ(ℓ)|.  (3)

Let Dist(φ) be the set of equivalence classes of ∼_{φ}. Note that

(*) | Dist(φ)| is the number of distinct ‘distances’, i.e., integers of the

form

|φ(i) − φ(j)| (i, j ∈ [n], i ≠ j), (4)

that φ induces. In what follows, we shall be interested in the numerical parameters | Dist(φ)| and max{φ(i): i ∈ [n]} of the functions φ: [n] → ℤ^{+}.

We now introduce a central definition. Definition 1 (G(φ, D)). Given φ: [n] → ℤ^{+} and D ⊂ ℤ^{+} = {1, 2, … }, we define the graph G(φ, D) as the graph whose vertex set is [n], with i and j adjacent if and only if |φ(i) − φ(j)| ∈ D.

If G is isomorphic to G(φ, D), then we shall say that (φ, D) spaces G (or that (φ, D) is a spacing of G).

Clearly, in the definition of G(φ, D) above, we make i adjacent to j if and only if the distance between φ(i) and φ(j) is an element of a set D of ‘distinguished’ distances. Furthermore, it is clear that the edge set of G(φ, D) is a union of equivalence classes of the relation ∼_{φ}; equivalently, if {i, j} ∼_{φ} {k, ℓ}, then {i, j} is an edge of G(φ, D) if and only if {k, ℓ} is.

We are interested in representing graphs G as graphs of the form G(φ, D). In particular, when representing an n-vertex graph G as some G(φ, D), numerical constraints on D and im(φ) = {φ(i): i ∈ [n]} arise. For instance, we shall show that for almost all G, we must allow |D| to be of order n^{2}. To prove such constraints, we shall give upper estimates for the number of graphs that are of the form G(φ, D), up to isomorphism.

Let us now define some extremal parameters for n-vertex graphs G. In what follows, φ and D will always stand for a function φ: [n] → ℤ^{+} and a set D ⊂ ℤ^{+}. (We mention that, in the definitions that follow, we may restrict ourselves to injective functions φ, as G has n vertices and we always wish to have G isomorphic to G(φ, D).)

Given φ, we shall say that a graph G is a φ-graph if G is isomorphic to G(φ, D) for some D. Similarly, given D, we shall say that G is a D-graph if G is isomorphic to G(φ, D) for some φ.

Our first extremal parameter is s(G), the minimal integer N for which there is a function φ with im(φ) ⊂ [N] such that G is a φ-graph. Formally,

s(G) = min{N: there is φ: [n] → ℤ^{+}
such that im(φ) ⊂ [N] and G is a φ-graph} (5)

= min{max im(φ): G is a φ-graph}.

Therefore, s(G) is the ‘space’ that we need in order to obtain a representation G(φ, D) of G. We now define μ(G) to be the maximal cardinality of an equivalence class of ∼_{φ}, where we let φ vary among all functions such that G is a φ-graph:

μ(G) = max{|C|: C is an equivalence class of ∼_{φ}, where φ is such that G is a φ-graph}. (6)

Thus, μ(G) is the maximum ‘multiplicity’ with which a ‘distance’ (recall (*)) may occur in a representation G(φ, D) of G.

Our third and fourth parameters concern the number of ‘distances’ that we use in our representations of G. We let

D(G) = min{| Dist(φ)|: G is a φ-graph}.  (7)

Hence, D(G) is the minimal possible number of ‘distances’ that are induced by the φ: [n] → ℤ^{+} in the representations G(φ, D) of G. We may also restrict ourselves to counting distinct ‘distances’ that occur as edges in our representations of G. We let

D_{e}(G) = min{|D|: G is a D-graph}.  (8)

Thus, D_{e}(G) is the minimum number of ‘edge lengths’ that are required in the representations G(φ, D) of G.

It is easy to see that s(K_{n}) = s(C_{n}) = s(P_{n}) = n, where, as usual, C_{n} is the cycle on n vertices and P_{n} is the path on n vertices. However, calculating the spacing number of a graph exactly can be delicate, even for very simple graphs. As usual, K_{m,n} denotes the complete bipartite graph with vertex classes of cardinality m and n.

Proposition 2. For m ≥ n, we have

s(K_{m,n}) = \begin{cases}2m & if m = n \\ 2m − 1 & if m > n. \end{cases}  (9)

In order to prove the proposition, we must first prove the following.

Proposition 3. For any n > 1, we have s(K_{1,n}) = 2n − 1.

To see that s(K_{1,n}) ≤ 2n − 1 consider G(φ, D), where

im(φ) = {1, 2, 3, 5, 7, …, 2n − 1}  (10)

and

D = {1, 3, 5, …, 2n − 3}.  (11)

Then (φ, D) spaces K_{1,n}, and hence s(K_{1,n}) ≤ 2n − 1. The reverse inequality will be proved in Section 2. Proposition 2 follows by monotonicity under taking induced subgraphs.

Another example that seems to show that the problem of determining or estimating s(G) does require some idea is the case in which G is a tree. The authors have not come across any general, non-trivial bounds for this case (see Section 6 below and [2, Remark 7.2]). Let us now get back to the general case.

Let

s(n) = max_{G} s(G), μ(n) = min_{G} μ(G), D(n) = max_{G} D(G), (12)

and

D_{e}(n) = max_{G} D_{e}(G),  (13)

where the maxima are taken over all n-vertex graphs G. For positive integers r, we also let

s_{r}(n) = max_{G} s(G),  (14)

where the maximum is taken over all r-regular graphs G on n vertices. Our main concern in this note is to give estimates for the extremal functions s(n), s_{r}(n), μ(n), D(n), and D_{e}(n).

1.2. Statement of the results. The following are our results pertaining to the parameters given above. The proofs will be given in Sections 4 and 5.

We start with the extremal functions s(n) and s_{r}(n).

Theorem 4. We have

n^{2} (1 − (4 + o(1))\sqrt{\frac{log n}{n}}) ≤ s(n) ≤ n^{2} + O(n^{1.525}).  (15)

Theorem 5. (i) For every fixed integer r ≥ 2 and for all n with rn even, we have

s_{r}(n) ≥ (1 + o(1)) (\frac{1}{r!})^{2/(r+2)} (\frac{r}{e\sqrt{2}})^{2r/(r+2)} n^{2r/(r+2)}.  (16)

(ii) Let r = r(n) be an integer function satisfying log n ≪ r ≤ (n − 1)/2 and with rn even for all n. Then

s_{r}(n) = (1 + o(1))n^{2}.  (17)

Our result concerning the ‘multiplicity’ parameter μ(n) is as follows.

Theorem 6. For all sufficiently large n, we have

μ(n) < 2 + 8 log_{2} n.  (18)

The next three results deal with the functions D(n) and D_{e}(n) and the parameter D_{e}(G), concerning the number of distinct distances that are involved in our representations of graphs.

Theorem 7. For any ε > 0, there is n_{0} = n_{0}(ε) such that if n ≥ n_{0}, then

D(n) > \binom{n}{2} − 4n log_{2} n + 2n − \frac{1}{2} log_{2}(2πn) − ε.  (19)

Theorem 8. For almost all n-vertex graphs G, we have

D_{e}(G) ≥ \frac{1}{2}\binom{n}{2} − (1 + o(1))n^{3/2}\sqrt{log n}.  (20)

Theorem 9. For any function ω = ω(n) such that ω(n) → ∞ as n → ∞, we have

D_{e}(n) ≥ \binom{n}{2} − 3ωn^{3/2}\sqrt{log n} − 3  (21)

for all large enough n.

Finally, we observe that there are n-vertex graphs G for which we have both D_{e}(G) = (1 + o(1))\binom{n}{2} and s(G) = (1 + o(1))n^{2}.

Corollary 10. Let ε > 0 be fixed and suppose ω = ω(n) → ∞ as n → ∞. Then, for all large enough n, there is an n-vertex graph G for which we have

D_{e}(G) ≥ \binom{n}{2} − 3ωn^{3/2}\sqrt{log n} − 3  (22)

and

s(G) ≥ (1 − (2\sqrt{6} + ε)ω^{1/2} (\frac{log n}{n})^{1/4}) n^{2}.  (23)

2. Proof of Proposition 3

We have already observed that s(K_{1,n}) ≤ 2n − 1. To establish the reverse inequality, we need the following claim.

Claim 11. If K_{1,n} is isomorphic to G(φ, D), where im(φ) ⊂ [2n − 1], then the root vertex is associated with neither 1 nor max im(φ).

Proof. Assume otherwise; specifically, assume that the root vertex of K_{1,n} is associated with 1. Then there are n distinct differences in D corresponding to the edges in the graph. However, since 1 is associated with the vertex of degree n in our graph, the largest value, namely max im(φ), must be associated with a leaf v. Hence there are n − 1 distinct values not in D corresponding to the non-edges between v and the other leaves. However this implies that 2n − 2 = |D| + |[2n − 2] \ D| ≥ n + n − 1 = 2n − 1, a contradiction. □

We can now prove the proposition.

Proof of Proposition 3. We proceed by induction on n, and note that the claim is easily shown true when n = 2 or n = 3. Let (φ, D) be a spacing of K_{1,n} (n > 3) that realizes the spacing number and assume that max im(φ) = s(K_{1,n}) is at most 2n − 2. If x is the vertex of degree n in the graph, then the claim tells us that x is not associated with 1 or s(K_{1,n}). Therefore, both 1 and s(K_{1,n}) must be leaves. Note that both 2 and s(K_{1,n}) − 1 must also be in im(φ) and associated with leaves, lest s(K_{1,n−1}) ≤ 2n − 4 (contradicting the induction assumption), or one of these points is associated with x, contradicting the claim. Now, assume that x is associated with some point p_{i} in im(φ). By the above, p_{i} ∉ {1, 2, s(K_{1,n}) − 1, s(K_{1,n})}. Assume that there are l ≥ 2 points associated with leaves in the interval [1, p_{i}] and n − l points associated with leaves in the interval [p_{i}, s(K_{1,n})]. Then the points from im(φ) in these intervals along with D comprise spacings of K_{1,l} and K_{1,n−l} respectively. Also, the root vertex of these stars are associated with the largest and smallest values in these intervals. In order to space K_{1,l} in this way, the claim implies p_{i} ≥ 2l. However, we then have s(K_{1,n−l}) ≤ s(K_{1,n}) − p_{i} ≤ 2n − 2 − 2l = 2(n − l) − 2, contradicting the induction assumption. □

As noted above, this also completes the proof of Proposition 2.

3. Auxiliary lemmas

In this section, we give two elementary results from combinatorial number theory.

3.1. Almost Sidon sets. To establish our bounds on s(n), we shall make use of a classical object from combinatorial number theory. A set

A = {a_{1}, …, a_{n}}  (24)

is called a Sidon set if

|\{|a_{i} − a_{j}|: i < j\}| = \binom{n}{2},  (25)

that is, if all of the differences of distinct elements are distinct. It was shown by Erdős and Turán in [9] that if A ⊂ [N] is an n-element Sidon set, then

N ≥ n^{2} + O(n^{3/2})  (26)

(see also [13, 14]). We shall examine a similar type of set, wherein the pairwise differences are almost all distinct. Lemma 12 below, in a slightly different form, appears as Theorem 1 in [6]. The proofs os Lemma 12 and [6, Theorem 1] follow [9] closely, and were obtained independently.

Lemma 12. Let 0 < ε = ε(n) ≤ 1 be such that εn → ∞ as n → ∞. Suppose φ: [n] → ℤ^{+} is an injective function such that

| Dist(φ)| ≥ (1 − ε)\binom{n}{2}  (27)

and

im(φ) ⊂ [N].  (28)

Then

N ≥ (1 − (2 + o(1))\sqrt{ε})n^{2}.  (29)

Proof. As mentione above, we follow [9] very closely. Let ε = ε(n) and φ: [n] → ℤ^{+} be as in the statement of our lemma. Let im(φ) = {x_{i}: 1 ≤ i ≤ n}, where

x_{1} < ⋯ < x_{n}.  (30)

Let m = ⌊ε^{1/2}n^{2}⌋. Let us consider the following N + m intervals of integers, each of cardinality m:

I_{1} = [−m + 1, 1), I_{2} = [−m + 2, 2), …, I_{N+m} = [N, N + m).  (31)

Let B_{k} be the number of x_{i} that belong to the interval I_{k} = [−m+k, k). Let us count the triples (x_{i}, x_{j}; I_{k}) for which we have x_{i} < x_{j} and x_{i}, x_{j} ∈ I_{k}. Let T be the number of such triples.

We have

T = ∑_{1≤k≤N+m} \binom{B_{k}}{2} ≥ \frac{1}{2}(N + m)\frac{nm}{N + m} (\frac{nm}{N + m} − 1) ,  (32)

where the inequality follows from convexity. Let us now estimate T in an alternative way.

Pick L ≥ (1 − ε)\binom{n}{2} pairs (x_{i_{λ}}, x_{j_{λ}}) (1 ≤ λ ≤ L) with x_{i_{λ}} < x_{j_{λ}} for all λ and all the differences

d_{λ} = x_{j_{λ}} − x_{i_{λ}}  (1 ≤ λ ≤ L)  (33)

distinct. Fix a pair (x_{i_{λ}}, x_{j_{λ}}). If d_{λ} = x_{j_{λ}} − x_{i_{λ}} ≥ m, then clearly there is no k for which both x_{i_{λ}} and x_{j_{λ}} ∈ I_{k}. If d_{λ} < m, then there are m − d_{λ} intervals I_{k} with both x_{i_{λ}} and x_{j_{λ}} ∈ I_{k}. Given that all the differences in these L pairs are distinct, we deduce that the number of triples of the form (x_{i_{λ}}, x_{j_{λ}}; I_{k}) (1 ≤ λ ≤ L) that we are interested in is

≤ ∑_{1≤d<m}(m − d) = \binom{m}{2}.  (34)

Now we have to take into account the triples (x_{i}, x_{j}; I_{k}) for the pairs (x_{i}, x_{j}) that are not one of the (x_{i_{λ}}, x_{j_{λ}}) (1 ≤ λ ≤ L). We use a crude bound for such pairs, of which there are at most ε\binom{n}{2}: each of the pairs occur in at most m − 1 intervals I_{k} each. Therefore, we have

T ≤ \binom{m}{2} + ε\binom{n}{2}(m − 1) ≤ \frac{1}{2}(m^{2} + εn^{2}m).  (35)

Comparing (32) and (35), we have

n (\frac{nm}{N + m} − 1) ≤ m + εn^{2},  (36)

which is equivalent to

n^{2}m ≤ (N + m)(m + εn^{2} + n).  (37)

Since εn → ∞ as n → ∞, we deduce from (37) that

N ≥ \frac{n^{2}m}{m + (1 + o(1))εn^{2}} − m ≥ n^{2} \frac{1}{1 + (1 + o(1))εn^{2}/m} − ε^{1/2}n^{2}

≥ n^{2} (1 − (1 + o(1))ε^{1/2}) − ε^{1/2}n^{2}, (38)

and (29) follows. □

3.2. The number of equivalence relations ∼_{φ}. Recall that each φ: [n] → ℤ^{+} defines an equivalence relation ∼_{φ} on \binom{[n]}{2} (see (3)). Let

T (n) = |{∼_{φ}: φ ∈ (ℤ^{+})^{[n]}}|.  (39)

The upper bound for T (n) given in Lemma 13 below will be crucial when estimating D(n) and D_{e}(n). The reader may find it interesting to observe how small T (n) is, in comparison with the total number of equivalence relations on \binom{[n]}{2}, which is given by the Bell number

b\binom{n}{2} = \binom{n}{2}^{(1+o(1))\binom{n}{2}} = n^{(1+o(1))n^{2}}  (40)

(see, e.g., [11]).

Lemma 13. For all n ≥ 3, we have

T (n) ≤ \binom{2\binom{\binom{n}{2}}{2}}{n} ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} .  (41)

Proof. Let φ_{λ}: [n] → ℤ^{+} (λ ∈ Λ) be T (n) maps with all the ∼_{φ_{λ}} distinct. Moreover, let p be a sufficiently large prime; any choice with

p > max_{λ∈Λ} (max im(φ_{λ}))^{2}  (42)

will do. We may consider the maps φ_{λ} as maps into 𝔽_{p}, the field of order p, in the obvious way:

φ_{λ}: [n] → 𝔽_{p}.  (43)

For convenience, let

x_{λ,i} = φ_{λ}(i) (λ ∈ Λ, i ∈ [n])  (44)

and let

x_{λ} = (x_{λ,i})_{1≤i≤n}.  (45)

Let

R = \binom{\binom{[n]}{2}}{2} = \binom{E(K^{n})}{2},  (46)

and consider the quadratic polynomials

f_{ϱ}(x_{1}, …, x_{n}) ∈ 𝔽_{p}[x_{1}, …, x_{n}]  (ϱ ∈ R),  (47)

where, if ϱ = {{i, j}, {k, ℓ}} ∈ R, then

f_{ϱ}(x_{1}, …, x_{n}) = (x_{i} − x_{j})^{2} − (x_{k} − x_{ℓ})^{2}.  (48)

We let x = (x_{1}, …, x_{n}) and f(x) = (f_{ϱ}(x))_{ϱ∈R}.

Given z = (z_{ϱ})_{ϱ∈R} ∈ 𝔽_{p}^{R}, let the zero pattern Z(z) of z be the {0, ∗}- vector (s_{ϱ})_{ϱ∈R}, where

s_{ϱ} = \begin{cases}0 & if z_{ϱ} = 0 \\ ∗ & otherwise. \end{cases}  (49)

We now consider the zero patterns Z(f(x^{∗})) of the vectors f(x^{∗}), where we let x^{∗} vary in 𝔽_{p}^{n}. Theorem 1.3 in [18] tells us that

|\{Z(f(x^{∗})): x^{∗} ∈ 𝔽_{p}^{n}\}| ≤ \binom{2|R|}{n}

= \binom{2\binom{\binom{n}{2}}{2}}{n} ≤ \binom{n^{4}/4}{n} ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} . (50)

It now suffices to relate zero patterns with the equivalence relations ∼_{φ_{λ}}. Recall (3), (42), (44), and (45), and observe that, for any ∼_{φ_{λ}} and any ϱ = {{i, j}, {k, ℓ}} ∈ R, we have

{i, j} ∼_{φ_{λ}} {k, ℓ} ⟺ |φ_{λ}(i) − φ_{λ}(j)| = |φ_{λ}(k) − φ_{λ}(ℓ)|

⟺ (x_{λ,i} − x_{λ,j})^{2} = (x_{λ,k} − x_{λ,ℓ})^{2} ⟺ f_{ϱ}(x_{λ}) = 0 in 𝔽_{p}. (51)

(Note that the ‘if’ part of the last ‘if and only if’ follows from (42).) By the definition of zero patterns, the equivalences in (51) tell us that the relations ∼_{φ_{λ}} and ∼_{φ_{λ′}} coincide if and only if Z(f(x_{λ})) = Z(f(x_{λ′})). This fact and (50) imply (41), and Lemma 13 is proved. □

4. Proofs of Theorems 4, 5, and 6

In this section we shall prove our results concerning the extremal functions s(n), s_{r}(n), and μ(n).

4.1. Proofs of Theorems 4 and 5. We start with the spacing parameters s(n) and s_{r}(n).

Proof of Theorem 4. We shall show that

(1 − (4 + o(1))\sqrt{\frac{log n}{n}}) n^{2} ≤ s(n) ≤ n^{2} + O(n^{1.525}).  (52)

We prove the upper bound using Sidon sets. Let G be a graph with vertex set {v_{1}, …, v_{n}} and let A = {a_{1}, …, a_{n}} be a Sidon set. Then (φ, D) spaces G, where φ: [n] → ℤ^{+} is any function such that im(φ) = A and

D = {|a_{i} − a_{j}|: {v_{i}, v_{j}} ∈ E(G)}.  (53)

Thus, in order to estimate s(n) from above, we wish to minimize the maximum element in an n-element Sidon set. The following is a well known consequence of a result of Singer [20] (for details, see [12, Chapter II]).

Lemma 14. Let q be a prime power. Then there is a (q + 1)-element Sidon set A = {a_{0}, a_{1}, …, a_{q}} with 1 ≤ a_{0} < a_{1} < ⋯ < a_{q} ≤ q^{2} + q + 1.

It was shown by Baker, Harman, and Pintz [3] that, for any sufficiently large n, there is always a prime q in the interval [n − 1, n + (1 + o(1))n^{.525}]. Putting together the observations above, we have

s(n) ≤ (n + (1 + o(1))n^{.525})^{2} + (n + (1 + o(1))n^{.525}) + 1

= n^{2} + O(n^{1.525}), (54)

and the upper bound in (52) follows. We now turn to the lower bound on s(n).

Let δ be a fixed positive real, and let

ε = ε(n) = \frac{4 log n}{n − 1}.  (55)

Suppose for a contradiction that

s(n) ≤ N_{0} = ⌊n^{2} (1 − (4 + δ)\sqrt{\frac{log n}{n}})⌋ .  (56)

Let us invoke Lemma 12, with ε given in (55). Lemma 12 tells us that if φ: [n] → ℤ^{+} is such that

| Dist(φ)| ≥ (1 − ε)\binom{n}{2}  (57)

and im(φ) ⊂ [N], then

N ≥ n^{2}(1 − (2 + o(1))\sqrt{ε}) = n^{2} (1 − (4 + o(1))\sqrt{\frac{log n}{n}}) .  (58)

Comparing (56) and (58), we see that, for all n ≥ n_{0}(δ), the φ: [n] → ℤ^{+} that are such that im(φ) ⊂ [N_{0}] must all be such that (57) fails, that is,

| Dist(φ)| < (1 − ε)\binom{n}{2}.  (59)

Note that (56) tells us that if we consider the graphs G(φ, D) with φ: [n] → ℤ^{+} such that im(φ) ⊂ [N_{0}] and D ⊂ ℤ^{+} arbitrary, then we obtain all nvertex graphs up to isomorphism.

Remark 19(i) and (59), coupled with the fact that there are at least 2^{\binom{n}{2}}/n! graphs on n vertices up to isomorphism, tell us that

\frac{N_{0}^{n}}{n!} 2^{(1−ε)\binom{n}{2}} ≥ \binom{N_{0}}{n}2^{(1−ε)\binom{n}{2}} ≥ \frac{1}{n!}2^{\binom{n}{2}}.  (60)

Inequalities (55) and (60) give that N_{0} ≥ n^{2}, which contradicts (56) for all n ≥ n_{0}(δ). This contradiction completes the proof of Theorem 4. □

The proof of Theorem 5 is similar to the proof of Theorem 4. The following estimates for the number of r-regular graphs will be used now. We first quote a classical result of Bender and Canfield [4] (see also [5, Corollary 2.17]), in the case in which r is a fixed integer.

Theorem 15. For any fixed integer r ≥ 2, the number R(n, r) of labelled, n-vertex r-regular graphs satisfies

R(n, r) ≥ (\sqrt{2} + o(1))e^{−(r^{2}−1)/4} (\frac{r^{r/2}}{e^{r/2}r!})^{n} n^{rn/2}  (61)

as n → ∞ with rn even.

For recent results concerning the number of r-regular graphs with r = r(n) → ∞ as n → ∞, see McKay and Wormald [16], where Theorem 15 is extended to r = o(\sqrt{n}). For a wider range of r, we shall make use of the following fact, which may be deduced from the well known theorems of Egorychev and Falikman [8, 10] and Brégman [7]. (A result stronger than Fact 16 may be proved with the same method; here, we only state a result that is enough for our purposes.)

Fact 16. If r = r(n) satisfies log n ≪ r ≤ n/2 and rn is even for all n, then the number R(n, r) of labelled, r-regular graphs on n vertices satisfies

R(n, r) ≥ \binom{\binom{n}{2}}{rn/2}(1 − o(1))^{rn}.  (62)

Note that Fact 16 implies that the number of r-regular graphs on n vertices is the same as the number of graphs with n vertices and rn/2 edges, up to a factor of the form exp{−o(rn)}. We shall only give a brief sketch of the proof of Fact 16 here. (For an alternative proof, the reader is referred to Shamir and Upfal [19].)

Proof of Fact 16 (Sketch). For simplicity, we suppose that n and r are both even. First we examine the number Bip(n/2, r/2) of r/2-regular spanning subgraphs of K_{n/2,n/2}. In a standard way, using the theorems of Egorychev [8] and Falikman [10] that give a lower bound for the number of perfect matchings in regular bipartite graphs (van der Waerden’s conjecture) and a result of Brégman [7] that gives an upper bound for such a number (Minc’s conjecture), one may show that

Bip(n/2, r/2) ≥ \binom{n/2}{r/2}^{n/2}(1 − o(1))^{rn}.  (63)

Next, one observes that

R(n, r) ≥ ∏_{j≥1} [Bip (\frac{n}{2^{j}} , \frac{r}{2^{j}} )]^{2^{j−1}}  (64)

(for simplicity, divisibility conditions are ignored in (64)). One may derive (62) from (63) and (64). □

We may now prove Theorem 5.

Proof of Theorem 5. We first prove (i). Note that if r = 2, then the claimed bound (16) is trivial. Fix an integer r ≥ 3. In what follows, rn is supposed to be even.

Let N be a positive integer. The number of graphs that are of the form G(φ, D) with D ⊂ ℤ^{+} and with φ: [n] → ℤ^{+} such that im(φ) ⊂ [N] is

≤ \binom{N}{n} ∑_{1≤j≤rn/2} \binom{N − 1}{j},  (65)

as we have \binom{N}{n} choices for im(φ) and we may suppose D ⊂ [N − 1].

Now suppose that s_{r}(n) ≤ N. Then the quantity in (61) divided by n! has to be at most the quantity in (65). This gives that

(\sqrt{2} + o(1))e^{−(r^{2}−1)/4} (\frac{r^{r/2}}{e^{r/2}r!})^{n} \frac{n^{rn/2}}{n!} ≤ \binom{N}{n} ∑_{1≤j≤rn/2} \binom{N − 1}{j}. (66)

Let us now show that N ≥ rn. Suppose for a contradiction that N < rn. In this case, we get from (66) that

(\sqrt{2} + o(1))e^{−(r^{2}−1)/4} (\frac{r^{r/2}}{e^{r/2}r!})^{n} \frac{n^{rn/2}}{n!} ≤ \binom{rn}{n}2^{rn}.  (67)

Taking the nth root, we obtain from (67) that

\frac{r^{r/2}}{e^{r/2}r!}n^{r/2} ≤ rn2^{r},  (68)

which is clearly false for n ≥ n_{0}(r) because r ≥ 3. This contradiction shows that we do have N ≥ rn.

It follows from N ≥ rn that the quantity in (65) is

≤ \frac{1}{2}rn\binom{N}{n}\binom{N}{rn/2}.  (69)

From (66), we have

(\sqrt{2} + o(1))e^{−(r^{2}−1)/4} (\frac{r^{r/2}}{e^{r/2}r!})^{n} \frac{n^{rn/2}}{n!} ≤ \frac{1}{2}rn\binom{N}{n}\binom{N}{rn/2}.  (70)

Taking the nth root, we obtain

(1 + o(1))\frac{r^{r/2}}{e^{r/2}r!}en^{r/2−1} ≤ \frac{eN}{n} (\frac{2eN}{rn} )^{r/2} ,  (71)

whence

(1 + o(1))\frac{r^{r}}{2^{r/2}e^{r}r!}n^{r} ≤ N^{(r+2)/2}.  (72)

Therefore

N ≥ (1 + o(1)) (\frac{1}{r!})^{2/(r+2)} (\frac{r}{e\sqrt{2}})^{2r/(r+2)} n^{2r/(r+2)},  (73)

and (16) follows. This completes the proof of (i).

Let us now turn to the proof of (ii). Let r = r(n) as in the statement of the theorem be given. Clearly, it follows from the upper bound in (15) that s_{r}(n) ≤ (1 + o(1))n^{2}. We need to prove the reverse inequality.

Assume that, for some fixed ε > 0,

s_{r}(n) ≤ (1 − ε)n^{2} for arbitrarily large n.  (74)

We shall derive a contradiction from this assumption, and this will complete the proof of (17).

Lemma 12 tells us that if φ: [n] → ℤ^{+} is such that

im φ ⊂ [(1 − ε)n^{2}],  (75)

then there exists some σ > 0 for which we have

| Dist(φ)| < (1 − σ)\binom{n}{2}.  (76)

Thus, the total number of φ-graphs with φ satisfying (75) is, up to isomorphism, at most

\binom{n^{2}}{n} ∑_{j≤rn/2} \binom{(1 − σ)\binom{n}{2}}{j}.  (77)

We shall now compare (62) and (77). It will be convenient to consider separately two ranges for r. Case 1. r ≤ (1 − σ)(n − 1)/2

In this case, we bound the quantity in (77) from above by

\binom{n^{2}}{n}\frac{rn}{2}\binom{(1 − σ)\binom{n}{2}}{rn/2}.  (78)

Using that r ≫ log n, we see that the quantity in (78) is smaller than (62) for n ≥ n_{0}(σ). This contradicts (74), completing the proof in this case. Case 2. (1 − σ)(n − 1)/2 < r ≤ (n − 1)/2

In this case, we bound the quantity in (77) from above by

2^{(1−σ)\binom{n}{2}}(1 + o(1))^{n^{2}}.  (79)

However, examining (62), one sees that in this case the number of r-regular graphs is at least

\binom{\binom{n}{2}}{⌊((1 − σ)/2)\binom{n}{2}⌋}(1 − o(1))^{n^{2}}.  (80)

We shall estimate (80) using the following well known fact, which is a consequence of Stirling’s formula.

Fact 17. Let 0 < α < 1 be fixed and let m be a positive integer. Then

\binom{m}{⌊αm⌋} = [(\frac{1}{α})^{α} (\frac{1}{1 − α})^{1−α}]^{m} (1 + o(1))^{m},  (81)

where o(1) → 0 as m → ∞.

Applying Fact 17 to (80), we have that the number of r-regular graphs is at least

[(\frac{2}{1 − σ} )^{(1−σ)/2} (\frac{2}{(1 + σ)})^{(1+σ)/2}]^{\binom{n}{2}} (1 − o(1))^{n^{2}}.  (82)

As in the first case, assumption (74) tells us that the quantity in (79) should be at least as large as the quantity in (82), that is,

[(\frac{2}{1 − σ} )^{(1−σ)/2} (\frac{2}{(1 + σ)})^{(1+σ)/2}]^{\binom{n}{2}} ≤ 2^{(1−σ)\binom{n}{2}}(1 + o(1))^{n^{2}}. (83)

We shall now see that (83) does not hold if n ≥ n_{0}(σ).

Keeping in mind that σ > 0 is a constant and n tends to infinity, inequality (83) simplifies to

(\frac{1 − σ}{2} ) log_{2} \frac{2}{1 − σ} + (\frac{1 + σ}{2} ) log_{2} \frac{2}{1 + σ} ≤ 1 − σ.  (84)

Equivalently,

(\frac{1 − σ}{2} ) (1 − log_{2}(1 − σ)) + (\frac{1 + σ}{2} ) (1 − log_{2}(1 + σ)) ≤ 1 − σ; (85)

that is,

(1 − σ) log_{2}(1 − σ) + (1 + σ) log_{2}(1 + σ) − 2σ ≥ 0.  (86)

Let

f(σ) = (1 − σ) log_{2}(1 − σ) + (1 + σ) log_{2}(1 + σ) − 2σ.  (87)

Note that f(0) = 0 and

f′(σ) = log_{2} (\frac{1 + σ}{1 − σ} ) − 2 < 0.  (88)

This implies that f is decreasing for σ ∈ (0, \frac{1}{2}]. Hence, for any small σ > 0, the inequalities given in (83)–(86) fail for n ≥ n_{0}(σ). Thus, as in Case 1, assumption (74) cannot hold. This completes the proof of Case 2, and hence (ii) of Theorem 5 is proved. □

4.2. Proof of Theorem 6. We now consider the ‘multiplicity’ parameter μ(n).

Proof of Theorem 6. We wish to show that there exists a graph G such that for any φ: [n] → ℤ^{+} such that G is a φ-graph, no element of Dist(φ) has cardinality 2 + 8 log_{2} n or more.

Suppose φ: [n] → ℤ^{+} is an injective function such that ∼_{φ} has an equivalence class C ⊂ \binom{[n]}{2} of cardinality μ ≥ 2 + 8 log_{2} n. It is clear that C spans a disjoint union of paths on [n]. Therefore, there is a matching M ⊂ C with |M| ≥ |C|/2. Let ν = |M| ≥ 1 + 4 log_{2} n. Considering this matching, one sees that there are 2ν distinct integers

x_{1} < y_{1}, x_{2} < y_{2}, …, x_{ν} < y_{ν}  (89)

in im(φ) with all the differences y_{i} − x_{i} (1 ≤ i ≤ ν) equal.

Clearly, by the definition of G(φ, D), regardless of D, the subgraphs of G(φ, D) induced by the x_{i} (1 ≤ i ≤ ν) and the y_{i} (1 ≤ i ≤ ν) are isomorphic. To prove our theorem, namely, to verify (18), it suffices to prove the following fact.

Fact 18. For all large enough n, there is an n-vertex graph G that does not contain two vertex disjoint, isomorphic induced subgraphs of order ν ≥ 1 + 4 log_{2} n.

Proof. Consider the binomial random graph G = G(n, p) with p = 1/2, and let ν = ν(n) ≥ 1 + 4 log_{2} n be given. Let X_{ν} = X_{ν}(G) be the number of pairs (H, H′) of induced subgraphs of G of order ν with H isomorphic to H′. Then

ℙ(X_{ν} > 0) ≤ 𝔼(X_{ν}) < n^{2ν}2^{−\binom{ν}{2}} = (n^{2}2^{−(ν−1)/2})^{ν} ≤ 1,  (90)

and therefore a graph as required does exist. □

As observed above, Fact 18 concludes the proof of Theorem 6. □

5. Proofs of Theorems 7, 8, and 9

Let us now prove our results concerning the number of distances in our representations of graphs. Before we proceed, we make the following remark on the number of graphs that may be ‘generated’ from a given φ. Remark 19. (i) Fix φ: [n] → ℤ^{+}. Then

|{G(φ, D): D ⊂ ℤ^{+}}| ≤ 2^{| Dist(φ)|}.  (91)

(ii) Fix φ: [n] → ℤ^{+} and let D be an integer. Then

|\{G(φ, D): |D| ≤ D\}| ≤ ∑_{j=0}^{D} \binom{| Dist(φ)|}{j} ≤ ∑_{j=0}^{D} \binom{\binom{n}{2}}{j}.  (92)

5.1. Proofs of Theorems 7 and 8. We start with our result concerning D(n).

Proof of Theorem 7. We wish to show that for any ε > 0 and any n ≥ n_{0}(ε), there exists a graph G on n vertices such that whenever G is a φ-graph we have

| Dist(φ)| > \binom{n}{2} − 4n log_{2} n + 2n − \frac{1}{2} log_{2}(2πn) − ε.

Let D = \binom{n}{2} − 4n log_{2} n + 2n − (1/2) log_{2}(2πn) − ε, where ε > 0 is an arbitrary fixed constant, and suppose for a contradiction that D(n) ≤ D. Note that if φ: [n] → ℤ^{+} is such that | Dist(φ)| ≤ D, then, by Remark 19(i), we have

|\{G(φ, D): D ⊂ ℤ^{+}\}| ≤ 2^{| Dist(φ)|} ≤ \frac{1}{2^{ε}\sqrt{2πn}}2^{\binom{n}{2}}n^{−4n}4^{n}.  (93)

By Lemma 13, as we let φ: [n] → ℤ^{+} vary, we have

T (n) ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n}  (94)

distinct ∼_{φ}. By (93) and (94), if we only consider φ: [n] → ℤ^{+} with | Dist(φ)| ≤ D, we are able to produce

≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} (\frac{4}{n^{4}} )^{n} \frac{2^{\binom{n}{2}}}{2^{ε}\sqrt{2πn}} = (1 + o(1)) (\frac{e}{n})^{n} \frac{2^{\binom{n}{2}}}{2^{ε}\sqrt{2πn}} (95)

non-isomorphic graphs. On the other hand, using Stirling’s formula n! = (1 + o(1))(n/e)^{n}\sqrt{2πn}, we see that there are

≥ \frac{1}{n!}2^{\binom{n}{2}} ≥ \frac{1 + o(1)}{\sqrt{2πn}} (\frac{e}{n})^{n} 2^{\binom{n}{2}}  (96)

graphs on n vertices up to isomorphism. According to our assumption that D(n) ≤ D, the quantity in (95) must be at least the quantity in (96), which is not the case for n ≥ n_{0}(ε). This completes the proof of Theorem 7. □

Proof of Theorem 8. We shall prove that for almost all graphs G on n vertices, if G is a D-graph, then

|D| ≥ \frac{1}{2}\binom{n}{2} − (1 + o(1))n^{3/2}\sqrt{log n}.  (97)

The proof of this result follows the same steps as the proof of Theorem 7, except that we shall make use of Remark 19(ii) instead of Remark 19(i).

For any given k, let us consider all D-graphs for all D ⊂ ℤ^{+} such that

|D| ≤ D = \frac{1}{2}\binom{n}{2} − k.  (98)

By Remark 19(ii) and Lemma 13, the number of such graphs is, up to isomorphism,

≤ T (n) ∑_{j=0}^{D} \binom{\binom{n}{2}}{j} ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} ∑_{j=0}^{D} \binom{\binom{n}{2}}{j}

≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} 2^{\binom{n}{2}} exp \{−2k^{2}\binom{n}{2}^{−1}\} , (99)

where in the last inequality we used that

∑_{j=0}^{⌈N/2−a⌉} \binom{N}{j} ≤ 2^{N}e^{−2a^{2}/N}  (100)

for all integers N ≥ 1 and all real a (see, e.g., [1, Theorem A.1]). From (99), we see that if, for some ε > 0, an ε-fraction of the graphs on n vertices are such that D_{e}(G) ≤ \frac{1}{2} \binom{n}{2} − k, then we must have

\frac{ε}{\sqrt{2πn}} (\frac{e}{n})^{n} 2^{\binom{n}{2}} ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} 2^{\binom{n}{2}} exp \{−2k^{2}\binom{n}{2}^{−1}\} , (101)

which tells us that

\frac{ε}{\sqrt{2πn}} (\frac{4}{n^{4}} )^{n} ≤ (1 + o(1)) exp \{−2k^{2}\binom{n}{2}^{−1}\} .  (102)

Therefore, for large enough n, we have, say,

\frac{2}{ε}\sqrt{πn} (\frac{n^{4}}{4} )^{n} ≥ exp \{2k^{2}\binom{n}{2}^{−1}\} ,  (103)

and hence

2k^{2} ≤ \binom{n}{2} (4n log n − n log 4 + \frac{1}{2} log(πn) + log \frac{2}{ε}) ,  (104)

which tells us that

k ≤ (1 + o(1))n^{3/2}\sqrt{log n}.  (105)

As ε > 0 was arbitrary, this concludes the proof. □

5.2. Proof of Theorem 9. The proof of our result on D_{e}(n), related to the number of ‘edge lengths’ in our representations of graphs, will be somewhat more technical.

5.2.1. Preliminary lemmas. In this section, we shall state and prove two simple inequalities related to a certain enumeration problem for an algebra of sets. Suppose we have a set X of cardinality N, and suppose we have an equivalence relation ∼ defined on X. We are interested in the sets that may be obtained by taking unions of equivalence classes of ∼. In fact, we are interested in such unions that have a given cardinality T. In what follows, we shall have N = \binom{n}{2} and T quite close to \binom{n}{2}.

Both the statement and the proof of our first lemma are purely numerical, and hence we postpone its combinatorial interpretation (see the discussion after the proof of Lemma 20).

Let a pair of non-negative integers b = (b_{1}, b_{2}) such that

b_{1} + 2b_{2} = \binom{n}{2}  (106)

be given. For all non-negative integers T and real g ≥ 0, we let

c(b; T, g) = c(b_{1}, b_{2}; T, g) = ∑ \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}},  (107)

where the sum is over all integers t_{1} and t_{2} such that t_{1}+2t_{2} = T, and t_{2} ≥ g. Note that, in (107), we may ignore the terms with t_{2} > b_{2}. In what follows, we always suppose that g ≤ t_{2} ≤ b_{2}.

Lemma 20. Let ω = ω(n) → ∞ as n → ∞, and suppose ω = o(\sqrt{n/ log n}). For any b = (b_{1}, b_{2}) as above, if g ≥ ωn^{3/2}\sqrt{log n} and

T = \binom{n}{2} − ⌈ωn^{3/2}\sqrt{log n}⌉ ,  (108)

then

c(b_{1}, b_{2}; T, g) ≤ n^{−ωn}\binom{\binom{n}{2}}{T}  (109)

for all large enough n.

Proof. We start by splitting the sum in (107) into two parts. Let us write ∑_{1} for the sum over all integers t_{1} and t_{2} such that t_{1} + 2t_{2} = T, t_{2} ≥ g, and, moreover,

\binom{b_{2}}{t_{2}} ≥ 2n^{ωn}.  (110)

Let ∑_{2} denote the sum over the remaining pairs (t_{1}, t_{2}) in (107). Therefore,

c(b_{1}, b_{2}; T, g) = ∑_{1} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}} + ∑_{2} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}}.  (111)

The first sum in (111) may be easily estimated from above, since

2n^{ωn} ∑_{1} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}} ≤ ∑_{1} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}}^{2}

≤ ∑_{1} \binom{b_{1}}{t_{1}}\binom{2b_{2}}{2t_{2}} ≤ \binom{\binom{n}{2}}{T}. (112)

Let us now consider the second sum in (111); that is, let us now consider t_{1} and t_{2} for which we have \binom{b_{2}}{t_{2}} < 2n^{ωn}. We shall estimate the terms

\binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}} < 2n^{ωn}\binom{b_{1}}{t_{1}}  (113)

by bounding \binom{b_{1}}{t_{1}}. Let us first derive some conclusions from the fact that \binom{b_{2}}{t_{2}} < 2n^{ωn}. Suppose b_{2} ≥ 2t_{2}. Then

2^{t_{2}} ≤ (\frac{b_{2}}{t_{2}} )^{t_{2}} ≤ \binom{b_{2}}{t_{2}} < 2n^{ωn},  (114)

and hence g ≤ t_{2} < 1+ωn log_{2} n, which is a contradiction for large enough n. Therefore, we have b_{2} = t_{2} + s with 0 ≤ s < t_{2}. But then

2^{s} ≤ (\frac{b_{2}}{s} )^{s} ≤ \binom{b_{2}}{s} = \binom{b_{2}}{t_{2}} < 2n^{ωn},  (115)

whence

s < 1 + ωn log_{2} n.  (116)

For convenience, put N = \binom{n}{2}. Now observe that

\binom{b_{1}}{t_{1}} = \binom{N − 2b_{2}}{T − 2t_{2}} = \binom{N}{T}\frac{(N − T)_{2(b_{2}−t_{2})}(T)_{2t_{2}}}{(N)_{2b_{2}}}

= \binom{N}{T}\frac{(N − T)_{2s}}{(N)_{2s}} \frac{(T)_{2t_{2}}}{(N − 2s)_{2t_{2}}} . (117)

By (108), (116), and the fact that ω = o(\sqrt{n/ log n}), the quantity in (117) is

≤ \binom{N}{T} (\frac{N − T}{N} )^{2s} (\frac{T}{N − 2s})^{2t_{2}}

≤ \binom{N}{T} (\frac{⌈ωn^{3/2}\sqrt{log n}⌉}{N})^{2s} (\frac{N − ωn^{3/2}\sqrt{log n}}{N − 2(1 + ωn log_{2} n)})^{2t_{2}}

≤ \binom{N}{T} (\frac{1 − 2ω\sqrt{(log n)/n}}{1 − (5ω log_{2} n)/n})^{2b_{2}} ≤ \binom{N}{T} (1 − ω\sqrt{\frac{log n}{n}})^{2b_{2}} , (118)

for all sufficiently large n. Using that b_{2} ≥ t_{2} ≥ g ≥ ωn^{3/2}\sqrt{log n}, we see that the quantity in (118) is

≤ \binom{N}{T} exp (−2ω^{2}n log n) = n^{−2ω^{2}n}\binom{N}{T}.  (119)

Therefore,

∑_{2} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}} < 2T n^{−2ω^{2}n+ωn}\binom{\binom{n}{2}}{T} < \frac{1}{2}n^{−ωn}\binom{\binom{n}{2}}{T}.  (120)

Putting together (111), (112), and (120), we get that

c(b_{1}, b_{2}; T, g) = ∑_{1} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}} + ∑_{2} \binom{b_{1}}{t_{1}}\binom{b_{2}}{t_{2}} ≤ n^{−ωn}\binom{\binom{n}{2}}{T}, (121)

as required. □

We may interpret Lemma 20 as follows. Suppose we have a partition of \binom{[n]}{2} into b_{1} blocks of cardinality 1 and b_{2} blocks of cardinality 2. Let us call a set E ⊂ \binom{[n]}{2} compatible with this partition if E is a union of blocks of this partition. We are interested in compatible, T -element subsets E of \binom{[n]}{2}, with the further restriction that we now describe.

For each such set E, let us say that we pay i − 1 pence for every block of cardinality i that we use in the decomposition of E as a union of blocks. In the function c(b; T, g) defined in (107), we are only counting those sets E for which we pay at least g pence, and Lemma 20 tells us that not many sets E cost at least g.

In our next lemma, we consider a general partition π of \binom{[n]}{2}, with b_{i} blocks of cardinality i (i ≥ 1). Lemma 21 tells us that the number of T - element subsets E of \binom{[n]}{2} with cost ≥ 2g, compatible with π, is dominated by the number of T -element subsets E of \binom{[n]}{2} with cost ≥ g, compatible with π′, a certain partition with blocks of cardinality 1 and 2 only.

Let us describe the setup that we consider in Lemma 21, which is, in fact, a purely numerical result. Suppose we have a sequence b = (b_{1}, b_{2}, …) of non-negative integers such that

b_{1} + 2b_{2} + 3b_{3} + ⋯ = \binom{n}{2}.  (122)

For all non-negative integers T and real g ≥ 0, we let

C(b; T, g) = C(b_{1}, b_{2}, …; T, g) = ∑ ∏_{i≥1} \binom{b_{i}}{t_{i}},  (123)

where the sum is over all sequences t = (t_{1}, t_{2}, …) of non-negative integers such that

t_{1} + 2t_{2} + 3t_{3} + ⋯ = T  (124)

and

t_{2} + 2t_{3} + 3t_{4} + ⋯ = ∑_{i≥2}(i − 1)t_{i} ≥ g.  (125)

Given b = (b_{1}, b_{2}, …) as above, let b′_{1} and b′_{2} be given by

b′_{1} = b_{1} + b_{3} + b_{5} + ⋯ = ∑_{k≥0} b_{2k+1}  (126)

and

b′_{2} = b_{2} + b_{3} + 2b_{4} + 2b_{5} + ⋯ = ∑_{k≥2} ⌊\frac{k}{2} ⌋ b_{k}.  (127)

Note that, then, we have

b′_{1} + 2b′_{2} = \binom{n}{2}.  (128)

Lemma 21. Let b, T, and g be as above. Then

C(b; T, 2g) ≤ c(b′_{1}, b′_{2}; T, g).  (129)

Proof. Consider a partition π of \binom{[n]}{2} into b_{i} blocks of size i for all i ≥ 1. Then π induces another partition π′ of \binom{[n]}{2} into b′_{1} blocks of size 1 and b′_{2} blocks of size 2, where b′_{1} and b′_{2} are as in (126) and (127). We construct π′ from π by arbitrarily decomposing every block of size 2k into k blocks of size 2, and arbitrarily decomposing every block of size 2k + 1 into one singleton block and k blocks of size 2.

Consider E, any T -element subset of \binom{[n]}{2} that is a union of blocks from π. Then, clearly, E is a T -element subset composed solely of blocks from π′. It remains to show that if E has ‘cost’ at least 2g in π, then G has cost at least g in π′.

Consider any block with 2k + 1 elements contained in E. In π, such a block would cost 2k pence. The corresponding blocks in π′ would consist of a singleton block and k blocks of size 2, and hence cost only k pence in total. Similarly, a block of size 2k in π would cost 2k − 1 pence, while the corresponding k blocks of size 2 in π′ would also cost k pence in total. This implies that the cost of any block in π is reduced by at most half in π′.

Thus, if the total cost of E is at least 2g pence in π, then E would cost at least g pence in π′, and the result holds. □

5.2.2. The proof. Having dealt with the technical lemmas in Section 5.2.1, the proof of Theorem 9 will be straightforward. Recall that we wish to show that for any sufficiently large n and ω = ω(n) such that ω(n) → ∞ as n → ∞, there exists a graph G on n vertices such that whenever G is a D-graph, then

|D| ≥ \binom{n}{2} − 3ωn^{3/2}\sqrt{log n} − 3.

Proof of Theorem 9. Let ω = ω(n) as in the statement of our theorem be given. We may clearly suppose that ω = o(\sqrt{n/ log n}).

Fix φ: [n] → ℤ^{+}, and consider the equivalence relation ∼_{φ} defined on \binom{[n]}{2}. Let b = (b_{1}, b_{2}, …), where b_{i} (i ≥ 1) is the number of blocks, i.e., equivalence classes, of ∼_{φ} with cardinality i.

Let us write G(n, T) for the class of n-vertex graphs with T edges, up to isomorphism, where

T = \binom{n}{2} − ⌈ωn^{3/2}\sqrt{log n}⌉ .  (130)

We have

|G(n, T)| ≥ \frac{1}{n!}\binom{\binom{n}{2}}{T}.  (131)

Let

g = ⌈ωn^{3/2}\sqrt{log n}⌉  (132)

and observe that the number of graphs in G(n, T) that are isomorphic to some G(φ, D) (D ⊂ ℤ^{+}) with

T − |D| ≥ 2g = 2 ⌈ωn^{3/2}\sqrt{log n}⌉  (133)

is

≤ C(b; T, 2g) ≤ n^{−ωn}\binom{\binom{n}{2}}{T},  (134)

where the second inequality in (134) follows from Lemmas 20 and 21.

Recall that we are considering a fixed φ: [n] → ℤ^{+}. However, as we consider all φ: [n] → ℤ^{+}, we only have

T (n) ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n}  (135)

distinct equivalence relations (see (39) and Lemma 13). Therefore, using (134) and (135), we see that the number of graphs in G(n, T) that are D-graphs with D satisfying (133) is

≤ T (n)C(b; T, 2g) ≤ (1 + o(1)) (\frac{en^{3}}{4} )^{n} n^{−ωn}\binom{\binom{n}{2}}{T},  (136)

which is a great deal smaller than the lower bound given in (131). This shows that there is a graph G_{0} in G(n, T) such that if G_{0} is isomorphic to G(φ, D) for some φ: [n] → ℤ^{+} and D ⊂ ℤ^{+}, then T − |D| < 2g. This graph G_{0} shows that

D_{e}(n) = max_{G} D_{e}(G) > T − 2g

= T − 2 ⌈ωn^{3/2}\sqrt{log n}⌉ > \binom{n}{2} − 3ωn^{3/2}\sqrt{log n} − 3, (137)

as required. □

5.3. Proof of Corollary 10. Corollary 10 follows from Theorem 9 and Lemma 12.

Proof of Corollary 10. Let ε > 0 and ω = ω(n) → ∞ as n → ∞ be given. Recall Theorem 9, and let n be large enough so that there is an n-vertex graph G for which we have

D_{e}(G) ≥ \binom{n}{2} − 3ωn^{3/2}\sqrt{log n} − 3.  (138)

Let φ: [n] → ℤ^{+} and D ⊂ ℤ^{+} be such that G is isomorphic to G(φ, D). We may clearly suppose that

| Dist(φ)| ≥ |D|.  (139)

We shall show that max im(φ) is at least as large as the right-hand side of (23) if n is sufficiently large, and this will conclude the proof of Corollary 10.

Inequalities (138) and (139) imply that | Dist(φ)| is at least as large as the right-hand side of (138). Therefore (27) in Lemma 12 holds with ε = (6 + o(1))ω\sqrt{(log n)/n}, and hence that lemma implies that

max im(φ) ≥ (1 − (2\sqrt{6} + o(1))ω^{1/2} (\frac{log n}{n})^{1/4}) n^{2}.  (140)

The result follows by taking n ≥ n_{0}(ε). □

6. Concluding remarks

Theorems 8 and 9 may be generalized to representations of graphs in high-dimensional Euclidean spaces. More precisely, we consider the graphs G(φ, D), but now with φ: [n] → ℝ^{d} and D ⊂ ℝ. Let

D_{e}^{ℝ}(d, G) = min{|D|: D ⊂ ℝ for which ∃φ ∈ (ℝ^{d})^{[n]}

such that G is isomorphic to G(φ, D)}, (141)

Note that, even for d = 2, it becomes easier to represent graphs in the form G(φ, D) in ℝ^{d}: an immediate argument shows that any tree may be drawn on the plane in such a way that all edges are straight lines of length 1, and no two non-adjacent vertices are at distance 1. Therefore, D_{e}^{ℝ}(2, T) = 1.

We mention that bounded degree graphs may be represented in bounded dimension: as proved in [15], if a graph G has maximum degree Δ, then D_{e}^{ℝ}(2Δ, G) = 1.

Let us now put D_{e}^{ℝ}(d, n) = max_{G} D_{e}^{ℝ}(d, G), where the maximum is taken over all n-vertex graphs.

As long as d = o(n/ log n), a bound similar to the one in Theorem 9 holds for D_{e}^{ℝ}(d, n). Moreover, one may also prove a bound similar to the one in Theorem 8 for D_{e}^{ℝ}(d, G) for almost all n-vertex graphs G. To prove these results, one may use a well known result of Warren [21].

In addition to these higher-dimensional remarks, one may consider several problems. First, is it possible to pair the lower bounds on D(n) or D_{e}(n) with similar upper bounds? Can one give a non-trivial bound from below for μ(n)?

It seems that a challenging problem is to find a non-trivial upper bound on s_{r}(n) or, in fact, to bound the spacing numbers of any broad class of graphs from above. In [2, Remark 7.2], a problem of representing trees in a similar manner is considered, and remains open.

It was demonstrated above (via K_{1,n}) that determining the spacing number of even very simple graphs may be somewhat delicate. It would be of some interest to find exactly the spacing numbers of more graphs.

Acknowledgements. The authors would like to thank John Schmitt and Brian Wagner for their help in proving Proposition 2. We would also like to extend our thanks to B. Bollobás, A. Kostochka, N. Linial, and O. Pikhurko for their helpful questions and remarks. We are greatly appreciative for the input of N. Wormald on the enumeration of regular graph. Finally, many thanks to the referee for several excellent suggestions.

References

1. Noga Alon and Joel H. Spencer, The probabilistic method, John Wiley & Sons Inc., New York, 1992, With an appendix by Paul Erdős, A Wiley-Interscience Publication. MR 93h:60002 5.1

2. László Babai and Vera T. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin. 6 (1985), no. 2, 101–114. MR 87f:05081 1, 1.1, 6

3. R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562. MR 2002f:11125 4.1

4. E. Bender and E.R. Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 296–307. MR 58 #21793 4.1

5. Béla Bollobás, Random graphs, second ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 2002j:05132 4.1 6. Béla Bollobás and Oleg Pikhurko, Integer sets with prescribed pairwise differences

being distinct, manuscript, 12pp, 2003. 1, 3.1

7. L. M. Brègman, Certain properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR 211 (1973), 27–30. MR 48 #6130 4.1, 4.1

8. G. P. Egoryčev, Reshenie problemy van-der-Vardena dlya permanentov, Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., Krasnoyarsk, 1980, Preprint IFSO-13 M. MR 82e:15006 4.1, 4.1

9. P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215. 3.1, 3.1, 3.1

10. D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981), no. 6, 931–938, 957. MR 82k:15007 4.1, 4.1

11. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, second ed., Addison-Wesley Publishing Company, Reading, MA, 1994, A foundation for computer science. MR 97d:68003 3.2

12. Heini Halberstam and Klaus Friedrich Roth, Sequences, second ed., Springer-Verlag, New York, 1983, MR83m:10094. 4.1

13. Bernt Lindström, An inequality for B_{2}-sequences, J. Combinatorial Theory 6 (1969), 211–212. MR 38 #4436 3.1

14. , On B_{2}-sequences of vectors, J. Number Theory 4 (1972), 261–265. MR 46 #3322 3.1

15. Hiroshi Maehara and Vojtěch Rödl, On the dimension to represent a graph by a unit distance graph, Graphs Combin. 6 (1990), no. 4, 365–367. MR 91m:05176 6

16. Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n^{1/2}), Combinatorica 11 (1991), no. 4, 369–382. MR 93e:05002 4.1

17. Oleg Pikhurko, Dense edge-magic graphs and thin additive bases, submitted, 2003. 1 18. L. Rónyai, L. Babai, and M.K. Ganapathy, On the number of zero-patterns of a

sequence of polynomials, J. Amer. Math. Soc. 14 (2001), no. 3, 717–735. MR 2002f:11026 3.2

19. E. Shamir and E. Upfal, Large regular factors in random graphs, Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., vol. 87, North-Holland, Amsterdam, 1984, pp. 271–282. MR 86k:05104 4.1

20. James Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), no. 3, 377–385. MR 1 501 951 4.1

21. Hugh E. Warren, Lower bounds for approximation by nonlinear manifolds, Trans. Amer. Math. Soc. 133 (1968), 167–178. MR 37 #1871 6

(Y. Kohayakawa) Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, Brazil

E-mail address: yoshi@ime.usp.br

(M. Ferrara and V. Rödl) Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA

E-mail address: {mferrar|rodl}@mathcs.emory.edu