Classification of crescent configurations
Let $n$ points be in crescent configurations in $\mathbb{R}^d$ if they lie in general position in $\mathbb{R}^d$ and determine $n-1$ distinct distances, such that for every $1 \leq i \leq n-1$ there is a distance that occurs exactly $i$ times. Since Erdős' conjecture in 1989 on the existence of $N$ sufficiently large such that no crescent configurations exist on $N$ or more points, he, Pomerance, and Palásti have given constructions for $n$ up to $8$ but nothing is yet known for $n \geq 9$. Most recently, Burt et. al. had proven that a crescent configuration on $n$ points exists in $\mathbb{R}^{n-2}$ for $n \geq 3$. In this paper, we study the classification of these configurations on $4$ and $5$ points through graph isomorphism and rigidity. Our techniques, which can be generalized to higher dimensions, offer a new viewpoint on the problem through the lens of distance geometry and provide a systematic way to construct crescent configurations.
\section{Introduction}
Erd\H{o}s once wrote, ``my most striking contribution to geometry is, no doubt, my problem on the number of distinct distances,'' \cite{Erd96}. The referred question, which asks what is the minimum number of distinct distances determined by $n$ points, was first asked in 1946 \cite{Erd46} and marked the beginning of a chain of variants. See \cite{She} and \cite{SM15} for a survey on these. Although one would expect all distances between $n$ points to be different if they were to be placed in the plane at random, if the distances are regularly placed, such as on a lattice, then many distances may repeat. Erd\H{o}s' conjectured lower bound, $\Omega(n/\sqrt{\log{n}})$, attained by a $\sqrt{n}\times \sqrt{n}$ integer lattice, was essentially proven up to a $\sqrt{\log{n}}$ factor by Guth and Katz in 2010. \cite{GK}

The variant we study in this paper is one where the distances have prescribed multiplicities. One says $n$ points are in crescent configuration in $\mathbb{R}^d$ if they are in general position and determine $n-1$ distinct distances such that for every $1 \leq i \leq n-1$, there is a distance that occurs exactly $i$ times. Erd\H{o}s conjectured that there exists a sufficiently large $N$ such that no crescent configuration exists on $N$ or more points \cite{Erd89}. Though constructions have been provided for $n=5,6,7,8$ by Erd\H{o}s, I. Pal\'asti and C. Pomerance \cite{Pal87, Pal89, Erd89}, little progress has been made towards a construction for $n \geq 9$. One problem often encountered in the search for these configurations is the lack of understanding of their properties and the difficulty in exhibiting the configurations' information combinatorially.

As such, we take a new approach to studying these crescent configurations, borrowing techniques from distance geometry and graph theory. Our main theorems are the results of two algorithms that search for and classify all crescent configurations on any $n \geq 4$ up to graph isomorphism and find geometric realizations for each of these isomorphism classes in the plane. 
\begin{theorem} \label{thm:3on4}
Given a set of three distinct distances $\{d_1,d_2,d_3\}$ on four points,  there are only three allowable crescent configurations up to graph isomorphism. In Figure \ref{fig:mcr} we provide graph realizations for each type.
\end{theorem}
\begin{figure}[h]
\includegraphics[width=\linewidth]{MCRMain.png}
\caption{Types M, C, and R.}
\label{fig:mcr}
\end{figure}
\begin{theorem}\label{thm:27on5}
Given a set of four distinct distances $\{d_1,d_2,d_3,d_4\}$ on five points, 
there are 27 allowable crescent configurations up to graph isomorphism. In Figure \ref{fig:allFIVE} we provide graph realizations for each type.
\end{theorem}
\begin{figure}[h]
\includegraphics[width=\textwidth]{configson52.png}
\caption{Representatives for all possible crescent configurations on five points.}
\label{fig:allFIVE}
\end{figure}

The advantage of this algorithmic method is that it can be applied in higher dimensions, though we hope that the running time ($\mathcal{O}(n^{n})$) can still be vastly improved.

In Appendix \ref{app: 5points} we include distance sets and realizable distances for each crescent configuration on four and five points.
\par

In Section 2, we introduce our distance geometry approach and prove a classification of crescent configurations for a general $n$. We follow this in Section 3 with an outline of the first half of the algorithm used to achieve Theorems \ref{thm:3on4} and \ref{thm:27on5}. 
We then move to Section 4 where we discuss how distance geometry methods may be applied to determine whether a distance set is realizable. In Section 5, we outline the second half of the algorithm, completing the proofs for Theorems \ref{thm:3on4} and \ref{thm:27on5}. After the theorems have been established, we discuss another way to verify the uniqueness of our isomorphism classes and also a different method to characterize these configurations through analysis of rigidity in Section 6. Lastly, we discuss potential future work based on our approach using graph theory, rigidity, and distance geometry.

\begin{rem} The authors are happy to provide copies of any code referenced in the course of this paper. Please email \href{mailto:Steven.Miller.MC.96@aya.yale.edu}{Steven.Miller.MC.96@aya.yale.edu}.
\end{rem}


\section{Classification of Crescent Configurations}\label{sec:classification}
In this section we provide the key definitions and theorems that we use to classify crescent configurations.
\begin{defi}[General Position \cite{SM15}]\label{def:genpos}
We say that n points are in general position in $\mathbb{R}^d$ if no d+1 points lie on the same hyperplane and no d+2 lie on the same hypersphere.
\end{defi}

\begin{defi}[Crescent Configuration \cite{SM15}] We say $n$ points are in crescent configuration (in $\mathbb{R}^{d}$) if they lie in general position in $\mathbb{R}^{d}$ and determine $n - 1$ distinct distances, such that for every $1 \leq i \leq n - 1$ there is a distance that occurs exactly $i$ times.
\end{defi}

The notion of general position is very important in the construction of crescent configuration. Without this notion, the problem of placing $n$ points in $\mathbb{R}^d$ to determine $n-1$ distinct distances satisfying the prescribed multiplicities becomes trivial. By simply placing $n$ points on a line in an arithmetic progression, we solve the problem in any dimension. 

\vspace{0.2cm}
\begin{defi}[Distance Coordinate]The \emph{distance coordinate}, $D_{A}$, of a point $A$ is the multiset of all distances, counting multiplicity, between $A$ and the other points in a set $\mathcal{P}$. Order does not matter.
\end{defi}
\begin{defi}[Distance Set] The \emph{distance set}, $\mathcal{D}$ corresponding to a set of points, $\mathcal{P}$, is the multiset of the distance coordinates for each point in the $\mathcal{P}$. 
\end{defi}
\begin{defi} [Isomorphism for Labeled Graph \cite{Gervasi}]\label{def:isomorphism} Graph A is isomorphic to graph B if and only if there exists a bijective function $f: V(A) \mapsto V(B)$, (where V(A) and V(B) are the vertex spaces) such that:
\begin{enumerate}
\item $\forall a_{i} \in A, \ l_{A}(a_{i}) = l_{B}(f(a_{i}))$,
\item $\forall a_{i},a_{j} \in V, \hspace{2mm} \{a_{i},a_{j}\}\in E_{A}\leftrightarrow \{f(a_{i}),f(a_{j})\}\in E_{B}$, and 
\item $\forall \{a_{i},a_{j}\}\in E_{A}, w_{A}(\{a_{i},a_{j}\})=w_{B}(f(\{a_{i},a_{j}\}))$, 
\end{enumerate}
where $\{l_{A}, l_{B}\}$ and $\{w_{A}, w_{B}\}$ are functions that define the labels of the vertices and edges of A and B respectively.
\end{defi}

