%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTex file for                                                  %
%                                                                    %
% Distance graphs on the integers                                    %
%                                                                    %
% by M. Ferrara, Y. Kohayakawa, and V. R\"odl                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 08 Jan 2004 12:53:50pm BRST yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%\usepackage{refcheck}
%\usepackage{doublespace}
\usepackage[colorlinks,backref]{hyperref} 
\usepackage{srcltx}
\usepackage{changebar}

%\def\ykcomm#1{\marginpar{\footnotesize\textsf{yk:} #1}}
%\def\mfcomm#1{\marginpar{\small\textsf{mf:} #1}}
%\def\ykcomm#1{}

%========================= Theorem .... styles ===============================
%From thmtest.tex, probably
\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below 
  {\sl}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\itshape}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\newtheoremstyle{introthms}% name
  {3pt}%      Space above, empty = `usual value'
  {3pt}%      Space below
  {\itshape}% Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\bfseries}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {\thmnote{#3}}% Thm head spec

\theoremstyle{plain}
\newtheorem{theorem}              {Theorem} 
\newtheorem{algorithm}  [theorem] {Algorithm}
\newtheorem{axiom}      [theorem] {Axiom}      
\newtheorem{claim}      [theorem] {Claim}
\newtheorem{conjecture} [theorem] {Conjecture} 
\newtheorem{corollary}  [theorem] {Corollary} 
\newtheorem{fact}       [theorem] {Fact}    
\newtheorem{lemma}      [theorem] {Lemma}         
\newtheorem{problem}    [theorem] {Problem} 
\newtheorem{proposition}[theorem] {Proposition}
  
\theoremstyle{note}
\newtheorem{remark}    [theorem] {Remark}
\newtheorem{case}                {Case}  
\newtheorem{criterion} [theorem] {Criterion}
\newtheorem{definition}[theorem] {Definition}       
\newtheorem{example}   [theorem] {Example} 
\newtheorem{notation}  [theorem] {Notation}
\newtheorem{note}      [theorem] {Note}       
\newtheorem{minorclaim}          {Claim}
   
\theoremstyle{introthms}
\newtheorem*{varthm}{}% all text supplied in the note
%========================= Theorem .... styles ===============================

%========================= DRAFT =============================================
%\draft % Uncomment for double spaced draft text, with draft line printed
        % at the bottom of the page.
%next lines that is my style draft:
%\special{!userdict begin /bop-hook{gsave 440 25 translate 45 rotate 2
%setlinewidth /Times-Roman findfont 60 scalefont setfont 0 0 moveto
%0.9 setgray (DRAFT) show -100 -10 moveto 400 -10 lineto stroke
%-200 52 moveto 400 52 lineto stroke grestore}def end}

%========================= paper specific macros =============================
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\langle}
\def\>{\rangle}
\let\:\colon
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}
\def\rmd{\text{\rm d}}
\def\wtc{\widetilde{c}\,}
\def\whc{\widehat{c}}
\def\bfb{{\mathbf b}}
\def\bff{{\mathbf f}}
\def\bft{{\mathbf t}}
\def\bfx{{\mathbf x}}
\def\bfz{{\mathbf z}}
\def\cB{{\mathcal B}}
\def\cD{{\mathcal D}}
\def\cG{{\mathcal G}}
\def\cM{{\mathcal M}}
\def\cN{{\mathcal N}}
\def\cR{{\mathcal R}}
\def\cS{{\mathcal S}}
\def\cW{{\mathcal W}}
\def\PP{{\mathbb P}}
\def\EE{{\mathbb E}}
\def\FF{{\mathbb F}}
\def\NN{{\mathbb N}}
\def\RR{{\mathbb R}}
\def\ZZ{{\mathbb Z}}
\def\e{{\rm e}}
\def\card{\mathop{\text{\rm card}}\nolimits}
\def\rank{\mathop{\text{\rm rank}}\nolimits}
\def\trace{\mathop{\text{\rm trace}}\nolimits}
\def\Ave{\mathop{\text{\rm Ave}}\nolimits}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\im{\mathop{\text{\rm im}}\nolimits}
\def\ind{\mathop{\text{\rm ind}}\nolimits}
\def\dist{\mathop{\text{\rm dist}}\nolimits}
\def\Dist{\mathop{\text{\rm Dist}}\nolimits}
\def\De{D_{\rm e}}
\def\sumL{\sum\nolimits_1}
\def\sumS{\sum\nolimits_2}
\def\Bip{\mathop{\text{\rm Bip}}\nolimits}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\let\tilde=\widetilde
%========================= paper specific macros =============================

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Distance graphs]%
{Distance graphs on the integers}
\author{M.~Ferrara}

\author{Y.~Kohayakawa}
\address{(Y.~Kohayakawa)\quad Instituto de Matem\'atica e Estat\'{\i}stica,
  Universidade de S\~ao Paulo, Rua do Mat\~ao 1010, 05508--090~S\~ao Paulo,
  Brazil}  
\email{yoshi@ime.usp.br}
\author{V.~R\"odl}
\address{(M.~Ferrara and V.~R\"odl)\quad Department of Mathematics and
  Computer Science, Emory University, Atlanta, GA 30322, USA}
\email{$\{$mferrar|rodl$\}$@mathcs.emory.edu}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thanks{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
%  on leave from Instituto de Matem\'atica e Estat\'{\i}stica, Universidade de
%  S\~ao Paulo, Rua do Mat\~ao 1010, 05508--090~S\~ao Paulo, Brazil,
%  and was
  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).}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subjclass{%
  Primary: %
  05C62. %                  % Graph representations (geometric and
                            % intersection representations, etc.) 
  Secondary:
  11B75}%,                  % Other combinatorial number theory
%}
\keywords{Sidon sets, geometric representations of graphs}
%\date{\bf Needs revision; not for circulation.  Version of 22 July 2003}
\date{8 January 2004}
%\date{\today}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\dedicatory{Dedicated to the memory of Professor Walter Deuber on the   
occasion of his 60th birthday}

\begin{abstract}
  We consider several extremal problems concerning representations of graphs
  as \textit{distance graphs} on the integers.  Given a graph $G=(V,E)$, we
  wish to find an injective function $\phi\:V\to\ZZ^+=\{1,2,\dots\}$ and a
  set~$\cD\subset \ZZ^+$ such that $\{u,v\}\in E$ if and only if
  $|\phi(u)-\phi(v)|\in \cD$.
  
  Let~$s(n)$ be the smallest~$N$ such that any graph~$G$ on~$n$ vertices
  admits a representation~$(\phi_G,\cD_G)$ such that~$\phi_G(v)\leq N$ for
  all~$v\in V(G)$.  We show that~$s(n)=(1+o(1))n^2$ as~$n\to\infty$.  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~$(\phi_G,\cD_G)$ such
  that~$\phi_G(v)\leq N$ for all~$v\in V(G)$, then~$s_r(n)=(1+o(1))n^2$
  as~$n\to\infty$ for any~$r=r(n)\gg\log n$ with~$rn$ even for all~$n$.
  
  Given a graph~$G=(V,E)$, let~$\De(G)$ be the smallest possible cardinality
  of a set~$\cD$ for which there is some~$\phi\:V\to\ZZ^+$ so
  that~$(\phi,\cD)$ represents~$G$.  We show that, for almost all $n$-vertex
  graphs~$G$, we have
  \begin{equation*}
    \De(G)\geq{1\over2}{n\choose2}-(1+o(1))n^{3/2}(\log n)^{1/2},
  \end{equation*}
  whereas for some $n$-vertex graph~$G$, we have
  \begin{equation*}
    \De(G)\geq{n\choose2}-n^{3/2}(\log n)^{1/2+o(1)}.
  \end{equation*}
  Further extremal problems of similar nature are considered.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\maketitle
\thispagestyle{empty}
%\tableofcontents

\section{Introduction and statement of the main results}
\label{sec:defs_results}
We are interested in representing a graph $G=(V,E)$ by assigning to each
vertex $v\in V$ an integer $\phi(v)$ so that we can then distinguish those
pairs of vertices $u$, $v$ that are edges from those that are not simply by
$|\phi(u)-\phi(v)|$.  In other words, for each graph~$G=(V,E)$ we wish to find
a function $\phi\:V\to\ZZ^+=\{1,2,\dots\}$ and a set~$\cD\subset \ZZ^+$ so
that $\{u,v\}\in E$ if and only if $|\phi(u)-\phi(v)|\in \cD$.

We shall investigate numerical parameters associated with such
representations~$(\phi,\cD)$ of~$G$.  A basic question is to determine or
estimate the smallest possible value for~$\max\{\phi(v)\:v\in V(G)\}$ for
a given graph~$G$, when we let~$\phi$ and~$\cD$ vary freely.  We denote this
value by~$s(G)$ (see~\eqref{eq:s_def}).  Let~$s(n)=\max_Gs(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~\ref{thm:s(n)_lwbd}).

We shall also investigate the size of the sets~$\cD$ that we need, both for
individual graphs and when considering all graphs on a fixed number of
vertices.  Other parameters pertaining to the function~$\phi$, which may be of
some interest on their own, will also be considered (see Lemmas~\ref{lem:ET}
and~\ref{lem:T(n)_upbd}).

%\begin{changebar}
We are grateful to B.~Bollob\'as and O.~Pikhurko for letting us know that
problems and results of nature similar to the ones considered here appear
in~\cite{bollobas03:_integ} and~\cite{pikhurko03:_dense}.
  
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\'os~\cite{babai:cayley2} 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 \textit{integers} is already of some interest.
%\end{changebar}

\subsection{Definitions}
\label{sec:defs}
We shall consider integer functions
\begin{equation}
  \label{eq:general_phi}
  \phi\colon[n]\to \ZZ^+
\end{equation}
with domain~$[n]=\{1,\dots,n\}$.  In what follows, the asymptotics will be
with respect to~$n\to\infty$.  A map~$\phi$ as in~\eqref{eq:general_phi}
defines an equivalence relation
\begin{equation}
  \label{eq:equiv_rel_def}
  \sim_\phi 
\end{equation}
on ${[n]\choose2}$, the edge set of the complete graph~$K_n$ with vertex
set~$[n]$, given by
\begin{equation}
  \label{eq:equiv_def}
  \{i,j\}\sim_{\phi}\{k,\ell\}
  \iff
  |\phi(i)-\phi(j)|=|\phi(k)-\phi(\ell)|.
\end{equation}
Let $\Dist(\phi)$ be the set of equivalence classes
of~$\sim_{\phi}$.  Note that  

\begin{enumerate}\it
\item[(*)]$|\Dist(\phi)|$ is the number of distinct `distances',
  i.e., integers of the form
  \begin{equation}
    \label{eq:diffs}
    |\phi(i)-\phi(j)|\qquad(i,\,j\in[n],\;i\neq j),
  \end{equation}
  that~$\phi$ induces.
\end{enumerate}
In what follows, we shall be interested in the numerical
parameters~$|\Dist(\phi)|$ and~$\max\{\phi(i)\:i\in[n]\}$ of the
functions~$\phi\:[n]\to\ZZ^+$.

We now introduce a central definition.

\begin{definition}[$G(\phi,\cD)$]
  \label{def:G(phi,cD)_def}
  Given~$\phi\:[n]\to\ZZ^+$ and~$\cD\subset\ZZ^+=\{1,2,\dots\}$, we define the
  graph~$G(\phi,\cD)$ as the graph whose vertex set is~$[n]$,
%  \begin{equation}
%    \label{eq:V(G(phi,cD))_def}
%    \im(\phi)=\{\phi(i)\:1\leq i\leq n\}
%  \end{equation}
%  and~$\phi(i)$ and~$\phi(j)$ are adjacent if and only
  with~$i$ and~$j$ adjacent if and only if~$|\phi(i)-\phi(j)|\in\cD$.
