††thanks: corresponding author

# An angle rounding parameter initialization technique for ma-QAOA

Anthony Wilkie  Department of Industrial and Systems Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996  James Ostrowski  Department of Industrial and Systems
Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996  Rebekah Herrman<EMAIL_ADDRESS>Department of
Industrial and Systems Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996

###### Abstract

The multi-angle quantum approximate optimization algorithm (ma-QAOA) is a
recently introduced algorithm that gives at least the same approximation ratio
as the quantum approximate optimization algorithm (QAOA) and, in most cases,
gives a significantly higher approximation ratio than QAOA. One drawback to
ma-QAOA is that it uses significantly more classical parameters than QAOA, so
the classical optimization component more complex. In this paper, we motivate
a new parameter initialization strategy in which angles are initially randomly
set to multiples of $\pi/4$ between $-2\pi$ and $2\pi$ and this vector is used
to seed one round of BFGS. We find that the parameter initialization strategy
on four-vertex and eight-vertex data sets gives average approximation ratios
of 0.931 and 0.894, respectively. This is comparable to the average
approximation ratios of ma-QAOA where optimal parameters are found using BFGS
with 1 random starting seed, which are 0.910 and 0.901 for the four-vertex and
eight-vertex data sets.

##  I Introduction

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-
classical algorithm that uses parameterized circuits with a classical
optimization subroutine to solve combinatorial optimization problems [1]. The
algorithm evolves an initial state ${\left|s\right\rangle}$ under alternating
cost ($U(C,\gamma)=e^{-iC\gamma}$) and mixing ($U(B,\beta)=e^{-iB\beta}$)
Hamiltonians for parameters (also called angles) $\beta,\gamma\in[0,2\pi)$
classically chosen to maximize the expected value of $U(C,\gamma)$. The QAOA
output state is

${\left|\gamma,\beta\right\rangle}=U(B,\beta_{p})U(C,\gamma_{p})\ldots
U(B,\beta_{1})U(C,\gamma_{1}){\left|s\right\rangle}$

where $C$ is problem dependent, and in some cases, $B$ and
${\left|s\right\rangle}$ are as well.

The MaxCut problem is one of the most widely studied CO problems in the
context of QAOA [2, 3, 4, 5], however the algorithm can be applied to any CO
problem with an Ising formulation [6]. The MaxCut problem is a graph problem
in which the vertices of a graph $G$ are partitioned into two sets such that
the number of edges with endpoints in each set is maximized. In typical QAOA
studies on the MaxCut problem,

$C=\frac{1}{2}\sum_{ij\in E(G)}(I-Z_{i}Z_{j}),$

where $Z_{i}$ is the Pauli-z operator acting on qubit $i$. The choice of mixer
$B$ can vary, but it is typically the sum of Pauli-x matrices acting on each
qubit. The metric of success for the algorithm is the approximation ratio,
which is the ratio of
${\left\langle\gamma,\beta\right|}C{\left|\gamma,\beta\right\rangle}=\langle
C\rangle$ over the size of an optimal problem solution.

QAOA is guaranteed to converge in the limit as $p\rightarrow\infty$ when the
initial state ${\left|s\right\rangle}$ is the lowest energy eigenstate of $B$
[1], however since the algorithm is currently implemented on NISQ devices [7,
8], minimizing the number of iterations it takes to converge on an optimal
solution is critical. In fact, recent work suggests that QAOA cannot beat the
classical Goemans-Williamson algorithm on 3-regular graphs in fewer than 11
iterations [9]. Thus, variants of QAOA such as ST-QAOA, X-QAOA, ma-QAOA, and
sym-QAOA have been introduced in an effort to decrease circuit depth [10, 11,
12, 13]. This work will focus on ma-QAOA, which is a QAOA variant in which
each term of $C$ and $B$ are given their own variational parameter, so
$U(C,\vec{\gamma})=e^{-iC_{k}\gamma_{k}}$ and
$U(B,\vec{\beta})=e^{-iB_{j}\beta_{j}}$. The expected value for one iteration
of ma-QAOA will be denoted $\langle C\rangle_{1}^{\mathrm{ma}}$ throughout
this work, and the approximation ratio will be denoted ARma. Since ma-QAOA
requires significantly more variational parameters, the classical optimization
subroutine becomes more challenging, especially when $p>1$ [14]. However, in
their work, the authors of [10] show that a significant proportion of the
angles that were found to optimize ma-QAOA on all connected 8-vertex graphs
were $0$, indicating that clauses can be dropped from $U(C,\gamma)$ and
$U(B,\beta)$.

Several parameter initialization strategies for QAOA have been introduced [15,
16, 17, 18], however ma-QAOA parameter initialization strategies have not been
well-studied[14]. In this work, we develop an ma-QAOA initial angle setting
heuristic to attempt to alleviate the challenges associated with finding
optimal ma-QAOA parameters while still maintaining a comparable approximation
ratio. In Section II, we first analyze patterns in optimal ma-QAOA angles.
These inspire an angle rounding heuristic described in Sec. III and an ma-QAOA
angle initialization strategy, which is detailed in Section IV. We close with
future research directions in Section V.

##  II Angle data and graph structure

In this work, we analyze the angles that optimize ma-QAOA on all connected,
non-isomorphic four-vertex and eight-vertex graphs. All data was generated
using the code found at [19], which is a modification of the code found at
[20], and then angles outside of the interval $(-2\pi,2\pi)$ were normalized
to be within the interval. The parameter optimization subroutine for the four-
vertex graphs uses the Broyden-Fletcher-Goldfarb-Shanno algorithm [21] with 1
random initial seed.

The four-vertex graph dataset has forty-nine angles, twenty-four of which are
$\beta$ (four $\beta$ angles for each of the six graphs). The eight-vertex
dataset has $249,156$ angles, $88,936$ of which are $\beta$ angles and the
rest are $\gamma$ angles. Interestingly, in both datasets, the $\gamma$ and
$\beta$ that maximize $\langle C\rangle_{1}^{\mathrm{ma}}$ tend to concentrate
around multiples of $\pi/4$. Over 53% of the $\gamma$ and $\beta$ that
maximized the expected value for the four-vertex graph dataset were multiples
of $\pi/4$ while approximately 82% of the eight-vertex angles were multiples
of $\pi/4$ (within three decimal places). The distribution of angles in the
eight-vertex case is relatively symmetric about $0$, as well, which can be
seen in Fig. 2.

A significant percentage of the $\beta_{v}$ that take the value of zero when
optimizing $\langle C\rangle_{1}^{\mathrm{ma}}$ coincide with maximum degree
vertices. In fact, there are two $\beta_{v}$ that are $0$ in the four-vertex
dataset, and both of these vertices have the highest degree in their
respective graphs. In the eight-vertex data, there are 5,754 $\beta_{v}=0$,
and of these, 2,759 coincide with maximum degree vertices in their respective
graphs. Thus, approximately 48% of the $\beta_{v}=0$ correspond to maximal
degree vertices in the eight-vertex dataset. Similarly, there are three
$\gamma_{uv}=0$ in the four-vertex dataset, and all of them are incident to at
least one maximal degree vertex, meaning a maximal degree vertex is one of
their endpoints. In the eight-vertex data set, there are 37,709
$\gamma_{uv}=0$, and of these, 18,108 are incident to at least one maximum
degree vertex, which is approximately 48%.

##  III An angle rounding heuristic

Approximately 53% (four-vertex graphs) and 82% (eight-vertex graphs) of the
$\beta_{i}$ and $\gamma_{uv}$ that optimize $\langle
C\rangle_{1}^{\mathrm{ma}}$, as found in [19], are multiples of $\pi/4$. Even
though a significant percentage of angles that maximize $\langle
C\rangle_{1}^{\mathrm{ma}}$ are not multiples of $\pi/4$, it is possible that
there exist angles that are multiples of $\pi/4$ that still yield the same
expected value. Thus, we round all angles that are not multiples of $\pi/4$ to
the nearest multiple of $\pi/4$ and calculate the new expected value of $C$.
We call the expected value of $C$ calculated using angles that were rounded
$\langle C\rangle_{1}^{\mathrm{ma},\;\mathrm{r}}$, where the $r$ stands for
rounded. Interestingly, for all four-vertex graphs, $\langle
C\rangle_{1}^{\mathrm{ma}}-\langle
C\rangle_{1}^{\mathrm{ma},\;\mathrm{r}}<10^{-6}$, which is the BFGS precision.

Approximately 88% of the eight-vertex graphs have the same expected value when
the angles are rounded as they had when the angles are not rounded. The
maximum difference between the expected values when angles are rounded to the
nearest $\pi/4$ and not rounded is $0.10$. This data can be seen in Fig. 3.

In the remainder of this section, we first present an example that provides
intuition as to why $\langle C\rangle_{1}^{\mathrm{ma},\;\mathrm{r}}$ can be
equal to $\langle C\rangle_{1}^{\mathrm{ma}}$. We then analyze the rounded
angle data.

Figure 1: The percent of $\beta_{v}$ and $\gamma_{i,j}$ that are optimized at
$k\pi$ for all connected, non-isomorphic four-vertex graphs. Figure 2: The
percent of $\beta_{v}$ and $\gamma_{i,j}$ that are optimized at $k\pi$ for all
connected, non-isomorphic eight-vertex graphs. Figure 3: Difference between
$AR^{\mathrm{ma}}$ and $AR^{\mathrm{ma},\;\mathrm{r}}$ and the number of times
difference occurs for all eight-vertex graphs.

###  III.1 Example: $P_{2m}$, $m\geq 2$

$v_{0}$$v_{1}$$\ldots$$v_{2m-2}$$v_{2m-1}$ Figure 4: $P_{2m}$. The vertices
$v_{1}$ through $v_{2m-2}$ each have two neighbors, while $v_{0}$ and
$v_{2m-1}$ have one neighbor each. Thus, the vertices $v_{1}$ through
$v_{2m-2}$ have maximal degree for this graph.

As a toy case that rounding angles to the nearest multiple of $\pi/4$ can
preserve the approximation ratio, let us consider the path $P_{2m}$, $m\geq 2$
as shown in Fig. 4. This has an even number of vertices, thus an odd number of
edges. Suppose $\gamma_{2i,2i+1}=\pi/2$ for all $i\leq m$ and
$\gamma_{2i+1,2i+2}=0$. Furthermore, suppose $\beta_{2j}=x_{j}-\delta_{j}$ and
$\beta_{2j+1}=x_{j}+\delta_{j}$ for some $x_{j}\in(-2\pi,2\pi)$ such that
$2x_{j}+\delta_{j}=2x_{j}=q_{j}\pi/4$ for some $q_{j}\in\mathbb{Z}$.

Consider new variables

$\displaystyle\sigma_{2j,2j+1}$
$\displaystyle=\beta_{2j}+\beta_{2j+1}=2x_{j}+\delta_{j}=q_{j}\pi/4.$

Note that rounding all $\beta_{j}$ to the nearest multiple of $\pi/4$ gives

$\displaystyle\beta_{2j}\to\beta_{2j}\pm\delta_{j}$
$\displaystyle\beta_{2j+1}\to\beta_{2j+1}\mp\delta_{j}$
$\displaystyle\sigma_{2j,2j+1}\to\beta_{2j}\pm\delta_{j}+\beta_{2j+1}\mp\delta_{j}=\beta_{2j}+\beta_{2j+1}=\sigma_{2j,2j+1}$

Define $\sigma_{2j,2j+1}$ to be the sum $\beta_{2j}+\beta_{2j+1}$. We shall
show that rounding $\beta_{2j}$ and $\beta_{2j+1}$ to the nearest multiple of
$\pi/4$ does not affect the approximation ratio for all $j$.

Consider the total evolution of the quantum state,

$\displaystyle|\psi\rangle=$
$\displaystyle\left(\prod_{k=0}^{2j-1}e^{-i\beta_{k}X_{k}}\right)\left(\prod_{j\ell\in
E(P_{2m})}e^{-i\gamma_{jk}Z_{j}Z_{k}}\right)|+\rangle^{\otimes m}$
$\displaystyle=$ $\displaystyle\prod_{j\leq
m}e^{-i(\beta_{2j}X_{2j}+\beta_{2j+1}X_{2j+1})}e^{-i\gamma_{2j,2j+1}Z_{2j}Z_{2j+1}}\times$
$\displaystyle|++\rangle_{2j,2j+1}$

Since $\gamma_{2j+1,2j+2}=0$, the all two qubit subspaces $2j$ and $2j+1$ are
independent from all others, thus the last line follows.