\vspace{0.2cm}

We note that a crescent configuration on $n$ points can be considered a weighted complete graph with $n-1$ distinct weights associated to the edges in a certain manner, so that the configuration can be realized in $\mathbb{R}^d$. The adjacency matrix, thus, is a 
natural way to store  information about the configuration. Should we rearrange the weights that each vertex is incident to, we would most likely have to draw a configuration differently. Due to this insight, we have the following theorem.
\begin{theorem}\label{thm: graphisom}
Let $A$ and $B$ be two crescent configurations on the same number of points $n$. If $A$ and $B$ have the same distance sets, then there exists a graph isomorphism from $A$ to $B$. 
\end{theorem}
\begin{proof}
Consider two crescent configurations, $A$ and $B$, each on $n$ points, $\{a_{1},...,a_{n}\}$ and $\{b_{1},...,b_{n}\}$, such that $A$ and $B$ have the same distance sets (up to order of the entries of the coordinates). We note that we do not yet care about the specific distances and, instead, designate each distance by the points that define them, as will be shown below. 

\par
First we show that the ordering of the  elements of the distance coordinates does not matter when comparing the distance sets. Then we prove that $A$ and $B$ are isomorphic when we view them as labeled graphs.

\par
Consider $A$. First, we number each point of $A$ from $1$ to $n$. For each point $a_{i}$, $1\leq i \leq n$, in the configuration, we re-order its distance coordinate so that the distance between $a_{i}$ and $a_{1}$, $d_{a_{i,1}}$, is in the first slot, the distance between $a_{i}$ and $a_{2}$, $d_{a_{i,2}}$, is in the second slot, and so on, inserting 0 into the $i$th slot, representing the distance between $a_{i}$ and $a_{i}$. We will call these \emph{augmented distance coordinates}. All of our augmented distance coordinates uniquely determine the points that they represent. Note that the arrangement of these augmented coordinates depends on how we choose to index the points of $A$. The nonzero entries, however, only encode information about the set of distances between a point and all other points in a given configuration. They do not account for relative position. That is to say, until assign a number to each of the points of $A$ (i.e., $a_1$, $a_2$, and so on), the order of the entries of the distance coordinates does not matter. The distance coordinate $\{d_1,d_2,d_3\}$ is the same as the coordinate $\{d_3,d_1,d_2\}$.\\

\par
Next we do the same thing for $B$. Since the distance sets of $A$ and $B$ are the same, we know that for every augmented coordinate in $A$, there is an augmented coordinate in $B$ with the same set of non-zero entries. Thus, let $a_{i}$ and $b_{j}$ have the same non-zero entries in their augmented coordinates. We define each point by its augmented coordinate, $$D_{a_{i}}=(d_{a_{i,1}},...,d_{a_{i,i-1}},0,d_{a_{i,i+1}},...,d_{a_{i,n}})$$ $$D_{b_{j}}=(d_{b_{j,1}},...,d_{b_{j,j-1}},0,d_{b_{j,j+1}},...,d_{b_{j,n}}).$$ Since the set of non-zero entries in $D_{a_{i}}$ and $D_{b_{j}}$ are the same, we know that there exists a permutation, $f_{ij}$ such that $f_{ij}(D_{a_{i}})= D_{b_{j}}$. Since we know that every distance coordinate in $A$ has a match in $B$, there exists a permutation function of this sort that maps $D_{a_{i}}$ to some $D_{b_{j}}$ for all $1\leq i \leq n$.
\par
Furthermore, we actually only need one permutation for all of the reordered coordinates of $A$. This can be quickly seen by recognizing that the ordering of a single augmented distance coordinate of $A$ determines the ordering of all augmented distance coordinates if we wish to retain all information. To prove that it this is indeed the case, we point out that the reordered distance coordinates of $A$ are, in fact, the rows and columns of a weighted adjacency matrix. The adjacency matrix below models a configuration on $3$ points. The element in row $1$, column $2$ represents the distance between points $a_1$ and $a_2$. 
$$\begin{bmatrix}
0&d_{1,2}&d_{1,3}\\
d_{1,2}&0&d_{2,3}\\
d_{1,3}&d_{2,3}&0
\end{bmatrix}$$
From this, a proof by induction will show that if we permute the entries of row $1$, the other rows (and columns) must undergo the same permutation in order to preserve the symmetry of the matrix. 

\par
We now identify each point of $A$ and $B$ by these augmented and rematched distance coordinates to create two labelled and weighted graphs where the vertices are the points of $A$ and $B$, and each edge $\{a_i,a_j\}$ is weighted by the distance between the two points, $d_{a_{i,j}}$. In these graphs, the vertex labels are the augmented distance coordinates of each point, where the coordinates of $A$ are further transformed by $f_{ij}$, and the edge labels are the distinct distances, $d_1,d_2,....,d_{n-1}$ that define our crescent configurations. Given this information, it is very straightforward to prove that these graphs are isomorphic by showing that they satisfy the three conditions in Definition \ref{def:isomorphism}.

\par
 Let $F: V(A_{D}) \mapsto V(B_{D})$ be such that $F(a_{i})=b_j$, where $b_j$ is chosen so that the distance coordinates of $a_i$ and $b_j$ have the same nonzero values. Since we augmented and transformed our distance coordinates by the permutation function $f_{ij}$, we know that $a_{i}$ and $b_{j}$ have the same vertex labels.
Thus, we know $F$ is one-to-one because the distance sets of $A$ and $B$ are the same. Furthermore, we know that $F$ is onto because $A$ and $B$ both have $n$ points. Therefore, $\forall b_{j}\in B$, $\exists \ a_{i} \in A$ such that $F(D_{a_{i}})=D_{b_{j}}$. Therefore, F is a bijection.


\par
\textit{Condition 1:} Let $l_A$ and $l_B$ be defined as in Definition \ref{def:isomorphism}. This menas that $l_{A}(a_i)=f_{ij}(D_{a_{i}})=D_{b_{j}}$ and $l_{B}(b_{j})=D_{b_{j}}$. Thus, given $F(a_{i})=b_{j}$, we have that $\forall a_{i} \in A, \ l_{A}(a_i)=l_{B}(F(a_{i}))$. 

\par
\textit{Condition 2:} This condition holds because crescent configurations are complete graphs, and $F$ is a bijection. Therefore $\{a_{i},a_{j}\}\in E_{A} \leftrightarrow \{F(a_{i}), F(a_{j})\} \in E_{B}$, where $E_A$ and $E_B$ are the edge sets of $A$ and $B$ respectively.

\par
\textit{Condition 3:} To prove this condition, we recall that applying $f_{ij}$ to $a_i$ is equivalent to re-indexing the points of $A$. Therefore, if we let $w_{A}$ and $w_{B}$ be functions that return the edge labels of $A$ and $B$, respectively, as defined as in Definition \ref{def:isomorphism}, then we know that $$w_{A}(\{a_i,a_j\})=d_{a_{i,j}}=d_{b_{l,k}}=w_{B}(\{b_l,b_k\})=w_{B}(\{F(a_{i}),F(a_{j})\}),$$
satisfying this condition.
Thus A and B are isomorphic.
\end{proof}
\begin{remark} Since the algorithm can only distinguish the similar permutations according to the distance labels, the resulting distance sets may define crescent configurations that are not geometrically realizable. We address this concern later in the paper (see Section \ref{sec:geomREAL} on geometric realizability).
\end{remark}