\end{definition}

If~$G$ is isomorphic to $G(\phi,\cD)$, then we shall say that $(\phi,\cD)$
{\it spaces}~$G$ (or that~$(\phi,\cD)$ is a {\it spacing} of~$G$).

Clearly, in the definition of~$G(\phi,\cD)$ above, we make~$i$ adjacent to~$j$
if and only if the distance between~$\phi(i)$ and~$\phi(j)$ is an element of a
set~$\cD$ of `distinguished' distances.  Furthermore, it is clear that the
edge set of~$G(\phi,\cD)$ is a union of equivalence classes of the
relation~$\sim_{\phi}$; equivalently, if~$\{i,j\}\sim_{\phi}\{k,\ell\}$,
then~$\{i,j\}$ is an edge of~$G(\phi,\cD)$ if and only if~$\{k,\ell\}$ is.

We are interested in representing graphs~$G$ as graphs of the
form~$G(\phi,\cD)$.  In particular, when representing an $n$-vertex graph $G$
as some $G(\phi,\cD)$, numerical constraints on~$\cD$ and
$\im(\phi)=\{\phi(i)\:i\in[n]\}$ arise.  For instance, we shall show that for
almost all~$G$, we must allow~$|\cD|$ 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(\phi,\cD)$, up to isomorphism.  

Let us now define some extremal parameters for $n$-vertex graphs~$G$.  In what
follows, $\phi$~and~$\cD$ will always stand for a function~$\phi\:[n]\to\ZZ^+$
and a set~$\cD\subset\ZZ^+$.  (We mention that, in the definitions that
follow, we may restrict ourselves to injective functions~$\phi$, as~$G$
has~$n$ vertices and we always wish to have~$G$ isomorphic to~$G(\phi,\cD)$.)

Given~$\phi$, we shall say that a graph~$G$ is a \textit{$\phi$-graph} if~$G$
is isomorphic to~$G(\phi,\cD)$ for some~$\cD$.  Similarly, given~$\cD$, we
shall say that~$G$ is a \textit{$\cD$-graph} if~$G$ is isomorphic
to~$G(\phi,\cD)$ for some~$\phi$.

Our first extremal parameter is~$s(G)$, the minimal integer~$N$ for which
there is a function~$\phi$ with~$\im(\phi)\subset[N]$ such that~$G$ is a
$\phi$-graph.  Formally, 
\begin{align}
  s(G)&=\min\{N\:\text{there is $\phi\:[n]\to\ZZ^+$}\nonumber\\
  &\qquad\qquad\qquad
  \text{such that $\im(\phi)\subset[N]$ and~$G$ is a $\phi$-graph}\}
  \label{eq:s_def}\\
  &=\min\{\max\im(\phi)\:\text{$G$ is a $\phi$-graph}\}.\nonumber
\end{align}
Therefore, $s(G)$~is the `space' that we need in order to obtain a
representation~$G(\phi,\cD)$ of~$G$.  We now define~$\mu(G)$ to be the maximal
cardinality of an equivalence class of~$\sim_\phi$, where we let~$\phi$ vary
among all functions such that~$G$ is a $\phi$-graph:
\begin{multline}
  \label{eq:mu_def}
  \quad\mu(G)=\max\{|C|\:\text{$C$~is an equivalence class of~$\sim_\phi$,}\\
  \text{where~$\phi$ is such that~$G$ is a $\phi$-graph}\}.
  \quad
\end{multline}
Thus, $\mu(G)$~is the maximum `multiplicity' with which a `distance'
(recall~(*)) may occur in a representation~$G(\phi,\cD)$ of~$G$.

Our third and fourth parameters concern the \textit{number} of `distances'
that we use in our representations of~$G$.  We let
\begin{equation}
  \label{eq:D_def}
  D(G)=\min\{|\Dist(\phi)|\:\text{$G$~is a $\phi$-graph}\}.
\end{equation}
Hence, $D(G)$~is the minimal possible number of `distances' that are induced
by the~$\phi\:[n]\to\ZZ^+$ in the representations~$G(\phi,\cD)$ of~$G$.  We
may also restrict ourselves to counting distinct `distances' that occur as
\textit{edges} in our representations of~$G$.  We let
\begin{equation}
  \label{eq:D_e_def}
  \quad \De(G)=\min\{|\cD|\:\text{$G$~is a $\cD$-graph}\}.
\end{equation}
Thus, $\De(G)$~is the minimum number of `edge lengths' that are required in
the representations~$G(\phi,\cD)$ 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$.

\begin{proposition}\label{proposition:kmnspace}
For $m\ge n$, we have
\begin{equation}
  \label{eq:complete_bip}
  s(K_{m,n})=
  \begin{cases}
    2m   &\text{if~$m=n$}\\
    2m-1 &\text{if~$m>n$.}
  \end{cases}
\end{equation}
\end{proposition}

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

\begin{proposition}
  \label{prop:starspace}
  For any $n>1$, we have~$s(K_{1,n})=2n-1$.
\end{proposition}

To see that $s(K_{1,n})\le 2n-1$ consider $G(\phi,\cD)$, where
\begin{equation}
  \label{eq:start_phi}
  \im(\phi)=\{1,2,3,5,7,\dots,2n-1\}
\end{equation}
and
\begin{equation}
  \label{eq:star_D}
  \cD=\{1,3,5,\dots,2n-3\}.
\end{equation}

Then $(\phi,\cD)$ spaces $K_{1,n}$, and hence~$s(K_{1,n})\leq2n-1$.  The
reverse inequality will be proved in Section~\ref{sec:proof_of_prop}.
Proposition \ref{proposition:kmnspace} 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~\ref{sec:conclude} below and~\cite[Remark~7.2]{babai:cayley2}).
Let us now get back to the general case.

Let
\begin{equation}
  \label{eq:s(n)D(n)_def}
  s(n)=\max_Gs(G),
  \quad \mu(n)=\min_G\mu(G),
  \quad D(n)=\max_GD(G),
\end{equation}
and
\begin{equation}
  \label{eq:De(n)_def}
  \De(n)=\max_G\De(G),
 \end{equation}
where the maxima are taken over all $n$-vertex graphs~$G$.  For positive
integers~$r$, we also let 
\begin{equation}
  \label{eq:s_r_def}
  s_r(n)=\max_Gs(G),
\end{equation}
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)$, $\mu(n)$, $D(n)$, and~$\De(n)$.

\subsection{Statement of the results}
\label{sec:results}
The following are our results pertaining to the parameters given above.  The
proofs will be given in Sections~\ref{sec:_s(n)_mu(n)_proofs}
and~\ref{sec:_D(n)_De(n)}.

We start with the extremal functions~$s(n)$ and~$s_r(n)$.

\begin{theorem}
  \label{thm:s(n)_lwbd}
  We have
  \begin{equation}
    \label{eq:s(n)_lwbd}
   n^2\(1-(4+o(1))\sqrt{\log n\over n}\)\leq s(n)\leq n^2+O(n^{1.525}).
  \end{equation}
\end{theorem}

\begin{theorem}
  \label{thm:s_r(n)_lwbd}
  \begin{enumerate}
  \item[(\textit{i})]For every fixed integer~$r\geq2$ and for all~$n$
    with~$rn$ even, we have
    \begin{equation}\label{eq:s_r(n)_lwbd}
      s_r(n)
      \geq(1+o(1))\(\frac{1}{r!}\)^{2/(r+2)}
      \(\frac{r}{\e\sqrt2}\)^{2r/(r+2)}n^{2r/(r+2)}.
    \end{equation}
  \item[(\textit{ii})]Let~$r=r(n)$ be an integer function satisfying~$\log
    n\ll r\leq(n-1)/2$ and with~$rn$ even for all~$n$.  Then
    \begin{equation}
      \label{eq:all_r}
      s_r(n)=(1+o(1))n^2.
    \end{equation}
  \end{enumerate}
\end{theorem}