For fixed $j$, each $Z_{2j}Z_{2j+1}$ term of the product is

$\displaystyle
e^{-i(\beta_{2j}X_{2j}+\beta_{2j+1}X_{2j+1})}e^{-i\gamma_{2j,2j+1}Z_{2j}Z_{2j+1}}|++\rangle_{2j,2j+1}.$
(1)

Use the variable $\sigma_{2j,2j+1}$ to express the leftmost operator as

$e^{-i(\beta_{2j}X_{2j}+\beta_{2j+1}X_{2j+1})}=e^{-i\sigma_{2j,2j+1}X_{2j}}e^{-i\beta_{2j+1}(X_{2j+1}-X_{2j})}.$

Plugging this into Eq. (1) gives

$\displaystyle
e^{-i\sigma_{2j,2j+1}X_{2j}}e^{-i\gamma_{2j,2j+1}Z_{2j}Z_{2j+1}}|++\rangle_{2j,2j+1}.$

Therefore, Eq. (1) (and thus ${\left|\psi\right\rangle}$ since each subspace
is independent) relies only on $\sigma_{2j,2j+1}$, and not the individual
$\beta_{2j}$ and $\beta_{2j+1}$. Note that the choice of $\gamma_{i,j}$ above
may not necessarily optimize the expected value of the graph. This is merely a
toy model to show that it is possible to preserve the expected value when
vertex angles are rounded if the edge angles have a specific pattern.

An example of a graph that is optimized at angles that are multiples of
$\pi/4$ is the path $P_{4}$. Label the vertices $0$ to $3$ from left to right,
and let the $\beta_{i}$ correspond to vertex $i$ and $\gamma_{i,i+1}$
correspond to the edge from vertex $v_{i}$ to vertex $v_{i+1}$. A set of
angles that maximize $\langle C\rangle_{1}^{\mathrm{ma}}$ is

$\displaystyle\beta_{0}$ $\displaystyle=-0.53\pi$ $\displaystyle\beta_{2}$
$\displaystyle=0.33\pi$ $\displaystyle\beta_{1}$ $\displaystyle=-0.22\pi$
$\displaystyle\beta_{3}$ $\displaystyle=-0.08\pi$ $\displaystyle\gamma_{01}$
$\displaystyle=\pi/2=\gamma_{23}$ $\displaystyle\gamma_{12}$
$\displaystyle=0.$

One can see from the analytical formula of ma-QAOA found in [10] that the
total expectation value $\langle C\rangle_{1}^{\mathrm{ma}}=2.5$. Letting
$\sigma_{0,1}=(\beta_{0}+0.3)\pi+(\beta_{1}-0.3)\pi$ and
$\sigma_{2,3}=(\beta_{2}-0.08)\pi+(\beta_{3}+0.08)\pi$ gives the same
approximation ratio.

While $\langle C\rangle_{1}^{\mathrm{ma}}=\langle
C\rangle_{1}^{\mathrm{ma},\;\mathrm{r}}$ in this case, it is only clear that
rounding holds after breaking the graph into two pieces that do not interact
and varying the angles in each piece together. This example is special in that
the graph $P_{4}$ contains a bridge (a single edge whose removal disconnects
the graph), and it received an angle of zero. In general, a graph may not have
a bridge. Define the edge-connectivity of a graph $G$, denoted $\lambda(G)$,
to be the smallest number of edges whose removal disconnects $G$. Note this
definition assumes $G$ is connected. In order to separate the graph into two
distinct pieces, at least $\lambda(G)$ edges need to receive a $\gamma$ angle
equal to $0$. It is not clear if there is a method that can be used to
determine whether or not angles can be rounded that does not depend on
assigning zero angles to some set of size at least $\lambda(G)$ first.

###  III.2 Randomly assigning multiples of $\pi/4$ as angles

We first examine if randomly assigning angles that are multiples of $\pi/4$
yields a high approximation ratio. In this experiment, we randomly assign
angles $k\pi/4$ for $-8\leq k\leq 8,k\in\mathbb{Z}$ to each $\beta_{i}$ and
$\gamma_{uv}$ for $i\in V(G),uv\in E(G)$ in each eight-vertex graph. We then
plug them into the expected value formula without performing any classical
optimization routine and note the approximation ratio, which is denoted ARma,
random init, no opt. As shown in Fig. 5, ARma \- ARma, random init, no opt is
close to 0.25 on average, which is a significant difference. Also note that an
insignificant number of graphs achieve ARma \- ARma, random init, no opt$=0$.
When using this heuristic, ma-QAOA achieves a mean approximation ratio of
$0.643$ with standard deviation $0.066$ for eight-vertex graphs. In fact,
97.9% of graphs have an approximation ratio higher than $0.5$ with a randomly
selected parameters that are multiples of $\pi/4$. This random angle selection
technique beats randomly guessing the MaxCut partitions on the eight-vertex
dataset. However, since the average ARma, random init, no opt varies
significantly from ARma, this method indicates that parameter optimization is
needed to obtain the best results.

##  IV An angle rounding parameter initialization strategy

In this section, we present a heuristic for initializing ma-QAOA angles based
on the data in Section II. From Figs. 1-2, we see that a significant
proportion of the angles that maximize $\langle C\rangle_{1}^{\mathrm{ma}}$
are multiples of $\pi/4$. We propose a heuristic that initializes all angles
to random multiples of $\pi/4$ in the interval $(-2\pi,2\pi)$ and use this
starting point to seed one round of BFGS for parameter optimization.

This initialization technique is expected to significantly outperform the
method in the previous section where random multiples of $\pi/4$ are assigned
to each $\beta_{i}$ and $\gamma_{uv}$ for $i\in V(G),uv\in E(G)$. In fact, for
eight-vertex graphs, this parameter initialization strategy achieves a mean
approximation ratio of $0.894$ with a standard deviation of $0.067$ when using
one iteration of the classical optimization subroutine to optimize the angles.
In the case of four-vertex graphs, the parameter initialization strategy
achieves a mean approximation ratio of $0.931$ with a standard deviation of
$0.111$. In Fig. 6, we see that the difference between ARma and ARma, random
init (the approximation ratio using the parameter initialization technique) is
zero for a significant portion of the eight-vertex dataset. These results are
comparable to the results of using ma-QAOA with no initialization strategy and
1 random BFGS seeds. In this case, the mean approximation ratio for all four-
vertex graphs is 0.910 and the mean approximation ratio for all eight-vertex
graphs is 0.901. Thus, using one round of BFGS to optimize parameters that are
initially seeded to be random multiples of $\pi/4$ performs well for these
small graphs. This method requires significantly less classical optimization
effort than using no initialization strategies and just using one randomly
seeded round of BFGS to find the optimal parameters.

Figure 5: Difference between the approximation ratio for the initial angles
and the approximation ratio for the optimal angles for all eight-vertex graphs
without classical optimization subroutine. Figure 6: Difference between the
approximation ratio for the initial angles and the approximation ratio for the
optimal angles for all eight-vertex graphs with one step of the classical
optimization subroutine.

##  V Discussion

In this work, we present an angle rounding parameter initialization scheme for
ma-QAOA where ma-QAOA initial angles are randomly selected to be multiples of
$\pi/4$ between $-2\pi$ and $2\pi$, and then BFGS is seeded from this vector
and allowed to search the parameter space for optimal solutions. The technique
requires few initial seeds for BFGS to attain an average approximation ratio
of 0.894 on all connected eight-vertex graphs. This is within 0.78% of the
average approximation ratio of ma-QAOA with no parameter initialization
technique, which is 0.901 on the same dataset.

Interestingly, the subgraphs induced by unique optimal edge angles tend to be
forests. This is reminiscent of ST-QAOA, where a spanning tree of the
underlying graph is found and given its own QAOA parameters. This work
suggests that instead of using spanning trees, setting distinct angles for
forests may provide higher approximation ratios. Future work includes
determining how to leverage forests in parameter selection or initialization
routines. Other future work includes leveraging problem symmetry for faster
training, such as in [22, 23]. Another route for future work includes
determining how the parameter initialization technique scales for large graphs
and if the initialization parameters that are used to seed BFGS can be
cleverly selected based on graph structure.

###### Acknowledgements.

The authors would like to acknowledge NSF award CCF-2210063. The authors would
like to thank Phillip Lotshaw for his insight.

## References Cited

  * [1] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” _arXiv preprint arXiv:1411.4028_ , 2014.
  * [2] G. G. Guerreschi and A. Y. Matsuura, “Qaoa for max-cut requires hundreds of qubits for quantum speed-up,” _Scientific reports_ , vol. 9, 2019.
  * [3] R. Herrman, L. Treffert, J. Ostrowski, P. C. Lotshaw, T. S. Humble, and G. Siopsis, “Impact of graph structures for qaoa on maxcut,” _arXiv preprint arXiv:2102.05997_ , 2021.
  * [4] G. E. Crooks, “Performance of the quantum approximate optimization algorithm on the maximum cut problem,” _arXiv preprint arXiv:1811.08419_ , 2018.
  * [5] Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, “Quantum approximate optimization algorithm for maxcut: A fermionic view,” _Physical Review A_ , vol. 97, no. 2, p. 022304, 2018.
  * [6] A. Ozaeta, W. van Dam, and P. L. McMahon, “Expectation values from the single-layer quantum approximate optimization algorithm on ising problems,” _Quantum Science and Technology_ , vol. 7, no. 4, p. 045036, sep 2022. [Online]. Available: https://doi.org/10.1088%2F2058-9565%2Fac9013
  * [7] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,” _Physical Review X_ , vol. 10, no. 2, June 2020. [Online]. Available: https://doi.org/10.1103%2Fphysrevx.10.021067
  * [8] N. Earnest, C. Tornow, and D. J. Egger, “Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware,” _Physical Review Research_ , vol. 3, no. 4, p. 043088, 2021.
  * [9] J. Wurtz and D. Lykov, “Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs,” _Physical Review A_ , vol. 104, no. 5, p. 052419, 2021.
  * [10] R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, “Multi-angle quantum approximate optimization algorithm,” _arXiv preprint arXiv:2109.11455_ , 2021.
  * [11] K. Shi, R. Herrman, R. Shaydulin, S. Chakrabarti, M. Pistoia, and J. Larson, “Multiangle qaoa does not always need all its angles,” _2022 IEEE/ACM 7th Symposium on Edge Computing (SEC)_ , pp. 414–419, 2022. [Online]. Available: https://ieeexplore.ieee.org/document/9996634/
  * [12] V. Vijendran, A. Das, D. E. Koh, S. M. Assad, and P. K. Lam, “An expressive ansatz for low-depth quantum optimisation,” _arXiv preprint arXiv:2302.04479_ , 2023.
  * [13] J. Wurtz and P. J. Love, “Classically optimal variational quantum algorithms,” _IEEE Transactions on Quantum Engineering_ , vol. 2, pp. 1–7, 2021.
  * [14] I. Gaidai and R. Herrman, “Performance analysis of multi-angle qaoa for $p>1$,” _arXiv e-prints_ , pp. arXiv–2312, 2023.
  * [15] S. H. Sack and M. Serbyn, “Quantum annealing initialization of the quantum approximate optimization algorithm,” _Quantum_ , vol. 5, p. 491, 2021. [Online]. Available: https://quantum-journal.org/papers/q-2021-07-01-491/
  * [16] S. H. Sack, R. A. Medina, R. Kueng, and M. Serbyn, “Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement,” _Physical Review A_ , vol. 107, p. 062404, 2023. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.107.062404
  * [17] J. Sud, S. Hadfield, E. Rieffel, N. Tubman, and T. Hogg, “A parameter setting heuristic for the quantum alternating operator ansatz,” 2022.
  * [18] S. H. Sureshbabu, D. Herman, R. Shaydulin, J. Basso, S. Chakrabarti, Y. Sun, and M. Pistoia, “Parameter setting in quantum approximate optimization of weighted problems,” 2023.
  * [19] A. Wilkie, “Angle rounding qaoa,” 2024, found at https://github.com/Vilcius/Angle-Rounding-QAOA.
  * [20] I. Gaidai, “Ma-qaoa,” found at https://github.com/GaidaiIgor/MA-QAOA.
  * [21] W. H. Press, B. P. Flannery, and S. A. Teukolsky, _Numerical Recipes in Fortran 77: The Art of Scientific Computing_ , 2nd ed. Cambridge University Press, 1993, https://people.sc.fsu.edu/ inavon/5420a/DFP.pdf.
  * [22] F. Sauvage, M. Larocca, P. J. Coles, and M. Cerezo, “Building spatial symmetries into parameterized quantum circuits for faster training,” _Quantum Science and Technology_ , vol. 9, no. 1, p. 015029, 2024.
  * [23] R. Shaydulin and S. M. Wild, “Exploiting symmetry reduces the cost of training qaoa,” _IEEE Transactions on Quantum Engineering_ , vol. 2, pp. 1–9, 2021.