\section{Method for Counting Isomorphism Classes}\label{sec: counting}
As a direct result of Theorem \ref{thm: graphisom}, we now have a method for classifying all crescent configurations on $n$ points into isomorphism classes. 
In this section we provide a sketch of the algorithm used to find these isomorphism classes. A pseudocode is provided in Appendix \ref{app: algorithms}.

\par 
Consider a set of distances, $\{d_1,d_2,d_2,...,d_{n-1}\}$, associated to a crescent configuration on $n$ points. This set of distances may be threaded through an $n \times n$ adjacency matrix like the one shown in the proof of Theorem \ref{thm: graphisom}.
\begin{comment}
Consider a set of distances associated to a crescent configuration on $n$ points: $\{d_1,d_2,d_2,...,d_{n-1}\}$. This set of distances may be threaded through the rows and columns of an adjacency matrix to define a complete graph on $n$ vertices as shown in \ref{eq:threadEx}
\begin{equation}\label{eq:threadEx}
\{d_1,d_2,d_2,...,d_{n-1}\} \ \to \ \begin{pmatrix}
0&d_1&d_2&d_2...&{}&...\\
d_1&0&...&{}&.&...\\
d_2&...&0&...&{}&...\\
d_2&{}&...&0&{}&...\\
.&.&{}&{}&.&...\\
.&{}&...&d_{n-1}&d_{n-1}&0\\
\end{pmatrix}
\end{equation}
\end{comment}
From this point on, we refer to these matrices as \textit{distance matrices}; however, they are the equivalent of weighted adjacency matrices in graph theory.
\begin{defi}[Distance Matrix]
Let $A$ be an $n \times n$ matrix. We say $A$ is a \textbf{distance matrix} if the following conditions are satisfied
\begin{enumerate}
\item $A$ is symmetric,
\item the entries along the main diagonal of $A$ are all 0, and
\item $a_{ij}$ (the entry found in the $ith$ row and $jth$ column of $A$) refers to the distance between points $i$ and $j$ of the point configuration (or graph) defined by $A$.
\end{enumerate}
\end{defi}

As each configuration has a distance matrix associated to it, we can generate all possible configurations by threading all permutations of $\{d_1,d_2,d_2,...,d_{n-1}\}$ through distance matrices. Using standard combinatorial techniques, we can quickly see that this method will generate 60 configurations on four points, 12,600 on five points, and 37,837,800 on six points. We would now like to apply Theorem \ref{thm: graphisom} and group these configurations into isomorphism classes (via graph isomorphism). 
\begin{comment}
To do so requires the following lemma.  
\begin{lemma}\label{lem: matrix2isom}
Let $A$ and $B$ be two $n \times n$ distance matrices describing two crescent configurations on $n$ points. For each matrix, we take the set of non-zero elements of row $i$ and call these sets $A_{i}$ and $B_{i}$. If $A_{i} \ \subset \{B_{i}\}_{i=1}^{n}$ for all $1 \leq i \leq n$, Then A and B are isomorphic.
\end{lemma}
\begin{proof}
Note that the set of non-zero elements of row $i$ in a given distance matrix represents the distances between point $i$ and all other points in the configuration. Therefore, it is equivalent to the \textbf{distance coordinate} of point $i$. Therefore, given a crescent configuration on $n$ points, the $n$ distance coordinates are the sets of non-zero elements of each row of its distance matrix, implying that the \textbf{distance set} of this configuration is entirely determined by the distance matrix.
The remainder of the proof is a direct application of \ref{thm: graphisom}.
\end{proof}
\par
Using this lemma, we may group all configurations on $n$ points into their isomorphism classes and conduct the remainder of our analysis on one representative from each class. For $n=4$, this reduces our initial $60$ to $4$ classes. For $n=5$, it reduces our initial $12,600$ to $85$ classes.
\end{comment}
\par
A computer program may then be used to group together all distance matrices defining configurations with identical distance sets. These groups then represent our isomorphism classes, and we can conduct the remainder of our analysis on one representative from each class. For $n=4$, this reduces our initial $60$ to $4$ classes. For $n=5$, it reduces our initial $12,600$ to $85$ classes.
\par
Having finished this classification, we note that there are three degenerate cases that will force the configuration to \textit{always} violate general position. These will remain unchanged under graph isomorphism since vertex and edge-set pairings stay the same, allowing us to eliminate entire isomorphism classes if one representative is proven to be degenerate. These cases are as follows.
\begin{enumerate}
\item The configuration contains one point at the center of a circle of radius $d_{i}$ with four or more points on this circle as seen in Figure \ref{fig:star}.
\item The configuration contains three (or more) isosceles triangles sharing the same base.
\item The configurations contains four points arranged on the vertices of an isosceles trapezoid.
\end{enumerate}
\begin{figure}[h]
\includegraphics[width=0.3\textwidth]{star.png}
\caption{The central point of this configuration has distance coordinate $\{d,d,d,d,d,d\}$.}
\label{fig:star}
\end{figure}
Although there exist other cases that will force a class to violate general position, these three cases may be accounted for by only considering the distance matrices. 
\par
Case 1 is very simple to account for and is only possible for $n\geq 5$. In order to eliminate these cases, we remove configurations containing one or more distance coordinates in which a particular distance, $d_{i}$, occurs four or more times. In Algorithm \ref{alg:class}, this case and case 3 are accounted for in the procedure REMOVECYCLIC.
\par
As with case 1, case 2 is only possible for $n\geq 5$. If three or more isosceles triangles share the same base, then all of their apexes must reside on the line bisecting this base, forcing them to violate general position. 
\par
In a distance matrix, an isosceles triangle is indicated by a matching pair of distances occurring in a row.
Therefore, we remove all distance matrices in which three or more rows contain a matching pair occurring in the same slots in each row.
This case is accounted for in Algorithm \ref{alg:class} by the procedure REMOVELINEARCASE. 
\par
Case 3 requires us to remove all configurations that contain a subset or subsets of four points defining an isosceles trapezoid, since isosceles trapezoids are always cyclic quadrilaterals. In Algorithm \ref{alg:class}, the procedures SUBMATRICES and REMOVECYCLIC are included to account for these cases, which may be identified by their distance matrices using the following lemma.

\begin{lemma}\label{cla:isosceles} A $4\times 4$ distance matrix will always define an isosceles trapezoid if and only if one of the following holds:
\begin{enumerate}
\item the matrix has only one distinct row such that
\begin{enumerate}
\item the matrix has only two distinct distances, or
\item the matrix only has three distinct distances,
\end{enumerate}
\item the matrix has two distinct rows, both with multiplicity two, such that
\begin{enumerate}
\item the matrix has three distinct distances with multiplicity no greater than three (note that this means each distance occurs no more than six times in the distance matrix), or
\item the matrix has four distinct distances with multiplicity no greater than two (each distance occurs no more than four times in the distance matrix).
\end{enumerate}
\end{enumerate}
\end{lemma}
\begin{proof}
($\Leftarrow$) According to Halsted \cite{Halsted}, a necessary and sufficient condition for a quadrilateral to be an isosceles trapezoid is that it has at least one pair of opposite sides with equal length and diagonals of equal length. It is not possible for these two lengths (sides and diagonals) to be equal because this would create two isosceles triangles that would have to be congruent. Therefore there are three cases for isosceles trapezoids: (1) four distinct distances, (2) three distinct distances, or (3) two distinct distances.
Figure \ref{fig: 4dist} presents possible realizations for each of these cases. From here, it is straightforward to show that each of these quadrilaterals satisfies one of the conditions stated in Lemma \ref{cla:isosceles}, thus completing this direction of the proof.
\begin{figure}[h]
\includegraphics[width=\linewidth]{isosceles_trap.png}
\caption{(1) Four distinct distances, (2) three distinct distances, (3) two distinct distances. }
\label{fig: 4dist}
\end{figure}
\par
($\Rightarrow$) We now prove the other direction.
\par
We begin with condition (1a): one distinct row and two distinct distances.
\par
Assume each row represents the distance coordinate $(a,a,b)$ (order of distances may differ among rows). Since we require all rows of the distance matrix to have the same distance coordinate, distance $b$ must touch every point yet only show up twice. Therefore, it must represent both diagonals or two opposite sides. Both cases yield a quadrilateral with a set of congruent opposite sides and congruent diagonals, a necessary and sufficient condition for an isosceles trapezoid.
\par
For condition 1b - one distinct row and three distinct distances - all three distances must be common to all points, so they must describe either a set of opposite sides or the diagonals, in all cases yielding an isosceles trapezoid.
\par
The proofs in the other directions all following similar arguments. In each case there are two distances that must be common to all points and at least one distance that can only be common to two points, implying that one set of opposite sides cannot be congruent, therefore the distances common to all points must describe the diagonals and only one set of opposite sides, thus describing an isosceles trapezoid in each case.
\end{proof}
Once these cases have been eliminated, we are left with three isomorphism classes for four points and $51$ for five points.
\begin{comment}\subsection{Usefulness of Classification}