Our result concerning the `multiplicity' parameter~$\mu(n)$ is as follows.

\begin{theorem}
  \label{thm:mu(n)_lwbd}
  For all sufficiently large~$n$, we have
  \begin{equation}
    \label{eq:mu(n)_lwbd}
    \mu(n)<2+8\log_2n.
  \end{equation}
\end{theorem}

The next three results deal with the functions~$D(n)$ and~$\De(n)$ and the
parameter~$\De(G)$, concerning the number of distinct distances that are
involved in our representations of graphs.

\begin{theorem}
  \label{thm:D(n)_lwbd}
  For any~$\epsilon>0$, there is~$n_0=n_0(\epsilon)$ such that if~$n\geq n_0$,
  then
  \begin{equation}
    \label{eq:D(n)_lwbd}
    D(n)>{n\choose2}-4n\log_2n+2n-{1\over2}\log_2(2\pi n)-\epsilon.
  \end{equation}
\end{theorem}

\begin{theorem}
  \label{thm:gamma(G)_upbd}
  For almost all $n$-vertex graphs~$G$, we have
  \begin{equation}
    \label{eq:gamma(n)_upbd}
    \De(G)\geq\frac{1}{2}{n\choose2}-(1+o(1))n^{3/2}\sqrt{\log n}.
  \end{equation}
\end{theorem}

\begin{theorem}
  \label{thm:De(n)_lwbd}
  For any function~$\omega=\omega(n)$ such that~$\omega(n)\to\infty$
  as~$n\to\infty$, we have
  \begin{equation}
    \label{eq:De(n)_lwbd}
    \De(n)\geq{n\choose2}-3\omega n^{3/2}\sqrt{\log n}-3
  \end{equation}
  for all large enough~$n$.  
\end{theorem}

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

\begin{corollary}
  \label{sec:simultaneous_De_s}
  Let~$\epsilon>0$ be fixed and suppose~$\omega=\omega(n)\to\infty$
  as~$n\to\infty$.  Then, for all large enough~$n$, there is an $n$-vertex
  graph~$G$ for which we have
  \begin{equation}
    \label{eq:large_De}
    \De(G)\geq{n\choose2}-3\omega n^{3/2}\sqrt{\log n}-3
  \end{equation}
  and
  \begin{equation}
    \label{eq:large_s}
    s(G)\geq\(1-(2\sqrt6+\epsilon)\omega^{1/2}\(\log n\over n\)^{1/4}\)n^2.
  \end{equation}
\end{corollary}

\section{Proof of Proposition~\ref{prop:starspace}}
\label{sec:proof_of_prop}
We have already observed that~$s(K_{1,n})\leq2n-1$.  To establish the reverse
inequality, we need the following claim.

\begin{claim}
  \label{claim:root_star}
  If~$K_{1,n}$ is isomorphic to~$G(\phi,\cD)$, where $\im(\phi)\subset[2n-1]$,
  then the root vertex is associated with neither~$1$ nor~$\max\im(\phi)$.
\end{claim}
\begin{proof}  
  Assume otherwise; specifically, assume that the root vertex of $K_{1,n}$ is
  associated with 1.  Then there are $n$ distinct differences in $\cD$
  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(\phi)$, must be associated with a leaf~$v$.  Hence there are $n-1$
  distinct values not in $\cD$ corresponding to the non-edges between $v$ and
  the other leaves.  However this implies that
  $2n-2=\big|\cD|+|[2n-2]\setminus\cD\big|\ge n+n-1=2n-1$, a contradiction.
\end{proof}

We can now prove the proposition.

\begin{proof}[Proof of Proposition~\ref{prop:starspace}] 
  We proceed by induction on $n$, and note that the claim is easily shown true
  when $n=2$ or $n=3$.  Let $(\phi,\cD)$ be a spacing of $K_{1,n}$ ($n>3$)
  that realizes the spacing number and assume that $\max\im(\phi)=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(\phi)$ and associated with leaves, lest
  $s(K_{1,n-1})\le 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(\phi)$.  By the above,
  $p_i\notin \{1,2,s(K_{1,n})-1,~s(K_{1,n})\}$.  Assume that there are $l\ge
  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(\phi)$ in these intervals along with $\cD$ 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\ge 2l$.  However, we then have~$s(K_{1,n-l})\le s(K_{1,n})-p_i\le
  2n-2-2l=2(n-l)-2$, contradicting the induction assumption.
\end{proof}

As noted above, this also completes the proof of Proposition
\ref{proposition:kmnspace}.  

\section{Auxiliary lemmas}
\label{sec:aux_lemmas}
In this section, we give two elementary results from combinatorial number
theory. 

\subsection{Almost Sidon sets}
\label{sec:approx_Sidon}
To establish our bounds on $s(n)$, we shall make use of a classical object
from combinatorial number theory.  A set
\begin{equation}
A=\{a_1,\dots,a_n\}
\end{equation}
 is called a \emph{Sidon set} if 
\begin{equation}
\big|\{|a_i-a_j|\:i<j\}\big|={n \choose 2},
\end{equation}
that is, if all of the differences of distinct elements are distinct.  It was
shown by Erd\H{o}s and Tur\'{a}n in \cite{erdos_sidon} that
if $A\subset[N]$ is an $n$-element Sidon set, then 
\begin{equation}
  \label{eq:Erdos-Turan}
  N\ge n^2+O(n^{3/2})
\end{equation}
(see also~\cite{lindstroem69:_b,lindstroem72:_b}).  We shall examine a similar
type of set, wherein the pairwise differences are almost all distinct.
Lemma~\ref{lem:ET} below, in a slightly different form, appears as Theorem~1
in~\cite{bollobas03:_integ}.  The proofs os Lemma~\ref{lem:ET}
and~\cite[Theorem~1]{bollobas03:_integ} follow~\cite{erdos_sidon} closely, and
were obtained independently.

\begin{lemma}
  \label{lem:ET}
  Let~$0<\epsilon=\epsilon(n)\leq1$ be such that~$\epsilon n\to\infty$
  as~$n\to\infty$.  Suppose~$\phi\:[n]\to\ZZ^+$ is an injective function such
  that
  \begin{equation}
    \label{eq:quasi-Sidon}
    |\Dist(\phi)|\geq(1-\epsilon){n\choose2}
  \end{equation}
  and
  \begin{equation}
    \label{eq:quasi-Sidon.b}
    \im(\phi)\subset[N].
  \end{equation}
  Then
  \begin{equation}
    \label{eq:N(n)_lwbd}
    N\geq\big(1-(2+o(1))\sqrt\epsilon\big)n^2.
  \end{equation}
\end{lemma}

\begin{proof}
  As mentione above, we follow~\cite{erdos_sidon} very closely.
  Let~$\epsilon=\epsilon(n)$ and $\phi\:[n]\to\ZZ^+$ be as in the statement of
  our lemma.  Let~$\im(\phi)=\{x_i\:1\leq i\leq n\}$, where
  \begin{equation}
    \label{eq:x_i_in_order}
    x_1<\dots<x_n.
  \end{equation}
  Let~$m=\lfloor\epsilon^{1/2}n^2\rfloor$.  Let us consider the
  following~$N+m$ intervals of integers, each of cardinality~$m$:
  \begin{equation}
    \label{eq:intervals}
    I_1=[-m+1,1),I_2=[-m+2,2),\dots,I_{N+m}=[N,N+m).
  \end{equation}
  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\in I_k$.  Let~$T$ be the number of such triples.

  We have
  \begin{equation}
    \label{eq:exact_count}
    T=\sum_{1\leq k\leq N+m}{B_k\choose2}
    \geq{1\over2}(N+m){nm\over N+m}\({nm\over N+m}-1\),
  \end{equation}
  where the inequality follows from convexity.  Let us now estimate~$T$ in an
  alternative way.
  
  Pick~$L\geq(1-\epsilon){n\choose2}$ pairs~$(x_{i_\lambda},x_{j_\lambda})$
  ($1\leq\lambda\leq L$) with~$x_{i_\lambda}<x_{j_\lambda}$ for all~$\lambda$
  and all the differences
  \begin{equation}
    \label{eq:dist_diffs}
    d_\lambda=x_{j_\lambda}-x_{i_\lambda}\qquad(1\leq\lambda\leq L)
  \end{equation}
  distinct.  Fix a pair~$(x_{i_\lambda},x_{j_\lambda})$.
  If~$d_\lambda=x_{j_\lambda}-x_{i_\lambda}\geq m$, then clearly there is
  no~$k$ for which both~$x_{i_\lambda}$ and~$x_{j_\lambda}\in I_k$.
  If~$d_\lambda<m$, then there are~$m-d_\lambda$ intervals~$I_k$ with
  both~$x_{i_\lambda}$ and~$x_{j_\lambda}\in 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_\lambda},x_{j_\lambda};I_k)$ ($1\leq\lambda\leq
  L$) that we are interested in is
  \begin{equation}
    \label{eq:triples_upbd}
    \leq\sum_{1\leq d<m}(m-d)={m\choose2}.
  \end{equation}
  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_\lambda},x_{j_\lambda})$ ($
  1\leq\lambda\leq L$).  We use a crude bound for such pairs, of which there
  are at most~$\epsilon{n\choose 2}$: each of the pairs occur in at
most~$m-1$ intervals~$I_k$ each.  Therefore, we have
  \begin{equation}
    \label{eq:T_upbd}
    T\leq{m\choose2}+\epsilon{n\choose2}(m-1)
    \leq{1\over2}(m^2+\epsilon n^2m).
  \end{equation}
  Comparing~\eqref{eq:exact_count} and~\eqref{eq:T_upbd}, we have
  \begin{equation}
    \label{eq:compare_Ts}
    n\({nm\over N+m}-1\)\leq m+\epsilon n^2,
  \end{equation}
  which is equivalent to
  \begin{equation}
    \label{eq:compare_Ts.b}
    n^2m\leq(N+m)(m+\epsilon n^2+n).
  \end{equation}
  Since~$\epsilon n\to\infty$ as~$n\to\infty$, we deduce
  from~\eqref{eq:compare_Ts.b} that
  \begin{multline}
    \label{eq:compare_Ts.c}
    N\geq{n^2m\over m+(1+o(1))\epsilon n^2}-m
    \geq n^2{1\over1+(1+o(1))\epsilon n^2/m}-\epsilon^{1/2}n^2\\
    \geq n^2\(1-(1+o(1))\epsilon^{1/2}\)-\epsilon^{1/2}n^2,
  \end{multline}
  and~\eqref{eq:N(n)_lwbd} follows. 
\end{proof}

\subsection{The number of equivalence relations~$\sim_\phi$}
\label{sec:no_types}
Recall that each~$\phi\:[n]\to\ZZ^+$ defines an equivalence
relation~$\sim_{\phi}$ on~${[n]\choose2}$ (see~\eqref{eq:equiv_def}).  Let
\begin{equation}
  \label{eq:T(n)_def}
  T(n)=\big|\{\sim_{\phi}\:\phi\in(\ZZ^+)^{[n]}\}\big|.
\end{equation}
The upper bound for~$T(n)$ given in Lemma~\ref{lem:T(n)_upbd} below will be
crucial when estimating~$D(n)$ and~$\De(n)$.  The reader may find it
interesting to observe how small~$T(n)$ is, in comparison with the total
number of equivalence relations on~${[n]\choose 2}$, which is given by the Bell
number
\begin{equation}
  \label{eq:Bell_no}
  b_{n\choose2}={n\choose2}^{(1+o(1)){n\choose2}}=n^{(1+o(1))n^2}
\end{equation}
(see, e.g., \cite{graham94:_concr}).

\begin{lemma}
  \label{lem:T(n)_upbd}
  For all~$n\geq3$, we have
  \begin{equation}
    \label{eq:T(n)_upbd}
    T(n)\leq{2{{n\choose2}\choose2}\choose n}
    \leq(1+o(1))\(\e n^3\over4\)^n.
  \end{equation}
\end{lemma}
\begin{proof}
  Let~$\phi_\lambda\:[n]\to\ZZ^+$ ($\lambda\in\Lambda$) be~$T(n)$ maps with
  all the~$\sim_{\phi_\lambda}$ distinct.  Moreover, let~$p$ be a sufficiently
  large prime; any choice with 
  \begin{equation}
    \label{eq:p_def}
    p>\max_{\lambda\in\Lambda}\(\max\im(\phi_\lambda)\)^2
  \end{equation}
  will do.  We may consider the maps~$\phi_\lambda$ as maps into~$\FF_p$, the
  field of order~$p$, in the obvious way:
  \begin{equation}
    \label{eq:phi_mod_p}
    \phi_\lambda\:[n]\to\FF_p.
  \end{equation}
  For convenience, let
  \begin{equation}
    \label{eq:x_i^lambda_def}
    x_{\lambda,i}=\phi_\lambda(i)\quad(\lambda\in\Lambda,\;i\in[n])
  \end{equation}
  and let
  \begin{equation}
    \label{eq:bfx_def}
    \bfx_\lambda=(x_{\lambda,i})_{1\leq i\leq n}.
  \end{equation}
  Let
  \begin{equation}
    \label{eq:R_def}
    \cR={{[n]\choose2}\choose2}={E(K^n)\choose 2},
  \end{equation}
  and consider the quadratic polynomials
  \begin{equation}
    \label{eq:f_system_def}
    f_\rho(x_1,\dots,x_n)\in\FF_p[x_1,\dots,x_n]\qquad(\rho\in\cR), 
  \end{equation}
  where, if~$\rho=\big\{\{i,j\},\{k,\ell\}\big\}\in\cR$, then
  \begin{equation}
    \label{eq:f_lambda_def}
    f_\rho(x_1,\dots,x_n)=(x_i-x_j)^2-(x_k-x_\ell)^2.
  \end{equation}
  We let~$\bfx=(x_1,\dots,x_n)$ and~$\bff(\bfx)=(f_\rho(\bfx))_{\rho\in\cR}$.

  Given~$\bfz=(z_\rho)_{\rho\in{\mathcal R}}\in\FF_p^{\mathcal R}$, let
the \textit{zero
    pattern}~$Z(\bfz)$ of~$\bfz$ be the $\{0,*\}$-vector~$(s_\rho)_{\rho\in
    {\mathcal R}}$, where
  \begin{equation}
    \label{eq:zero_def}
    s_\rho=
    \begin{cases}
      0&\text{if~$z_\rho=0$}\\
      *&\text{otherwise}.
    \end{cases}
  \end{equation}
  We now consider the zero patterns~$Z(\bff(\bfx^*))$ of the
  vectors~$\bff(\bfx^*)$, where we let~$\bfx^*$ vary in~$\FF_p^n$.
  Theorem~1.3 in~\cite{ronyai01} tells us that
  \begin{multline}
    \label{eq:no_Z}
    \qquad\big|\{Z(\bff(\bfx^*))\:\bfx^*\in\FF_p^n\}\big|
    \leq{2|\cR|\choose n}\\
    ={2{{n\choose2}\choose2}\choose n}
    \leq{n^4/4\choose n}
    \leq(1+o(1))\(\e n^3\over4\)^n.\qquad
  \end{multline}
  It now suffices to relate zero patterns with the equivalence
  relations~$\sim_{\phi_\lambda}$.  Recall~\eqref{eq:equiv_def},
  \eqref{eq:p_def}, \eqref{eq:x_i^lambda_def}, and~\eqref{eq:bfx_def}, and
  observe that, for any~$\sim_{\phi_\lambda}$ and
  any~$\rho=\big\{\{i,j\},\{k,\ell\}\big\}\in\cR$, we have
  \begin{multline}
    \label{eq:type_=_Z}
    \{i,j\}\sim_{\phi_\lambda}\{k,\ell\}
    \iff|\phi_\lambda(i)-\phi_\lambda(j)|= 
    |\phi_\lambda(k)-\phi_\lambda(\ell)|\\ 
    \iff(x_{\lambda,i}-x_{\lambda,j})^2=(x_{\lambda,k}-x_{\lambda,\ell})^2
    \iff\bff_\rho(\bfx_\lambda)=0\text{\; in~$\FF_p$}.
  \end{multline}
  (Note that the `if' part of the last `if and only if' follows
  from~\eqref{eq:p_def}.)  By the definition of zero patterns, the
  equivalences in~\eqref{eq:type_=_Z} tell us that the
  relations~$\sim_{\phi_\lambda}$ and~${\sim_{\phi_{\lambda'}}}$ coincide if
  and only if~$Z(\bff(\bfx_\lambda))=Z(\bff(\bfx_{\lambda'}))$.  This
  fact and~\eqref{eq:no_Z} imply~\eqref{eq:T(n)_upbd}, and
  Lemma~\ref{lem:T(n)_upbd} is proved.
\end{proof}

\section{Proofs of Theorems~\ref{thm:s(n)_lwbd}, \ref{thm:s_r(n)_lwbd},
  and~\ref{thm:mu(n)_lwbd}} 
\label{sec:_s(n)_mu(n)_proofs}
In this section we shall prove our results concerning the extremal
functions~$s(n)$, $s_r(n)$, and~$\mu(n)$.

\subsection{Proofs of Theorems~\ref{thm:s(n)_lwbd} and~\ref{thm:s_r(n)_lwbd}}
\label{sec:pf_s(n)_s_r(n)}
We start with the spacing parameters~$s(n)$ and~$s_r(n)$.

\begin{proof}[Proof of Theorem~\ref{thm:s(n)_lwbd}]
  We shall show that
  \begin{equation}
    \label{eq:snbd}
    \left(1-(4+o(1))\sqrt{\frac{\log n}{n}}\right)n^2
    \leq s(n) \leq
    n^2+O(n^{1.525}).
  \end{equation}
  
  We prove the upper bound using Sidon sets.  Let $G$ be a graph with vertex
  set~$\{v_1,\dots,v_n\}$ and let $A=\{a_1,\dots,a_n\}$ be a Sidon set.  Then
  $(\phi,\cD)$ spaces~$G$, where $\phi\:[n]\to\ZZ^+$ is any function such that
  $\im(\phi)=A$ and
  \begin{equation}
    \label{eq:triv_cD}
    \cD=\big\{|a_i-a_j|\:\{v_i,v_j\}\in E(G)\big\}.
  \end{equation}
  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~\cite{singer38} (for details,
  see~\cite[Chapter~II]{HalberstamRoth2ndEd}).

  \begin{lemma}
    \label{lem:Singer}
    Let~$q$ be a prime power.  Then there is a $(q+1)$-element Sidon
    set~$A=\{a_0,a_1,\dots,a_q\}$ with $1\leq a_0<a_1<\dots<a_q\leq q^2+q+1$.
  \end{lemma}

%   \begin{lemma}
%     \label{lem:Chowla}
%     Let $q$ be a prime power.  Then there is a Sidon set $A\subset[q^2]$ with
%     exactly $q$ elements.
%   \end{lemma}
  
  It was shown by Baker, Harman, and Pintz \cite{bakerprimes} 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
  \begin{multline}
    \label{eq:Baker_consequence}
    s(n)\le\(n+(1+o(1))n^{.525}\)^2+\(n+(1+o(1))n^{.525}\)+1\\
    =n^2+O(n^{1.525}),
  \end{multline}
  and the upper bound in \eqref{eq:snbd} follows.  We now turn to the lower
  bound on~$s(n)$.
  
  Let~$\delta$ be a fixed positive real, and let
  \begin{equation}
    \label{eq:epsilon_def}
    \epsilon=\epsilon(n)={4\log n\over n-1}.
  \end{equation}
  Suppose for a contradiction that 
  \begin{equation}
    \label{eq:s(n)_upbd_hyp}
    s(n)\leq N_0=\llfloor n^2\(1-(4+\delta)\sqrt{\log n\over n}\)\rrfloor. 
  \end{equation}
  
  Let us invoke Lemma~\ref{lem:ET}, with~$\epsilon$ given
  in~\eqref{eq:epsilon_def}.  Lemma~\ref{lem:ET} tells us that
  if~$\phi\:[n]\to\ZZ^+$ is such that 
  \begin{equation}
    \label{eq:quasi-Sidon.X}
    |\Dist(\phi)|\geq(1-\epsilon){n\choose2}
  \end{equation}
  and~$\im(\phi)\subset[N]$, then
  \begin{equation}
    \label{eq:N(n)_lwbd.b}
    N\geq n^2\big(1-(2+o(1))\sqrt\epsilon\big)
    =n^2\(1-(4+o(1))\sqrt{\log n\over n}\).
  \end{equation}
  Comparing~\eqref{eq:s(n)_upbd_hyp} and~\eqref{eq:N(n)_lwbd.b}, we see that,
  for all~$n\geq n_0(\delta)$, the~$\phi\:[n]\to\ZZ^+$ that are such
  that~$\im(\phi)\subset[N_0]$ must all be such that~\eqref{eq:quasi-Sidon.X}
  fails, that is,
  \begin{equation}
    \label{eq:quasi-Sidon.Y}
    |\Dist(\phi)|<(1-\epsilon){n\choose2}.
  \end{equation}
  
  Note that~\eqref{eq:s(n)_upbd_hyp} tells us that if we consider the
  graphs~$G(\phi,\cD)$ with~$\phi\:[n]\to\ZZ^+$ such
  that~$\im(\phi)\subset[N_0]$ and~$\cD\subset\ZZ^+$ arbitrary, then we obtain
  all $n$-vertex graphs up to isomorphism.
  
  Remark~\ref{rem:1}(\textit{i}) and~\eqref{eq:quasi-Sidon.Y}, coupled with
  the fact that there are at least~$2^{n\choose2}/n!$ graphs on~$n$ vertices
  up to isomorphism, tell us that
  \begin{equation}
    \label{eq:enough_grs}
    {N_0^n\over n!}2^{(1-\epsilon){n\choose2}}
    \geq{N_0\choose n}2^{(1-\epsilon){n\choose2}}
    \geq{1\over n!}2^{n\choose2}.
  \end{equation}
  Inequalities~\eqref{eq:epsilon_def} and~\eqref{eq:enough_grs} give
  that~$N_0\geq n^2$, which contradicts~\eqref{eq:s(n)_upbd_hyp} for
  all~$n\geq n_0(\delta)$.  This contradiction completes the proof of
  Theorem~\ref{thm:s(n)_lwbd}.
\end{proof}

The proof of Theorem~\ref{thm:s_r(n)_lwbd} is similar to the proof of
Theorem~\ref{thm:s(n)_lwbd}.  The following estimates for the number of
$r$-regular graphs will be used now.  We first quote a classical result of
Bender and Canfield~\cite{bender78} (see also~\cite[Corollary~2.17]{BBf}),
in the case in which~$r$ is a fixed integer.

\begin{theorem}
  \label{thm:Bender_Canfield}
  For any fixed integer~$r\geq2$, the number~$R(n,r)$ of labelled, $n$-vertex  
  $r$-regular graphs satisfies
  \begin{equation}
    \label{eq:L_r(n)}
    R(n,r)\geq
    (\sqrt2+o(1))\e^{-(r^2-1)/4}\(r^{r/2}\over\e^{r/2}r!\)^nn^{rn/2}
  \end{equation}
  as~$n\to\infty$ with~$rn$ even.
\end{theorem}

For recent results concerning the number of $r$-regular graphs
with~$r=r(n)\to\infty$ as~$n\to\infty$, see McKay and
Wormald~\cite{mckay91:_asymp}, where Theorem~\ref{thm:Bender_Canfield} 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~\cite{egorycev80:_reshen_varden,falikman81:_proof_waerd} and
Br\'egman~\cite{bregman73:_certain}.  (A result stronger than
Fact~\ref{fact:no_reg.gs} may be proved with the same method; here, we only
state a result that is enough for our purposes.)

\begin{fact}
  \label{fact:no_reg.gs}
  If~$r=r(n)$ satisfies~$\log n\ll r\leq n/2$ and~$rn$ is even for all~$n$,
  then the number~$R(n,r)$ of labelled, $r$-regular graphs on~$n$ vertices
  satisfies
  \begin{equation}
    \label{eq:no_reg.gs}
    R(n,r)\geq\binom{\binom n2}{rn/2}(1-o(1))^{rn}.
  \end{equation}
\end{fact}

Note that Fact~\ref{fact:no_reg.gs} 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~\ref{fact:no_reg.gs} here.  (For an
alternative proof, the reader is referred to Shamir and
Upfal~\cite{shamir84:_large}.)

\begin{proof}[Proof of Fact~\ref{fact:no_reg.gs} (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~\cite{egorycev80:_reshen_varden} and
  Falikman~\cite{falikman81:_proof_waerd} 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\'egman~\cite{bregman73:_certain} that gives
  an upper bound for such a number (Minc's conjecture), one may show that
  \begin{equation}
    \label{eq:bip}
    \Bip(n/2,r/2)\ge\binom{n/2}{r/2}^{n/2}(1-o(1))^{rn}.
  \end{equation}
  Next, one observes that
  \begin{equation}
    \label{eq:inf_prod}
    R(n,r)\ge\prod_{j\ge 1}
    \[\Bip\(\frac{n}{2^{j}},\frac{r}{2^j}\)\]^{2^{j-1}} 
  \end{equation}
  (for simplicity, divisibility conditions are ignored
  in~\eqref{eq:inf_prod}).  One may derive~\eqref{eq:no_reg.gs}
  from~\eqref{eq:bip} and~\eqref{eq:inf_prod}.
\end{proof}

We may now prove Theorem~\ref{thm:s_r(n)_lwbd}.

\begin{proof}[Proof of Theorem~\ref{thm:s_r(n)_lwbd}]
  We first prove~(\textit{i}).  Note that if $r=2$, then the claimed
  bound~\eqref{eq:s_r(n)_lwbd} is trivial.  Fix an integer~$r\ge 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(\phi,\cD)$ with~$\cD\subset\ZZ^+$ and with~$\phi\:[n]\to\ZZ^+$ such
  that~$\im(\phi)\subset[N]$ is
  \begin{equation}
    \label{eq:no._graphs_in_N}
    \leq{N\choose n}\sum_{1\leq j\leq rn/2}{N-1\choose j},
  \end{equation}
  as we have~${N\choose n}$ choices for~$\im(\phi)$ and we may
  suppose~$\cD\subset[N-1]$.
                               
  Now suppose that~$s_r(n)\leq N$.  Then the quantity in~\eqref{eq:L_r(n)}
  divided by~$n!$ has to be at most the quantity
  in~\eqref{eq:no._graphs_in_N}.  This gives that
  \begin{equation}
    \label{eq:r-reg.1}
    (\sqrt2+o(1))\e^{-(r^2-1)/4}\(r^{r/2}\over\e^{r/2}r!\)^n{n^{rn/2}\over n!} 
    \leq{N\choose n}\sum_{1\leq j\leq rn/2}{N-1\choose j}.
  \end{equation}
  
  Let us now show that~$N\geq rn$.  Suppose for a contradiction that~$N<rn$.
  In this case, we get from~\eqref{eq:r-reg.1} that
  \begin{equation}
    \label{eq:r-reg.11}
    (\sqrt2+o(1))\e^{-(r^2-1)/4}\(r^{r/2}\over\e^{r/2}r!\)^n{n^{rn/2}\over
      n!} \leq{rn\choose n}2^{rn}.
  \end{equation}
  Taking the $n$th root, we obtain from~\eqref{eq:r-reg.11} that
  \begin{equation}
    \label{eq:r-reg.12}
    \frac{r^{r/2}}{e^{r/2}r!} n^{r/2} \le rn2^r,
  \end{equation}
  which is clearly false for $n\ge n_0(r)$ because~$r\geq3$.  This
  contradiction shows that we do have~$N\geq rn$.
  
  It follows from~$N\geq rn$ that the quantity in \eqref{eq:no._graphs_in_N}
  is
  \begin{equation}
    \leq\frac{1}{2}rn{N\choose n}{N\choose rn/2}.
  \end{equation}
  From~\eqref{eq:r-reg.1}, we have 
  \begin{equation}
    (\sqrt2+o(1))\e^{-(r^2-1)/4}\(r^{r/2}\over\e^{r/2}r!\)^n{n^{rn/2}\over
      n!} \leq \frac{1}{2}rn{N\choose n}{N\choose rn/2}.
  \end{equation}
  Taking the $n$th root, we obtain
  \begin{equation}
    \label{eq:r-reg.2}
    (1+o(1)){r^{r/2}\over\e^{r/2}r!}\e n^{r/2-1}
    \leq{\e N\over n}\(2\e N\over rn\)^{r/2},
  \end{equation}
  whence
  \begin{equation}
    \label{eq:r-reg.3}
    (1+o(1)){r^r\over2^{r/2}\e^rr!}n^r
    \leq N^{(r+2)/2}.
  \end{equation}
  Therefore
  \begin{equation}
    \label{eq:r-reg.4}
    N\geq(1+o(1))\(1\over r!\)^{2/(r+2)}
    \(r\over\e\sqrt2\)^{2r/(r+2)}n^{2r/(r+2)},
  \end{equation}
  and~\eqref{eq:s_r(n)_lwbd} follows.  This completes the proof
  of~(\textit{i}).
  
  Let us now turn to the proof of~(\textit{ii}).  Let~$r=r(n)$ as in the
  statement of the theorem be given.  Clearly, it follows from the upper bound
  in~\eqref{eq:s(n)_lwbd} that~$s_r(n)\leq(1+o(1))n^2$.  We need to prove the
  reverse inequality.  
  
  Assume that, for some fixed~$\epsilon>0$, 
  \begin{equation}
    \label{eq:assump}
    s_r(n)\le(1-\epsilon)n^2\text{ for arbitrarily large~$n$.}
  \end{equation}
  We shall derive a contradiction from this assumption, and this will complete
  the proof of~\eqref{eq:all_r}.
  
  Lemma~\ref{lem:ET} tells us that if $\phi\:[n]\to\ZZ^+$ is such that
  \begin{equation}
    \label{eq:assume}
    \im\phi\subset[(1-\epsilon)n^2], 
  \end{equation}
  then there exists some~$\sigma>0$ for which we have
  \begin{equation}
    \label{eq:Dist_bdd}
    |\Dist(\phi)|<(1-\sigma)\binom{n}{2}.
  \end{equation}
  Thus, the total number of $\phi$-graphs with~$\phi$
  satisfying~\eqref{eq:assume} is, up to isomorphism, at most
  \begin{equation}
    \label{eq:no_phi_grs}
    \binom{n^2}{n}\sum_{j\le rn/2} \binom{(1-\sigma)\binom{n}{2}}{j}.
  \end{equation}
  We shall now compare~\eqref{eq:no_reg.gs} and~\eqref{eq:no_phi_grs}.  It
  will be convenient to consider separately two ranges for~$r$.

  \begin{case}
    \label{case:small_r}
    $r\leq(1-\sigma)(n-1)/2$
  \end{case}
  
  In this case, we bound the quantity in~\eqref{eq:no_phi_grs} from above by 
  \begin{equation}
    \label{eq:small_r_spaceable}
    \binom{n^2}{n}\frac{rn}{2}\binom{(1-\sigma)\binom{n}{2}}{rn/2}.
  \end{equation}
  Using that~$r\gg\log n$, we see that the quantity
  in~\eqref{eq:small_r_spaceable} is smaller than~\eqref{eq:no_reg.gs}
  for~$n\geq n_0(\sigma)$.  This contradicts~\eqref{eq:assump}, completing the
  proof in this case.

  \begin{case}
    \label{case:large_r}
    $(1-\sigma)(n-1)/2<r\leq(n-1)/2$
  \end{case}
  
  In this case, we bound the quantity in~\eqref{eq:no_phi_grs} from above by 
  \begin{equation}
    \label{eq:large_r_spaceable}
    2^{(1-\sigma)\binom{n}{2}}(1+o(1))^{n^2}.
  \end{equation}  
  However, examining~\eqref{eq:no_reg.gs}, one sees that in this case the
  number of $r$-regular graphs is at least
  \begin{equation}
    \label{eq:num_r_reg_2}
    \binom{\binom{n}{2}}{\llfloor((1-\sigma)/2)\binom{n}{2}\rrfloor}
    (1-o(1))^{n^2}.
  \end{equation}
  
  We shall estimate~\eqref{eq:num_r_reg_2} using the following well known
  fact, which is a consequence of Stirling's formula.
  
  \begin{fact}
    \label{fact:alpha_m}
    Let~$0<\alpha<1$ be fixed and let~$m$ be a positive integer.  Then
    \begin{equation}
      \label{eq:entropy}
      \binom{m}{\lfloor\alpha
        m\rfloor}=\[\(\frac{1}{\alpha}\)^{\alpha}
      \(\frac{1}{1-\alpha}\)^{1-\alpha}\]^m(1+o(1))^m,   
    \end{equation}
    where~$o(1)\to0$ as~$m\to\infty$.
    
  \end{fact}
  
  Applying Fact~\ref{fact:alpha_m} to~\eqref{eq:num_r_reg_2}, we have that the
  number of $r$-regular graphs is at least
  \begin{equation}\label{eq:num_r_reg_3}
    \[\(\frac{2}{1-\sigma}\)^{(1-\sigma)/2}
  \(\frac{2}{(1+\sigma)}\)^{(1+\sigma)/2}\]^{\binom{n}{2}}(1-o(1))^{n^2}. 
  \end{equation}
  As in the first case, assumption~\eqref{eq:assump} tells us that the
  quantity in~\eqref{eq:large_r_spaceable} should be at least as large as the
  quantity in~\eqref{eq:num_r_reg_3}, that is,
  \begin{equation}
    \label{eq:first}
    \[\(\frac{2}{1-\sigma}\)^{(1-\sigma)/2}
    \(\frac{2}{(1+\sigma)}\)^{(1+\sigma)/2}\]^{{n\choose2}}
    \leq
    2^{(1-\sigma)\binom{n}{2}}(1+o(1))^{n^2}.
  \end{equation}
  We shall now see that~\eqref{eq:first} does not hold if~$n\geq
  n_0(\sigma)$.  
  
  Keeping in mind that~$\sigma>0$ is a constant and~$n$ tends to infinity,
  inequality~\eqref{eq:first} simplifies to
  \begin{equation}
    \label{eq:log_ineq}
    \(\frac{1-\sigma}{2}\)\log_2 \frac{2}{1-\sigma} +
    \(\frac{1+\sigma}{2}\)\log_2\frac{2}{1+\sigma}\le 1-\sigma.
  \end{equation}
  Equivalently,
  \begin{equation}
    \label{eq:log_ineq2}
    \(\frac{1-\sigma}{2}\)\(1 - \log_2(1-\sigma)\)+\(\frac{1+\sigma}{2}\)\(1 -
    \log_2(1+\sigma)\)\le 1-\sigma;
  \end{equation}
  that is,
  \begin{equation}\label{eq:last}
    (1-\sigma)\log_2(1-\sigma)+(1+\sigma)\log_2(1+\sigma)-2\sigma\ge0.
  \end{equation}
  Let
  \begin{equation}
    \label{eq:ff_def}
    f(\sigma)=(1-\sigma)\log_2(1-\sigma) + (1+\sigma)\log_2(1+\sigma) - 2\sigma.
  \end{equation}
  Note that $f(0)=0$ and
  \begin{equation}
    \label{eq:f'}
    f'(\sigma)=\log_2\(\frac{1+\sigma}{1-\sigma}\)-2<0.
  \end{equation}
  This implies that~$f$ is decreasing for~$\sigma\in(0,\frac{1}{2}]$.  Hence,
  for any small~$\sigma>0$, the inequalities given in
  \eqref{eq:first}--\eqref{eq:last} fail for~$n\geq n_0(\sigma)$.  Thus, as in
  Case~\ref{case:small_r}, assumption~\eqref{eq:assump} cannot hold.  This
  completes the proof of Case~\ref{case:large_r}, and hence~(\textit{ii}) of
  Theorem~\ref{thm:s_r(n)_lwbd} is proved.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:mu(n)_lwbd}}
\label{sec:pf_of_mu(n)_lwbd}
We now consider the `multiplicity' parameter~$\mu(n)$.

\begin{proof}[Proof of Theorem~\ref{thm:mu(n)_lwbd}]
 We wish to show that there exists a graph $G$ such
 that for any $\phi\:[n]\to\ZZ^+$ such that $G$ is a $\phi$-graph, no element of
 $\Dist(\phi)$ has cardinality $2+8\log_2n$ or more.
 
 Suppose~$\phi\:[n]\to\ZZ^+$ is an injective function such that~$\sim_{\phi}$
 has an equivalence class~$C\subset{[n]\choose2}$ of
 cardinality~$\mu\geq2+8\log_2n$.  It is clear that~$C$ spans a disjoint union
 of paths on~$[n]$.  Therefore, there is a matching~$M\subset C$
 with~$|M|\geq|C|/2$.  Let~$\nu=|M|\geq1+4\log_2n$.  Considering this
 matching, one sees that there are~$2\nu$ distinct integers
  \begin{equation}
    \label{eq:x_iy_i}
    x_1<y_1,x_2<y_2,\dots,x_\nu<y_\nu
  \end{equation}
  in~$\im(\phi)$ with all the differences~$y_i-x_i$ ($1\leq i\leq\nu$) equal.
  
  Clearly, by the definition of~$G(\phi,\cD)$, regardless of~$\cD$, the
  subgraphs of $G(\phi,\cD)$ induced by the~$x_i$ ($1\leq i\leq\nu$) and
  the~$y_i$ ($1\leq i\leq\nu$) are isomorphic.  To prove our theorem, namely,
  to verify~\eqref{eq:mu(n)_lwbd}, it suffices to prove the following fact.

  \begin{fact}
    \label{fact:Erdos}
    For all large enough~$n$, there is an $n$-vertex graph~$G$ that does not
    contain two vertex disjoint, isomorphic induced subgraphs of
    order~$\nu\geq1+4\log_2n$.
  \end{fact}
  \begin{proof}
    Consider the binomial random graph~$G=G(n,p)$ with~$p=1/2$, and
    let~$\nu=\nu(n)\geq1+4\log_2n$ be given.  Let~$X_\nu=X_\nu(G)$ be the
    number of pairs~$(H,H')$ of induced subgraphs of~$G$ of order
$\nu$ with~$H$ isomorphic
    to~$H'$.  Then 
    \begin{equation}
      \label{eq:expectation}
      \PP(X_\nu>0)\leq\EE(X_\nu)<n^{2\nu}2^{-{\nu\choose2}}
      =\(n^22^{-(\nu-1)/2}\)^\nu\leq1,
    \end{equation}
    and therefore a graph as required does exist.
  \end{proof}

  As observed above, Fact~\ref{fact:Erdos} concludes the proof of
  Theorem~\ref{thm:mu(n)_lwbd}. 
\end{proof}

\section{Proofs of Theorems~\ref{thm:D(n)_lwbd}, \ref{thm:gamma(G)_upbd},
  and~\ref{thm:De(n)_lwbd}}  
\label{sec:_D(n)_De(n)}
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~$\phi$.

\begin{remark} 
  \label{rem:1}
  \begin{enumerate}
  \item[(\textit{i})]Fix~$\phi\:[n]\to\ZZ^+$.  Then
    \begin{equation}
      \label{eq:no_Gs_ind}
      \big|\{G(\phi,\cD)\:\cD\subset\ZZ^+\}\big|\leq2^{|\Dist(\phi)|}.
    \end{equation}
  \item[(\textit{ii})]Fix~$\phi\:[n]\to\ZZ^+$ and let~$D$ be an
integer.  Then
    \begin{equation}
      \label{eq:no_Gs_cD}
      \big|\{G(\phi,\cD)\:|\cD|\leq D\}\big|  
      \leq\sum_{j=0}^D{|\Dist(\phi)|\choose j}
      \leq\sum_{j=0}^D{{n\choose2}\choose j}.
    \end{equation}
  \end{enumerate}
\end{remark}


\subsection{Proofs of Theorems~\ref{thm:D(n)_lwbd} and \ref{thm:gamma(G)_upbd}}
\label{sec:pf_of_thm:D(n)_lwbd_thm:gamma(G)_upbd}
We start with our result concerning~$D(n)$.

\begin{proof}[Proof of Theorem~\ref{thm:D(n)_lwbd}]
We wish to show that for any $\epsilon>0$ and any
$n\ge n_0(\epsilon)$, there exists a graph $G$ on $n$ vertices such that
whenever $G$ is a $\phi$-graph we have $$|\Dist(\phi)|>{n\choose
2}-4n\log_2n+2n-\frac{1}{2}\log_2(2\pi n)-\epsilon.$$
  
  Let~$D={n\choose2}-4n\log_2n+2n-(1/2)\log_2(2\pi n)-\epsilon$,
  where~$\epsilon>0$ is an arbitrary fixed constant, and suppose for a contradiction that
  $D(n)\leq D$.  Note that if~$\phi\:[n]\to\ZZ^+$ is such
  that~$|\Dist(\phi)|\leq D$, then, by Remark~\ref{rem:1}(\textit{i}), we
  have
  \begin{equation}
    \label{eq:no_Gs_ind2}
    \big|\{G(\phi,\cD)\:\cD\subset\ZZ^+\}\big|\leq2^{|\Dist(\phi)|}
    \leq{1\over2^\epsilon\sqrt{2\pi n}}2^{n\choose2}n^{-4n}4^n.
  \end{equation}
  By Lemma~\ref{lem:T(n)_upbd}, as we let~$\phi\:[n]\to\ZZ^+$ vary, we
  have
  \begin{equation}
    \label{eq:T(n)_upbd.b}
    T(n)\leq(1+o(1))\(\e n^3\over4\)^n
  \end{equation}
  distinct $\sim_{\phi}$.  By~\eqref{eq:no_Gs_ind2}
  and~\eqref{eq:T(n)_upbd.b}, if we only consider~$\phi\:[n]\to\ZZ^+$ with
  $|\Dist(\phi)|\leq D$, we are able to produce
  \begin{equation}
    \label{eq:no_graphs_upbd}
    \leq(1+o(1))\(\e n^3\over4\)^n\(4\over
    n^4\)^n{2^{n\choose2}\over2^\epsilon\sqrt{2\pi n}}
    =(1+o(1))\(\e\over n\)^n{2^{n\choose2}\over2^\epsilon\sqrt{2\pi n}} 
  \end{equation}
  non-isomorphic graphs.  On the other hand, using Stirling's formula
  $n!=(1+o(1))(n/\e)^n\sqrt{2\pi n}$, we see that there are
  \begin{equation}
    \label{eq:no_graphs_lwbd}
    \geq{1\over n!}2^{n\choose2}
    \geq{1+o(1)\over\sqrt{2\pi n}}\(\e\over n\)^n2^{n\choose2}
  \end{equation}
  graphs on~$n$ vertices up to isomorphism.  According to our assumption
  that~$D(n)\leq D$, the quantity in~\eqref{eq:no_graphs_upbd} must be at
  least the quantity in~\eqref{eq:no_graphs_lwbd}, which is not the case
  for~$n\geq n_0(\epsilon)$.  This completes the proof of
  Theorem~\ref{thm:D(n)_lwbd}. 
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:gamma(G)_upbd}]
  We shall prove that for almost all graphs $G$ on $n$ vertices, if $G$ is a
  $\cD$-graph, then
  \begin{equation}\label{eq:De(G)bd}
    |\cD|\ge \frac{1}{2}{n\choose2}-(1+o(1))n^{3/2}\sqrt{\log n}.
  \end{equation}

  The proof of this result follows the same steps as the
  proof of Theorem~\ref{thm:D(n)_lwbd}, except that we shall make use of
  Remark~\ref{rem:1}(\textit{ii}) instead of Remark~\ref{rem:1}(\textit{i}).
  
  For any given~$k$, let us consider all $\cD$-graphs for all
  $\cD\subset\ZZ^+$ such that
  \begin{equation}
    \label{eq:k_def}
    |\cD|\leq D={1\over2}{n\choose2}-k.
  \end{equation}
  By Remark~\ref{rem:1}(\textit{ii}) and Lemma~\ref{lem:T(n)_upbd}, the number
  of such graphs is, up to isomorphism,
  \begin{multline}
    \label{eq:no_G(f,cD)_upbd}
    \leq T(n)\sum_{j=0}^D {{n\choose2}\choose j}
    \leq(1+o(1))\(\e n^3\over4\)^n\sum_{j=0}^D{{n\choose2}\choose j}\\
    \leq(1+o(1))\(\e
    n^3\over4\)^n2^{n\choose2}\exp\left\{-{2k^2{n\choose2}^{-1}}\right\}, 
  \end{multline}
  where in the last inequality we used that
  \begin{equation}
    \label{eq:large_dev}
    \sum_{j=0}^{\lceil N/2-a\rceil}{N\choose j}\leq2^N\e^{-2a^2/N}
  \end{equation}
  for all integers~$N\geq1$ and all real~$a$ (see, e.g.,
  \cite[Theorem~A.1]{alon92}).  From~\eqref{eq:no_G(f,cD)_upbd}, we see that
  if, for some $\epsilon>0$, an $\epsilon$-fraction of the graphs on $n$
  vertices are such that $\De(G)\le \frac{1}{2}{n\choose2}-k$, then we must
  have
  \begin{equation}
    \label{eq:no_Gs_vs_upbd}
    {\epsilon\over\sqrt{2\pi n}}\(\e\over n\)^n2^{n\choose2}
    \leq(1+o(1))\(\e
    n^3\over4\)^n2^{n\choose2}\exp\left\{-{2k^2{n\choose2}^{-1}}\right\}, 
  \end{equation}
  which tells us that
  \begin{equation}
    \label{eq:no_Gs_vs_upbd2}
    {\epsilon\over\sqrt{2\pi n}}\(4\over n^4\)^n
    \leq(1+o(1))\exp\left\{-{2k^2{n\choose2}^{-1}}\right\}.
  \end{equation}
  Therefore, for large enough~$n$, we have, say,
  \begin{equation}
    \label{eq:no_Gs_vs_upbd3}
    \frac{2}{\epsilon}\sqrt{\pi n}\(n^4\over4\)^n
    \geq\exp\left\{{2k^2{n\choose2}^{-1}}\right\},
  \end{equation}
  and hence
  \begin{equation}
    \label{eq:no_Gs_vs_upbd4}
    2k^2
    \leq{n\choose2}\(4n\log n-n\log4+{1\over2}\log(\pi n)+\log\frac{2}{\epsilon}\),
  \end{equation}
  which tells us that
  \begin{equation}
    \label{eq:no_Gs_vs_upbd5}
    k\leq(1+o(1))n^{3/2}\sqrt{\log n}.
  \end{equation}
  As~$\epsilon>0$ was arbitrary, this concludes the proof.
\end{proof} 

\subsection{Proof of Theorem~\ref{thm:De(n)_lwbd}}
\label{sec:pf_of_thm:De(n)_lwbd}
The proof of our result on~$\De(n)$, related to the number of `edge lengths'
in our representations of graphs, will be somewhat more technical.

\subsubsection{Preliminary lemmas}
\label{sec:prelims}
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~$\sim$ defined
on~$X$.  We are interested in the sets that may be obtained by taking unions
of equivalence classes of~$\sim$.  In fact, we are interested in such unions
that have a given cardinality~$T$.  In what follows, we shall
have~$N={n\choose2}$ and~$T$ quite close to~${n\choose2}$.

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~\ref{lem:extreme_case}).

Let a pair of non-negative integers~$\bfb=(b_1,b_2)$ such that
\begin{equation}
  \label{eq:b_12b2=nchoose2}
  b_1+2b_2={n\choose2}
\end{equation}
be given.  For all non-negative integers~$T$ and real~$g\geq0$, we let
\begin{equation}
  \label{eq:f_def}
  c(\bfb;T,g)=c(b_1,b_2;T,g)=\sum{b_1\choose t_1}{b_2\choose t_2},
\end{equation}
where the sum is over all integers~$t_1$ and~$t_2$ such that~$t_1+2t_2=T$,
and~$t_2\geq g$.  Note that, in~\eqref{eq:f_def}, we may ignore the terms
with~$t_2>b_2$.  In what follows, we always suppose that~$g\leq t_2\leq b_2$. 

\begin{lemma}
  \label{lem:extreme_case}
  Let~$\omega=\omega(n)\to\infty$ as~$n\to\infty$, and
  suppose~$\omega=o(\sqrt{n/\log n})$.  For any~$\bfb=(b_1,b_2)$ as above,
  if~$g\geq\omega n^{3/2}\sqrt{\log n}$ and
  \begin{equation}
    \label{eq:T_def}
    T={n\choose2}-\llceil\omega n^{3/2}\sqrt{\log n}\rrceil,
  \end{equation}
  then
  \begin{equation}
    \label{eq:f_upbd}
    c(b_1,b_2;T,g)\leq n^{-\omega n}{{n\choose2}\choose T}
  \end{equation}
  for all large enough~$n$.
\end{lemma}
\begin{proof}
  We start by splitting the sum in~\eqref{eq:f_def} into two parts.  Let us
  write~$\sumL$ for the sum over all integers~$t_1$ and~$t_2$ such
  that~$t_1+2t_2=T$, $t_2\geq g$, and, moreover,
  \begin{equation}
    \label{eq:b_2t_2_large}
    {b_2\choose t_2}\geq2n^{\omega n}.
  \end{equation}
  Let~$\sumS$ denote the sum over the remaining pairs~$(t_1,t_2)$
  in~\eqref{eq:f_def}.  Therefore,
  \begin{equation}
    \label{eq:f_split_sum}
    c(b_1,b_2;T,g)
    =\sumL{b_1\choose t_1}{b_2\choose t_2}
    +\sumS{b_1\choose t_1}{b_2\choose t_2}.
  \end{equation}
  The first sum in~\eqref{eq:f_split_sum} may be easily estimated from above,
  since   
  \begin{multline}
    \label{eq:sumL_upbd}
    \qquad
    2n^{\omega n}\sumL{b_1\choose t_1}{b_2\choose t_2}
    \leq\sumL{b_1\choose t_1}{b_2\choose t_2}^2\\
    \leq\sumL{b_1\choose t_1}{2b_2\choose2t_2}
    \leq{{n\choose2}\choose T}.
    \qquad
  \end{multline}
  Let us now consider the second sum in~\eqref{eq:f_split_sum}; that is, let
  us now consider~$t_1$ and~$t_2$ for which we have~${b_2\choose
    t_2}<2n^{\omega n}$.  We shall estimate the terms
  \begin{equation}
    \label{eq:terms}
    {b_1\choose t_1}{b_2\choose t_2}<2n^{\omega
      n}{b_1\choose t_1}
  \end{equation}
  by bounding~${b_1\choose t_1}$.  Let us first derive some conclusions from
  the fact that ${b_2\choose t_2}<2n^{\omega n}$.  Suppose~$b_2\geq2t_2$.
  Then
  \begin{equation}
    \label{eq:concl.1}
    2^{t_2}\leq\(b_2\over t_2\)^{t_2}
    \leq{b_2\choose t_2}<2n^{\omega n},
  \end{equation}
  and hence~$g\leq t_2<1+\omega n\log_2n$, which is a contradiction for large
  enough~$n$.  Therefore, we have~$b_2=t_2+s$ with~$0\leq s<t_2$.  But then
  \begin{equation}
    \label{eq:concl.2}
    2^s\leq\(b_2\over s\)^s\leq{b_2\choose s}={b_2\choose t_2}<2n^{\omega n},
  \end{equation}
  whence
  \begin{equation}
    \label{eq:s_small}
    s<1+\omega n\log_2n.
  \end{equation}
  For convenience, put~$N={n\choose2}$.  Now observe that
  \begin{multline}
    \label{eq:binom.fiddle}
    {b_1\choose t_1}
    ={N-2b_2\choose T-2t_2}
    ={N\choose T}
    {(N-T)_{2(b_2-t_2)}(T)_{2t_2}\over(N)_{2b_2}}\\
    \qquad\qquad={N\choose T}
    {(N-T)_{2s}\over(N)_{2s}}{(T)_{2t_2}\over(N-2s)_{2t_2}}.
  \end{multline}
  By~\eqref{eq:T_def}, \eqref{eq:s_small}, and the fact
  that~$\omega=o(\sqrt{n/\log n})$, the quantity in~\eqref{eq:binom.fiddle}
  is
  \begin{align}
    &\leq{N\choose T}
    \(N-T\over N\)^{2s}\(T\over N-2s\)^{2t_2}\nonumber\\
    &\qquad\leq{N\choose T}
    \(\llceil\omega n^{3/2}\sqrt{\log n}\rrceil\over N\)^{2s}
    \(N-\omega n^{3/2}\sqrt{\log n}\over N-2(1+\omega
    n\log_2n)\)^{2t_2}\nonumber\\ 
    &\qquad\leq{N\choose T}
    \(1-2\omega\sqrt{(\log n)/n}\over1-(5\omega\log_2n)/n\)^{2b_2}
    \leq{N\choose T}
    \(1-\omega\sqrt{\log n\over n}\)^{2b_2},\label{eq:b_1t_1.upbd.aux}
  \end{align}
  for all sufficiently large~$n$.  Using that~$b_2\geq t_2\geq g\geq\omega
  n^{3/2}\sqrt{\log n}$, we see that the quantity
  in~\eqref{eq:b_1t_1.upbd.aux} is
  \begin{equation}
    \label{eq:big_align}
    \leq{N\choose T}
    \exp\(-2\omega^2n\log n\)
    =n^{-2\omega^2n}{N\choose T}.
  \end{equation}
  Therefore,
  \begin{equation}
    \label{eq:sumS_upbd}
    \sumS{b_1\choose t_1}{b_2\choose t_2}
    <2Tn^{-2\omega^2n+\omega n}{{n\choose2}\choose T}
    <{1\over2}n^{-\omega n}{{n\choose2}\choose T}.
  \end{equation}
  Putting together~\eqref{eq:f_split_sum}, \eqref{eq:sumL_upbd},
  and~\eqref{eq:sumS_upbd}, we get that
  \begin{equation}
    \label{eq:f_upbd.final}
    c(b_1,b_2;T,g)
    =\sumL{b_1\choose t_1}{b_2\choose t_2}
    +\sumS{b_1\choose t_1}{b_2\choose t_2}
    \leq n^{-\omega n}{{n\choose2}\choose T},
  \end{equation}
  as required.  
\end{proof}

We may interpret Lemma~\ref{lem:extreme_case} as follows.  Suppose we have a
partition of~${[n]\choose2}$ into~$b_1$ blocks of cardinality~$1$ and~$b_2$
blocks of cardinality~$2$.  Let us call a set~$E\subset{[n]\choose2}$
compatible with this partition if~$E$ is a union of blocks of this partition.
We are interested in compatible, $T$-element subsets~$E$ of~${[n]\choose2}$,
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(\bfb;T,g)$ defined in~\eqref{eq:f_def}, we are only
counting those sets~$E$ for which we pay at least~$g$ pence, and
Lemma~\ref{lem:extreme_case} tells us that not many sets~$E$ cost at least~$g$.

In our next lemma, we consider a general partition~$\pi$ of~${[n]\choose2}$,
with~$b_i$ blocks of cardinality~$i$ ($i\geq1$).  Lemma~\ref{lem:comparison}
tells us that the number of $T$-element subsets~$E$ of~${[n]\choose2}$ with
cost~$\geq 2g$, compatible with~$\pi$, is dominated by the number of
$T$-element subsets~$E$ of~${[n]\choose2}$ with cost~$\geq g$, compatible
with~$\pi'$, a certain partition with blocks of cardinality~$1$ and~$2$ only.

Let us describe the setup that we consider in Lemma~\ref{lem:comparison},
which is, in fact, a purely numerical result.  Suppose we have a
sequence~$\bfb=(b_1,b_2,\dots)$ of non-negative integers such that
\begin{equation}
  \label{eq:b_1b_2...nchoose2}
  b_1+2b_2+3b_3+\dots={n\choose2}.
\end{equation}
For all non-negative integers~$T$ and real~$g\geq0$, we let
\begin{equation}
  \label{eq:F_def}
   C(\bfb;T,g)=C(b_1,b_2,\dots;T,g)
  =\sum\prod_{i\geq1}{b_i\choose t_i},
\end{equation}
where the sum is over all sequences~$\bft=(t_1,t_2,\dots)$ of non-negative
integers such that
\begin{equation}
  \label{eq:ts_part_T}
  t_1+2t_2+3t_3+\dots=T
\end{equation}
and
\begin{equation}
  \label{eq:general_gap}
  t_2+2t_3+3t_4+\dots=\sum_{i\geq2}(i-1)t_i\geq g.
\end{equation}

Given~$\bfb=(b_1,b_2,\dots)$ as above, let~$b_1'$ and $b_2'$ be given by
\begin{equation}
  \label{eq:b_1'_def}
  b_1'=b_1+b_3+b_5+\dots=\sum_{k\geq0}b_{2k+1}
\end{equation}
and
\begin{equation}
  \label{eq:b_2'_def}
  b_2'=b_2+b_3+2b_4+2b_5+\dots
  =\sum_{k\geq2}\llfloor k\over2\rrfloor b_k.
\end{equation}
Note that, then, we have
\begin{equation}
  \label{eq:b_1'2b_2'}
  b_1'+2b_2'={n\choose2}.
\end{equation}

\begin{lemma}
  \label{lem:comparison}
  Let~$\bfb$, $T$, and~$g$ be as above.  Then
  \begin{equation}
    \label{eq:comparison}
    C(\bfb;T,2g)\leq c(b_1',b_2';T,g).
  \end{equation}
\end{lemma}
\begin{proof}
  Consider a partition $\pi$ of ${[n]\choose 2}$ into $b_i$ blocks of size $i$
  for all $i\ge 1$.  Then $\pi$ induces another partition $\pi'$ of
  ${[n]\choose 2}$ into $b_1'$ blocks of size~$1$ and $b_2'$ blocks of
  size~$2$, where~$b_1'$ and~$b_2'$ are as in~\eqref{eq:b_1'_def}
  and~\eqref{eq:b_2'_def}.  We construct~$\pi'$ from $\pi$ 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 ${[n]\choose 2}$ that is a union of
  blocks from~$\pi$.  Then, clearly, $E$ is a $T$-element subset composed
  solely of blocks from~$\pi'$.  It remains to show that if $E$ has `cost' at
  least $2g$ in $\pi$, then $G$ has cost at least $g$ in $\pi'$.
  
  Consider any block with $2k+1$ elements contained in $E$.  In $\pi$, such a
  block would cost $2k$ pence.  The corresponding blocks in $\pi'$ 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 $\pi$ would cost
  $2k-1$ pence, while the corresponding $k$ blocks of size 2 in $\pi'$ would
  also cost $k$ pence in total.  This implies that the cost of any block in
  $\pi$ is reduced by at most half in $\pi'$. Thus, if the total cost of $E$
  is at least $2g$ pence in $\pi$, then $E$ would cost at least $g$ pence in
  $\pi'$, and the result holds.
\end{proof}

\subsubsection{The proof} \label{sec:pf_thm:De(n)_lwbd} Having dealt with the
technical lemmas in Section~\ref{sec:prelims}, the proof of
Theorem~\ref{thm:De(n)_lwbd} will be straightforward.  Recall that we wish to
show that for any sufficiently large $n$ and $\omega=\omega(n)$ such that
$\omega(n)\to\infty$ as $n\to\infty$, there exists a graph $G$ on $n$ vertices
such that whenever $G$ is a $\cD$-graph, then $$|\cD|\ge{n\choose
2}-3\omega n^{3/2}\sqrt{\log n}-3.$$


\begin{proof}[Proof of Theorem~\ref{thm:De(n)_lwbd}]
  Let~$\omega=\omega(n)$ as in the statement of our theorem be given.  We may
  clearly suppose that~$\omega=o(\sqrt{n/\log n})$.
  
  Fix~$\phi\:[n]\to\ZZ^+$, and consider the equivalence relation~$\sim_{\phi}$
  defined on~${[n]\choose2}$.  Let~$\bfb=(b_1,b_2,\dots)$, where~$b_i$
  ($i\geq1$) is the number of blocks, i.e., equivalence classes,
  of~$\sim_{\phi}$ with cardinality~$i$.
  
  Let us write~$\cG(n,T)$ for the class of $n$-vertex graphs with~$T$ edges, up
  to isomorphism, where
  \begin{equation}
    \label{eq:T_def.2}
    T={n\choose2}-\llceil\omega n^{3/2}\sqrt{\log n}\rrceil.
  \end{equation}
  We have
  \begin{equation}
    \label{eq:G(n,T)_lwbd}
    |\cG(n,T)|\geq{1\over n!}{{n\choose2}\choose T}.
  \end{equation}
  Let \begin{equation}
        g=\llceil\omega n^{3/2}\sqrt{\log n}\rrceil
  \end{equation} and observe that the number of graphs in~$\cG(n,T)$ that are
  isomorphic to some~$G(\phi,\cD)$ ($\cD\subset\ZZ^+$) with
  \begin{equation}
    \label{eq:gap_cond}
    T-|\cD|\geq 2g=2\llceil\omega n^{3/2}\sqrt{\log n}\rrceil
  \end{equation}
  is 
  \begin{equation}
    \label{eq:F_as_upbd}
    \leq C(\bfb;T,2g)
    \leq n^{-\omega n}{{n\choose2}\choose T},
  \end{equation}
  where the second inequality in~\eqref{eq:F_as_upbd} follows from
  Lemmas~\ref{lem:extreme_case} and~\ref{lem:comparison}.
  
  Recall that we are considering a fixed~$\phi\:[n]\to\ZZ^+$.  However, as we
  consider all~$\phi\:[n]\to\ZZ^+$, we only have
  \begin{equation}
    \label{eq:T(n)_upbd.bb}
    T(n)\leq(1+o(1))\(\e n^3\over4\)^n
  \end{equation}
  distinct equivalence relations (see~\eqref{eq:T(n)_def} and
  Lemma~\ref{lem:T(n)_upbd}).  Therefore, using~\eqref{eq:F_as_upbd}
  and~\eqref{eq:T(n)_upbd.bb}, we see that the number of graphs in~$\cG(n,T)$
  that are $\cD$-graphs with~$\cD$ satisfying~\eqref{eq:gap_cond} is
  \begin{equation}
    \label{eq:T(n)F_as_upbd}
    \leq T(n)C(\bfb;T,2g)
    \leq(1+o(1))\(\e n^3\over4\)^nn^{-\omega n}{{n\choose2}\choose T},
  \end{equation}
  which is a great deal smaller than the lower bound given
  in~\eqref{eq:G(n,T)_lwbd}.  This shows that there is a graph~$G_0$
  in~$\cG(n,T)$ such that if~$G_0$ is isomorphic to~$G(\phi,\cD)$ for
  some~$\phi\:[n]\to\ZZ^+$ and~$\cD\subset\ZZ^+$, then~$T-|\cD|<2g$.  This
  graph~$G_0$ shows that
  \begin{multline}
    \label{eq:De(n)_lwbd_kill}
    \quad\De(n)=\max_G\De(G)>T-2g\\
    =T-2\llceil\omega n^{3/2}\sqrt{\log n}\rrceil
    >{n\choose 2}-3\omega n^{3/2}\sqrt{\log n}-3,\quad
  \end{multline}
  as required.  
\end{proof}

\subsection{Proof of Corollary~\ref{sec:simultaneous_De_s}}
\label{sec:pf_of_cor}
Corollary~\ref{sec:simultaneous_De_s} follows from
Theorem~\ref{thm:De(n)_lwbd} and Lemma~\ref{lem:ET}.

\begin{proof}[Proof of Corollary~\ref{sec:simultaneous_De_s}]
  Let~$\epsilon>0$ and~$\omega=\omega(n)\to\infty$ as~$n\to\infty$ be given.
  Recall Theorem~\ref{thm:De(n)_lwbd}, and let~$n$ be large enough so that
  there is an $n$-vertex graph~$G$ for which we have
  \begin{equation}
    \label{eq:large_De.again}
    \De(G)\geq{n\choose2}-3\omega n^{3/2}\sqrt{\log n}-3.
  \end{equation}
  Let~$\phi\:[n]\to\ZZ^+$ and~$\cD\subset\ZZ^+$ be such that~$G$ is isomorphic
  to~$G(\phi,\cD)$.  We may clearly suppose that
  \begin{equation}
    \label{eq:WLOG_Dist_geq_cD}
    |\Dist(\phi)|\geq|\cD|.
  \end{equation}
  We shall show that~$\max\im(\phi)$ is at least as large as the right-hand
  side of~\eqref{eq:large_s} if~$n$ is sufficiently large, and this will
  conclude the proof of Corollary~\ref{sec:simultaneous_De_s}.
  
  Inequalities~\eqref{eq:large_De.again} and~\eqref{eq:WLOG_Dist_geq_cD} imply
  that~$|\Dist(\phi)|$ is at least as large as the right-hand side
  of~\eqref{eq:large_De.again}.  Therefore~\eqref{eq:quasi-Sidon} in
  Lemma~\ref{lem:ET} holds with~$\epsilon=(6+o(1))\omega\sqrt{(\log n)/n}$,
  and hence that lemma implies that
  \begin{equation}
    \label{eq:large_imphi}
    \max\im(\phi)\geq\(1-(2\sqrt6+o(1))\omega^{1/2}\(\log n\over n\)^{1/4}\)n^2.
  \end{equation}
  The result follows by taking~$n\geq n_0(\epsilon)$.
\end{proof}

\section{Concluding remarks}
\label{sec:conclude}
Theorems~\ref{thm:gamma(G)_upbd} and~\ref{thm:De(n)_lwbd} may be generalized
to representations of graphs in high-dimensional Euclidean spaces.  More
precisely, we consider the graphs $G(\phi,\cD)$, but now
with~$\phi\:[n]\to\RR^d$ and~$\cD\subset\RR$.  Let
\begin{multline}
  \label{eq:DRR_e_def}
  \quad
  \De^\RR(d,G)=\min\{|\cD|\:\text{$\cD\subset\RR$ for which
    $\exists\phi\in\big(\RR^d\big)^{[n]}$}\\
  \text{such that~$G$ is isomorphic to~$G(\phi,\cD)$}\},
  \quad
\end{multline}

Note that, even for~$d=2$, it becomes easier to represent graphs in the
form~$G(\phi,\cD)$ in~$\RR^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,
$\De^\RR(2,T)=1$.  We mention that bounded degree graphs may be represented in
bounded dimension: as proved in~\cite{rodl:E_n}, if a graph $G$ has maximum
degree $\Delta$, then $\De^\RR(2\Delta,G)=1$.

Let us now put~$\De^\RR(d,n)=\max_G\De^\RR(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~\ref{thm:De(n)_lwbd} holds for~$\De^\RR(d,n)$.  Moreover, one may also
prove a bound similar to the one in Theorem~\ref{thm:gamma(G)_upbd}
for~$\De^\RR(d,G)$ for almost all $n$-vertex graphs~$G$.  To prove these
results, one may use a well known result of Warren~\cite{warren68:_lower}.

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~$\De(n)$ with similar upper bounds?  Can one give a non-trivial bound from
below for~$\mu(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~\cite[Remark~7.2]{babai:cayley2}, 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.
%As in \ref{prop:starspace}, the difficulty lies in establishing that the
%proposed spacing number is correct from below.
It would be of some interest to find exactly the spacing numbers of more
graphs.

\subsection*{Acknowledgements}
The authors would like to thank John Schmitt and Brian Wagner for their help
in proving Proposition~\ref{proposition:kmnspace}.  We would also like to
extend our thanks to B.~Bollob\'as, 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.%\vspace{-1.5cm}

%========================= references ========================================
\bibliographystyle{amsplain}
%\bibliography{spacing}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{alon92}
Noga Alon and Joel~H. Spencer, \emph{The probabilistic method}, John Wiley \&
  Sons Inc., New York, 1992, With an appendix by Paul Erd\H os, A
  Wiley-Interscience Publication. \MR{93h:60002}

\bibitem{babai:cayley2}
L{\'a}szl{\'o} Babai and Vera~T. S{\'o}s, \emph{Sidon sets in groups and
  induced subgraphs of {C}ayley graphs}, European J. Combin. \textbf{6} (1985),
  no.~2, 101--114. \MR{87f:05081}

\bibitem{bakerprimes}
R.~C. Baker, G.~Harman, and J.~Pintz, \emph{The difference between consecutive
  primes. {II}}, Proc. London Math. Soc. (3) \textbf{83} (2001), no.~3,
  532--562. \MR{2002f:11125}

\bibitem{bender78}
E.~Bender and E.R. Canfield, \emph{The asymptotic number of labeled graphs with
  given degree sequences}, J. Combinatorial Theory Ser. A \textbf{24} (1978),
  no.~3, 296--307. \MR{58 \#21793}

\bibitem{BBf}
B{\'e}la Bollob{\'a}s, \emph{Random graphs}, second ed., Cambridge Studies in
  Advanced Mathematics, vol.~73, Cambridge University Press, Cambridge, 2001.
  \MR{2002j:05132}

\bibitem{bollobas03:_integ}
B\'ela Bollob\'as and Oleg Pikhurko, \emph{Integer sets with prescribed
  pairwise differences being distinct}, manuscript, 12pp, 2003.

\bibitem{bregman73:_certain}
L.~M. Br{\`e}gman, \emph{Certain properties of nonnegative matrices and their
  permanents}, Dokl. Akad. Nauk SSSR \textbf{211} (1973), 27--30. \MR{48
  \#6130}

\bibitem{egorycev80:_reshen_varden}
G.~P. Egory{\v{c}}ev, \emph{Reshenie problemy van-der-{V}ardena dlya
  permanentov}, Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., Krasnoyarsk, 1980,
  Preprint IFSO-13 M. \MR{82e:15006}

\bibitem{erdos_sidon}
P.~Erd\H{o}s and P.~Tur\'{a}n, \emph{On a problem of {S}idon in additive number
  theory, and on some related problems}, J. London Math. Soc. \textbf{16}
  (1941), 212--215.

\bibitem{falikman81:_proof_waerd}
D.~I. Falikman, \emph{Proof of the van der {W}aerden conjecture on the
  permanent of a doubly stochastic matrix}, Mat. Zametki \textbf{29} (1981),
  no.~6, 931--938, 957. \MR{82k:15007}

\bibitem{graham94:_concr}
Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik, \emph{Concrete
  mathematics}, second ed., Addison-Wesley Publishing Company, Reading, MA,
  1994, A foundation for computer science. \MR{97d:68003}

\bibitem{HalberstamRoth2ndEd}
Heini Halberstam and Klaus~Friedrich Roth, \emph{Sequences}, second ed.,
  Springer-Verlag, New York, 1983, MR83m:10094.

\bibitem{lindstroem69:_b}
Bernt Lindstr{\"o}m, \emph{An inequality for {$B\sb{2}$}-sequences}, J.
  Combinatorial Theory \textbf{6} (1969), 211--212. \MR{38 \#4436}

\bibitem{lindstroem72:_b}
\bysame, \emph{On {$B\sb{2}$}-sequences of vectors}, J. Number Theory
  \textbf{4} (1972), 261--265. \MR{46 \#3322}

\bibitem{rodl:E_n}
Hiroshi Maehara and Vojt{\v{e}}ch R{\"o}dl, \emph{On the dimension to represent
  a graph by a unit distance graph}, Graphs Combin. \textbf{6} (1990), no.~4,
  365--367. \MR{91m:05176}

\bibitem{mckay91:_asymp}
Brendan~D. McKay and Nicholas~C. Wormald, \emph{Asymptotic enumeration by
  degree sequence of graphs with degrees {$o(n\sp {1/2})$}}, Combinatorica
  \textbf{11} (1991), no.~4, 369--382. \MR{93e:05002}

\bibitem{pikhurko03:_dense}
Oleg Pikhurko, \emph{Dense edge-magic graphs and thin additive bases},
  submitted, 2003.

\bibitem{ronyai01}
L.~R{\'o}nyai, L.~Babai, and M.K. Ganapathy, \emph{On the number of
  zero-patterns of a sequence of polynomials}, J. Amer. Math. Soc. \textbf{14}
  (2001), no.~3, 717--735. \MR{2002f:11026}

\bibitem{shamir84:_large}
E.~Shamir and E.~Upfal, \emph{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}

\bibitem{singer38}
James Singer, \emph{A theorem in finite projective geometry and some
  applications to number theory}, Trans. Amer. Math. Soc. \textbf{43} (1938),
  no.~3, 377--385. \MR{1 501 951}

\bibitem{warren68:_lower}
Hugh~E. Warren, \emph{Lower bounds for approximation by nonlinear manifolds},
  Trans. Amer. Math. Soc. \textbf{133} (1968), 167--178. \MR{37 \#1871}

\end{thebibliography}

%=============================================================================
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