# On some non-rigid unit distance patterns

Nóra Frankl Alfréd Rényi Institute of Mathematics, Budapest, Email:
<EMAIL_ADDRESS>Dora Woodruff Harvard University, Cambridge, MA, Email:
<EMAIL_ADDRESS>
###### Abstract

A recent generalization of the Erdős Unit Distance Problem, proposed by
Palsson, Senger and Sheffer, asks for the maximum number of unit distance
paths with a given number of vertices in the plane and in $3$-space. Studying
a variant of this question, we prove sharp bounds on the number of unit
distance paths and cycles on the sphere of radius $1/\sqrt{2}$. We also
consider a similar problem about $3$-regular unit distance graphs in
$\mathbb{R}^{3}$.

##  1 Introduction

The Erdős Unit Distance Problem is one of the most famous unsolved problems in
discrete geometry. It asks for $u_{2}(n)$, the maximum possible number of unit
distances among $n$ points in the plane. The best known lower bound,
$u_{2}(n)=\Omega(n^{1+c/\log\log n})$ for some constant $c$ is due to Erdős
[5], and the current best upper bound $u_{2}(n)=O(n^{\frac{4}{3}})$ is due to
Spencer, Szemerédi and Trotter[13]. The analogous problem is also interesting,
and still far from a resolution, in $\mathbb{R}^{3}$ and on spheres of most
radii. We note that however, starting from dimension $4$, up to the order of
magnitude, the question is less interesting, as one can find $\Omega(n^{2})$
many unit distances by a well known construction of Lentz [6]. The exact value
for large $n$ and even $d\geq 4$ was determined by Brass [2] and Swanepoel
[14].

Several variants and generalizations of the unit distance problem have been
studied. Recently, Sheffer, Palsson and Senger [10] proposed to find the
maximum number of unit distance paths $P_{k}(n)$ with $k$ vertices in
$\mathbb{R}^{2}$ or $\mathbb{R}^{3}$. This problem was essentially solved in
$\mathbb{R}^{2}$ in [7] by finding almost sharp bounds for $k=0,1\mod 3$ and
showing that the for $k=2\mod 3$ the problem is essentially equivalent to the
Unit Distance problem. Similar questions have been studied for paths and trees
determined by dot products by Kilmer, Marshall, Senger [12] and Gunter,
Palsson, Rhodes, Senger [8]. Passant [11] obtained results for the
corresponding distinct distances problem.

We continue this line of research. First, we study the unit distance path
problem on the sphere $\mathbb{S}^{2}$ of radius $\frac{1}{\sqrt{2}}$.
Stereographic projection from the center of the sphere shows that unit
distance graphs on a sphere of this radius are very similar to point-line
incidence graphs in the plane. The only difference comes from the fact that
when we project a line to a great circle on the sphere, we can choose any of
its poles to represent the line. Thus, while the maximum number of edges in
the two graphs are in within a constant factor, $K_{2,t}$ subgraphs with
$t\geq 3$ are not excluded from unit distance graphs on the sphere. In other
words, instead of unit distance graphs on the sphere, we could think about
point-line incidence graphs in the plane, but allowing every line to be used
twice.

For any fixed $k$, we determine $P^{S}_{k}(n)$, the maximum number of unit
distance paths with $k$ vertices on the sphere $\mathbb{S}^{2}$, up to a
polylogarithmic factor. We will use notations $\tilde{\Theta}$ and $\tilde{O}$
to hide a poly-logarithmic error term.

######  Theorem 1.

For any fixed $k\geq 1$, the number of paths on $k$ vertices on the sphere is

$P^{S}_{k}(n)=\begin{cases}\tilde{\Theta}\left(n^{\lfloor
2(k+3)/5\rfloor}\right),&\mbox{if }k=0,1,3,4\textrm{ }({\rm mod\
}5),\\\\[4.0pt] \tilde{\Theta}\left(n^{\lfloor
2(k+3)/5\rfloor-2/3}\right),&\mbox{if }k=2\textrm{ }({\rm mod\
}5).\end{cases}$

The $k=2$ case of the theorem above (without the polylogarithmic error), via
stereographic projection, is the Szemerédi-Trotter bound for point-line
incidences. Note that while the planar quantity, $P_{k}(n)$ depends on $k$ mod
$3$, on the sphere the answer depends on $k$ mod $5$. The constructions for
the lower bounds, described in Section $2$, will explain this difference. We
also remark that the exponent $2k/5$ is very close the non-tight upper bounds
from [10] for the planar case, but this appears to be a coincidence.

Next, we study $C_{k}^{S}(n)$, the maximum possible number of unit distance
cycles with $k$ vertices determined by a set of $n$ points in the sphere
$\mathbb{S}^{2}$. For most cycle lengths we have almost sharp results, however
working with short cycles is more difficult. Again, bounding the number of
cycles of length $2k$ on the sphere is equivalent to finding a bound on the
number of polygons with $k$ vertices in the plane that can be determined by
$n$ points and $n$ lines, such that we are allowed to use every line twice.

######  Theorem 2.

We have $C_{4}^{S}(n)=\Theta(n^{2})$, and for any $k\geq 5$, with the
exception of $k=6,7,9$ we have

$C^{S}_{k}(n)=\begin{cases}\tilde{\Theta}\left(n^{\lfloor
2k/5\rfloor}\right),&\mbox{if }k=0,1,3,4({\rm mod\ }5),\\\\[4.0pt]
\tilde{\Theta}\left(n^{\lfloor 2k/5\rfloor+1/3}\right),&\mbox{if }k=2({\rm
mod\ }5).\end{cases}$

For $k=3,6,7,9$ there is a gap between the exponent of the lower and upper
bounds. We summarize the (to our knowledge) best bounds for these lengths in
Proposition 2 in Section $3$. We note that a related problem about cycles in
incidence graphs of points and lines was studied by de Caen and Székely [4].
They conjectured that the maximum number of $6$-cycles determined by an
incidence graph of $n$ points and $m$ lines is $O(mn)$, which was disproved by
Klavík, Král and Mach [9].

Next, we turn to a similar question in $\mathbb{R}^{3}$. We study the maximum
number of unit distance subgraphs isomorphic to a given $3$-regular graph $G$.

######  Theorem 3.

Let $G$ be a fixed $3$-regular graph on $k$ vertices. The maximum number of
unit distance subragraphs isomorphic to $G$ determined by a set of $n$ points
in $\mathbb{R}^{3}$ is $\tilde{O}\left(n^{k/2}\right)$.

By slightly modifying the problem, and asking for the maximum number of copies
of $G$ with prescribed edge lengths, our upper bound remains valid. In this
modified setting, for bipartite graphs we can match this bound by simple
constructions.

### Acknowledgment

This project was done as part of the 2021 New York Discrete Math REU, funded
by NSF grant DMS 2051026. NF was partially supported by ERC Advanced Grant
"GeoScape". We thank Adam Sheffer and Pablo Soberón for their organization of
the REU, as well as all mentors and participants of the program for their
support.

##  2 Paths on the sphere

We begin by recalling the Szemerédi-Trotter bound [15] on the number of point
line incidences. For the maximum number of incidences $I(n,m)$ between a set
of $n$ points and $m$ lines in the plane we have

$I(n,m)=\Theta\left(n^{\frac{2}{3}}m^{\frac{2}{3}}+m+n\right).$ (1)

Let $u(m,n)$ denote the maximum number of unit distance pairs between a set of
$n$ and a set of $m$ points on the sphere. Via stereographic projection, (1)
implies

$u(n,m)=\Theta\left(n^{\frac{2}{3}}m^{\frac{2}{3}}+m+n\right).$ (2)

For any $r\geq 1$, we say that a point $p$ on $\mathbb{S}^{2}$ is _$r$ -rich_
with respect to a set of $n$ points $P\subseteq\mathbb{S}^{2}$, if it is unit
distance apart from at least $r$ points of $P$. A well-known equivalent
formulation of (1) gives that the maximum number of $r$-rich points with
respect to $P$ is

$O\left(\frac{n^{3}}{r^{2}}+\frac{n}{r}\right).$ (3)

We now list some simple observations, which will be very helpful in this and
in the following section. First, on a sphere of radius $\frac{1}{\sqrt{2}}$,
two points $p,q$ are unit distance apart if and only if $p$ lies on the great
circle that has $q$ as a pole. Furthermore, if $p$ and $q$ are not antipodal,
then there are at most $2$ points unit distance from both of them. However, if
$p$ and $q$ are antipodal, then any point lying on their great circle will be
unit distance from both. The work of Palsson, Senger, and Sheffer in [10] and
Frankl and Kupavskii in [7] for paths in the plane relies on the fact that in
the plane, there are at most two points unit distance from two fixed points.
Therefore, we will need to find some way to work around the existence of
antipodal pairs in our proofs.

We call a path $(p_{1},p_{2},\dots,p_{k})$ on the sphere _antipodal-free_ if
there is no $1\leq i\leq k-2$ such that $p_{i}$ and $p_{i+2}$ are antipodal.
From the observations above, Theorem 2 in [7] implies the following statement.

######  Proposition 1.

For any fixed $k$, the number of antipodal-free $k$-paths
$(p_{1},p_{2},\dots,p_{k})$ determined by a set of $n$ points on the sphere is
at most $P_{k}(n)$, the number of $k$-paths in a set of $n$ points in the
plane. That is, the number of antipodal-free $k$-paths is
$\tilde{O}(n^{\lfloor k/3\rfloor+1})$ for $k=0,1\mod 3$, and
$\tilde{O}(n^{(k+2)/3})$ for $k=2\mod 3$.

###### Proof of Theorem 1.

We start by proving the upper bounds. The proof is by induction on $k$. We
have to consider several base cases.

  * •

For $k=1$, we trivially have $P^{S}_{1}(n)=n$.

  * •

For $k=2$, by (2) we have $P^{S}_{2}(n)=O(n^{\frac{4}{3}})$.

  * •

For $k=3$, in a path $(p_{1},p_{2},p_{3})$ either $p_{1}$ and $p_{3}$ are
antipodal, or not. In the first case, after choosing $p_{1}$, the antipodal
pair $p_{3}$ is uniquely determined, giving the bound $O(n^{2})$. In the
second case, after choosing $p_{1}$ and $p_{3}$, there are at most two choices
for the middle vertex $p_{2}$, and we obtain again the bound $O(n^{2})$.
Overall we still obtain $P^{S}_{3}(n)=O(n^{2})$.

  * •

For $k=4$, any path $(p_{1},p_{2},p_{3},p_{4})$ is either antipodal-free, or
not. If it is not antipodal-free, we may assume without loss of generality
that $p_{2}$ and $p_{4}$ are antipodal. Then after choosing
$(p_{1},p_{2},p_{3})$, the last vertex $p_{4}$ is uniquely determined. By the
$k=3$ case we have $O(n^{2})$ choices for $(p_{2},p_{3},p_{4})$, obtaining the
$O(n^{2})$ bound. In the antipodal-free case Proposition 1 implies the bound
$\tilde{O}(n^{2})$. Adding together the two cases, we obtain the bound
$\tilde{O}(n^{2})$.

  * •

For $k=5,6,8$, in any path $(p_{1},\dots,p_{k})$ either $p_{k-2}$ and $p_{k}$
are antipodal, or not. In the first case, after choosing
$(p_{1},\dots,p_{k_{1}})$ the last vertex $p_{k}$ is uniquely determined, and
we are done by the $k-1$ case. In the second case, after choosing
$(p_{1},\dots,p_{k-2})$ and $p_{k}$, there are at most $2$ options for
$p_{k-1}$, and we are done by the $k-2$ case.

  * •