\par
The usefulness of this classification system becomes evident when considering the question of geometric realizability (see \ref{def:geomreal}). Take, for instance, the two configurations shown in Figure \ref{fig:realisom}.
\par
If we do not assign values to $d_{1},d_{2},\ or \ d_{3}$, these two configurations are isomorphic, and thus fall in to the same isomorphism class. However, they clearly do not possess the same set of distances. And yet, in Section \ref{sec:geomREAL} that the distances are actually two different solutions to the same system of equations. By placing all crescent configurations into isomorphism classes, we set ourselves up nicely to solve for ALL realizable crescent configurations in a single class with one system of equations.
\end{comment}
\begin{figure}[h]
\includegraphics[width=0.3\textwidth]{isomfigs.png}
\caption{Two isomorphic configurations.}
\label{fig:realisom}
\end{figure}
\begin{rem}\label{rem:runtime}
It should be noted that the runtime of Algorithm \ref{alg:class} is $\mathcal{O}(n^{n})$, so its use is limited to crescent configurations on relatively few points. However, we believe that with enough processing power, upper bounds can be established using the algorithm for small $n$ such as $7$ and $8$. As such, at this time, this does not pose much of an issue to the progress of this research, as no crescent configurations on more than $8$ points is yet to be found.
\end{rem}

\section{Geometrically Realizability of Crescent Configurations} \label{sec:geomREAL}

In the previous sections we developed a way to  find every isomorphism class of distance sets that corresponded to a crescent configuration on $n$ points;  however, it is not clear that given some $m$ and one of these distance sets, there exists a set of points in $\ensuremath{\mathbb{R}}^m$ that realizes this distance set.  Thus, we formally define geometric realizability.

\begin{defi}\label{def:geomreal}
A crescent configuration on $n$ points is \emph{geometrically realizable} in $\ensuremath{\mathbb{R}}^m$ if there exists some distances $d_1, \dots,d_{n-1}$ for which there exist points $P_1, P_2, \dots, P_n$ in $\ensuremath{\mathbb{R}}^m$ that realize the corresponding distance set.  
\end{defi}

We have thus far established upper bounds on the number of crescent configurations on $n$ points based on the combinatorial aspects of this problem. We now sharpen these bounds by considering criteria for geometric realizability.  
\begin{remark}
Burt et. al. \cite{SM15} showed that given an $n$, there exists an $m$ such that an $n-$crescent configuration exists in $\ensuremath{\mathbb{R}}^m$.  In this section, we fix $m$ and determine whether a given distance set is geometrically realizable in $\ensuremath{\mathbb{R}}^m$.
\end{remark}

In Section \ref{sec: counting}, we classify crescent configurations in terms of the distances between each pair of points.  The problem of determining information about a set of points based on the distances between them is well studied, and is known as the distance geometry problem. Thus, we are now able to use techniques from distance geometry in order to sharpen the bounds on the number of geometrically realizable configurations on $n$ points.  We begin by introducing some of these techniques.  

\begin{defi}
The \emph{Cayley-Menger matrix} corresponding to a  set  of $n$ points $\{P_1, P_2, \dots, P_n\}$ is an $(n+1)\times (n+1)$ matrix of the following form:
$$
\left(
\begin{matrix}
0 &  d_{1,2}^2  & \ldots & d_{1,n}^2 & 1\\
d_{2,1}^2  &  0 & \ldots & d_{2,n}^2 &1\\
\vdots & \vdots & \ddots &  \vdots &\vdots\\
d_{n,1}^2 & d_{n,2}^2 & \dots &0&1\\
1  &   1       &\ldots & 1 & 0
\end{matrix}
\right)
,$$
where $d_{i,j}$ is the distance between $P_i$ and $P_j$.
\end{defi}

The Cayley-Menger matrix corresponding to a set of points can be used to determine whether those points lie in a $d$-dimensional Euclidian space.  Note that  $n+1$ points always lie in a hyperplane of $\ensuremath{\mathbb{R}}^n$; thus we only need to consider collections of points of size at least $n+2$.

\begin{theorem}[Cayley-Menger Matrix]\label{thm: cayley}
\cite{LL}
Let $M$ be a $(n+3) \times (n+3)$ matrix of the form specified above.  $M$ is the Cayley-Menger matrix of a set of $n+2$ points in $\mathbb{R}^n$ if and only if $\det{M} = 0$.
\end{theorem}

\begin{corollary}\label{cor:cayley}
Let $M$ be a $n+1\times n+1$ matrix of the form specified above;  $M$ is the Cayley-Menger matrix of a set of $n$ points, $\{P_1, \dots, P_n\}$ in $\mathbb{R}^2$, if and only if the Cayley-Menger matrix corresponding to every size $m+2$ subset has determinant zero.
\end{corollary}
\begin{proof}
$\Rightarrow$ Suppose that $M$ is the Cayley-Menger matrix of $n$ points that can be realized in $\ensuremath{\mathbb{R}}_m$.  Thus, every subset of $m+2$ points can also be realized in $\ensuremath{\mathbb{R}}^m$, and thus has a corresponding Cayley-Menger matrix with determinant zero.  \\
$\Leftarrow$ Suppose that the Cayley-Menger matrix corresponding to every size $m+2$ subset has determinant zero.  Note that $P_1, \dots, P_{m+1}$ must define an $m$-dimensional subspace of any Euclidean space. Note that by assumption, for every $i$, the Cayley-Menger matrix corresponding to $P_1, \dots, P_{m+1}, P_i$ has determinant $0$.  Thus, as a consequence of Theorem \ref{thm: cayley}, $P_i$ is in the same $m$-dimensional subspace.  Thus, our set of $n$ points must be realizable in $\ensuremath{\mathbb{R}}^m$. 
\end{proof}

Submatrices of the Cayley-Menger matrix can also determine whether the points determined by a set of distances lie on the same hypersphere.

\begin{defi}
The \emph{Euclidian distance matrix} corresponding to a  set  of $n$ points $\{P_1, P_2, \dots P_n\}$ is an $n\times n$ matrix of the following form:

$$
\left(
\begin{matrix}
0 &  d_{1,2}^2  & \ldots & d_{1,n}^2 \\
d_{2,1}^2  &  0 & \ldots & d_{2,n}^2\\
\vdots & \vdots & \ddots &  \vdots &\vdots\\
d_{n,1}^2 & d_{n,2}^2 & \dots &0
\end{matrix}
\right)
.$$
\end{defi}
Note that the Euclidean distance matrices defined above are slightly different than the general notion of distance matrices used in previous sections.
\begin{theorem}\label{thm: circles} \cite{CS}
Let $E$ be the Euclidean distance matrix corresponding to points $P_1, \dots P_n$ in Euclidean space. These points lie on a hypersphere in $\ensuremath{\mathbb{R}}^{n-2}$ if and only if $\det{E} = 0$.
\end{theorem}

We apply these techniques to the problem of counting crescent configurations in the following corollary.

\begin{cor}\label{cor: realize}
Let $M$ be the Cayley-Menger matrix corresponding to a distance set on n points, $\mathcal{D}$.  Then $\mathcal{D}$ is geometrically realizable in general position in $\ensuremath{\mathbb{R}}^m$ if and only if the following conditions hold.
\begin{enumerate}
\item Let $S$ be a size $m+3$ subset of $\{1, 2, \dots, n, n+1\}$ that contains $n+1$. Let $M_S$ be the submatrix of $M$ with rows and columns indexed by $S$.  For every choice of $S$, $\det{M_S} = 0$.
\item Let $S$ be a size $m+2$ subset of $\{1, \dots, n, n+1\}$. For every such choice of $S$, $\det{M_S} \neq 0$.

\end{enumerate}


\end{cor}
\begin{proof}
 From Corollary \ref{cor:cayley}, a collection of distances between $n$ points is geometrically realizable  in $\ensuremath{\mathbb{R}}^m$  if and only if the Cayley-Menger matrix corresponding to each subset $m+2$ points has determinant 0. Each of these matrices is one of the submatrices specified by the first condition.  

We consider the submatrices specified by the second condition in two parts. First, consider the submatrices $M_S$ for which $n+1 \in S$.   We see that these comprise the Cayley-Menger matrices for each subset of $m+1$ points.  We now consider the submatrices $M_S$ for which $n+1 \not\in S$.  We see that these comprise the Euclidean distance matrices for each subset of $m+2$ points.  
Thus, we can see that the submatrices specified by the second condition is the set of all Euclidean  distance matrices for each size $m+2$ subset of the $n$ points together with the set of all Cayley-Menger matrices for each size $m+1$ subset of the $n$ points. By Theorem \ref{thm: circles}, a Euclidean distance matrix on $m+2$ points has determinant 0 if and only if these points lie on the same hypersphere in $\ensuremath{\mathbb{R}}^m$. By Theorem \ref{thm: cayley}, the Cayley-Menger matrix of $m+1$ points has determinant 0 if and only if these points lie on the same hyperplane in $\ensuremath{\mathbb{R}}^m$. Thus, this second condition holds if and only if the points lie in general position in $\ensuremath{\mathbb{R}}^m$. 
\end{proof}
\par
Our application of this corollary to the distance sets on $4$ and $5$ points have allowed us to determine the geometric realizability of each of the distance sets found using techniques from earlier sections. These geometrically realizable configurations are discussed in the following section. 

Thus far, most of our attentions have been focused on crescent configurations in the plane.  However, these techniques can be applied to finding crescent configurations in higher dimensions, furthering the work of Burt et. al. \cite{SM15}.

\section{Finding Geometric Realizations for Crescent Configurations} 
As stated in Section \ref{sec: counting}, Algorithm \ref{alg:class} yields three crescent configurations on four points and 51 on five points, unique up to isomorphism. However, these procedures do not guarantee that each isomorphism class contains geometrially realizable configurations.


\begin{comment}\begin{theorem} \label{thm:3on4}
Given a set of three distinct distances, $\{d1,d2,d3\}$, on four points in crescent configuration, there are only three allowable crescent configurations up to graph isomorphism.
We refer to these configurations as M-type, C-type, and R-type, respectively. In Figure \ref{fig:mcr} we provide graph realizations, adjacency matrices, and a set of distances for each.
\end{theorem}

\begin{theorem}\label{thm:27on5}
Given a set of four distinct distances, $\{d_1,d_2,d_3,d_4\}$, on five points in crescent configuration, there are 27 allowable crescent configurations up to graph isomorphism.
\end{theorem}
In Appendix \ref{app: 5points} we include distance sets and realizable distances for each crescent configuration on five points.
\end{comment}
\par
To check which of these configurations are geometrically realizable, we run Algorithm \ref{alg: check4}. A pseudocode of this algorithm can be found in Appendix \ref{app: algorithms}. Note that we assume $d_{1}=1$ in order to simplify the procedure.
\par 
Algorithm \ref{alg: check4} is an extended application of Theorem \ref{cor: realize}. The first step of this algorithm is to take the Cayley-Menger determinants of all $4$-point subsets of each configuration found by Algorithm \ref{alg:class} and set them equal to zero. Doing so yields a system of $\begin{pmatrix} n\\ 4 \end{pmatrix}$ equations with unknowns : $\{d_2,d_3,...,d_{n-1}\}$. If the configuration is realizable in the plane, solving this system of equations will give all possible solutions to these distances in $\mathbb{R}^{2}$. Note that the values must be positive and real-valued.
\par
For each of these solutions, we check the Cayley-Menger determinants of all $3$-point subsets of the configuration. If one or more of these determinants equals zero, that solution forces the configuration to place three points on the same line, violating general position, so we throw it away. If none of the determinants are zero, we keep the solution.
\par
For each remaining solution, we take the determinant of the Euclidean distance matrix of each $4$-point subset of the configuration. If any of these determinants equal zero, the solution forces four points onto the same circle, violating general position, and we throw it away. 
\par
Any remaining solutions represent the distances of a geometrically realizable crescent configuration.
Applying this algorithm to the configurations returned by Algorithm \ref{alg:class} completes the proofs of Theorems \ref{thm:3on4} and \ref{thm:27on5}, as we find that there are exactly three realizable crescent configurations on four points and 27 realizable crescent configurations on five points.
\par
In Appendix \ref{app: 5points}, we provide a set of distances for every configuration on five points that had at least one remaining solution after applying this algorithm.