For $k=7$, in any path $(p_{1},\dots,p_{7})$ at most one of $(p_{2},p_{4})$
and $(p_{4},p_{6})$ are antipodal (if both pairs were antipodal, then we would
have $p_{2}=p_{6}$, which is forbidden). Without loss of generality, we may
assume that $p_{4}$ and $p_{6}$ are not antipodal. Then after choosing
$(p_{1},p_{2},p_{3},p_{4})$ and $(p_{6},p_{7})$ we have at most two options
for $p_{5}$ and we obtain the bound
$\tilde{O}(n^{2})O(n^{4/3})=\tilde{O}(n^{10/3})$ bound by the $k=4$ and $k=2$
cases.

  * •

For $k=9$, in any path $(p_{1},\dots,p_{9})$ either $p_{4}$ and $p_{6}$ are
antipodal, or not. If they are not antipodal, then after choosing
$(p_{1},\dots,p_{4})$ and $(p_{6},\dots,p_{9})$ we have at most $2$ choices
for $p_{5}$, and obtain the $\tilde{O}(n^{4})$ bound by the $k=4$ case. If
$p_{4}$ and $p_{6}$ are antipodal, then $p_{6}$ and $p_{8}$ cannot be
antipodal. Then after choosing $(p_{1},p_{2})$, $(p_{5},p_{6})$ and
$(p_{8},p_{9})$, the vertex $p_{4}$ is uniquely determined, and we have at
most two choices for $p_{3}$ and $p_{7}$. Thus, we obtain the bound
$O(n^{4/3})O(n^{4/3})O(n^{4/3})=O(n^{4})$ bound by the $k=2$ case.

For the induction step, we notice that in the bounds we want to prove

$\textrm{the difference between the exponent of }P^{S}_{k}(n)\textrm{ and
}P^{S}_{k-5}(n)\textrm{ is }2\textrm{ for any }k\geq 6$ (4)

and

$\textrm{the difference between the exponent of }P^{S}_{k}(n)\textrm{ and
}P^{S}_{k-8}(n)\textrm{ is at least }3\textrm{ for any }k\geq 9.$ (5)

In any path $(p_{1},\dots,p_{k})$ either one of the pairs
$(p_{4},p_{6}),(p_{k-3},p_{k-5})$ are antipodal, or none of them are
antipodal. We bound the number of each of these type of paths separately.

If $p_{4}$ and $p_{6}$ are not antipodal, then by the $k=4$ case there are
$\tilde{O}(n^{2})$ different ways to choose $(p_{1},p_{2},p_{3},p_{4})$.
Further, by definition there are $P^{S}_{k-5}(n)$ ways to choose
$(p_{6},\dots,p_{k})$. Since $p_{4}$ and $p_{6}$ are not antipodal, after
choosing the first $4$ and the last $k-5$ vertices, there are at most $2$
different ways to extend it to a path. This gives the bound

$\tilde{O}(n^{2})P^{S}_{k-5}(n)$ (6)

for the number of paths of this type. So, by observation (4) about the
exponent of $P^{S}_{k-5}(n)$ and by induction, in this case we are done.
Symmetrically, if the $p_{k-3}$ and $p_{k-5}$ are antipodal, we obtain again
the bound

$\tilde{O}(n^{2})P^{S}_{k-5}(n).$ (7)

If both $p_{4},p_{6}$ and $p_{k-3},p_{k-5}$ are antipodal and $k\geq 10$ then
after choosing $(p_{5},p_{6},\dots,p_{k-4})$ the vertices $p_{4}$ and
$p_{k-3}$ are uniquely determined. Further, both $(p_{1},p_{2})$ and
$(p_{k-1},p_{k})$ can be chosen in $O(n^{\frac{4}{3}})$ different ways. Since
$(p_{2},p_{4})$ and $(p_{k-3},p_{k-1})$ cannot be antipodal, there are at most
two different choices of $p_{3}$ through which $p_{2}$ and $p_{4}$ can be
connected, and at most two different choices of $p_{k-2}$ through which
$p_{k-3}$ and $p_{k-1}$ can be connected. Together, these imply that the
maximum number of paths of this type is

$O(n^{\frac{4}{3}})P^{S}_{k-8}(n)O(n^{\frac{4}{3}})=O(n^{3})P^{S}_{k-8}(n).$
(8)

From (6)-(8) we obtain that the maximum number of $k$-paths is bounded by

$\tilde{O}(n^{2})P^{S}_{k-5}(n)+O(n^{3})P^{S}_{k-8}(n).$

This, by induction and by observations (4) and (5) about the exponent of
$P^{S}_{k-5}(n)$ and $P^{S}_{k-8}(n)$ finishes the proof of the upper bound.

We know turn to the lower bound. For the $k=0,1,3,4$ $\mod 5$ cases, we
imitate the planar constructions from [10], taking advantage of the antipodal
vertices. For an illustration see Figure 1. Let $m=\lfloor 5n/2k\rfloor$. We
take $\lceil 2k/5\rceil$ great circles $K_{0},\dots,K_{\lfloor 2k/5-1\rfloor}$
and on each of them we place a set $Q_{i}$ of $(m-2)$ points on each such
that:

  * •

For any $0\leq i<\lceil 2k/5\rceil-1$ and for any $p_{i}\in Q_{i}$ there is a
point $p_{i+1}\in Q_{i+1}$ at unit distance apart from $p_{i}$.

  * •

For any $0\leq i\leq\lceil 2k/5\rceil-1$ the set $Q_{i}$ does not contain any
pole of any circle $K_{j}$.

Further, for every $i$ we place two points $N_{i}$ and $S_{i}$ in the poles
the circle $K_{i}$. In this construction, we can find $\Omega(n^{\lfloor
2(k+3)/5\rfloor})$ many $k$-paths $(p_{1},p_{2},\dots,p_{k})$ such that for
$i=5\ell+j$ with $1\leq j\leq 5$:

  * •

$p_{i}$ is in $Q_{\ell}$ if $j=1,3,5$

  * •

$p_{i}=N_{\ell}$ for $j=2$

  * •

$p_{i}=S_{\ell}$ for $j=4$.

Indeed, after choosing $p_{1}$ from $Q_{0}$ and $p_{5\ell+3},p_{5\ell+5}$ (for
$5\ell+3,5\ell+5\leq k$) from $Q_{\ell}$ arbitrarily for every $\ell$, we can
extend the resulting set to a $k$-path.

Finally, we explain the modification to obtain the $n^{1/3}$ improvement for
$k=2\mod 5$. We take the construction described previously with the circles
$K_{i}$, points sets $Q_{i}\in K_{i}$ and poles $N_{i},S_{i}$ for $k-2$. Take
another point set $Q$ of of $m$ points and with
$\Omega(m^{4/3})=\Omega(n^{4/3})$ unit distance pairs (this can be done by the
same stereographic projection argument discussed in the introduction). Then
modify $Q_{0}$ on $K_{5}$ such that for any point $q\in Q$ there is a
$q_{1}\in Q_{0}$ at unit distance apart from $q$. Similarly as before, we can
find $\Omega(n^{\lfloor 2(k+3)/5\rfloor+1/3})$ many $k$-paths
$(q_{1},q_{2},p_{1},p_{2},\dots,p_{k-2})$ such that for $i=5\ell+j$ with
$1\leq j\leq 5$:

  * •

$p_{i}$ is in $Q_{\ell}$ if $j=1,3,5$,

  * •

$p_{i}=N_{\ell}$ for $j=2$,

  * •

$p_{i}=S_{\ell}$ for $j=4$,

  * •

$q_{1},q_{2}\in Q$.

Indeed, after choosing a unit distance pair $(q_{1},q_{2})$ from $Q$, and
$p_{5\ell+3},p_{5\ell+5}$ (for $5\ell+3,5\ell+5\leq k-2$) from $Q_{\ell}$
arbitrarily for every $\ell$, we can extend the resulting set to a $k$-path.

Figure 1: The circles are the great circles $K_{i}$ and $N_{i}$, $S_{i}$ are
their two poles. A possible path starting with a point from $Q_{0}$ and ending
in a point in $Q_{3}$ is shown in red.

∎

##  3 Cycles on the sphere of Radius $\frac{1}{\sqrt{2}}$

To obtain the lower bounds, we slightly modify the path construction as
follows. We can arrange the points on the last great circle $K_{\lfloor
2k/5-1\rfloor}$ such it has a point at unit distance apart from any point of
$Q_{1}$ in the $k=0,1,3,4$ cases, and from any point of $Q$ in the $k=2$ case.
This will allow closing any $(k-1)$-path $(p_{1},p_{2},\dots,p_{k-1})$ (in the
$k=0,1,3,4$ cases) or $(q_{1},q_{2},p_{1},p_{2},\dots,p_{k-3})$ (in the $k=2$
case) to a $k$-cycle. Notice that in this construction the exponent is one
smaller than the corresponding number of paths for each $k$, thus it indeed
matches the claimed bound.

###### Proof of upper bound in Theorem 2.

We begin by proving the upper bounds. First we bound the number of those
cycles $(p_{1},p_{2},\dots,p_{k})$ in which there are at most one antipodal
pair separated by one other vertex. If $(p_{1},\dots,p_{k})$ is antipodal-
free, then after choosing $(p_{1},\dots,p_{k-1})$, we have at most two choices
for the last vertex $p_{k}$. Further, by Proposition 1, the number of
$(k-1)$-paths $(p_{1},\dots,p_{k-1})$ is bounded by $2P_{k-1}(n)$.

If there is exactly one antipodal pair, say $p_{1}$ and $p_{3}$, then after
choosing the $(k-2)$-path $(p_{2},p_{3},\dots,p_{k-1})$, the antipodal pair
$p_{1}$ of $p_{3}$ is uniquely determined. Further, we have at most $2$
choices for the last vertex $p_{k}$. Thus, Proposition 1, the number of cycles
is bounded by $2P_{k-2}(n)$.

Overall, we obtain that the number of such cycles is bounded by
$2P_{k-1}(n)+kP_{k-2}(n)\leq 2kP_{k-1}(n)$. This, by Proposition 1 implies the
bound $\tilde{O}(n^{\lfloor k/3\rfloor+1})$ for $k=0,1$ $\mod 3$, and
$\tilde{O}(n^{\lfloor k/3\rfloor+1/3})$ for $k=2$ $\mod 3$. These bounds imply
directly the desired bounds. Indeed, for $k\geq 21$ it follows from $k/3+1\leq
2(k+3)/5-1$, and for $k\leq 20$ it can be checked (except for $k=3,6,7,9$) by
a brief case analysis.

Thus, we only have to bound the number of cycles under the assumption that
there are at least $2$ antipodal pairs. The argument depends on the length of
the path up to equivalence$\mod 5$.

$\bm{k=0,1,3\mod 5:}$ In this case we only need the assumption that there is
at least one pair of antipodal vertices. If $p_{1}$ and $p_{k-1}$ are
antipodal, then after choosing a $(k-2)$-path $(p_{3},p_{4},\dots,p_{k})$, the
vertex $p_{1}$ is uniquely determined. Further, since $p_{1}$ and $p_{3}$
cannot be antipodal, there are at most $2$ choices of $p_{2}$ to extend
$(p_{1},p_{3},p_{4},\dots,p_{k})$ to a cycle. Thus the number of cycles in
this case is at most $2$-times the number of $(k-2)$-paths, which is
$\tilde{O}(n^{\lfloor(2k+1)/5\rfloor})=\tilde{O}(n^{\lfloor 2k/5\rfloor})$ by
Theorem 1. As we can argue similarly for any other antipodal pair, overall we
obtain the bound $k\tilde{O}(n^{\lfloor 2k/5\rfloor})$ for the number of
cycles of this type.

$\bm{k=2\mod 5:}$ Assume that there are two antipodal pairs $(p_{1},p_{3})$
and $(p_{i},p_{i+2})$ such that $i\notin\\{1,3\\}$. First, we prove the bound
in the case when the $5$-paths $(p_{k},p_{1},p_{2},p_{3},p_{4})$ and
$(p_{i-1},p_{i},p_{i+1},p_{i+2},p_{i+3})$ are disjoint and their complements
consist of two non-empty paths $(p_{5},\dots,p_{i-2})$ and
$(p_{i+4},\dots,p_{k-1})$ of lengths $k_{1}$ and $k_{2}$ respectively. Since
$k_{1}+k_{2}=2\mod 5$, we may assume without loss of generality that
$(k_{1},k_{2})=(1,1),(2,0)$ or $(3,4)$ $\mod 5$.

  * •

If $(k_{1},k_{2})=(1,1)$ then after choosing $(p_{2},p_{3},\dots,p_{i-2})$ and
$(p_{i+1},p_{i+2},\dots,p_{k-1})$ arbitrarily, the antipodal pair $p_{1}$ of
$p_{3}$ and $p_{i}$ of $p_{i+2}$ is uniquely determined. Further, there are at
most $2$ choices for $p_{k}$ and $p_{i-1}$. Thus, the total number of cycles
of this type, using Theorem 1, is bounded by

$P^{S}_{k_{1}+3}(n)\cdot P^{S}_{k_{2}+3}(n)=\tilde{O}(n^{\lfloor
2(k_{1}+6)/5\rfloor+\lfloor 2(k_{2}+6)/5\rfloor})\\\
=\tilde{O}(n^{2(k_{1}+4)/5+2(k_{2}+4)/5})=\tilde{O}(n^{(2k-4)/5})=\tilde{O}(n^{\lfloor
2k/5\rfloor+1/3}).$

  * •

If $(k_{1},k_{2})=(2,0)$ then after choosing the paths
$(p_{2},p_{3},\dots,p_{i+1})$ and $(p_{i+4},\dots,p_{k-1})$ the antipodal pair
$p_{1}$ of $p_{3}$ and $p_{i+2}$ of $p_{i}$ is uniquely determined. Further,
there are at most $2$ choices for $p_{k}$ and $p_{i+3}$. Thus, the total
number of cycles of this type, using Theorem 1, is bounded by

$P^{S}_{k_{1}+6}(n)\cdot P^{S}_{k_{2}}(n)=\tilde{O}(n^{\lfloor
2(k_{1}+9)/5\rfloor+\lfloor
2(k_{2}+3)/5\rfloor-2/3})=\tilde{O}(n^{\frac{2k+1}{5}-\frac{2}{3}})=\tilde{O}(n^{\lfloor
2k/5\rfloor+1/3}).$

  * •

If $(k_{1},k_{2})=(3,4)$ then after choosing the paths
$(p_{2},p_{3},\dots,p_{i+1})$ and $(p_{i+4},\dots,p_{k-1})$ the antipodal pair
$p_{1}$ of $p_{3}$ and $p_{i+2}$ of $p_{i}$ is uniquely determined. Further,
there are at most $2$ choices for $p_{k}$ and $p_{i+3}$. Thus, the total
number of cycles of this type, using Theorem 1, is bounded by

$P^{S}_{k_{1}+6}(n)\cdot P^{S}_{k_{2}}(n)=\tilde{O}(n^{\lfloor
2(k_{1}+9)/5\rfloor+\lfloor
2(k_{2}+3)/5\rfloor})=\tilde{O}(n^{(2k-4)/5})=\tilde{O}(n^{\lfloor
2k/5\rfloor+1/3}).$

We also have to consider the more "degenerate" cases, when the paths
$(p_{k},p_{1},p_{2},p_{3},p_{4})$ and
$(p_{i-1},p_{i},p_{i+1},p_{i+2},p_{i+3})$ are either not disjoint or their
complement consists only of one path. That is, up to symmetry we have to
consider the cases when $i\in\\{2,4,5,6\\}$. We obtain the bound
$\tilde{O}(n^{\lfloor 2(k+3)/5\rfloor+1/3})$

  * •

for $i=2$ by choosing the $(k-3)$-path $(p_{3},p_{4},\dots,p_{k-1})$ first,

  * •

for $i=4$ by choosing the $4$-path $(p_{2},p_{3},p_{4},p_{5})$ and
$(k-8)$-path $(p_{8},\dots,p_{k-1})$ first,

  * •

for $i=5$ by choosing the $(k-3)$-path $(p_{6},p_{7},\dots,p_{k},p_{1},p_{2})$
first.

  * •

and for $i=6$ by choosing the $6$-path $(p_{k},p_{1},\dots,p_{5})$ and
$(k-10)$-path $(p_{8},p_{9}\dots,p_{k-3})$ first.

$\bm{k=4\mod 5:}$ Assume that there are two antipodal pairs $(p_{1},p_{3})$
and $(p_{i},p_{i+2})$ such that $i\notin\\{1,3\\}$. We will assume that the
$5$-paths $(p_{k},p_{1},p_{2},p_{3},p_{4})$ and
$(p_{i-1},p_{i},p_{i+1},p_{i+2},p_{i+3})$ are disjoint, and their complement
consists of two non-empty paths $(p_{5},\dots,p_{i-2})$ and
$(p_{i+4},\dots,p_{k-1})$ of lengths $k_{1}$ and $k_{2}$ respectively. The
"degenerate" cases can be done similarly as in the $k=2\mod 5$ case, thus we
omit the details. Since $k_{1}+k_{2}=4\mod 5$, we may assume without loss of
generality that $(k_{1},k_{2})=(0,4),(1,3)$ or $(2,2)\mod 5$. The analysis for
the $(0,4)$ and $(1,3)$ cases are similar to the argument in the $k=2$ case.

  * •

If $(k_{1},k_{2})=(1,3)$ then after choosing $(p_{2},p_{3},\dots,p_{i-2})$ and
$(p_{i+1},p_{i+2},\dots,p_{k-1})$ arbitrarily, the antipodal pair $p_{1}$ of
$p_{3}$ and $p_{i}$ of $p_{i+2}$ is uniquely determined. Further, there are at
most $2$ choices for $p_{k}$ and $p_{i-1}$. Thus, the total number of cycles
of this type, using Theorem 1, is bounded by

$P^{S}_{k_{1}+3}(n)\cdot P^{S}_{k_{2}+3}(n)=\tilde{O}(n^{\lfloor
2(k_{1}+6)/5\rfloor+\lfloor 2(k_{2}+6)/5\rfloor})\\\
=\tilde{O}(n^{(2k_{1}+9)/5+(2k_{2}+8)/5})=\tilde{O}(n^{(2k-3)/5})=\tilde{O}(n^{\lfloor
2k/5\rfloor}).$

  * •

If $(k_{1},k_{2})=(0,4)$ then after choosing the paths
$(p_{2},p_{3},\dots,p_{i+1})$ and $(p_{i+4},\dots,p_{k-1})$ the antipodal pair
$p_{1}$ of $p_{3}$ and $p_{i+2}$ of $p_{i}$ is uniquely determined. Further,
there are at most $2$ choices for $p_{k}$ and $p_{i+3}$. Thus, the total
number of cycles of this type, using Theorem 1, is bounded by

$P^{S}_{k_{1}+6}(n)\cdot P^{S}_{k_{2}}(n)=\tilde{O}(n^{\lfloor
2(k_{1}+9)/5\rfloor+\lfloor
2(k_{2}+3)/5\rfloor})=n^{(2k_{1}+15)/5+(2k_{2}+2)/5}=\tilde{O}(n^{\lfloor
2k/5\rfloor}).$

  * •

If $(k_{1},k_{2})=(2,2)$ an argument similar to the one used for the
$(k_{1},k_{2})=(1,3)$ and $(0,4)$ cases is not sufficient, and we need to
consider a few other cases depending whether there are other antipodal pairs.
(The difficulty of this case comes from the following fact. When we only break
up the cycle into two paths, there lengths are in a way that the product of
the number of paths of the corresponding length is too large). Assume first
that there are no other antipodal pairs. After choosing
$(p_{2},p_{3},\dots,p_{i+1})$ and $(p_{i+4},\dots,p_{k-1})$, the antipodal
pair $p_{1}$ of $p_{3}$ and $p_{i+2}$ of $p_{i}$ is uniquely determined.
Further, there are at most $2$ choices for $p_{k}$ and $p_{i+1}$. We bound the
number of paths $(p_{2},p_{3},\dots,p_{i+1})$ and $(p_{i+4},\dots,p_{k-1})$ by
Proposition 1, and obtain the bound

$4P_{k_{1}+2}P_{k_{2}}=\tilde{O}(n^{\lfloor 2k/5\rfloor+\frac{1}{3}}).$

Indeed, for $k\geq 19$ it follows from

$4P_{k_{1}+2}P_{k_{2}}=\tilde{O}(n^{(k_{1}+6)/3+1}n^{k_{2}/3+1})=\tilde{O}(n^{(k-3)/3+2})\leq\tilde{O}(n^{\lfloor
2k/5\rfloor}),$

and for $k\leq 15$ it follows by using the exact bounds from Proposition 1.

Thus, we may assume that without loss of generality there is a third antipodal
pair $(p_{j},p_{j+1})$ with $2\leq j\leq i-1$. Again, we assume that the
$5$-paths $(p_{k},p_{1},p_{2},p_{3},p_{4})$,
$(p_{j-1},p_{j},p_{j+1},p_{j+2},p_{j+3})$ and
$(p_{i-1},p_{i},p_{i+1},p_{i+2},p_{i+3})$ are pairwise disjoint, and their
complement consists of non-empty paths $(p_{5},\dots,p_{j-2})$,
$(p_{j+4},\dots,p_{i-2})$ and $(p_{i+4},\dots,p_{k-1})$, of lengths
$\ell_{1},\ell_{2}$ and $k_{2}$ respectively. Without loss of generality we
may assume that $(\ell_{1},\ell_{2},k_{2})=(0,2,2),(1,1,2)$ or $(3,4,2)$. In
any of these cases, using the antipodal pairs $(p_{1},p_{3})$ and
$(p_{j},p_{j+1})$, we can proceed as in the $(k_{1},k_{2})=(0,4)$ or $(1,3)$
cases.

Finally, we note that the degenerate cases, when two antipodal pairs are too
close to each other, can be done similarly as in the $k=2\mod 5$ case.

∎

The next proposition summarizes the bounds for short cycles.

######  Proposition 2.

We have

$\displaystyle C_{3}(n)$ $\displaystyle=\Omega(n)$ and $\displaystyle
C_{3}(n)$ $\displaystyle=O(n^{4/3}),$ $\displaystyle C_{6}(n)$
$\displaystyle=\Omega(n^{2}\log\log n)$ and $\displaystyle C_{6}(n)$
$\displaystyle=\tilde{O}(n^{20/9}),$ $\displaystyle C_{7}(n)$
$\displaystyle=\Omega(n^{7/3})$ and $\displaystyle C_{7}(n)$
$\displaystyle=\tilde{O}(n^{8/3}),$ $\displaystyle C_{9}(n)$
$\displaystyle=\Omega(n^{3})$ and $\displaystyle C_{9}(n)$
$\displaystyle=\tilde{O}(n^{10/3}).$

It would be interesting to find sharp bounds for short cycles too. The lower
bound $C_{6}(n)=\Omega(n^{2}\log\log n)$, via stereographic projection, is an
immediate corollary of a construction by Klávik, Král and Mach [9] giving
$\Omega(n^{2}\log n\log n)$ $6$-cycles in an incidence graph of $n$ points and
$n$ lines. This disproved a conjecture of de Caen and Székely [4] that the
maximum number of $6$-cycles is $O(n^{2})$ in the point-line incidence graph.
It is not hard to see that the number of those $6$-cycles that contain an
antipodal pair in the unit distance graph on the sphere is $O(n^{2})$. Thus,
up to the order of magnitude, the problem of bounding the number of $6$-cycles
in point line incidence graphs and in unit distance graphs on the sphere, are
equivalent.

There is a similar explanation why the $C_{7}$ and $C_{9}$ cases are more
difficult than the longer cycles: It is not hard to prove upper bounds
matching the lower bounds for the number of those cycles, in which there are
is least one antipodal pair. Thus, again, for $C_{7}$ and $C_{9}$ the most
difficult types of cycles to bound are those in which there are no antipodal
pairs. For longer cycles, there is no similar issue. This is because no
antipodal pair means we can use the bound from Proposition 1 for long sub-
paths, and even with a wasteful estimate we will obtain sufficiently good
bounds.

###### Proof of Proposition 2.

We start with the lower bounds. For $k=3$ finding linear lower bounds is
trivial, and for $k=6$ it follows from [9] combined with stereographic
projection. For $k=7,9$ we can use the same constructions as for the $k\geq
10$ case. We now turn to the lower bound.

$\bm{k=3:}$ The upper bound follows from the Szemerédi-Trotter bound, since
every edge can be extended in at most two different ways to a triangle.

For the other cases we use a nested dyadic decomposition argument, similar to
the one used by [7]. The proof for the $k=6,7,9$ cases are all similar, but
the $k=6$ cases is somewhat harder. Thus we only spell out the proof for the
$k=6$ case and omit the details for $k=7,9$.