\begin{comment}
\begin{figure}[h]
\definecolor{qqwuqq}{rgb}{0.,0.39215686274509803,0.}
\definecolor{qqqqff}{rgb}{0.,0.,1.}
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-3.810089413056916,1.0780675462585876) rectangle (15.017641730323243,7.476163793212526);
\draw [color=ffqqqq] (-2.,6.)-- (-3.,5.);
\draw [color=ffqqqq] (-3.,5.)-- (-1.,5.);
\draw [color=ffqqqq] (-2.,6.)-- (-1.,5.);
\draw [color=qqqqff] (-3.,5.)-- (-2.,3.);
\draw [color=qqqqff] (-1.,5.)-- (-2.,3.);
\draw [color=qqwuqq] (-2.,6.)-- (-2.,3.);
\draw [color=ffqqqq] (0.,5.)-- (2.,5.);
\draw [color=ffqqqq] (0.,5.)-- (1.,4.);
\draw [color=ffqqqq] (2.,5.)-- (1.,4.);
\draw [color=qqqqff] (0.,5.)-- (1.,3.);
\draw [color=qqqqff] (2.,5.)-- (1.,3.);
\draw [color=qqwuqq] (1.,4.)-- (1.,3.);
\draw [color=qqqqff] (5.,3.)-- (6.,6.);
\draw [color=qqqqff] (6.,6.)-- (7.,3.);
\draw [color=qqwuqq] (5.,3.)-- (7.,3.);
\draw [color=ffqqqq] (5.995999144407565,4.297200458023963)-- (6.,6.);
\draw [color=ffqqqq] (5.,3.)-- (5.995999144407565,4.297200458023963);
\draw [color=ffqqqq] (7.,3.)-- (5.995999144407565,4.297200458023963);
\draw [color=qqwuqq] (10.,3.)-- (10.,5.);
\draw [color=qqqqff] (10.,5.)-- (13.,6.);
\draw [color=qqqqff] (13.,6.)-- (14.,3.);
\draw [color=ffqqqq] (10.,5.)-- (14.,3.);
\draw [color=ffqqqq] (10.,3.)-- (13.,6.);
\draw [color=ffqqqq] (10.,3.)-- (14.,3.);
\draw (-0.7443349613914741,2.610944772091302) node[anchor=north west] {M};
\draw (5.787054957374033,2.5109745182326466) node[anchor=north west] {C};
\draw (11.718623352987604,2.544297936185532) node[anchor=north west] {R};
\end{tikzpicture}
\[
\hspace{1cm}
\{d_1,d_2,d_2\},\{d_1,d_3,d_3\},
\hspace{1.5cm}
\{d_1,d_2,d_3\},\{d_1,d_2,d_3\},
\hspace{1.5cm}
\{d_1,d_2,d_3\},\{d_1,d_3,d_3\},
\]
\[
\hspace{1cm}
\{d_2,d_3,d_3\},\{d_2,d_3,d_3\} 
\hspace{1.7cm}
\{d_2,d_2,d_3\},\{d_3,d_3,d_3\} 
\hspace{1.7cm}
\{d_2,d_3,d_2\},\{d_3,d_3,d_2\}\]

\[
\{d_{1} \ = \ \sqrt{3} \ + \ \sqrt{8}, \  d_{2} \ = \ 3, \ d_{3} \ = \ 2\}
\hspace{0.5cm}
\{d_{1} \ = \ 1, \ d_{2} \ = \ \frac{\sqrt{17}}{2}, \ d_{3} \ = \ \frac{17}{16}\}
\hspace{0.5cm}
\{d_{1} \ = \ \sqrt{\frac{3}{2}}, \ d_{2} \ = \ 2, \ d_{3} \ = \ 1\}
\]

\caption{Types M, C, and R.}
\label{fig:mcr}
\end{figure}
\end{comment}
\begin{comment}
\begin{figure}[h]
\includegraphics[width=\textwidth]{configson52.png}
\caption{Representatives for all possible distance sets on five points.}
\label{fig:allFIVE}
\end{figure}
\end{comment}

\section{Rigidity of Crescent Configurations}\label{sec: rigid}

So far in this paper, we have shown that crescent configurations can be classified into a finite number of isomorphism classes for each positive integer $n$ and defined a method to geometrically realize these configurations. We now turn our attention to testing whether our crescent configurations are rigid, which can help answer questions, such as, whether one distance set could define two different realizations of crescent configurations belonging to the same isomorphism class.
For this reason, we shall treat our configurations as graphs and adopt the following definition of graph rigidity.
\begin{defi}[Asimow \& Roth]\cite{AsimowRoth}
Let $G$ be a graph $(V,E)$ on $v$ vertices in $\ensuremath{\mathbb{R}}^n$ then $G(p)$ is $G$ together with the point $ p = (p_1,p_2, \dots, p_v) \in \ensuremath{\mathbb{R}}^n \times \ensuremath{\mathbb{R}}^n \times \ensuremath{\mathbb{R}}^n \dots \ensuremath{\mathbb{R}}^n = \ensuremath{\mathbb{R}}^{nv}$. Let $K$ be the complete graph on $v$ vertices. The graph $G(p)$ is \emph{rigid} in $\ensuremath{\mathbb{R}}^n$ if there exists a neighbordhood $\mathbf{U}$ of $p$ such that 
$$e_K^{-1}(e_K(p)) \cap \mathbf{U} = e_G^{-1}(e_G(p)) \cap \mathbf{U},$$
where $e_K$ and $e_G$ are the edge functions of $K$ and $G$, which return the distances of edges of the associated graphs.
\end{defi}
In other words, a rigid graph cannot have its vertices be continuously moved to noncongruent positions while preserving the distances. The rigidity testing of these configurations would not only serve as a verification for our classification under graph isomorphism, but would also give us another way to characterize these crescent configurations. 
\par
One important note is that all crescent configurations are complete graphs. It is a rather direct result of the following theorem and its corollary that all complete graphs are rigid in $\ensuremath{\mathbb{R}}^2$.
\begin{theorem}[Laman]\label{thm:rigidR2}\cite{Laman}
The edges of a graph $G = (V,E)$ are independent in two dimensions if and only if no subgraph $G' = (V',E')$ has more than $2n-3$ edges.
\end{theorem}
\begin{cor}
A graph with $2n-3$ edges is rigid in two dimensions if and only if no subgraph $G'$ has more than $2n'-3$ edges.
\end{cor}
We can easily check that the complete graph on $1$, $2$ and $3$ points ($K_1$, $K_2$ and $K_3$ respectively) satisfy the condition and thus are rigid. For $n \geq 3$, the complete graph on $n$ points (or $K_n$ by convention) is composed of triangles, which are $K_3$. Since each $K_3$ composing $K_n$ is rigid, it must also be the case that one cannot move the vertices of $K_n$ to noncongruent positions while preserving the distances because this would inevitably change the distances in each $K_3$ subgraph. Therefore, all crescent configurations are rigid.
\par
Nonetheless, this fact does not imply our work is over, as there is more than one kind of rigidity for graphs. Thus, we want to study whether all crescent configurations fall into just one category of rigidity or if there are certain crescent configurations that are more rigid than others. In addition, Theorem \ref{thm:rigidR2} can only be used to show the rigidity of crescent configurations in two dimensions. Furthermore, in the near future, we want to extend our definition of crescent configuration to $\epsilon$ crescent configurations, where two edges are considered equal if their lengths are within a sufficiently small $\epsilon$ from each other. Thus we need another method that could accommodate the exploration in higher dimensions and the assessment of stability of an extended family of crescent configurations.\\
\par