Recall that by (3) that for any $0\leq\alpha\leq 1$ the maximum number of
$n^{\alpha}$-rich points is $O(\max\\{n^{3-2\alpha},n^{1-\alpha}\\})$. We call
a point _usual_ if it is $n^{\alpha}$-rich for some $0\leq\alpha\leq 1/2$ and
_very rich_ if it is $n^{\alpha}$-rich for some $\frac{1}{2}\leq\alpha\leq 1$.

$\bm{k=6:}$ Bounding the number of those $6$-cycles in which there are
antipodal pairs, can be done similarly as for the $k\geq 10$ cases. Thus, we
may assume that there are no antipodal pairs. First, we bound the number of
those $6$-cycles in which there are no four consecutive usual points. In any
such cycle, we can find two disjoint edges, separated by another vertex in
each direction, that both have a very rich endpoint. Assume that they are
$n^{\alpha_{1}}$ and $n^{\alpha_{2}}$-rich respectively. Since there are no
antipodal pairs in the cycle, after choosing the two disjoint edges, there are
at most $4$ different ways to extend it to a $6$-cycle. Thus, by using dyadic
decomposition and (3), we obtain the bound

$\sum_{(\alpha_{1},\alpha_{2}\in\Lambda)}O(n^{1-\alpha_{1}}n^{\alpha_{1}}n^{1-\alpha_{2}}n^{\alpha_{2}})=\tilde{O}(n)^{2},$

where $\Lambda=\left\\{(i,j)\ \colon
i,j\in\\{\lfloor\frac{\log_{2}n}{2}\rfloor,\lfloor\frac{\log_{2}n}{2}\rfloor+1,\dots,\lfloor\log_{2}n\rfloor\\}\right\\}$.

Next, we bound the number of those $6$-cycles
$(p_{1},p_{2},p_{3},p_{4},p_{5},p_{6})$, in which there are four consecutive
usual points, say $(p_{2},p_{3},p_{4},p_{5})$.

For some $0\leq\alpha_{2},\alpha_{3},\alpha_{4},\alpha_{5}\leq\frac{1}{2}$ let
$Q_{2}(\alpha_{2})$ be the set of those points that are at least
$n^{\alpha_{2}}$-rich and at most $2n^{\alpha_{2}}$-rich, and let
$Q_{5}(\alpha_{5})$ be the set of those points that are at least
$n^{\alpha_{5}}$-rich and at most $2n^{\alpha_{5}}$-rich. Further, let
$Q_{3}(\alpha_{2},\alpha_{3})$ be the set of those points that are at least
$n^{\alpha_{3}}$-rich and at most $2n^{\alpha_{3}}$ with respect to
$Q_{2}(\alpha_{3})$, and let $Q_{4}(\alpha_{4})$ be the set of those points
that are at least $n^{\alpha_{4}}$-rich and at most $2n^{\alpha_{4}}$-rich
with respect to $Q_{5}(\alpha_{5})$. Finally, let
$Q_{1}(\alpha_{2},\alpha_{3})$ be the union of the second neighborhoods of
points in $Q_{3}(\alpha_{3})$, and $Q_{6}(\alpha_{4},\alpha_{5})$ be the union
of the second neighborhoods of the points in $Q_{4}(\alpha_{4})$.

Using dyadic decomposition, it is sufficient to show that for any fixed
$0\leq\alpha_{2},\alpha_{3},\alpha_{4},\alpha_{5}\leq\frac{1}{2}$ the number
of those $6$-cycles $(p_{1},\dots,p_{6})$ such that $p_{i}\in
Q_{i}(\alpha_{i})$ for $i\in\\{2,3,4,5\\}$ is $O(n^{20/9})$. Note that for any
such cycle $p_{1}$ must be in $Q_{1}(\alpha_{2},\alpha_{3})$ and $p_{6}$ must
be in $Q_{6}(\alpha_{4},\alpha_{5})$. In the rest of the proof we will use the
notation $Q_{i}=Q_{i}(\alpha_{i})$ for $i\in\\{2,3,4,5\\}$, and
$Q_{6}=Q_{6}(\alpha_{4},\alpha_{5})$, $Q_{1}=Q_{1}(\alpha_{2},\alpha_{3})$.

Let $0\leq x_{1},\dots,x_{6}\leq 1$ such that $|Q_{i}|=n^{x_{i}}$. First, we
bound the number of $6$-cycles in the case when at least two $Q_{i}$ is of
size $O(n^{1/2})$. If there are two cyclically adjacent indices, say $1$ and
$2$, such that $Q_{1}$ and $Q_{2}$ are of size $O(n^{1/2})$, then we obtain
the bound

$4u(n^{x_{1}},n^{x_{6}})u(n^{x_{3}},n^{x_{4}})=O(n^{2/3}n^{4/3})=O(n^{2}),$

by picking $(p_{1},p_{6})$, $(p_{3},p_{4})$ and extending
$(p_{2},p_{3},p_{4},p_{6})$ to a $6$ cycle in at most $4$ different ways. If
there are two such non-adjacent $i$ and $j$ such that $Q_{i}$ and $Q_{j}$ are
of size $O(n^{1/2})$, then we will find two disjoint pairs of indices,
separated by $1$ index in each direction, say $(1,6)$ and $(3,4)$ such that
$u(n^{x_{1}},n^{x_{6}})=O(n)$ and $u(n^{x_{3}},n^{x_{4}})=O(n)$, and obtain
the bound $O(n^{2})$ again.

Next, we bound the number of $6$-cycles in the case when at least one $Q_{i}$,
say $Q_{1}$ is of size $O(n^{2/9})$. In this case, by picking
$(p_{3},p_{4},p_{5})$ and $p_{1}$ first, we can extend it to a $6$-cycle in at
most $4$ different ways, and obtain the bound $O(n^{2})n^{2/9}=O(n^{20/9})$.

From now on, we assume that there are at most one $Q_{i}$ with
$|Q_{i}|=O(n^{\frac{1}{2}})$, and every $Q_{i}$ is of size $\Omega(n^{2/9})$.
We count the $6$-cycles by picking $(p_{3},p_{4})$ first. Then $p_{1}$ must be
in the second neighborhood of $p_{3}$, and $p_{6}$ must be in the second
neighborhood of $p_{4}$. Further, once $(p_{1},p_{3},p_{4},p_{6})$ is picked,
there are at most $4$ different ways to finish the cycles. With this, we
obtain the bound

$u(n^{x_{3}},n^{x_{4}})u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}}).$
(9)

We also have

$n^{\alpha_{2}}\leq\frac{u(n^{x_{2}},n)}{n^{x_{2}}},\textrm{ }\textrm{
}n^{\alpha_{3}}\leq\frac{u(n^{x_{2}},n^{x_{3}})}{n^{x_{3}}},\textrm{ }\textrm{
}n^{\alpha_{4}}\leq\frac{u(n^{x_{4}},n^{x_{5}})}{n^{x_{4}}},\textrm{ }\textrm{
}n^{\alpha_{5}}\leq\frac{u(n^{x_{5}},n)}{n^{x_{5}}}.$ (10)

By (2) we have $u(m,n)=O(m^{2/3}n^{2/3}+n+m)=O(\max\\{m^{2/3}n^{2/3},n,m\\})$.
We will distinguish a few cases based on which term the maximum is taken in
(9) and in the inequalities in (10).

Case 1:  Both in (9) and (10) the maximum is taken on the first term
everywhere. Then we obtain the bound

$u(n^{x_{3}},n^{x_{4}})u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O\left(n^{\frac{2}{3}(x_{3}+x_{4})}n^{\frac{2}{3}(\frac{4}{3}+\frac{1}{3}(x_{2}+x_{5})-\frac{1}{3}(x_{3}+x_{4}))}\right)=O(n^{20/9}).$

Case 2:  $u(n^{x_{3}},n^{x_{4}})=O(\max\\{n^{x_{3}},n^{x_{4}}\\})$. Without
loss of generality we may assume that $u(n^{x_{3}},n^{x_{4}})=O(n^{x_{4}})$.
Note that this implies $n^{x_{3}}=O(n^{1/2})$. Then we may assume that
$u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O(n^{\frac{2}{3}(\alpha_{2}+\alpha_{3}+\alpha_{4}+\alpha_{5})})$,
otherwise we would obtain the bound $O(n^{2})$. Similarly, we may assume that
the maximum in the bound for
$u(n^{x_{2}},n),u(n^{x_{4},x_{5}}),u(n^{x_{5}},n)$ the maximum is taken on the
first term, otherwise we would obtain two parts $Q_{i}$ of size $O(n^{1/2})$.

  * •

If $u(n^{x_{2}},n^{x_{3}})=O(n^{x_{3}})$, then $n^{x_{2}}=O(n^{1/2})$, giving
a $Q_{i}$ of size $O(n^{1/2})$.

  * •

If $u(n^{x_{2}},n^{x_{3}})=O(n^{x_{2}})$, then we obtain the bound

$u(n^{x_{3}},n^{x_{4}})u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O\left(n^{x_{4}}n^{\frac{2}{3}(\frac{4}{3}+\frac{2}{3}x_{2}-x_{3}-\frac{1}{3}x_{4}+\frac{1}{3}x_{5})}\right)=O(n^{20/9}),$

using the assumption that $n^{x_{3}}=\Omega(n^{2/9})$.

  * •

Finally, if $u(n^{x_{2}},n^{x_{3}})=u(n^{\frac{2}{3}(x_{2}+x_{3})})$, then we
obtain

$u(n^{x_{3}},n^{x_{4}})u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O\left(n^{x_{4}}n^{\frac{2}{3}(\frac{4}{3}+\frac{1}{3}(x_{2}+x_{5})-\frac{1}{3}(x_{3}+x_{4}))}\right)=O(n^{20/9}).$

Case 3:
$u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O(\max\\{n^{\alpha_{2}+\alpha_{3}},n^{\alpha_{4}+\alpha_{5}}\\})$.
Without loss of generality we may assume that
$u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O(\max\\{n^{\alpha_{2}+\alpha_{3}}\\})$.
This implies $n^{\alpha_{4}+\alpha_{5}}=O(n^{1/2})$. Similarly as in Case 2,
we may assume that in the bound for $u(n^{x_{2}},n)$,
$u(n^{x_{2}},n^{x_{3}})$, $u(n^{x_{3}},n^{x_{4}})$ the maximum is taken in the
first term. Then regardless on which term the maximum is taken in
$u(n^{x_{5}},n)$, we obtain the bound

$u(n^{x_{3}},n^{x_{4}})u(4n^{\alpha_{2}+\alpha_{3}},4n^{\alpha_{4}+\alpha_{5}})=O\left(n^{\frac{2}{3}(x_{3}+x_{4})}n^{\frac{2}{3}+\frac{1}{3}x_{2}-\frac{1}{3}x_{3}}\right)=O(n^{20/9}).$

$\bm{k=7,9:}$ The proof is by using dyadic decomposition in a similar way as
in the $k=6$ case. The reason why there is $3$ in the denominator of the
exponent instead of $9$ is that we do not consider
$Q_{1}(\alpha_{2},\alpha_{3})$ type of sets, only $Q_{i}(\alpha_{i})$.

∎

##  4 3-Regular graphs in $\mathbb{R}^{3}$

The main goal of this section is to prove Theorem 3. As it does not affect the
answer up to the order of magnitude, we switch to the multipartite version of
the problem. For a fixed $3$-regular graph $G$ on $k$ vertices, and for $k$
sets $P_{1},\dots,P_{k}\subseteq\mathbb{R}^{3}$ we denote by
$F(P_{1},\dots,P_{k})$ the maximum number of $k$-tuples $(p_{1},\dots,p_{k})$
such that the unit distance graph determined by them is isometric to $G$, and
$p_{i}\in P_{i}$ for every $i\in[k]$. Further, we use the notation

$f(n_{1},\dots,n_{k})=\max|F(P_{1},\dots,P_{k})|,$

and $f(n)=f(n,\dots,n)$.

To prove Theorem 3, we follow a divide and conquer strategy of Agarwal and
Sharir [1]. The strategy uses _cuttings_ , a partitioning technique, which was
a precursor to the more recent polynomial partitioning method. We say that a
sphere $S$ _crosses_ a subset $\tau\subseteq\mathbb{R}^{n}$ if
$S\cap\tau\neq\emptyset$, but $\tau\not\subset S$. To follow usual
terminology, we will call the subsets in the partition _cells_. (Note that
usually a _cell_ in this context, means a more specific subset described by a
bounded number of polynomials. However, since we only use the cutting results
as a black-box in a very specific case, for simplicity, we do not define cells
here more properly.)

The following cutting lemma was proved in [1]).

######  Lemma 1 (Cutting Lemma from [1]).

Given a set of points $P$ and $\ell$ sets $Q_{0},\dots,Q_{\ell}$ of spheres in
$\mathbb{R}^{d}$, for any $1\leq r\leq n$ we can partition the
$\mathbb{R}^{d}$ into cells such that the following three conditions hold.

  1. 1.

The number of cells is $\tilde{O}(r^{d})$.

  2. 2.

The number of points in each cell is $O\left(\frac{|P|}{r^{d}}\right)$.

  3. 3.

For every $i\in[\ell]$ each cell is crossed by
$O\left(\frac{|Q_{i}|}{r}\right)$ many spheres from $Q_{i}$.

Further, if $P$ is contained in a $(d-1)$-sphere $\mathbb{S}^{d-1}$, then we
can partition $\mathbb{S}^{d-1}$ into cells such that the following three
conditions holds.

  1. 1.

The number of cells is $\tilde{O}(r^{d-1})$.

  2. 2.

The number of points in each cell is $O\left(\frac{|P|}{r^{d-1}}\right)$.

  3. 3.

For every $i\in[\ell]$ each cell is crossed by
$O\left(\frac{|Q_{i}|}{r}\right)$ many spheres from $Q_{i}$.

To illustrate the method, we first prove the following simpler proposition,
which gives the best upper bound we have been able to prove on the number of
$4$-cycles in $\mathbb{R}^{3}$.

######  Proposition 3.

The maximum number of unit $4$-cycles determined by a set of $n$ points in
$\mathbb{R}^{3}$ is $\tilde{O}(n^{12/5})$.

It would be interesting to find better estimates. The best lower bounds we
found is $\Omega(n^{2})$, given by the same construction used on the sphere.

######  Problem 1.

Find the maximum possible number of $4$-cycles determined by a set of $n$
points in $\mathbb{R}^{3}$.

###### Proof of Proposition 3.

We again switch to the multipartite version of the problem, and for sets
$P_{1},P_{2},P_{3},P_{4}$ we denote by $C_{4}(P_{1},P_{2},P_{3},P_{4})$ the
maximum number of unit $4$-cycles $(p_{1},p_{2},p_{3},p_{4})$ with $p_{i}\in
P_{i}$. Further, let
$c_{4}(n_{1},n_{2},n_{3},n_{4})=\max|C_{4}(P_{1},P_{2},P_{3},P_{4})|$ where
the maximum is taken over all $P_{i}$ with $|P_{i}|\leq n_{i}$, and let
$c_{4}(n)=c_{4}(n,n,n,n)$. For a point $p$ we also denote by $S(p)$ the unit
sphere centered at $p$. We will bound $C_{4}(P_{1},P_{2},P_{3},P_{4})$ with
$|P_{i}|\leq n$ for all $i\in[4]$.

For some parameter $r$ we partition $\mathbb{R}^{3}$ into $\tilde{O}(r^{3})$
cells as in Lemma 1 with $P_{1}$ as the set of points, and $\left\\{S(p_{2})\
\colon p_{2}\in P_{2}\right\\}$ and $\left\\{S(p_{4})\ \colon p_{4}\in
P_{4}\right\\}$ as the sets of spheres. For a cell $\tau$ let
$P_{1}^{\tau}=P_{1}\cap\tau$, further, for $i=2,4$ let
$Q_{i}^{\tau}\subseteq\left\\{S(p_{i})\ \colon p_{i}\in P_{i}\right\\}$ be the
set of those spheres that cross $\tau$, and
$R_{i}^{\tau}\subseteq\left\\{S(p_{i})\ \colon p_{i}\in P_{i}\right\\}$ be the
set of those spheres that contain $\tau$. Summing over all cells $\tau$ we
obtain

$C_{4}(P_{1},P_{2},P_{3},P_{4})\leq\sum_{\tau}\Big{(}C_{4}(P_{1}^{\tau},Q_{2}^{\tau},P_{3},Q_{4}^{\tau})+C_{4}(P_{1}^{\tau},R_{2}^{\tau},P_{3},P_{4})+C_{4}(P_{1}^{\tau},P_{2},P_{3},R_{4}^{\tau})\Big{)}.$

######  Proposition 4.

$C_{4}(P_{1}^{\tau},R_{2}^{\tau},P_{3},P_{4})=\tilde{O}(n^{2})$ and
$C_{4}(P_{1}^{\tau},P_{2},P_{3},R_{4}^{\tau})=\tilde{O}(n^{2})$.

###### Proof.

We will only prove
$C_{4}(P_{1}^{\tau},R_{2}^{\tau},P_{3},P_{4})=\tilde{O}(n^{2})$, which is
sufficient by symmetry. This means we have to bound the number of $4$-cycles
under the condition that all points in $P_{1}^{\tau}$ are contained in the
intersection of unit spheres centered around the points of $R_{2}^{\tau}$.
Since in $\mathbb{R}^{3}$ for any $3$ points there are at most $2$ other
points unit distance apart from each, we either have $|P_{1}^{\tau}|\leq 2$ or
$|R_{2}^{\tau}|\leq 2$. Thus, $C_{4}(P_{1}^{\tau},R_{2}^{\tau},P_{3},P_{4})$
is bounded by four times the maximum number of $3$-paths in $\mathbb{R}^{3}$,
which is $\tilde{O}(n^{2})$ by [7]. ∎

By the properties of the cutting we also have
$C_{4}(P_{1}^{\tau},Q_{2}^{\tau},P_{3},Q_{4}^{\tau})\leq
c_{4}(\frac{n}{r^{3}},\frac{n}{r},n,\frac{n}{r})$. Thus, we obtain

$C_{4}(P_{1},P_{2},P_{3},P_{4})\leq\sum_{\tau}\Big{(}c_{4}\left(\frac{n}{r^{3}},\frac{n}{r},n,\frac{n}{r}\right)+\tilde{O}(n^{2})\Big{)}.$

Repeating a similar analysis three more times with cyclic shifts (in the next
round $P_{2}$ plays the role of $P_{1}$, $P_{3}$ plays the role of $P_{2}$,
$P_{4}$ play the role of $P_{3}$, and $P_{1}$ plays the role of $P_{4}$, and
so on), and using that the number of cells in the cutting is
$\tilde{O}(r^{3})$, we obtain the recurrence

$c_{4}(n)\leq\tilde{O}(r^{12})c_{4}\left(\frac{n}{r^{5}}\right).$

With an appropriate choice of $r$ this recursion yields
$c_{4}(n)\leq\tilde{O}(n^{12/5})$. ∎

Notice that in the proof of Proposition 3 in each round when the Cutting Lemma
is applied, for every cell we have to consider two different situations and
split into two subproblems. For those spheres that cross the cell, we directly
plug in the bound on the number of crossings from the Lemma, and obtain the
main term of the recursion. Those spheres that contain the cell are accounted
for in Proposition 4. Proving Proposition 4 was simple, and we could deal with
it by ‘hand‘. However, when we work with a large $3$-regular graph, knowing
information only about one local containment situation does not make the
problem sufficiently simpler.

Therefore, we will follow further ideas of Agarwal and Sharir that they
developed for bounding the number of $k$-simplices in higher dimension. We
will sketch these ideas for completeness with incorporating the sufficient
changes in the method, adjusting it to our problem. Notice that for $d=0,1$
Lemma 1 is trivial. Yet, we will utilize these trivial cases, as they will
give a convenient uniform way to handle the containment situations mentioned
in the previous paragraph.

###### Proof of Theorem 3.

We will use the Cutting Lemma in $k$-rounds to derive a recurrence for $f(n)$,
following Section $5$ of [1], with making some suitable changes. We will
assume that the vertex set of $G$ is $[k]$.

Let $P_{1},\dots,P_{k}\subseteq\mathbb{R}^{3}$ be point sets with $|P_{i}|\leq
n_{i}$ for every $i\in[k]$. We denote by $S(p)$ the unit sphere centered at
$p$. Without loss of generality, we may assume that $2,3,4$ are the neighbors
of $1$.

In the first round, we use the Cutting Lemma with some parameter $r$, with
$P_{1}$ as the set of points, and $Q_{i}=\left\\{S(p)\ \colon p\in
P_{i}\right\\}$ as the sets of spheres for $i=2,3,4$. For a cell $\tau$ let
$P_{1}^{\tau}=P_{1}\cap\tau$. Further, for $i=2,3,4$ let
$Q_{i}^{\tau}\subseteq Q_{i}$ be the set of those spheres that cross $\tau$,
and $R_{i}^{\tau}$ be the set of those spheres that contain $\tau$. Summing
over all cells $\tau$ we obtain

$F(P_{1},\dots,P_{k})=\sum_{\tau}\Big{(}F(P_{1}^{\tau},Q_{2}^{\tau},Q_{3}^{\tau},Q_{4}^{\tau},P_{5},\dots,P_{k})+F(P_{1}^{\tau},R_{2}^{\tau},P_{3},\dots,P_{k})\\\
+F(P_{1}^{\tau},P_{2},R_{3}^{\tau},P_{4},\dots,P_{k})+F(P_{1}^{\tau},P_{2},P_{3},R_{4}^{\tau},P_{5}\dots,P_{k})\Big{)}.$
(11)

We will bound the first term in each summand by plugging in the information
from the Cutting Lemma. In the proof of Proposition 3 we bounded the terms
similar to the other three terms in Proposition 4, by observing that they
correspond to bounding cycles in a geometrically constrained situation. While
it is still true here that for example either $|P_{1}^{\tau}|\leq 2$ or
$|R_{2}^{\tau}|\leq 2$, for large $k$ it does not constrain the geometry
sufficiently to bound $F(P_{1},R_{2}^{\tau},P_{3},\dots,P_{k})$ easily.

Thus, we will introduce new sub-problems, where we will keep track of
containments that occur between certain parts by a weighted auxiliary graph
$H$. Notice that we can say more than just $|P_{1}^{\tau}|\leq 2$ or
$|R_{2}^{\tau}|\leq 2$. It is also true that if $|P_{1}^{\tau}|\geq 3$, then
$P_{1}$ is contained in a $2$-sphere, and a similar observation holds for
$R_{2}$.

For a subgraph $H$ of $G$ we say that a $k$-tuple of points
$(P_{1},\dots,P_{k})$ is of _type $H$_, if for every edge $(i,j)$ of $H$ the
distance between every point of $P_{i}$ and $P_{j}$ is the one. We denote by

$F^{H}(n_{1},\dots,n_{k})=\max F(P_{1},\dots,P_{k}),$

where the maximum is taken over all $k$-tuples $(P_{1},\dots,P_{k})$ of type
$H$ with $|P_{i}|\leq n_{i}$.

With this notation, (11) implies

$F(n_{1},\dots,n_{k})=\\\\[3.0pt]
\tilde{O}(r^{3})\left(F\left(\frac{n_{1}}{r^{3}},\frac{n_{2}}{r},\frac{n_{3}}{r},\frac{n_{4}}{r},n_{5},\dots,n_{k}\right)+F^{H_{2}}(n_{1},\dots,n_{k})+F^{H_{3}}(n_{1},\dots,n_{k})+F^{H_{4}}(n_{1},\dots,n_{k})\right),$

where $H_{i}$ is the graph with a single edge $(1,i)$.

Refining the notion further, for a vector
$\boldsymbol{\lambda}=(\lambda_{1},\dots,\lambda_{k})\in\\{0,1,2,3\\}^{k}$ we
say that a $k$-tuple $(P_{1},\dots,P_{k})$ is of type
$(H,\boldsymbol{\lambda})$,

  * •

if $(P_{1},\dots,P_{k})$ is of type $H$, and

  * •

if $\lambda_{i}\leq 2$, then $P_{i}$ is contained in a $\lambda_{i}$-sphere
but is not contained in a $\lambda_{i}-1$-sphere, further

  * •

if $\lambda_{i}=3$, then $P_{i}$ is not contained in a sphere.

We define $F^{H,\boldsymbol{\lambda}}(n_{1},\dots,n_{k})$ analogously to
$F^{H}(n_{1},\dots,n_{k})$. Further, we say that a pair
$(H,\boldsymbol{\lambda})$ is _realizable_ , if there exists a $k$-tuple
$(P_{1},\dots,P_{k})$ of type $(H,\boldsymbol{\lambda})$.