This leads us to using \textbf{rigidity matrices
. These are an extremely powerful and flexible tool that can be used in $\ensuremath{\mathbb{R}}^d$ for all $d \in \mathbb{N}$. We introduce them and other necessary terminologies in Subsection \ref{sub:prelim} and apply them to our analysis in Subsection \ref{sub:analysis}.

\subsection{Preliminaries}\label{sub:prelim} 
\par
The following definitions and theorems will be used through out the rest of the paper to analyze the rigidity of crescent configurations on $4$ and $5$ points in $\ensuremath{\mathbb{R}}^2$. The formulation of each of these definitions have been adopted from one paper by Bruce Hendrickson \cite{Hendrickson} due to their accessible nature. For other formulations and characterizations of rigidity, see also \cite{AsimowRoth, Connelly, Roth, Roth2}.\\

\begin{defi}[Realization]\cite{Hendrickson}
Let $G=(V,E)$ be a graph with some pairwise associated distance measurements. A realization $f$ of $G$ is a function that maps the vertices of $G$ to coordinates in some Euclidean space such that the distance measurements are realized.
\end{defi}

\begin{defi}[Framework]\cite{Hendrickson}
A framework is a combination of a graph $G = (V,E)$ and a realization of $G$ in some Euclidean space, denoted $f(G)$
\end{defi}

In our case, we will mostly be concerned with frameworks in $\ensuremath{\mathbb{R}}^2$, though the techniques can be generalized to higher dimension and in any Euclidean space.

\begin{defi}[Flexibility of Frameworks] \label{def:flex} \cite{Hendrickson}
A framework is called flexible if and only if it can be continuously deformed while preserving the distance constraints; otherwise the framework is rigid. A framework is redundantly rigid if and only if one can remove any edge and the remaining framework is rigid.
\end{defi}

\begin{defi}[Infinitesimal motion]\cite{Hendrickson}
An \textbf{infinitesimal motion} is an assignment of velocity to each vertex such that $(v_i - v_j)(f_i - f_j) = 0$ for all pairs $(i,j) \in E$. A framework $f(G)$ is infinitesimally rigid if and only if it does not have any infinitesimal motion.
\end{defi}

\begin{theorem}[Gluck 1975]\label{thm:gluck} \cite{Gluck}
If a graph has a single infinitesimally rigid realization, then all its generic realizations are rigid.
\end{theorem}

The main tool we will use to study the rigidity of our crescent configurations, as mentioned, are \textbf{rigidity matrices}. Each framework has a rigidity matrix associated to it. This matrix is the set of all equations whose solutions are the infinitesimal motions of that framework. Its rows correspond to the edges and its $nd$ columns correspond to the components of the vertices in $\mathbb{R}^d$. There are $2d$ nonzero elements in each row, one for each coordinate of the vertices connected to the corresponding edge. The differences in the coordinate values for the two vertices are these nonzero values. 

\begin{theorem}[Hendrickson 1992]\label{thm:Hend} \cite{Hendrickson}
A framework $f(G)$ is rigid if and only if its rigidity matrix has rank exactly equal to $S(n,d)$,the number of allowed motions, which is equal to $nd - d(d+1)/2$ for $n \geq d$ and $n(n-1)/2$ otherwise.
\end{theorem}

All the above theorems and objects are tied together in the following lemma, which provides the basis for our analysis in the next section. 

\begin{lemma}\label{lem:BJackson} \cite{Jackson}
The following statements are equivalent:
\begin{enumerate}
\item $G$ is rigid in $\ensuremath{\mathbb{R}}^d$,
\item some framework $f(G)$ in $\ensuremath{\mathbb{R}}^d$ is infinitesimally rigid,
\item every generic framework of $G$ in $\ensuremath{\mathbb{R}}^d$ is rigid.
\end{enumerate}
\end{lemma}

\subsection{Rigidity Analysis for 4-point Crescent Configurations} \label{sub:analysis}

\vspace{0.2cm}
The first thing we need to do before we are able to study the rigidity matrix is to construct a realization. By Theorem \ref{thm:gluck}, it suffices to construct a single realization for each type of crescent configurations on $n$ points and study the rigidity of that framework. 

Figure 6 is a realization of type C obtained by fixing $d_1 = 1$. We note that since the distances in these configurations must satisfy general position as well as geometric realizability, fixing one distance to calculate the rest of the distances in the distance set does not affect the rigidity characterization of the configuration.

\begin{figure}[h]
\includegraphics[width=0.5\textwidth]{TypeC.png}
\caption{Realization of type C obtained by fixing $d_1 = 1$}
\end{figure}


The above realization yield the following rigidity matrix, which we denote $A_C$:
\[A_C = 
\begin{bmatrix}
\frac{1}{2} & y + \sqrt{\frac{1+4y^2}{4}}&-\frac{1}{2} & -y - \sqrt{\frac{1+4y^2}{4}}&0&0&0&0\\
-\frac{1}{2}&y + \sqrt{\frac{1+4y^2}{4}}& 0& 0& \frac{1}{2}& -y - \sqrt{\frac{1+4y^2}{4}}&0&0\\
0& \sqrt{\frac{1+4y^2}{4}}& 0&0& 0& 0& 0&-\sqrt{\frac{1+4y^2}{4}}\\
0& 0& -1& 0& 1& 0& 0& 0\\
0& 0& -\frac{1}{2}& -y& 0& 0& \frac{1}{2}& y\\
0& 0& 0& 0& \frac{1}{2}& -y& -\frac{1}{2}& y\\
\end{bmatrix}
.\]
By row reduction operations, we get that Rank($A_C$)$=5 = S(4,2)$. Thus by Theorem \ref{thm:Hend}, the framework is infinitesimally rigid. Since the row reduction operations yield the same result whether $y > 0$ or $y < 0$, we can conclude that type $C$ is rigid for all $y \neq 0$ by Lemma \ref{lem:BJackson}.\\


Similarly, we can carry out the same analysis on type M. There are two realizations of type $M$, which are included in Figure 7.
\begin{figure}[h]
\includegraphics[width=0.7\textwidth]{TypeM.png}
\caption{Two realizations of type M: $M_1$ and $M_2$}
\end{figure}

Note that $d_1$ is the only distance that differs in these two realizations. If we remove $d_1$ and denote the remaining framework as $M'_1$ and $M'_2$ respectively, we could continuously deform one into the other. This fact also means that type M cannot be redundantly rigid by definition. Therefore, type M is another rigid graph.
\begin{comment}
\[A_{M_1} =
\begin{bmatrix}
-2 x &  0 & 2 x & 0 & 0 & 0 &  0 & 0\\
-x & -x \sqrt{3} & 0 & 0 & x & x \sqrt{3} &  0 & 0 \\
-x & -x \sqrt{3} - y & 0 & 0 & 0 & 0 & x& x\sqrt{3} + y\\
0 & 0 & x & -x \sqrt{3} & -x & x\sqrt{3} & 0 & 0 \\
0 & 0 & x & -x \sqrt{3} - y & 0 & 0 & -x & x\sqrt{3} + y \\
0 & 0 & 0 & 0 & 0 & -y & 0 & y \\
\end{bmatrix}
\]
Again by row reduction operations, Rank($A_{M_1}$) $=5$ thus by \ref{thm:Hend}, the framework is infinitesimally rigid therefore type M is another rigid graph.
\end{comment}

Last but not least, type R can also be studied using the same method. We start with a realization that is included in Figure 8 and a rigidity matrix $A_R$ to follow:
\begin{figure}[ht]
\includegraphics[width=0.7\textwidth]{TypeR.png}
\caption{Realization of type R obtained by fixing $d_1 = 1$}
\end{figure}

\[A_R = 
\begin{bmatrix}
-x & 0 & x & 0 & 0 & 0 & 0 & 0\\
\frac{-x}{2} & \frac{-x}{y} & 0 & 0 & \frac{x}{2} & \frac{x}{y} & 0 & 0 \\
\frac{-1}{2x} & \frac{-y}{2x} & 0 & 0 & 0 & 0 & \frac{1}{2x} & \frac{y}{2x}\\
0 & 0 & x - \frac{x}{2} & \frac{-x}{2y} & -x + \frac{x}{2} & \frac{x}{2y} & 0 & 0\\
0 & 0 & x - \frac{1}{2x} & \frac{-y}{2x} & 0 & 0 & -x + \frac{1}{2x} & \frac{y}{2x}\\
0 & 0 & 0 & 0 & \frac{x}{2} - \frac{1}{2x} & \frac{x}{2y} - \frac{y}{2x} & \frac{-x}{2} + \frac{1}{2x}& \frac{-x}{2y} + \frac{y}{2x}\\
\end{bmatrix}
.\]

By carrying out row reduction operations once more, we find that Rank($A_R$) $= 6 > S(4,2)$. However, since removing any row in the matrix is equivalent to removing any edge in the framework and the rank of any remaining matrix obtained this way is always $5$, we conclude that type R is redundantly rigid by Definition \ref{def:flex}. By \cite{Hendrickson}, the conditions for unique realization of a graph is rigidity, $(d+1)$-connectedness, and redundant rigidity. Since type R satisfies all these conditions, it immediately follows that for each value of $x$ that we choose, there is a \emph{unique realization} of type R.

In conclusion we have found that not all crescent configurations on four points have the same rigidity. As stated above, only type R has a unique realization in $\ensuremath{\mathbb{R}}^2$. Similarly, this analysis may be done on all $27$ crescent configurations on $5$ points to determine which ones have a unique realization in $\ensuremath{\mathbb{R}}^2$. \\

As mentioned previously, rigidity matrices are very accommodating. Suppose we need to lift our crescent configurations into $\ensuremath{\mathbb{R}}^d$ for $d > 2$, which we discuss in Subsection \ref{sub:high}. Then, the number of rows and columns of the associated rigidity matrices as well as $S(n,d)$ would change but the method of evaluating rigidity would remain the same. Similarly, with the extension of our definition from crescent configuration to $\epsilon$ crescent configuration (\ref{sub:epsilon}), we can insert $\epsilon$ into the matrix by constructing a realization that involves $\epsilon$ and then solve for $\epsilon$ depending on what stability type we want the configuration to exhibit. 


\section{Future Work}
\subsection{Further Explorations in the Plane}\label{sub:further}
Thus far, we have used our techniques to classify crescent configurations in the plane for $n=4$ and $n=5$.  Because of the complexity of our algorithm, we have not been able to apply our techniques to higher $n$. As mentioned above, the runtime of our current algorithm is on the order of $n^n$, which  prevents us from carrying out this process for large $n$.  However, thus far no configurations have been found for $n>8$, so even running a similar algorithm for $n=9$ would yield significant progress on this problem. Thus, we are interested in the possibility of modifying our algorithm or finding a new technique that would allow us to count crescent configurations on higher $n$.  In this way, we could develop a sequence of $\{c_i\}$, where each $c_i$ gives the number of crescent configurations on $i$ points.  If Erd\H{o}s' conjecture is correct, then $\{c_i\}$ only has a finite number of non-zero terms. It would be interesting to see Erd\H{o}s' conjecture realized as a sequence that goes to zero. 

Since our techniques yield every possible crescent configuration for a given $n$, we can use these to observe patterns.  For example, one can see from Figure \ref{fig:allFIVE} that many of crescent configurations on 5 points contain crescent configurations on 4 points.  We may be able to develop techniques using such patterns that generate some of the possible crescent configurations for larger $n$.  



\subsection{Extensions to Higher Dimensions}\label{sub:high}
As mentioned earlier, the distance geometry techniques that we use naturally extend to higher dimensions. Thus, we are interested in using these techniques to find the number of crescent configurations on $n$ points in a given dimension. Our goal is to construct a sequence  for each $d$ consisting of the number of crescent configurations on $i$ points in $\ensuremath{\mathbb{R}}^d$ for each $i$.  Currently, constructions in $\ensuremath{\mathbb{R}}^3$ have been found for 3, 4, and 5 points. Thus, even finding a single 6 point configuration in 3D would give new information.  We have attempted to use techniques from distance geometry to find a realization in $\ensuremath{\mathbb{R}}^3$ of a known distance set for $n=6$ in the plane.  However, the resulting systems of equations exceeded our computational resources.

Recently, Burt et. al \cite{SM15} found that given $d$ high enough, one can always construct a crescent configuration on $n$ points in $\ensuremath{\mathbb{R}}^d$. We can consider similar questions using the concept of distance coordinates. We are interested in determining whether given a distance set there always exists a dimension in which the set is geometrically realizable.  

\subsection{Properties of Crescent Configuration Types}\label{sub:epsilon}
Now that we have developed a way of classifying crescent configurations, we can examine certain properties for each of the types of crescent configurations.  We started to explore in this direction with our rigidity calculations. \\
One direction we are interested in is to develop a concept of stability for these configurations, as we noticed that moving the points of the M, R, and C- type configurations resulted in different amounts of change in the distances. Further, should we define two distances to be equal if they are $\epsilon$ apart, then our study of the stability of crescent configurations could have some powerful applications to the study of molecules.




\begin{comment}
Lastly, the techniques here can extend to problems more general than the problem of finding crescent configurations.  Given some restraints on the distances between a set of points, we can use these techniques to find geometric realizations.

\begin{comment}\section {Proof of the classifications of crescent configurations on 4 points} \label{sec: 4crescent}


\par
The remaining three steps of the program require the user to input specific values for $\{d1,d2,d3\}$. Once the user has done this, the second step of the program checks to see if any of the three general crescent configurations defined above are geometrically realizable given these distances. To do this, the program uses the \textit{Caley-Menger Determinant}.

\par
\par
Once this check has been completed, the final step of the program, "circleCheck4[distances,dim]," employs Ptolemy's formula to remove any of the remaining configurations that define cyclic quadrilaterals. The output of this final step is the list of all geometrically realizable crescent configurations for the specified distances.\\

\section{Proof of the classifications of crescent configurations on 5 points}
\begin{theorem}\label{thm:5points}
Given a set of four distinct distances, $\{d1,d2,d3,d4\}$, there are at most 85 five-point crescent configurations that may be formed with these distances.
\end{theorem}
\begin{proof}
As with \ref{thm: 4point}, this result was determined using a Mathematica program to carry out the combinatorics. The full code can be found in Appendix B
\par
Just as in \ref{thm: 4point}, this program has four steps, and we again only consider the first step, the function "crescentClassStep1[distances,dim]," to acheive the upper bound of 85. The first step is nearly identical to the first step in the proof of \ref{thm: 4point}, except that we can no longer eliminate cases of isosceles trapezoids because, with four distinct distances, a collection of four points with only two distinct distance coordinates may define a non-square rhombus and its diagonals. A non-square rhombus is not a cyclic quadrilateral
\par
Instead, the program tests for distance coordinates with only one distinct distance. This distance coordinate would define a point at the center of a circle surrounded by four points on said circle, violating general position.
\par
Once these cases have been eliminated, we are left with only 85 distance matrices.
\end{proof}



CAYLEY-MENGER DETERMINANTS
\end{comment}


2016-10-26T02:05:01.000
1610
1610.07836
en
https://arxiv.org/abs/1610.07836
Let $n$ points be in crescent configurations in $\mathbb{R}^d$ if they lie in general position in $\mathbb{R}^d$ and determine $n-1$ distinct distances, such that for every $1 \leq i \leq n-1$ there is a distance that occurs exactly $i$ times. Since Erdős' conjecture in 1989 on the existence of $N$ sufficiently large such that no crescent configurations exist on $N$ or more points, he, Pomerance, and Palásti have given constructions for $n$ up to $8$ but nothing is yet known for $n \geq 9$. Most recently, Burt et. al. had proven that a crescent configuration on $n$ points exists in $\mathbb{R}^{n-2}$ for $n \geq 3$. In this paper, we study the classification of these configurations on $4$ and $5$ points through graph isomorphism and rigidity. Our techniques, which can be generalized to higher dimensions, offer a new viewpoint on the problem through the lens of distance geometry and provide a systematic way to construct crescent configurations.
Combinatorics (math.CO)
Classification of crescent configurations
Qwen/Qwen-72B
1. YES
2. YES