For any subgraph $H$ of $G$, and any vector $\boldsymbol{\lambda}$ by applying
the cutting lemma with the $i$-th part playing the role of the points, and
with some parameter $r_{i}$, we obtain

$F^{H,\boldsymbol{\lambda}}(n_{1},\dots,n_{k})=\\\\[3.0pt]
\tilde{O}(r^{3})\Big{(}F^{H,\boldsymbol{\lambda}}(m_{1},\dots,m_{k})+F^{H_{1},\boldsymbol{\lambda}_{1}}(n_{1},\dots,n_{k})+F^{H_{2},\boldsymbol{\lambda}_{2}}(n_{1},\dots,n_{k})+F^{H_{3},\boldsymbol{\lambda}_{3}}(n_{1},\dots,n_{k})\Big{)},$

where

  * •

$m_{i}=\frac{n^{i}}{r^{\lambda_{i}}}$,

  * •

$m_{j}=\frac{n_{j}}{r}$ if $(i,j)\in G\setminus H$,

  * •

$m_{j}=n_{j}$ otherwise,

  * •

each $H_{i}$ is $H$ extended by an edge connecting $i$ with one of its
neighbours in $G$, and

  * •

$\boldsymbol{\lambda}_{i}$ is $\boldsymbol{\lambda}$ modified suitably along
the new edge.

By applying the cutting lemma similarly $k$ times such that in the $i$-th
round we have the points of the $i$-th part as the set of points, the spheres
centred in the neighbours (in $G$) of $i$ as spheres, and $r_{i}=r^{x_{i}}$ as
parameter, for any subgraph $H$ we obtain

$F^{H,\boldsymbol{\lambda}}(n_{1},\dots,n_{k})=\tilde{O}\Big{(}\prod_{i}{r^{x_{i}}}\Big{)}\Big{(}F^{H,\boldsymbol{\lambda}}(m_{1},\dots,m_{1})+\sum_{H^{\prime}}F^{H^{\prime}}(n_{1},\dots,n_{k})\Big{)}$

where the sum is taken over all subgraphs $H^{\prime}$ of $G$ with strictly
more edges than $H$, and where

$m_{i}=\frac{n_{i}}{r^{x_{i}\lambda_{i}+\sum_{(i,j)\in G\setminus H}x_{j}}}.$

Let $\xi(H,\boldsymbol{\lambda})$ be the solution of the following linear
optimization problem:

$\displaystyle\min\sum{x_{i}\lambda_{i}}\ \ \ \text{subject to: }$ (12)
$\displaystyle x_{i}\geq 0\ \ \ \ \ \ \ \ \ \ \ \ \ \,\ \ \ \textrm{ for
}1\leq i\leq k$ (13) $\displaystyle\lambda_{i}x_{i}+\sum_{(i,j)\in G\setminus
H}x_{j}\geq 1\ \ \textrm{ for }1\leq i\leq k$ (14)

With this, we obtain

$F^{H,\boldsymbol{\lambda}}(n)=\tilde{O}\Big{(}r^{\xi(H,\boldsymbol{\lambda})}\Big{)}\Big{(}F^{H,\boldsymbol{\lambda}}\Big{(}\frac{n}{r}\Big{)}+\sum_{H^{\prime}}F^{H^{\prime}}(n)\Big{)}.$
(15)

Let $\xi=\max_{H,\boldsymbol{\lambda}}{\xi(H,\boldsymbol{\lambda})}$, where
the maximum is taken over all realizable $(H,\boldsymbol{\lambda})$. By
induction on the number of edges in $G\setminus H$, and with an appropriate
choice of $r$, using (15) one can show that we have
$F(n)=\tilde{O}({n^{\xi}})$. Note that the starting case of the induction is
$G=H$, for which one can show directly that $F^{G}(n)=O(n^{\frac{k}{2}})$.
Indeed, if $(P_{1},\dots,P_{k})$ is of type $G$, then $|P_{i}|\leq 2$ for at
least $\frac{k}{2}$ indices $i$.

Thus, it is sufficient to show that the solution of the linear optimization
problem for any realizable pair $(H,\boldsymbol{\lambda})$ is at most
$\frac{k}{2}$.

We make some geometric observations about realizable pairs
$(H,\boldsymbol{\lambda})$:

  1. (i)

If $\lambda_{i}=3$, then $i$ is an isolated vertex of $H$.

  2. (ii)

If $\lambda_{i}=2$, then $i$ has exactly one neighbour $j$ in $H$, for which
we must have $\lambda_{j}=0$. (As $P_{j}$ must be in the center of a
$2$-sphere)

  3. (iii)

If $\lambda_{i}=1$, then for any neighbour $j$ of $i$ in $H$ we must have
$\lambda_{j}=0$ (As there are at most two points at a given distance from all
points of a circle.)

  4. (iv)

If $i$ is an isolated vertex in $H$, then we may assume that for every
neighbour $j$ of $i$ in $G$ we have $\lambda_{j}\geq 1$.

  5. (v)

We may assume that if $\lambda_{i}=0$, then $\deg_{H}(i)=3$. (Indeed, if
$\lambda_{i}=0$, and $(P_{1},\dots,P_{n})$ is of type
$(H,\boldsymbol{\lambda})$, then $|P_{i}|\leq 2$. Since we only want to bound
$F^{H,\boldsymbol{\lambda}}(n)$ up to the order of magnitude, we may assume
that $|P_{i}|=1$. Then if $(i,j)\in G$, we may discard those $p_{j}\in P_{j}$
that are not at distance one from the single point of $P_{i}$, as they cannot
be part of any copy of $G$.)

.

Let us define $\mathbf{x}=(x_{1},\dots,x_{k})$ as

$x_{i}=\begin{cases*}\frac{1}{2\lambda_{i}}&if $\lambda_{i}\neq 0$ and
$\textrm{deg}_{H}(i)=0$\\\\[4.0pt]
\frac{1-\frac{1}{6}(3-\deg_{H}(i))}{\lambda_{i}}&if $\lambda_{i}\neq 0$ and
$\textrm{deg}_{H}(i)\neq 0$\\\\[4.0pt] 0&if $\lambda_{i}=0$.\end{cases*}$

We will show that this $\mathbf{x}$ satisfies the constraints in (14) in the
linear optimisation problem, and gives optimal-function value $\frac{k}{2}$ in
(12). This will finish the proof.

To check (14) we point out that each vertex $i$ gets a contribution from those
vertices $j$ that are neighbours if $i$ in $G$ but not in $H$. Notice that
$x_{j}\geq\frac{1}{6}$ if $\lambda_{j}\neq 0$. This, together with (v) implies
that

$\lambda_{i}x_{i}+\sum_{(i,j)\in G\setminus H}x_{j}\geq
1-\frac{1}{6}(3-\deg_{H}(i))+(3-\deg_{H}(i))\frac{1}{6}=1.$

To finish, we show that $\displaystyle{\Sigma_{i=1}^{k}}\lambda_{i}x_{i}\leq
k/2$. Let

$\displaystyle k_{0}$ $\displaystyle=|\left\\{i\
\colon\deg_{H}(i)=0\right\\}|,$ $\displaystyle k_{1}$
$\displaystyle=|\left\\{i\ \colon\deg_{H}(i)=1,\lambda_{i}=2\right\\}|,$
$\displaystyle k_{2}$ $\displaystyle=|\left\\{i\
\colon\deg_{H}(i)=3,\lambda_{i}=1\right\\}|,$ $\displaystyle k_{3}$
$\displaystyle=|\left\\{i\ \colon\deg_{H}(i)=1,\lambda_{i}=1\right\\}|,$
$\displaystyle k_{4}$ $\displaystyle=|\left\\{i\
\colon\deg_{H}(i)=2,\lambda_{i}=1\right\\}|,$ $\displaystyle k_{5}$
$\displaystyle=|\left\\{i\ \colon\lambda_{i}=0\right\\}|.$

Then (ii), (iii) and (v) together with a double counting implies that

$3k_{5}=k_{1}+3k_{2}+k_{3}+2k_{4},$

which gives that

$k=k_{0}+k_{1}+k_{2}+k_{3}+k_{4}+k_{5}=k_{0}+\frac{4}{3}k_{1}+2k_{2}+\frac{4}{3}k_{3}+\frac{5}{3}k_{4}.$

From this, and the definition of $\mathbf{x}$ it follows that

$\sum_{i=1}^{k}\lambda_{i}x_{i}=\frac{1}{2}k_{0}+\frac{1}{3}k_{1}+k_{2}+\frac{2}{3}k_{3}+\frac{5}{6}k_{4}\leq\frac{k}{2}.$

∎

We close this section by describing constructions for bipartite $G$ that match
the upper bound in the slightly modified setting, when we count the number of
copies of $G$ with prescribed edge lengths. We choose $\frac{k}{2}$ points on
a line $\ell$, Then, we fix a circle $C$ in a plane orthogonal to $\ell$, and
centred in a point of $\ell$, and place $n-\frac{k}{2}$ points on it. Now it
is easy to check that by picking the $\frac{k}{2}$ points from $\ell$, and any
$\frac{k}{2}$ points from $C$, we obtain a copy of $G$.

##  5 Concluding remarks and further problems

While we could find sharp bounds for unit distance $k$-cycles for most $k$, on
$\mathbb{R}^{2}$ and in $\mathbb{R}^{3}$ the problem seems more difficult.
Proving good bounds for short cycles would be particularly interesting. In the
plane, for $k=3$ an easy upper bound is $u_{2}(n)$, and the best lower bound
is $ne^{\Omega(\frac{\log n}{\log\log n})}$. (See discussion in Chapter 6 of
[3].) For $k=4$ in the plane, we can construct $\Omega(u_{2}(n))$ many
$4$-cycles by using two translated copies of a set with optimally many unit
distances, and the best upper bound we could prove is
$\tilde{O}(n^{\frac{5}{3}})$.

For $3$-regular graphs in $\mathbb{R}^{3}$, our bounds are sharp for bipartite
graphs for the modified setting. It would be interesting to find sharp bounds
in the general case, or at least for some small non-bipartite $3$-regular
graphs.

## References

  * [1] P. Agarwal and M. Sharir, _On the number of congruent simplices in a point set_ , Discrete Comput. Geom 28 (2002), 123–150.
  * [2] P. Brass, _On the maximum number of unit distances among n points in dimension four_ , Intuitive Geometry 6 (1997), 277–290.
  * [3] P. Brass, W. O. J. Moser, and J. Pach, _Research problems in discrete geometry_ , Springer Science & Business Media, 2006.
  * [4] D. De Caen and L. A. Székely, _On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar point–line systems_ , J. Combin. Theory Ser. A 77 (1997), no. 2, 268–278.
  * [5] P. Erdős, _On sets of distances of n points_ , Amer. Math. Monthly 53 (1946), no. 5, 248–250.
  * [6] P. Erdős, _On sets of distances of n points in Euclidean space_ , Magyar Tudományos Akadémia Matematikai Kutató Intézet Közleményei 5 (1960), 165–169.
  * [7] N. Frankl and A. Kupavskii, _Almost sharp bounds on the number of discrete chains in the plane_ , 36th International Symposium on Computational Geometry (SoCG 2020) (2020).
  * [8] S. Gunter, E. Palsson, B. Rhodes, and S. Senger, _Bounds on point configurations determined by distances and dot products_ , arXiv preprint arXiv:2011.15055 (2020).
  * [9] P. Klavík, D. Král, and L. Mach, _Triangles in arrangements of points and lines in the plane_ , J. Combin. Theory Ser. A 118 (2011), 1140–1142.
  * [10] E. A. Palsson, S. Senger, and A. Sheffer, _On the number of discrete chains_ , Proc. Amer. Math. Soc. 149 (2021), no. 12, 5347–5358.
  * [11] J. Passant, _On Erdős chains in the plane_ , Bull. Korean Math. Soc. 58 (2021), no. 5, 1279–1300.
  * [12] S. Senger S. Kilmer, C. Marshall, _Dot product chains_ , arXiv preprint arXiv:2006.11467 (2020).
  * [13] J. Spencer, E. Szemerédi, and W. Trotter, Jr., _Unit distances in the Euclidean plane_ , Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, pp. 293–303. MR 777185
  * [14] K. J. Swanepoel, _Unit distances and diameters in euclidean spaces_ , Discrete Comput. Geom. 41 (2009), no. 1, 1–27.
  * [15] E. Szemerédi and W. T. Trotter, _Extremal problems in discrete geometry_ , Combinatorica 3 (1983), no. 3, 381–392.