Thus, these three maps $R_{0},P_{1}$, and $P_{-1}$ are mutually inequivalent.
Moreover, $R_{\alpha}\sim P_{1}$ for $\alpha>0$ and similarly $R_{\alpha}\sim
P_{-1}$ for $\alpha<0$ (in contrast, the trace of the Ahlfors tensor of CR
maps into the sphere is always nonnegative [28]).

The map $I$ satisfies

$\varrho_{{D^{\mathrm{IV}}_{3}}}\circ I=\varrho_{\mathbb{S}^{3}}$

and thus has vanishing Ahlfors tensor. Consequently, $I$ is of geometric rank
zero at all points. Clearly, any smooth deformation of $I$ along the sphere
must be equivalent to $I$.

None of the rational maps $R_{0},P_{1}$, and $P_{-1}$ can be equivalent to the
irrational map $I$, since all the automorphisms of the source and target are
rational. Hence, these four maps are pairwise inequivalent. This can also be
verified by analyzing elementary geometric properties of the maps as already
explained in Remark 2.

Finally, assume $H\colon\mathbb{B}^{2}\to{D^{\mathrm{IV}}_{3}}$ is a proper
holomorphic map that extends smoothly to a boundary point
$p\in\mathbb{S}^{3}$. We can assume that $p=(0,1)$ and
$H(p)=\left(0,\frac{1}{2},\frac{i}{2}\right)$. Then $\tilde{H}:=\Phi^{-1}\circ
H\circ\mathcal{C}^{-1}$ defines a germ at the origin of CR maps sending
$\mathbb{H}^{3}$ into $\mathcal{X}$. Thus, it must belong to one of the five
equivalence classes of the germs represented by $r_{0},r_{1},r_{-1}$, $\iota$,
and $t$ for some nowhere CR transversal map $t$ as given in Lemma 4.24. But if
$\tilde{H}$ is equivalent to $t$, then $H$ cannot be proper as can be easily
checked. Hence, $\tilde{H}$ must be in one of the equivalence classes
represented by the germs of CR transversal maps, which are the four
equivalence classes of the germs of $\Phi^{-1}\circ F\circ\mathcal{C}^{-1}$
with $F\in\\{R_{0},P_{1},P_{-1},I\\}$. In fact, the four germs of CR maps
$\Phi^{-1}\circ F\circ\mathcal{C}^{-1}$, $F\in\\{R_{0},P_{1},P_{-1},I\\}$ are
pairwise inequivalent as can be easily checked using the Ahlfors invariant and
the irrationality. Thus, there are local CR automorphisms
$\psi\in\operatorname{Aut}(\mathcal{X},0)$ and
$\gamma\in\operatorname{Aut}(\mathbb{H}^{3},0)$ such that
$\psi\circ\tilde{H}\circ\gamma^{-1}=\Phi^{-1}\circ F\circ\mathcal{C}^{-1}$
near the origin for some $F\in\\{R_{0},P_{1},P_{-1},I\\}$. Thus, if
$\tilde{\psi}:=\Phi\circ\psi\circ\Phi^{-1}$ and
$\tilde{\gamma}:=\mathcal{C}^{-1}\circ\gamma\circ\mathcal{C}$, then, as germs
at $p$, $\tilde{\psi}\circ
H\circ\tilde{\gamma}^{-1}=F\in\\{R_{0},P_{1},P_{-1},I\\}$. But $\tilde{\psi}$
is a global automorphism of ${D^{\mathrm{IV}}_{3}}$ by Theorem 2.3 and
$\tilde{\gamma}$ is a global automorphism of the unit ball. This completes the
proof of Corollary 1.3.

######  Remark 6.

Although $P_{1}$ and $P_{-1}$ have quite simple formulas, to the best of the
authors’ knowledge, they didn’t appear before in the literature. Take the
family of rational maps $r_{\beta}\colon\mathbb{H}^{3}\to\mathcal{X}$ as above
and transform it into a family of rational maps $\Phi\circ
r_{\beta}\circ\mathcal{C}$ to get various representatives of the equivalence
classes of $P_{\pm 1}$. For certain values of $\beta$, the formulas simplify.
For example, if $\beta=-1/4$, then the map $\Phi\circ
r_{\beta}\circ\mathcal{C}$ sends $\mathbb{B}^{2}$ into
${D^{\mathrm{IV}}_{3}}\cap\\{z_{3}-iz_{2}=0\\}$. This suggest that we
substitute $z_{3}=iz_{2}$ into $\varrho_{{D^{\mathrm{IV}}_{3}}}$ to obtain

$\varrho_{{D^{\mathrm{IV}}_{3}}}(z_{1},z_{2},iz_{2})=1-2|z_{1}|^{2}-4|z_{2}|^{2}+|z_{1}|^{4}=(1-|z_{1}|^{2})^{2}-4|z_{2}|^{2}.$

From this, we can easily find the desired map $P_{-1}$. The formula for
$P_{1}$ can be constructed easily by analyzing the map $\Phi\circ
r_{\beta}\circ\mathcal{C}$ with $\beta=1/4$.

##  5\. Examples

Observe that $\mathcal{X}\cap\\{\zeta=0\\}$ is CR equivalent to the Heisenberg
hypersurface $v=|z|^{2}$. In fact, $\mathcal{X}\cap\\{\zeta=0\\}$ is the image
of $\mathbb{H}^{3}$ under the linear map $\ell(z,w)$ in part (i) of Theorem
1.2. The formula for the stability group of
$\operatorname{Aut}(\mathcal{X},0)$ suggests we consider the variety
$V=\\{w\zeta+iz^{2}=0\\}\subset\mathbb{C}^{3}$ which has a singularity at the
origin. On $V$, we have $\operatorname{Re}(z^{2}\bar{\zeta})=-|\zeta|^{2}v$
and thus on $\mathcal{X}\cap V$,

$v=\frac{|z|^{2}-v|\zeta|^{2}}{1-|\zeta|^{2}},$

implying $v=|z|^{2}$. The real subvariety $V\cap\mathcal{X}$ contains a
complex variety $(0,\zeta,0)$, and a graph over the Heisenberg hypersurface
$v=|z|^{2}$ given by $(z,-iz^{2}/w,w)$, $w\neq 0$. All germs of nontranversal
CR maps at the origin send an open set in $\mathbb{H}^{3}$ into this complex
variety, see Lemma 4.24. From Lemma 2.2, we find that $V\cap\mathcal{X}$ is
“invariant” in the following sense: For $(\tilde{z},\tilde{\zeta},\tilde{w})$
in the stability group, we have

$\tilde{w}\tilde{\zeta}+i\tilde{z}^{2}=-\lambda^{2}u^{2}(w\zeta+iz^{2})/\delta.$

That is $\gamma(\mathcal{X}\cap V)\subset\mathcal{X}\cap V$ for all
$\gamma\in\operatorname{Aut}(\mathcal{X},0)$. From the observation above, we
can construct a examples of maps from $\mathbb{H}^{3}$ into $\mathcal{X}$ as
follows.

######  Example 5.1.

Each map in the family of rational maps $H_{t}(z,w)=(z,-iz^{2}/(w+t),w+t)$,
$t\in\mathbb{R}$, sends $\mathbb{H}^{3}\setminus\\{(0,-t)\\}$ into
$\mathcal{X}\cap V$ transversally, but does not extend holomorphically to the
point $(0,-t)$. It turns out that at any point
$p\in\mathbb{H}^{3}\setminus\\{(0,-t)\\}$, $H_{t}$ represents a germ at $p$
that is equivalent to the germ of $\ell$ at the origin. In fact,

$\widetilde{\varrho}_{\mathcal{X}}\circ
H_{t}=|w+t+2i|^{-2}\varrho_{\mathbb{H}^{3}},$

and hence outside the pole of $H_{t}$, the Ahlfors tensor $\mathcal{A}(H_{t})$
vanishes identically. Thus, $H_{t}$ must be equivalent to either $\ell$ or
$\iota$. But the latter possibility is ruled out by the rationality and
$H_{t}$ is equivalent to $\ell$. Transferring this map into a map from the
unit ball into the type IV model, we obtain a map that is equivalent to
$R_{0}$. Explicitly, with $t=0$, we have

$\Phi\circ H_{0}\circ\mathcal{C}\circ\gamma_{1}=-R_{0},$

for

$\gamma_{1}(z,w)=\left(-\frac{2\sqrt{2}z}{w+3},-\frac{3w+1}{w+3}\right)$

is an automorphism of $\mathbb{B}^{2}$ exchanging the origin and $(0,-1/3)$.

######  Example 5.2.

As an application of the transitive part of the automorphisms in section 2.2,
we explicitly verify that the rational map
$R:\mathbb{B}^{2}\rightarrow{D^{\mathrm{IV}}_{3}}$ from [41, Theorem 1.4],
given by

$\displaystyle
R(z_{1},z_{2})=\left(z_{1},\frac{z_{1}^{2}/2-z_{2}^{2}+z_{2}}{\sqrt{2}(1-z_{2})},\frac{i(z_{1}^{2}/2+z_{2}^{2}-z_{2})}{\sqrt{2}(1-z_{2})}\right),$

corresponds to the linear map
$\ell:\mathbb{H}^{3}\rightarrow\mathcal{X},\ell(z,w)=(z,0,w)$ from Theorem
1.2. Note that $R$ sends $p=(0,1/2)\in\mathbb{B}^{2}$ to
$q=(0,1/2\sqrt{2},-i/2\sqrt{2})\in{D^{\mathrm{IV}}_{3}}$. We define
$\Psi_{1}:\mathbb{C}^{3}\setminus\\{z_{2}-iz_{3}=\sqrt{2}\\}\rightarrow\mathbb{C}^{3}$,
given by

$\displaystyle\Psi_{1}(z_{1},z_{2},z_{3})=\left(\frac{-2z_{1}}{\sqrt{2}-z_{2}+iz_{3}},\frac{2z_{2}+2iz_{3}-\sqrt{2}(z_{1}^{2}+z_{2}^{2}+z_{3}^{2})}{2(\sqrt{2}-z_{2}+iz_{3})},\frac{2(\sqrt{2}i+iz_{2}+z_{3})}{\sqrt{2}-z_{2}+iz_{3}}\right),$

which locally sends ${\mathcal{R}}$ into $\mathcal{X}$ and $q$ to
$(0,1/2,2i)\in\mathcal{X}$, and
$\Psi_{2}:\mathbb{C}^{2}\setminus\\{w=-i\\}\rightarrow\mathbb{C}^{2}$, given
by

$\displaystyle\Psi_{2}(z,w)=\left(\frac{i-w}{i+w},\frac{2iz}{i+w}\right),$

which sends $\mathbb{H}^{3}$ into $\mathbb{S}^{3}$ and $(1/2,i)$ to $p$. We
consider

$\displaystyle\hat{R}(z,w)=\Psi_{1}\circ R\circ\Psi_{2}=$
$\displaystyle\left(\frac{2\sqrt{2}(1-2z-2izw+w^{2})}{-1+4z+(6i-4iz+w)w},\frac{1-4z+2iw(1+2z)+8z^{2}-w^{2}}{-1+4z+(6i-4iz+w)w}\right.,$
$\displaystyle\quad\left.2i+\frac{4i(i-w)^{2}}{-1+4z+(6i-4iz+w)w}\right),$

which locally maps $\mathbb{H}^{3}$ to $\mathcal{X}$ and $\hat{p}=(0,1)$ to
$\hat{q}=\frac{1}{3}(-2\sqrt{2}i,1,2i)$. Next, we compose $\hat{R}$ with
automorphisms to ensure that it sends $0$ to $0$. More precisely, we define

$\displaystyle\varphi(z,w)=(z,w+1),$

which is an automorphism of $\mathbb{H}^{3}$, and

$\displaystyle\varphi^{\prime}_{1}(z,\zeta,w)$
$\displaystyle=\left(\frac{2\sqrt{2}z}{3-\zeta},\frac{3\zeta-1}{3-\zeta},w-\frac{iz^{2}}{3-\zeta}\right),$
$\displaystyle\varphi^{\prime}_{2}(z,\zeta,w)$
$\displaystyle=\left(z+i(1+\zeta),\zeta,2z+w+i(1+\zeta)\right),$

which originate from choosing $\lambda^{\prime}=1/2$ in (2.4) and $b=i$ and
$r=0$ in (2.3) respectively. If we set

$\displaystyle\check{R}(z,w)$
$\displaystyle=\varphi_{2}^{\prime}\circ\varphi_{1}^{\prime}\circ\hat{R}\circ\varphi$
$\displaystyle=\left(\frac{2(2i(z-(1-i))z-2izw+w^{2})}{-2((i-1)+z)^{2}+((2+4i)-4iz)w+w^{2}},\right.$
$\displaystyle\qquad\frac{2z(3z-(2-2i))-w(2-4iz)-w^{2}}{-2((i-1)+z)^{2}+((2+4i)-4iz)w+w^{2}},$
$\displaystyle\qquad\left.\frac{(4+4i)w((1+i)-2iz+w)}{-2((i-1)+z)^{2}+((2+4i)-4iz)w+w^{2}}\right),$

we obtain a map, which, again, locally sends $\mathbb{H}^{3}$ into
$\mathcal{X}$ and $0$ to $0$. For the final step, we define the following
automorphisms of $\mathbb{H}^{3}$ and $\mathcal{X}$ respectively, fixing $0$,

$\displaystyle\phi(z,w)$
$\displaystyle=\left(\frac{2z+w}{(2+2i)(i+z)+w},\frac{(i-1)w}{(2+2i)(i+z)+w}\right),$
$\displaystyle\phi^{\prime}(z,\zeta,w)$
$\displaystyle=\left(-2i+\frac{8+4iz}{i(z-2i)^{2}+(\zeta-1)w},\frac{(4+iz)z-4i\zeta+(\zeta-1)w}{i(z-2i)^{2}+(\zeta-1)w},\right.$
$\displaystyle\left.\qquad\frac{-4iw}{i(z-2i)^{2}+(\zeta-1)w}\right),$

which are obtained by following the procedure in the proof of Theorem 3.1. It
can be verified that the map $L=\phi^{\prime}\circ\check{R}\circ\phi$ agrees
with $\ell$.

######  Remark 7.

Carrying out the analogous steps as in Example 5.2 it can be shown that the
irrational map $I:\mathbb{B}^{2}\rightarrow{D^{\mathrm{IV}}_{3}}$ given by
$I(z,w)=\left(z,w,1-\sqrt{1-z^{2}-w^{2}}\,\right)\bigl{/}\sqrt{2}$ found by
Xiao–Yuan in [41, Theorem 1.4] corresponds to the irrational map $\iota$
obtained in Theorem 1.2. More precisely, it is possible to obtain a map
$\check{I}$ from $I$, which sends $(\mathbb{H}^{3},0)$ to $(\mathcal{X},0)$.
After that, bringing $\check{I}$ to the partial normal form given in Theorem
3.1, it can be verified that the $4$-jets at the origin of this map and
$\iota$ agree. Since the formulas involved are more complicated than in the
rational case we refrain from displaying them here.

######  Example 5.3.

The mapping equation (4.2) can be regarded as a system of infinitely many
linear and nonlinear equations for the Taylor coefficients of the components
of the map under consideration. Each solution to this system gives rise to
holomorphic or formal CR map sending the germ $(\mathbb{H}^{3},0)$ into
$(\mathcal{X},0)$ as a subset of formally. We give an example of a holomorphic
map whose Taylor coefficients solve all _but_ three equations of weight 14 as
well as three holomorphic functional equations in Lemma 4.19, yet the map does
_not_ send $\mathbb{H}^{3}$ into $\mathcal{X}$. Indeed, consider the following
family of holomorphic maps

$H:=(f,\phi,g)=\left(z+2tzw^{3},-4itz^{2}w^{2},w+tw^{4}\right),\
t\in\mathbb{R}.$

which satisfies the functional equations in Lemma 4.19. If
$\Sigma_{1}\colon(z,\bar{z},\bar{w})\mapsto(z,\bar{w}+2iz\bar{z})$ is a
parametrization of the (complexification) of the Heisenberg hypersurface, then

$\widetilde{\varrho}\circ
H_{t}\circ\Sigma_{1}=-4t^{2}\bar{w}^{3}z\bar{z}(\bar{w}+2iz\bar{z})^{3}.$

Hence, $H_{t}$ sends $\mathbb{H}^{3}$ into $\mathcal{X}$ if and only if $t=0$.

## References

  * [1] A. B. Aleksandrov.  The existence of inner functions in a ball.  Mat. Sb. (N.S.), 118(160)(2):147–163, 287, 1982.
  * [2] H. Alexander.  Proper holomorphic mappings in $\mathbb{C}^{n}$.  Indiana University Mathematics Journal, 26(1):137–146, 1977.
  * [3] M. Salah Baouendi, Peter Ebenfelt, and Linda Preiss Rothschild.  Real submanifolds in complex space and their mappings, volume 47.  Princeton University Press, 1999.
  * [4] Elie Cartan.  Sur les domaines bornés homogènes de l’espace den variables complexes.  Abh. Math. Sem. Univ. Hamburg, 11(1):116–162, 1935.
  * [5] Shan Tai Chan and Ngaiming Mok.  Holomorphic isometries of $\mathbb{B}^{m}$ into bounded symmetric domains arising from linear sections of minimal embeddings of their compact duals.  Mathematische Zeitschrift, 286(1):679–700, 2017.
  * [6] J. A. Cima and T. J. Suffridge.  Proper holomorphic mappings from the two-ball to the three-ball.  Trans. Amer. Math. Soc., 311(1):227–239, 1989.
  * [7] John P. D’Angelo.  Proper holomorphic maps between balls of different dimensions.  Michigan Math. J., 35(1):83–90, 1988.
  * [8] Giuseppe della Sala, Bernhard Lamel, and Michael Reiter.  Sufficient and necessary conditions for local rigidity of CR mappings and higher order infinitesimal deformations.  Arkiv för Matematik, 58(2):213–242, 2020.
  * [9] Peter Ebenfelt.  Normal forms and biholomorphic equivalence of real hypersurfaces in $\mathbb{C}^{3}$.  Indiana Univ. Math. J., 47(2):311–366, 1998.
  * [10] James J. Faran.  Maps from the two-ball to the three-ball.  Inventiones mathematicae, 68(3):441–475, 1982.
  * [11] James J. Faran.  The linearity of proper holomorphic maps between balls in the low codimension case.  Journal of Differential Geometry, 24(1):15–17, 1986.
  * [12] Gregor Fels and Wilhelm Kaup.  CR-manifolds of dimension 5: a Lie algebra approach.  J. Reine Angew. Math., 604:47–71, 2007.
  * [13] Franc Forstnerič.  Extending proper holomorphic mappings of positive codimension.  Invent. Math., 95(1):31–61, 1989.
  * [14] Josef Greilhuber.  Smooth regularity of CR maps into boundaries of classical symmetric domains.  Master’s thesis, University of Vienna, 2020.
  * [15] Monique Hakim and Nessim Sibony.  Fonctions holomorphes bornées sur la boule unité de ${\mathbb{C}}^{n}$.  Invent. Math., 67(2):213–222, 1982.
  * [16] Hidetaka Hamada.  Rational proper holomorphic maps from $\mathbb{B}^{n}$ into $\mathbb{B}^{2n}$.  Math. Ann., 331(3):693–711, 2005.
  * [17] L. K. Hua.  Harmonic analysis of functions of several complex variables in the classical domains.  Translated from the Russian by Leo Ebner and Adam Korányi. American Mathematical Society, Providence, R.I., 1963.
  * [18] Xiaojun Huang.  On a linearity problem for proper holomorphic maps between balls in complex spaces of different dimensions.  J. Differential Geom., 51(1):13–33, 1999.
  * [19] Xiaojun Huang.  On a semi-rigidity property for holomorphic maps.  Asian J. Math., 7(4):463–492, 2003.
  * [20] Xiaojun Huang and Shanyu Ji.  Mapping $\mathbb{B}^{n}$ into $\mathbb{B}^{2n-1}$.  Inventiones mathematicae, 145(2):219–250, 2001.
  * [21] Xiaojun Huang, Shanyu Ji, and Dekang Xu.  A new gap phenomenon for proper holomorphic mappings from $B^{n}$ into $B^{N}$.  Math. Res. Lett., 13(4):515–529, 2006.
  * [22] Xiaojun Huang, Shanyu Ji, and Wanke Yin.  On the third gap for proper holomorphic maps between balls.  Math. Ann., 358(1-2):115–142, 2014.
  * [23] Xiaojun Huang, Jin Lu, Xiaomin Tang, and Ming Xiao.  Boundary characterization of holomorphic isometric embeddings between indefinite hyperbolic spaces.  Advances in Mathematics, 374:107388, 2020.
  * [24] Shanyu Ji.  A new proof for Faran’s theorem on maps between $\mathbb{B}^{2}$ and $\mathbb{B}^{3}$.  In Recent advances in geometric analysis, volume 11 of Adv. Lect. Math. (ALM), pages 101–127. Int. Press, Somerville, MA, 2010.
  * [25] Wilhelm Kaup and Dmitri Zaitsev.  On local CR-transformation of Levi-degenerate group orbits in compact Hermitian symmetric spaces.  J. Eur. Math. Soc. (JEMS), 8(3):465–490, 2006.
  * [26] Martin Kolar and Ilya Kossovskiy.  A complete normal form for everywhere levi degenerate hypersurfaces in $\mathbb{C}^{3}$.  arXiv preprint arXiv:1905.05629, 2019.
  * [27] Ilya Kossovskiy, Bernhard Lamel, and Ming Xiao.  Regularity of CR-mappings of codimension one into Levi-degenerate hypersurfaces.  Comm. Anal. Geom., 29(1):151–181, 2021.
  * [28] Bernhard Lamel and Duong Ngoc Son.  The CR ahlfors derivative and a new invariant for spherically equivalent CR maps.  to appear in Annales de l’Institut Fourier. arXiv:1907.00834, 2019\.
  * [29] Erik Løw.  A construction of inner functions on the unit ball in ${\mathbb{C}}^{p}$.  Invent. Math., 67(2):223–229, 1982.
  * [30] Erik Løw.  Embeddings and proper holomorphic maps of strictly pseudoconvex domains into polydiscs and balls.  Math. Z., 190(3):401–410, 1985.
  * [31] Nordine Mir.  Holomorphic deformations of real-analytic CR maps and analytic regularity of CR mappings.  J. Geom. Anal., 27(3):1920–1939, 2017.
  * [32] Ngaiming Mok.  Geometry of holomorphic isometries and related maps between bounded domains.  In Geometry and analysis. No. 2, volume 18 of Adv. Lect. Math. (ALM), pages 225–270. Int. Press, Somerville, MA, 2011.
  * [33] Ngaiming Mok.  Some recent results on holomorphic isometries of the complex unit ball into bounded symmetric domains and related problems.  In Geometric complex analysis, volume 246 of Springer Proc. Math. Stat., pages 269–290. Springer, Singapore, 2018.
  * [34] Ngaiming Mok and Sui Chung Ng.  Germs of measure-preserving holomorphic maps from bounded symmetric domains to their Cartesian products.  J. Reine Angew. Math., 669:47–73, 2012.
  * [35] M Henri Poincaré.  Les fonctions analytiques de deux variables et la représentation conforme.  Rendiconti del Circolo Matematico di Palermo (1884-1940), 23(1):185–220, 1907.
  * [36] Michael Reiter.  Classification of holomorphic mappings of hyperquadrics from $\mathbb{C}^{2}$ to $\mathbb{C}^{3}$.  J. Geom. Anal., 26(2):1370–1414, 2016.  arXiv:1409.5968.
  * [37] A. E. Tumanov and G. M. Khenkin.  Local characterization of analytic automorphisms of classical domains.  Dokl. Akad. Nauk SSSR, 267(4):796–799, 1982.
  * [38] Harald Upmeier, Kai Wang, and Genkai Zhang.  Holomorphic isometries from the unit ball into symmetric domains.  International Mathematics Research Notices, 2019(1):55–89, 2019\.
  * [39] S. M. Webster.  On mapping an $n$-ball into an $(n+1)$-ball in complex spaces.  Pacific J. Math., 81(1):267–272, 1979.
  * [40] Ming Xiao.  Regularity of mappings into classical domains.  Math. Ann., 378(3-4):1271–1309, 2020.
  * [41] Ming Xiao and Yuan Yuan.  Holomorphic maps from the complex unit ball to Type IV classical domains.  Journal de Mathématiques Pures et Appliquées, 133:139–166, 2020.


# Orthogonal Colourings of Random Geometric Graphs

Jeannette Janssen  Department of Mathematics, Dalhousie University  Kyle
MacKeigan  Department of Mathematics, Mount Saint Vincent University

###### Abstract

In this paper, we study orthogonal colourings of random geometric graphs. Two
colourings of a graph are orthogonal if they have the property that when two
vertices receive the same colour in one colouring, then those vertices receive
distinct colours in the other colouring. A random geometric graph $RG(n,r)$ is
a graph constructed by randomly placing $n$ vertices in the unit square and
connecting two vertices with an edge if and only if their distance is less
than the threshold $r$. We show first that random geometric graphs with
$r>n^{-\alpha}$, where $0\leq\alpha\leq\frac{1}{4}$, have an orthogonal
colouring using $n^{1-2\alpha}(1+o(1))$ colours with high probability. Then,
we show for an infinite number of values of $n$, random geometric graphs with
threshold $r<cn^{-\frac{1}{4}}$, $c<1$, have an optimal orthogonal colouring
with high probability. We obtain both of these results by constructing
orthogonal colourings of the clique grid graph.

##  1 Introduction

Two vertex colourings of a graph are orthogonal if they have the property that
when two vertices receive the same colour in one colouring, then those
vertices must receive distinct colours in the other colouring. An orthogonal
colouring is a pair of orthogonal vertex colourings. The orthogonal chromatic
number of a graph $G$, denoted $O\chi(G)$, is the minimum number of colours
required for an orthogonal colouring.

Orthogonal colourings were first defined in 1985 by Archdeacon, Dinitz, and
Harary in the context of edge colourings [2]. Later in 1999, Caro and Yuster
studied orthogonal colourings in the context of vertex colourings [4]. Then in
2013, Ballif studied upper bounds on collections of orthogonal vertex
colourings [3]. In previous work [5], the authors explored orthogonal
colourings of Cayley graphs and Cartesian products of graphs. A part of the
results presented here were obtained in the second author’s doctoral
dissertation [7].

For a graph $G$ with $n$ vertices, in order for two colourings to be
orthogonal, at least $\lceil\sqrt{n}\,\rceil$ colours are required. If
$O\chi(G)=\lceil\sqrt{n}\,\rceil$, then $G$ is said to have an optimal
orthogonal colouring. Graphs with optimal orthogonal colourings are of
particular interest due to their applications to independent coverings [8] and
combinatorial game theory [1]. In this paper, optimal orthogonal colourings of
random geometric graphs are studied.

The random geometric graph model, denoted $RG(n,r)$, is defined as follows. In
this model, $n$ points are placed in the unit square, $[0,1]^{2}$, uniformly
at random. Two vertices are then connected by an edge if and only if the
Euclidean distance between the two vertices is less than $r$. If $G$ is a
graph sampled from the random geometric graph model, then this is denoted by
$G\sim RG(n,r)$. Random geometric graphs are interesting to study since they
can be used to model real world networks [6].

We will focus on connected graphs. Penrose [11] showed that if
$\frac{r^{2}n}{\ln n}\to\infty$ as $n\to\infty$, then $G\sim RG(n,r)$ is
connected with high probability. A random geometric graph $RG(n,r)$ with
threshold $r=r(n)$ so that $\frac{r^{2}n}{\ln n}\to\infty$ as $n\to\infty$ is
called a dense random geometric graph. McDiarmid [10] showed that if $G\sim
RG(n^{2},r)$ is a dense random geometric graph, then
$\chi(G)\leq\frac{\sqrt{3}}{2}r^{2}n^{2}$ with high probability. This was done
by constructing a graph homomorphism into the triangular lattice graph.

In this paper, we study orthogonal colourings of dense random geometric graphs
by constructing a graph homomorphism into a structured graph we call the
clique grid graph. In Section 2, we define the clique grid graph and establish
results on its orthogonal chromatic number. In Section 3, we use the clique
grid graph to bound the orthogonal chromatic number of dense random geometric
graphs. In Section 3.1 we show that, if $r=n^{-\alpha}$ where
$0\leq\alpha\leq\frac{1}{4}$, a random geometric graph $G\sim RG(n,r)$ has an
orthogonal colouring using $n^{1-2\alpha}(1+o(1))$ colours with high
probability. In Section 3.2, we show that, if $r\leq cn^{-\frac{1}{4}})$,
$c<1$, then a random geometric graph $G\sim RG(n,r)$ has an optimal orthogonal
colouring with high probability.

##  2 Orthogonal Colourings of the Clique Grid Graph

We will prove our results about random geometric graphs by mapping such graphs
to graphs that have a highly geometric structure. We will refer to such graphs
as _clique grid graphs_. In this section, we define clique grid graphs, and
give results on their orthogonal chromatic number.

The clique grid graph will be constructed by taking the strong graph product
of the following graph with itself. Let $H(m,d,t)$ be the graph with vertices
labelled $v_{i}^{j}$ for $0\leq i<m$ and $0\leq j<t$, where two vertices
$v_{i_{1}}^{j_{1}}$ and $v_{i_{2}}^{j_{2}}$ are adjacent if and only if
$|i_{1}-i_{2}|\leq d$. That is, $H(m,d,t)$ is the graph obtained by taking $m$
cliques of size $t$, denoted $C_{i}$, where all of the vertices in $C_{i_{1}}$
and $C_{i_{2}}$ are adjacent to one another if and only if $|i_{1}-i_{2}|\leq
d$. For example, the graph $H(9,1,2)$ is given in Figure 2.1; it consists of
nine cliques of size two, and only adjacent cliques are connected.

$v_{0}^{0}$$v_{1}^{0}$$v_{2}^{0}$$v_{3}^{0}$$v_{4}^{0}$$v_{5}^{0}$$v_{6}^{0}$$v_{7}^{0}$$v_{8}^{0}$$v_{0}^{1}$$v_{1}^{1}$$v_{2}^{1}$$v_{3}^{1}$$v_{4}^{1}$$v_{5}^{1}$$v_{6}^{1}$$v_{7}^{1}$$v_{8}^{1}$
Figure 2.1: $H(9,1,2)$

Orthogonal colourings of the graph $H(m,d,t)$ are now considered. These will
later be extended to orthogonal colourings of the clique grid graph. It is
easy to see that $H(m,d,t)$ has order $mt$ and clique number $t(d+1)$.
Therefore, $t(d+1)$ is a lower bound on the chromatic number, and thus also
the orthogonal chromatic number. The following theorem shows that either
$H(m,d,t)$ has an optimal orthogonal colouring, or the orthogonal chromatic
number of $H(m,d,t)$ is at most one more than the clique number.

######  Theorem 2.1.

For all positive integers $m,d,t$,

$O\chi(H(m,d,t))=\left\\{\begin{array}[]{lll}t(d+1)&\text{if }m\leq
t(d+1),&\text{(Case 1)}\\\ t(d+1)+1&\text{if }t(d+1)<m\leq
t(d+1)^{2},&\text{(Case 2)}\\\
\lceil\sqrt{mt}\rceil&\text{otherwise.}&\text{(Case 3)}\end{array}\right.$

In particular, if we are in Case 3, then $H(m,d,t)$ has an optimal orthogonal
colouring.

Proof: Suppose first that we are in Case 1, and let $N=t(d+1)$. According to
our condition, $mt\leq N^{2}$. Consider the following two colourings
$c_{1},c_{2}$ of $H(m,d,t)$. For all $0\leq i<m$ and $0\leq j<t$, let

$\displaystyle c_{1}(v_{i}^{j})=$ $\displaystyle j+it$
$\displaystyle(\textrm{mod}~{}N),\text{ and}$ $\displaystyle
c_{2}(v_{i}^{j})=$
$\displaystyle\left(j+\left\lfloor\frac{i}{d+1}\right\rfloor\right)(\text{mod}~{}{t})+it$
$\displaystyle(\textrm{mod}~{}N).$

Here and in the rest of the paper we use $x=a(\text{mod}~{}{b})$ to mean that
$a$ is the unique integer $0\leq a<b$ which is equivalent to $x$ modulo $b$.

First, we will show that these two colourings are proper. Suppose that the
vertices $v_{i_{1}}^{j_{1}}$ and $v_{i_{2}}^{j_{2}}$ are adjacent, that is,
$|i_{1}-i_{2}|\leq d$. Since $(i_{1},j_{1})\not=(i_{2},j_{2})$ and
$j_{1},j_{2}<t$, we have that $j_{1}+i_{1}t\not=j_{2}-i_{2}t$. Moreover, we
have that

$|j_{1}+i_{1}t-j_{2}-i_{2}t|\leq|i_{1}-i_{2}|t+|j_{1}-j_{2}|<t(d+1).$

Since $N=t(d+1)$, it follows that $c_{1}(v_{i_{1}}^{j_{1}})\neq
c_{1}(v_{i_{2}}^{j_{2}})$. This proves that $c_{1}$ is a proper colouring.

Next we show that $c_{2}$ is proper. We consider two cases. If $i_{1}=i_{2}$,
then

$\left|c_{2}(v_{i_{1}}^{j_{1}})-c_{2}(v_{i_{2}}^{j_{2}})\right|=(j_{1}-j_{2})(\text{mod~{}}{t})<t<N.$

Since $j_{1}\not=j_{2}$, $c_{2}(v_{i_{1}}^{j_{1}})\neq
c_{2}(v_{i_{2}}^{j_{2}})$. Suppose then that $i_{1}\neq i_{2}$. Let
$s_{k}=\left(j_{k}+\left\lfloor\frac{i_{k}}{d+1}\right\rfloor\right)(\text{mod}~{}t)$
for $k=1,2$ and assume _wlog_ that $s_{1}\geq s_{2}$ and thus $0\leq
s_{1}-s_{2}<t$. Then

$\left|s_{1}+i_{1}t-(s_{2}+i_{2}t)\right|\geq|i_{1}-i_{2}|t-|s_{1}-s_{2}|\geq
t-(s_{1}-s_{2})>0,$

and similarly,

$\left|s_{1}+i_{1}t-(s_{2}+i_{2}t)\right|\leq|i_{1}-i_{2}|t+|s_{1}-s_{2}|<dt+t=N,$

and thus $c_{2}(v_{i_{1}}^{j_{1}})\neq c_{2}(v_{i_{2}}^{j_{2}})$. We now prove
that $c_{1}$ and $c_{2}$ are orthogonal. Since $N=t(d+1)$ we have a repeating
pattern of colours on each clique. Specifically, for each $0\leq b<(d+1)$,
$c_{1}$ and $c_{2}$ both assign colours $a+bt$, $0\leq a<t$ to cliques
$C_{b},C_{b+(d+1)},C_{b+2(d+1)},\dots$, where the last clique to receive this
set of colours is clique $C_{b+s(d+1)}$ where $s$ is the largest integer so
that $b+s(d+1)<m$.

Now consider vertex $v_{i}^{j}$ in clique $i=b+c(d+1)$. Since $i<m$, we have
that $c\leq\lfloor\frac{m}{d+1}\rfloor\leq t$ by the conditions of Case 1.
This vertex receives colours

$c_{1}(v_{i}^{j})=j+bt+ct(d+1)\,(\text{mod}~{}N)=j+bt\text{ and
}c_{2}(v_{i}^{j})=(j+c)\,(\text{mod}~{}{t})+bt.$

As argued earlier, $c<t$. Therefore, for all $0\leq b<d+1$, each pair of
colours $(j+bt,j+c+bt\,(\text{mod}~{}{t}))$, $0\leq c<t$ occurs at most once.
Colour pairs $(j+b_{1}t,j+c+b_{2}t\,(\text{mod}~{}{t}))$ never occur. Thus,
$c_{1}$ and $c_{2}$ constitute an orthogonal colouring. Since $H(m,d,t)$ has
clique number and chromatic number equal to $t(d+1)=N$, this orthogonal
colouring is optimal.

Suppose next that we are in Case 2, and let $N=t(d+1)$. First we show that
$O\chi(H(m,d,t)>N$. Suppose an orthogonal colouring $c_{1},c_{2}$ with $N$
colours exists. Then such a colouring must have the repeating pattern as in
Case 1. Specifically, for each $0\leq b<(d+1)$, $c_{1}$ and $c_{2}$ must both
assign colours $a+bt$, $0\leq a<t$ to cliques
$C_{b},C_{b+(d+1)},C_{b+2(d+1)},\dots,C_{b+s(d+1)}$, where $s$ is the largest
integer so that $b+s(d+1)<m$. Namely, cliques $C_{0},C_{1},\dots,C_{d}$ form a
clique, so admit a unique colouring. Every vertex in $C_{d+1}$ is adjacent to
all vertices in clique $C_{1},\dots,C_{d}$, so the only colours available are
the colours used on clique $C_{0}$. Similarly, for each $d+1\leq k<m$, the
only colours available to colour clique $C_{k}$ are the colours used to colour
$C_{k-(d+1)}$. Now consider the colourings assigned by $c_{1}$ and $c_{2}$ to
cliques $C_{0},C_{(d+1)},\dots,C_{s(d+1)}$, where
$s=\lceil\frac{m}{d+1}\rceil-1$. Each of these colourings assigns the same set
of $t$ colours. There are at most $t^{2}$ colour pairs with this set of
colours, so these cliques together can contain at most $t^{2}$ vertices,
Therefore, we must have that $s<t$ and thus $m\leq t(d+1)$.

To show that $O\chi(H(m,d,t)=N+1$, consider the following two colourings using
$N+1$ colours. For all $0\leq i<m$ and $0\leq j<t$, let

$\displaystyle c_{1}(v_{i}^{j})=$ $\displaystyle j+it$
$\displaystyle(\textrm{mod}~{}N),\text{ and}$ $\displaystyle
c_{2}(v_{i}^{j})=$
$\displaystyle(j+it)\,(\text{mod}~{}{N})+\lfloor\frac{i}{d+1}\rfloor$
$\displaystyle(\textrm{mod}~{}N+1).$

Colouring $c_{1}$ is the same as in the previous case, and to prove it is
proper we did not need the condition on $m$. Next we show that $c_{2}$ is
proper. Let $v_{i_{1}}^{j_{1}}$ and $v_{i_{2}}^{j_{2}}$ be two adjacent
vertices. We consider two cases. If $i_{1}=i_{2}$, then
$(j_{1}+i_{1}t)(\text{mod}~{}{N})\not=(j_{2}+i_{2}t)(\text{mod}~{}{N})$ as
argued before, and thus
$c_{2}(v_{i_{1}}^{j_{1}})\not=c_{2}(v_{i_{2}}^{j_{2}})$. Suppose then that
$0<i_{1}-i_{2}\leq d$. Then

$\left\lfloor\frac{i_{1}}{d+1}\right\rfloor-\left\lfloor\frac{i_{2}}{d+1}\right\rfloor\leq\left\lfloor\frac{i_{1}-i_{2}}{d+1}\right\rfloor+1\leq
1.$ (1)

If the quantity in (1) equals zero, then
$c_{2}(v_{i_{k}}^{j_{k}})=c_{1}(v_{i_{k}}^{j_{k}})$ for $k=1,2$, which is
impossible since $c_{1}$ is proper. Then

$1\leq(j_{1}+i_{1}t-j_{2}-i_{2}t)\,(\text{mod}~{}{N})+\left\lfloor\frac{i_{1}}{d+1}\right\rfloor-\left\lfloor\frac{i_{2}}{d+1}\right\rfloor\leq(N-1)+1\leq
N,$

and thus $c_{2}(v_{i_{1}}^{j_{1}})\not=c_{2}(v_{i_{2}}^{j_{2}})$.

We now prove that $c_{1}$ and $c_{2}$ are orthogonal. Suppose
$c_{1}(v_{i_{1}}^{j_{1}})=c_{1}(v_{i_{2}}^{j_{2}})$. Since $c_{1}$ is a proper
colouring, we must have that $|i_{1}-i_{2}|\geq d+1$. Since $i_{k}<m\leq
N(d+1)$ for $k=1,2$,

$|c_{2}(v_{i_{1}}^{j_{1}})-c_{2}(v_{i_{2}}^{j_{2}})|=\left|\left\lfloor\frac{i_{1}}{d+1}\right\rfloor-\left\lfloor\frac{i_{2}}{d+1}\right\rfloor\right|\,(\textrm{mod}~{}N+1)\not=0.$

Suppose finally that we are in Case 3 and let $N=\lceil\sqrt{mt}\rceil$ . By
the conditions of this case, $mt>t^{2}(d+1)^{2}$, so $N\geq t(d+1)+1$.
Consider the following two colourings $c_{1},c_{2}$ of $H(m,d,t)$. For all
$0\leq i<m$ and $0\leq j<t$, let

$\displaystyle c_{1}(v_{i}^{j})=$ $\displaystyle j+it$
$\displaystyle(\textrm{mod}~{}N),\text{ and}$ $\displaystyle
c_{2}(v_{i}^{j})=$ $\displaystyle
j+it+\left\lfloor\frac{j+it}{N}\right\rfloor$
$\displaystyle(\textrm{mod}~{}N).$

Note that $j+it<mt$.

Colouring $c_{1}$ is the same as in Case 1, so we proceed to show that $c_{2}$
is proper. Suppose that $v_{i_{1}}^{j_{1}}\not=v_{i_{2}}^{j_{2}}$ and $0\leq
i_{1}-i_{2}\leq d$.

Since $N>t(d+1)$, we have that

$\displaystyle\left\lfloor\frac{j_{1}+i_{1}t}{N}\right\rfloor-\left\lfloor\frac{j_{2}+i_{2}t}{N}\right\rfloor$
$\displaystyle\leq$
$\displaystyle\left\lfloor\frac{j_{1}+i_{1}t-(j_{2}+i_{2}t)}{N}\right\rfloor+1$
$\displaystyle\leq$
$\displaystyle\left\lfloor\frac{|j_{1}-j_{2}|+(i_{1}-i_{2})t}{N}\right\rfloor+1$
$\displaystyle\leq$
$\displaystyle\left\lfloor\frac{t-1+dt}{N}\right\rfloor+1\leq 1.$

It follows that

$\displaystyle
j_{1}+i_{1}t+\left\lfloor\frac{j_{1}+i_{1}t}{N}\right\rfloor-\left(j_{2}+i_{2}t+\left\lfloor\frac{j_{2}+i_{2}t}{N}\right\rfloor\right)$
$\displaystyle\leq$ $\displaystyle|j_{1}-j_{2}|+|i_{1}-i_{2}|t+1$
$\displaystyle\leq$ $\displaystyle(t-1)+dt+1=t(d+1)<N,$

and

$\displaystyle
j_{1}+i_{1}t+\left\lfloor\frac{j_{1}+i_{1}t}{N}\right\rfloor-\left(j_{2}+i_{2}t+\left\lfloor\frac{j_{2}+i_{2}t}{N}\right\rfloor\right)$
$\displaystyle\geq$ $\displaystyle(j_{1}-j_{2})+(i_{1}-i_{2})t+1$
$\displaystyle\geq$ $\displaystyle-(t-1)+t+0>0.$

It follows that $c_{2}(v_{i_{1}}^{j_{1}})\neq c_{2}(v_{i_{2}}^{j_{2}})$.
Hence, $c_{1}$ and $c_{2}$ are proper colourings of $H(m,d,t)$.

We will now show that $c_{1}$ and $c_{2}$ are orthogonal colourings. Suppose
that $c_{1}(v_{i_{1}}^{j_{1}})=c_{1}(v_{i_{2}}^{j_{2}})$ and
$c_{2}(v_{i_{1}}^{j_{1}})=c_{2}(v_{i_{2}}^{j_{2}})$ where $i_{1}\neq i_{2}$ or
$j_{1}\neq j_{2}$. Since $c_{1}(v_{i_{1}}^{j_{1}})=c_{1}(v_{i_{2}}^{j_{2}})$,
this implies that $i_{1}t+j_{1}=i_{2}t+j_{2}+cN$. Since $0\leq j_{k}<t$ and
$0\leq i_{k}<m$ for $k=1,2$ we have that
$0<(j_{1}-j_{2})+(i_{1}-i_{2})t<mt\leq N^{2}$, so $0<c<N$. It follows that

$\displaystyle c_{2}(v_{i_{1}}^{j_{1}})$
$\displaystyle=i_{2}t+j_{2}+\left\lfloor\frac{i_{2}t+j_{2}+cN}{N}\right\rfloor(\textrm{mod}~{}N)$
$\displaystyle=i_{2}t+j_{2}+c+\left\lfloor\frac{i_{2}t+j_{2}}{N}\right\rfloor(\textrm{mod}~{}N)$
$\displaystyle=c_{2}(v_{i_{2}}^{j_{2}})+c\,(\textrm{mod}~{}N).$

Since $c_{2}(v_{i_{1}}^{j_{1}})=c_{2}(v_{i_{2}}^{j_{2}})$, this gives that
$c\equiv 0(\textrm{mod}~{}N)$, contradicting $0<c<N$.

$\Box$

Now, we can define the clique grid graph and extend the orthogonal colouring
of $H(m,d,t)$. The clique grid graph, denoted $L(m^{2},d,t^{2})$, is obtained
by taking the strong product of $H(m,d,t)$ with itself. That is,
$L(m^{2},d,t^{2})=H(m,d,t)\boxtimes H(m,d,t)$. Alternatively,
$L(m^{2},d,t^{2})$ can be viewed as $m^{2}$ cliques of size $t^{2}$, denoted
$C_{i,j}$, where all of the vertices in $C_{i_{1},j_{1}}$ and
$C_{i_{2},j_{2}}$ are adjacent to one another if and only if
$|i_{1}-i_{2}|\leq d$ and $|j_{1}-j_{2}|\leq d$. For example, the clique grid
$L(25,1,1)$ is given in Figure 2.2.

Figure 2.2: $L(25,1,1)$

By using the orthogonal colourings of $H(m,d,t)$ from Lemma 2.1, an orthogonal
colouring of $L(m^{2},d,t^{2})$ is obtained. This comes from the fact that for
any graphs $G$ and $H$, we can use a previous result, proved in [9] along with
other graph product results.

######  Theorem 2.2 ([9]).

For any two graphs $G$ and $H$,

$O\chi(G\boxtimes H)\leq O\chi(G)O\chi(H).$

Therefore, we have the following corollary.

######  Corollary 2.3.

For all positive integers $m,d,t$,

$O\chi(L(m^{2},d,t^{2}))\leq\left\\{\begin{array}[]{lll}t^{2}(d+1)^{2}&\text{if
}m\leq t(d+1),&\text{(Case 1)}\\\ (t(d+1)+1)^{2}&\text{if }t(d+1)<m\leq
t(d+1)^{2},&\text{(Case 2)}\\\
\left(\lceil\sqrt{mt}\rceil\right)^{2}&\text{otherwise.}&\text{(Case
3)}\end{array}\right.$

In particular, if we are in Case 3 and $mt$ is a square, then
$L(m^{2},d,t^{2})$ has an optimal orthogonal colouring. Note also that
$\omega(L^{2}(m^{2},d,t^{2}))=t^{2}(d+1)^{2}$, and thus we have equality in
Case 1.

In the next section, we show that an injective graph homomorphism from dense
random geometric graphs into the clique grid graph exists with high
probability. If such a graph homomorphisms exists, then the orthogonal
colourings of $L(m^{2},d,t^{2})$ in Lemma 2.3 can be applied to the dense
random geometric graphs.

##  3 Dense Random Geometric Graphs

To obtain orthogonal colourings of dense random geometric graphs, we will show
that with high probability and for the appropriate choice of parameters,
$G\sim RG(n,r)$ is isomorphic to a subgraph of $L(m^{2},d,t^{2})$. We
distinguish two cases. First we consider $RG(n,r)$ where $r=n^{-\alpha}$,
$0<\alpha\leq 1/4$. We will see that the orthogonal chromatic number in this
case is mostly constrained by the clique number. After that we will see that
if $\alpha>1/4$, then the graph has, with high probability, an optimal
orthogonal colouring.

###  3.1 Orthogonal colourings close to the clique number

To obtain a subgraph isomorphism between a random geometric graph and a clique
grid graph, the unit square is divided into $m\times m$ equal size squares. In
particular, for $l=\frac{1}{m}$, the set $S_{ij}$ will contain the vertices of
$G$ in the square with coordinates in the subsquare
$((i-1)l,il)\times((j-1)l,jl)$.

To show that $G$ is isomorphic to a subgraph of $L(m^{2},d,t^{2})$, all of the
vertices in $S_{ij}$ are mapped to vertices in the cliques $C_{ij}$ in
$L(m^{2},d,t^{2})$. To show that this is a subgraph isomorphism with
$H\subseteq L(m^{2},d,t^{2})$, we show that with high probability, for all
$i,j$, that $|S_{ij}|\leq|C_{ij}|=t^{2}$. Additionally, we show that if two
vertices are adjacent in $G$, then their images in $H$ are adjacent.

Now, notice that two vertices $u\in C_{i_{1},j_{1}}$ and $v\in
C_{i_{2},j_{2}}$ are adjacent if and only if $|i_{1}-i_{2}|\leq d$ and
$|j_{1}-j_{2}|\leq d$. On the other hand, two vertices $u\in S_{i_{1},j_{1}}$
and $v\in S_{i_{2},j_{2}}$ are adjacent in $G$ if and only if their Euclidean
distance is less than $r$. To distinguish between Euclidean distance and the
absolute value, the Euclidean distance between two points $u$ and $v$ is
denoted by $\|u-v\|$.

We will show in Lemma 3.3 that
$\|u-v{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}}|<r$
implies that $|i_{1}-i_{2}|<\frac{r}{l}+1$ and $|j_{1}-j_{2}|<\frac{r}{l}+1$.
Therefore, we define $r=n^{-\alpha},l=\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil^{-1}$, and $d=\left\lceil\frac{n^{\frac{1}{2}-\alpha}}{\ln
n}\right\rceil+2$ so that

$\displaystyle\frac{r}{l}+1$
$\displaystyle=n^{-\alpha}\left\lceil\frac{\sqrt{n}}{\ln n}\,\right\rceil+1$
$\displaystyle\leq\frac{n^{1/2-\alpha}}{\ln n}+n^{-\alpha}+1$
$\displaystyle<\left\lceil\frac{n^{1/2-\alpha}}{\ln n}\,\right\rceil+2=d$ (2)

Therefore, Lemma 3.3 will give that if $\|u-v\|<r$ then
$|i_{1}-i_{2}|<\frac{r}{l}+1<d$. Hence, the subgraph isomorphism described
will preserve the edges. Additionally, we define two other parameters,
$t=\lceil\ln n\rceil$ and $m=\left\lceil\frac{\sqrt{n}}{\ln n}\right\rceil$.
These two parameters are defined in this way to satisfy the probabilistic
lemmas proved later. For reference, the follow parameters are used throughout
this section.

$\displaystyle t$ $\displaystyle=\lceil\ln n\rceil$ (3) $\displaystyle m$
$\displaystyle=\left\lceil\frac{\sqrt{n}}{\ln n}\right\rceil$ (4)
$\displaystyle l$ $\displaystyle=\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil^{-1}$ (5) $\displaystyle d$
$\displaystyle=\left\lceil\frac{n^{\frac{1}{2}-\alpha}}{\ln n}\right\rceil+2$
(6)

Recall that an event $E$ occurs with high probability if as $n$ tends to
infinity, the probability that $E$ occurs tends to one. We will show that with
high probability and for all $i,j$, that $|S_{ij}|\leq|C_{ij}|=t^{2}$. We
prove this result with the well-known Chernoff’s bound, which is now stated.

######  Theorem 3.1 (Chernoff’s Bound).

Suppose that $X_{1},X_{2},\dots,X_{n}$ are independent random variables taking
values in $\\{0,1\\}$. Let $X$ denote their sum and let $\mu=\mathbb{E}[X]$.
For any $\delta\geq 0$, it follows that

$\mathbb{P}(X<(1-\delta)\mu)\leq e^{-\frac{\delta^{2}\mu}{2}}\text{ and
}\mathbb{P}(X>(1+\delta)\mu)\leq e^{-\frac{\delta^{2}\mu}{3}}$

Chernoff’s bound gives exponentially decreasing bounds and can be applied to
bound the probability that $|S_{ij}|\leq|C_{ij}|$ for a single square.
However, it is required that this inequality holds for all squares in the
partition. To extend this result to all squares, the Union Bound is required.
For the events $E_{1},\dots,E_{n}$, let $\cup_{i}E_{i}$ denote the event that
at least one of the events occurs. The Union Bound is then as follows:

$\mathbb{P}(\cup_{i}E_{i})\leq\sum_{i}^{n}\mathbb{P}(E_{i}).$

######  Lemma 3.2.

For $G\sim RG(n,r)$. Let $t,m,l$ be the parameters in Equations 3, 4 and 5.
For all $1\leq i,j\leq m$, let $S_{ij}$ denote the set of vertices of $G$ in
the square $((i-1)l,il)\times((j-1)l,jl)$. With high probability and for all
$i,j$, $|S_{i,j}|\leq t^{2}$.

Proof: First, fix the indices $i$ and $j$. For all vertices $v\in V(G)$,
define the random variable $X_{v}$ as $X_{v}=0$ if $v\not\in S_{i,j}$ and
$X_{v}=1$ if $v\in S_{i,j}$. Let $X_{i,j}$ denote the sum of the random
variables. That is,

$X_{i,j}=\sum_{v\in V}X_{v}=|S_{i,j}|$

Recall that the points of $G$ are placed uniformly at random in the unit
square, which has an area of 1. Also, the area of each of the $m^{2}$
subsquares in the partition of the unit square is
$1/m^{2}=l^{2}=\left\lceil\frac{\sqrt{n}}{\ln n}\right\rceil^{-2}$. Therefore,

$\mathbb{E}(X_{v})=\mathbb{P}(X_{v}=1)=\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil^{-2}.$

Since there are $n$ points, the expected number of points in the fixed square
is given by $\mu=\mathbb{E}(X_{ij})=n\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil^{-2}\leq(\ln n)^{2}=t^{2}$. Lastly, let
$\delta=\frac{\sqrt{3\ln n}}{\sqrt{n}}\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil>0$. By applying Chernoff’s bound, it follows that

$\displaystyle\mathbb{P}(X_{i,j}>(1+\delta)\mu)$ $\displaystyle\leq
e^{-\frac{\left(\frac{\sqrt{3\ln n}}{\sqrt{n}}\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil\right)^{2}n\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil^{-2}}{3}}=e^{-\ln n}=n^{-1}$

Thus with high probability and for a fixed $i,j$,
$|S_{i,j}|=\mathbb{E}(X_{ij})\leq t^{2}$. However, to obtain our result, it is
required that with high probability and for all $i,j$, that $|S_{i,j}|\leq
t^{2}$. We obtain this by applying the Union Bound:

$\displaystyle\mathbb{P}(\cup_{i,j}\\{X_{i,j}>(1+\delta)\mu\\})$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{j=1}^{m}\mathbb{P}(X_{i,j}>(1+\delta)\mu)$
$\displaystyle\leq m^{2}n^{-1}$ $\displaystyle=\left\lceil\frac{\sqrt{n}}{\ln
n}\right\rceil^{2}n^{-1}$ $\displaystyle\leq(\ln n)^{-2}+2(\sqrt{n}\ln
n)^{-1}+n^{-1}$

Note that each of terms in this expression tends to zero as $n$ tends to
infinity. Therefore with high probability and for all $i,j$, $|S_{i,j}|\leq
t^{2}$.  $\Box$

Lemma 3.2 gives that the vertices in $S_{i,j}$ in the random geometric graph
can be mapped injectively into the cliques $C_{i,j}$ of $L(m^{2},d,t^{2})$.
Thus, one required property of the subgraph isomorphism is obtained. It
remains to show that the edges are preserved under this mapping. The following
lemma provides this property.

######  Lemma 3.3.

Let $G\sim RG(n,r)$ with $r=n^{-\alpha}$. Let $t,m,l,d$ be the parameters in
Equations 3, 4, 5, and 6. For all $1\leq i,j\leq m$, let $S_{ij}$ denote the
vertices of $G$ in the square $((i-1)l,il)\times((j-1)l,jl)$. For $u,v\in
V(G)$, suppose that $u\in S_{i_{1},j_{1}}$ and $v\in S_{i_{2},j_{2}}$. If
$uv\in E(G)$, then $|i_{1}-i_{2}|<d$ and $|j_{1}-j_{2}|<d$.

Proof: Recall that $d$ is the parameter that provides which cliques in
$L(m^{2},d,t^{2})$ are adjacent. Suppose that $u\in S_{i_{1},j_{1}}$, $v\in
S_{i_{2},j_{2}}$, and $uv\in E(G)$. Note that, for any $j$ because there are
at least $|i_{1}-i_{2}|-1$ inclusive squares between $S_{i_{1},j}$ and
$S_{i_{2},j}$, each of width $l$. Therefore, $|i_{1}-i_{2}|<\frac{r}{l}+1$.
Similarly, for any $i$, there are at least $|j_{1}-j_{2}|-1$ squares between
$S_{i,j_{1}}$ and $S_{i,j_{2}}$, each of height $l$. Therefore,
$|j_{1}-j_{2}|<\frac{r}{l}+1$. However, by the specific choice of parameters,
$\frac{r}{l}+1<d$, as in(3.1). Therefore, $|i_{1}-i_{2}|<d$ and
$|j_{1}-j_{2}|<d$.  $\Box$

Lemma 3.3 provides that the previously described mapping will preserve all of
the edges. Therefore, by combining Lemma 3.2 and Lemma 3.3 with Corollary 2.3,
we obtain the following result.

######  Theorem 3.4.

Let $t,m,l,d$ be the parameters in Equations 3, 4, 5, and 6. For $G\sim
RG(n,r)$ where $r=n^{-\alpha}$, if $0\leq\alpha\leq\frac{1}{4}$, then with
high probability

$\frac{\sqrt{3}}{2}n^{1-2\alpha}\leq O\chi(G)\leq n^{1-2\alpha}(1+o(1))$

In particular, if $\alpha=\frac{1}{4}$, then with high probability

$O\chi(G)=\sqrt{n}(1+o(1))$

Proof: Consider partitioning the unit square into $m\times m$ equal size
squares. Let $S_{ij}$ denote the vertices of $G$ in the square with dimensions
$((i-1)l,il)\times((j-1)l,jl)$. Consider the mapping that takes all of the
vertices in $S_{i,j}$ and maps them to vertices in $C_{i,j}$ in
$L(m^{2},d,t^{2})$. Lemma 3.2 and Lemma 3.3 then give that, with high
probability, $G$ is a subgraph of $L(m^{2},d,t^{2})$ through this mapping. To
apply Corollary 2.3 (Case 1 or 2) to find an orthogonal colouring of
$L(m^{2},d,t^{2})$, it is required that $m\leq t(d+1)^{2}$. By the choice of
parameters, it follows that

$\displaystyle(d+1)^{2}=\left(\frac{n^{1/2-\alpha}}{\ln n}+3\right)^{2}$
$\displaystyle\geq\left(\displaystyle{\frac{n^{1/4}}{\ln n}}+3\right)^{2}$
(since $0\leq\alpha\leq\frac{1}{4}$)
$\displaystyle\geq\displaystyle{\frac{n^{1/2}}{(\ln n)^{2}}}+9$
$\displaystyle=\displaystyle{\frac{\frac{\sqrt{n}}{\ln n}}{\ln n}}+9$
$\displaystyle\geq\displaystyle{\frac{m}{t}}.$

Therefore, since $m\leq t(d+1)^{2}$, we are in Case 1 or 2, and Corollary 2.3
can be applied to find an orthogonal colouring of $L(m^{2},d,t^{2})$. By
substituting the parameters into the bound from Corollary 2.3, it follows that

$\displaystyle O\chi(L(m^{2},d,t^{2}))$ $\displaystyle\leq(t(d+1)+1)^{2}$
$\displaystyle\leq\left((\ln n+1)\left(\frac{n^{\frac{1}{2}-\alpha}}{\ln
n}+2\right)+1\right)^{2}$ $\displaystyle\leq n^{1-2\alpha}(1+o(1))$

When $\alpha=1/4$, the upper bound approximately matches the lower bound of
$\sqrt{n}$, so this gives that $O\chi(G)\leq\sqrt{n}(1+o(1))$. On the other
hand, it is known [10] that with high probability,
$\chi(G)=\frac{\sqrt{3}}{2}n^{1-2\alpha}$. Therefore, since the orthogonal
chromatic number is at least the chromatic number, for $\alpha<1/4$ we have
that $O\chi(G)=cn^{1-2\alpha}(1+o(1))$ with high probability, where
$\frac{\sqrt{3}}{2}\leq c\leq 1$.  $\Box$

###  3.2 Optimal orthogonal colourings when $r<n^{-1/4}$

We now consider the case where $r\leq cn^{-1/4}$, $c\in(0,1)$, and establish
that in this case we have an optimal orthogonal colouring. Again, we proceed
by partitioning the unit square into a similar structure as the clique grid.
Whereas in the previous case we had an approximately equal number of points in
each cell, in this case we wish to control the number of points in each cell
exactly. The trade-off is that the cells will not be of equal size, and may be
rectangular rather than square.

We assume without loss of generality that $n$ is a perfect square. Since we
are considering the dense case, we will assume that $n$ is large enough so
that $r\leq(\ln{n})^{2}n^{-1/2}$. Let $G\sim RG(n,r)$ and let $P=V(G)$. So $P$
is a collection of points in the unit square, selected independently and
uniformly. Let $n=m^{2}t^{2}$ for some integers $1\leq t\leq m$ (we will later
add restrictions on $t$ and $m$). Divide the unit square into $m^{2}$ cells
containing exactly $t^{2}$ points from $P$ in the following way. First, order
all of the $n$ points in $P$ according to their $y$-values. That is, suppose
that $y_{1}<y_{2}<\dots<y_{n}$. Then for $0\leq i\leq m$, define $y_{i}^{*}$
as

$y_{i}^{*}=\left\\{\begin{array}[]{ll}0&\text{ if }i=0\\\ {y_{itn}}&\text{ if
}1\leq i<{m}\\\ 1&\text{ if }i=m\end{array}\right.$ (7)

Now, let $S_{i}=\\{(x,y)\in[0,1]^{2}:y_{i-1}^{*}<y\leq y_{i}^{*}\\}$. By
definition, the sets $S_{i}$ partition the unit square into $m$ strips, each
containing $tn=mt^{2}$ vertices. It is important to note that the $x$-values
of the points in each strip are still random. This is because they are
independent of the $y$-values. Now, for each $i,1\leq i\leq t$, we will order
the $x$-values of the points in each of the sets $S_{i}$. That is, we suppose
that $x_{i,1}<x_{i,2}<\dots<x_{i,mt^{2}}$. Then, define $x_{i,j}^{*}$, $0\leq
j\leq m$, as

$x_{i,j}^{*}=\left\\{\begin{array}[]{ll}0&\text{ if }j=0\\\
x_{i,jt^{2}}&\text{ if }1\leq j<m\\\ 1&\text{ if }j=m\end{array}\right.$ (8)

Now, let $S_{i,j}=S_{i}\cap\\{(x,y)\in[0,1]^{2}:x_{i,j-1}^{*}<x\leq
x_{i,j}^{*}\\}$. That is, the $S_{i,j}$’s partition each strip into $m$ cells,
each containing $t^{2}$ vertices of $G$. Now that we have our partition of the
unit square, we can define our mapping of vertices in $G$ to vertices in
$L(m^{2},d,t^{2})$, where $d$ is yet to be determined. The mapping is so that
for each $(i,j)$, all points in $S_{i,j}$ are mapped injectively to the
vertices of clique $C_{i,j}$ in any order.

Let $F:P\to[n]^{2}$, be a mapping from $P$ to the vertices of
$L(m^{2},d,t^{2})$ as described above. By definition $F$ is a bijection. If
$F$ is a homomorphism then any orthogonal colouring of $L(m^{2},d,t^{2})$
induces an orthogonal colouring of $G$: assign each vertex $v$ of $G$ the
colours of $F(v)$. We can then apply Lemma 2.3 to obtain an optimal orthogonal
colouring of $L(m^{2},d,t^{2})$ and thus also of $G$. To determine the correct
value of $d$ and to show that the mapping $F$ is a homomorphism (with high
probability), we need to bound the values of the variables $y_{i}^{*}$ and
$x_{i,j}^{*}$. For this, we will use the following two lemmas, which follow
directly from the Chernoff bound, stated earlier as Theorem 3.1 .

If the points that determine the random geometric graph were evenly spaced in
the unit square, then we would have that $y_{i}^{*}=\frac{i}{m}$ for all $i$.
We can use the following lemma to establish that this is approximately true.
In the following, we say that an event $E$ holds _with exponential probability
(w.e.p.)_ if the probability that $E$ does not hold is exponentially small.
Precisely, $E$ holds w.e.p. if $P(E)=1-e^{-\Omega(-(\ln n)^{2})}$.

######  Lemma 3.5.

Let $P$ be a collection of $n=m^{2}t^{2}$ points, chosen u.a.r. from the unit
square. If $\delta=\frac{2\ln n}{\sqrt{n}}=\frac{2\ln n}{mt}$, then with
exponential probability, for all points $(a,b)\in P$ and for all integers
$1\leq s<m$, if

$\left|\\{(x,y)\in P:y\leq b\\}\right|=smt^{2},$

then

$\left|b-\frac{s}{m}\right|\leq\delta.$

Proof: Fix $p_{0}=(a,b)\in P$ and $1\leq s<m$, and assume
$b-\frac{s}{m}>\delta$. Let $X=|\\{(x,y)\in P:y\leq b\\}|$. Relative to point
$(a,b)$ all other $n-1$ points are chosen independently u.a.r. in the unit
square. For all $p=(x,y)\in P\setminus\\{p_{0}\\}$, let $X_{p}$ be the
indicator variable of $\\{y\leq b\\}$, and let $X=\sum_{p\in
P\setminus\\{p_{0}\\}}X_{p}$. Then ${\mathbb{E}}(X_{p})=b$. Let $n$ be large
enough so that $\delta n\geq 2$. Then

$\mu={\mathbb{E}}(X)=b(n-1)>(\frac{s}{m}+\delta)n-1\geq smt^{2}+\delta
n/2=smt^{2}+mt\ln(n).$

By the Chernoff bound,

${\mathbb{P}}(X=smt^{2})\leq{\mathbb{P}}(X<(1-\frac{mt\ln{n}}{\mu})\mu)\leq
e^{-\frac{n(\ln{n})^{2}}{3\mu}}$

By definition, $\mu\leq n-1<n$, so the absolute value of the exponent is
greater than $\ln(n)^{2}/3$, and thus the probability that $X=smt^{2}$ is
exponentially small. Thus w.e.p. if $b-\frac{s}{m}>\delta$ then
$\left|\\{(x,y)\in P:y\leq b\\}\right|\neq smt^{2}$. With a similar argument,
we can show that, if $\frac{s}{m}-b>\delta$ then w.e.p. we have that
$\left|\\{(x,y)\in P:y\leq b\\}\right|\neq smt^{2}$.

For any $p=(a,b)\in P$, let $\mathcal{E}_{p}$ be the event that
$\left|\\{(x,y)\in P:y\leq b\\}\right|=smt^{2}$ and
$\left|b-\frac{s}{m}\right|>\delta$. We saw that
${\mathbb{P}}(\mathcal{E}_{p})$ is exponentially small. Since $|P|=n$, we have
by a union bound that ${\mathbb{P}}(\cup_{p\in P}\mathcal{E}_{p})$ is also
exponentially small. This concludes the argument.  $\Box$

Lemma 3.5 says that w.e.p. if the number of points with $y$-value less than or
equal to $b$ is some multiple $s$ of $mt^{2}$, then
$\left|b-\frac{s}{m}\right|\leq\delta=2\ln(n)/mt$. Since the $y_{i}^{*}$’s are
the positions where this would occur, we obtain the following corollary.

######  Corollary 3.6.

Consider $n=m^{2}t^{2}$ points chosen uniformly at random from the unit
square, and let $y_{i}^{*}$, $0\leq i\leq m$ be defined as in (7). With
exponential probability, for all $1\leq i<m$,

$|y_{i}^{*}-\frac{i}{m}|\leq\frac{2\ln n}{mt}.$ (9)

Corollary 3.6 gives an upper and lower bound on the position of $y_{i}^{*}$.
This will be useful in determining the parameter $d$ and proving that the map
$F$ is indeed a homomorphism. We now proceed to bound the positions of the
$x_{i,j}^{*}$.

######  Lemma 3.7.

Let $P$ be a collection of $n=m^{2}t^{2}$ points, chosen u.a.r. from the unit
square. Let $\delta=\frac{2\ln n}{t^{1/2}n^{1/4}}=\frac{2\ln n}{t\sqrt{m}}$.
Then with exponential probability, for all points $p_{1}=(a_{1},b_{1})$,
$p_{2}=(a_{2},b_{2})$, $p_{3}=(a_{3},b_{3})\in P$, and for all integers $1\leq
s<m$,

if $\displaystyle\left|\\{(x,y)\in P:b_{2}<y\leq b_{3}\\}\right|=t^{2}m$ and
$\displaystyle\left|\\{(x,y)\in P:b_{2}<y\leq b_{3},\,x\leq
a_{1}\\}\right|=st^{2},$ then
$\displaystyle\left|a_{1}-\frac{s}{m}\right|\leq\delta.$

Proof: Fix $p_{i}=(a_{i},b_{i})\in P$ for $i=1,2,3$ and fix $1\leq s<m$. Let
$P_{0}=\\{(x,y)\in P:b_{2}<y\leq b_{3}\\}$ and assume $|P_{0}|=t^{2}m=tn$.
Also assume that $a_{1}-\frac{s}{m}>\delta$.

Let $X=|\\{(x,y)\in P_{0}\setminus\\{p_{1}\\}:x\leq a_{1}\\}|$. Since
$x$-values and $y$-values of the randomly chosen points are independent, $X$
is the sum of $t^{2}m-1$ independent Bernouilli variables with success
probability $a_{1}$. Thus

$\mu={\mathbb{E}}(X)=a_{1}(t^{2}m-1)\geq
a_{1}t^{2}m-1>(\frac{s}{m}+\delta)t^{2}m-1\geq st^{2}+t\sqrt{m}\ln(n),$

for $n$ large enough so that $\delta t^{2}m\geq 2$. By the Chernoff bound,

${\mathbb{P}}(X=st^{2})\leq{\mathbb{P}}(X<(1-\frac{t\sqrt{m}\ln{n}}{\mu})\mu)\leq
e^{-\frac{t^{2}m(\ln{n})^{2}}{3\mu}}$

By definition, $\mu\leq|P_{0}|=t^{2}m$, so the absolute value of the exponent
is at least $\ln(n)^{2}/3$, and thus the probability that $X=smt^{2}$ is
exponentially small. Thus w.e.p. if $b-\frac{s}{m}>\delta$ then
$\left|\\{(x,y)\in P:y\leq b\\}\right|\neq smt^{2}$. With a similar argument,
we can show that, if $\frac{s}{m}-b>\delta$ then w.e.p. we have that
$\left|\\{(x,y)\in P:y\leq b\\}\right|\neq smt^{2}$. Thus, the implication
holds for this particular choice of $p_{1},p_{2},p_{3}$ and $s$. The result
then follows by a union bound.

$\Box$

Lemma 3.7 says that if $b_{1}$ and $b_{3}$ border a strip containing $t^{2}m$
points, and there are $st^{2}$ points in this strip with $x$-value less than
$a_{1}$, then $|a_{1}-\frac{s}{m}|\leq\delta=2\ln{n}/t\sqrt{m}$. Since the
$x_{i,j}^{*}$’s are the positions where this would occur, we obtain the
following corollary.

######  Corollary 3.8.

Consider $n^{2}=m^{2}t^{2}$ points chosen uniformly at random from the unit
square, and let $x_{i,j}^{*}$, $0\leq i,j\leq m$ be defined as in (8). With
exponential probability, for all $1\leq i,j<m$,

$|x_{i,j}^{*}-\frac{j}{m}|\leq\frac{2\ln n}{t\sqrt{m}}.$ (10)

With these two results in hand, we now bound the Euclidean distance between
any pair of points in $S_{i,j}$ and $S_{i^{\prime},j^{\prime}}$.

######  Corollary 3.9.

Assume that $y_{i}^{*}$ and $x_{i,j}^{*}$ satisfy bounds (9) and (10) for all
$1\leq i,j\leq m$. Then for all points $p_{1}\in S_{i,j}$ and $p_{2}\in
S_{i^{\prime},j^{\prime}}$ we have that

$\|p_{1}-p_{2}\|\geq\frac{1}{m}\left(\max\\{|i-i^{\prime}|,|j-j^{\prime}|\\}-1-\frac{4\sqrt{m}\ln{n}}{t}\right).$
(11)

Proof: Let $p_{1}=(a_{1},b_{1})$ and $p_{2}=(a_{2},b_{2})$. Each cell
$S_{i,j}$ is bounded below and above by $y_{i-1}^{*}$, $y_{i}^{*}$, and left
and right by $x_{i,j-1}^{*}$ and $x^{*}_{i,j}$. Suppose first (by possible
relabelling) that $b_{2}\geq b_{1}$, and thus $i^{\prime}\geq i$. Then by
Corollary 3.6,

$\|p_{1}-p_{2}\|\geq b_{2}-b_{1}\geq
y^{*}_{i^{\prime}-1}-y^{*}_{i}\geq(i^{\prime}-1-i)/m-2\left(\frac{2\ln{n}}{mt}\right).$

Since $\sqrt{m}\geq 1$, the bound (11) follows.

Next assume _wlog_ that $a_{1}\leq a_{2}$ and thus $j^{\prime}\geq j$ (where
$i,i^{\prime}$ can have any order). Then by Corollary 3.8,

$\|p_{1}-p_{2}\|\geq|a_{2}-a_{1}|\geq|x^{*}_{i^{\prime},j^{\prime}-1}-x^{*}_{i,j}|\geq(j^{\prime}-1-j)/m-2\left(\frac{2\ln{n}}{t\sqrt{m}}\right).$

This matches the bound (11).  $\Box$

We can use this corollary directly to prove a lemma that establishes when the
map $F$ is a homomorphism.

######  Lemma 3.10.

Let $n=m^{2}t^{2}$ where $1\leq t\leq m$, and assume $G\sim RG(n,r)$. If
$d>rm+4\sqrt{m}\ln{n}/t$, then w.e.p. there is a bijective homomorphism from
$G$ into $L(m^{2},d,t^{2})$.

Proof: Assume that $y_{i}^{*}$ and $x_{i,j}^{*}$ satisfy bounds (9) and (10)
for all $1\leq i,j\leq m$. Let $F$ be the bijection from $G$ to $L(m^{2},d,t)$
defined by mapping each set $S_{i,j}$ to the corresponding clique $C_{i,j}$
(in any order). It suffices to show that $F$ preserves edges. Note that for
points $p_{1},p_{2}\in P$, $p_{1}$ is adjacent to $p_{2}$ in $G$ if and only
if $\|p_{1}-p_{2}\|\leq r$. Therefore we need to prove that for all $p_{1}\in
S_{i,j}$ and $p_{2}\in S_{i^{\prime},j^{\prime}}$, if $\|p_{1}-p_{2}\|\leq r$
then $\max\\{|i^{\prime}-i|,|j^{\prime}-j|\\}\leq d$. We prove the converse.
Assume that $\max\\{|i^{\prime}-i|,|j^{\prime}-j|\\}\geq d+1$. Then by
Corollary 3.9 we have that

$\|p_{1}-p_{2}\|\geq\frac{1}{m}\left(d-4\frac{\sqrt{m}\ln{n}}{t}\right)>r,$

where the last inequality follows from the condition on $d$. This shows that
$F$ is a (bijective) homomorphism.  $\Box$

The last step in establishing that $RG(n,r)$ has an optimal orthogonal
colouring when $r<n^{-1/4}$ is to show that there are parameters $m,d,t$ such
that $L(m^{2},d,t^{2})$ has an optimal orthogonal colouring.

######  Theorem 3.11.

Fix $c\in(0,1)$ and assume $r\leq cn^{-1/4}$. Let $G\sim RG(n,r)$. If
$n=m^{2}t^{2}$ where $\ln(n)^{4}\leq t\leq rn^{1/2}/\ln(n)$, then a.a.s. $G$
has an optimal orthogonal colouring.

Proof: Fix $c\in(0,1)$ and assume $r=r(n)=cn^{-1/4}$. Take $d=\lfloor
rm+4\sqrt{m}\ln(n)/t\rfloor+1$, so

$d+1\leq rm\left(1+\frac{2}{rm}\right)+\frac{4\sqrt{m}\ln n}{t}.$ (12)

Now since $mt=n^{1/2}$ and $t\leq rn^{1/2}/\ln{n}$,

$rm=rn^{1/2}/t\geq\ln(n)\rightarrow\infty\text{ as }n\rightarrow\infty,$

and thus $2/rm=o(1)$. Fix $\epsilon>0$ and let $n$ be large enough so that

$\left(1+\frac{2}{rm}\right)^{2}<\frac{1-\epsilon}{c^{2}},$ (13)

and thus

$\left(1+\frac{2}{rm}\right)^{2}r^{2}m^{2}<(1-\epsilon)n^{-1/2}m^{2}.$

Then we have that

$\displaystyle t(d+1)^{2}$ $\displaystyle\leq$ $\displaystyle
t\left(rm\left(1+\frac{2}{rm}\right)+\frac{4\sqrt{m}\ln n}{t}\right)^{2}$
$\displaystyle<$
$\displaystyle(1-\epsilon)tn^{-1/2}m^{2}+8\sqrt{(1-\epsilon)}n^{-1/4}m^{3/2}\ln
n+16m(\ln n)^{2}/t$ $\displaystyle\leq$ $\displaystyle
m(1-\epsilon+8t^{-1/2}+16/(\ln n)^{2})$ $\displaystyle=$ $\displaystyle
m\left(1-\epsilon+o\left(\frac{1}{\ln n}\right)\right),$

where the last two lines follow from the fact that $t\geq\ln(n)^{4}$.

Therefore, for large enough $n$ we have that $t(d+1)^{2}<m$. Then we are in
Case 3 of Theorem 2.3, and $O\chi(G)=O\chi(L(m^{2},d,t^{2})=mt=\sqrt{n}$.
Therefore, if $y_{i}^{*}$ and $x_{i,j}^{*}$ satisfy bounds (9) and (10) then
$G$ has an optimal orthogonal colouring. By Lemma 3.5 and Lemma 3.7, this
occurs w.e.p.  $\Box$

Note that Theorem 3.4 only applies for values of $n$ that have a factor
$t\geq(\ln n)^{4}$. There are, of course, infinitely many such values. We
believe that the proof of the theorem can be adjusted to accommodate values of
$n$ that do not have a large factor. In that case, we can divide the unit
square in cells so that most cells contain $t^{2}$ points, but at most one
square in each slice $S_{i}$ has less than $t^{2}$ points. We have not pursued
this argument since it promised to be overly technical.

## References

  * [1] Stephan Dominique Andres, Melissa Huggan, Fionn Mc Inerney, and Richard J Nowakowski, _The orthogonal colouring game_ , Theoretical Computer Science 795 (2019), 312–325.
  * [2] Dan Archdeacon, JH Dinitz, and Frank Harary, _Orthogonal edge colorings of graphs_ , Congressus Numerantium 47 (1985), 49–67.
  * [3] Serge C Ballif, _Upper bounds on sets of orthogonal colorings of graphs_ , Discrete Mathematics 313 (2013), no. 20, 2195–2205.
  * [4] Yair Caro and Raphael Yuster, _Orthogonal colorings of graphs_ , the electronic journal of combinatorics (1999), R5–R5.
  * [5] Jeannette Janssen and Kyle MacKeigan, _Orthogonal colourings of cayley graphs_ , Discrete Mathematics 343 (2020), no. 11, 112079.
  * [6] Robert Kozma and Marko Puljic, _Random graph theory and neuropercolation for modeling brain oscillations at criticality_ , Current opinion in neurobiology 31 (2015), 181–188.
  * [7] Kyle MacKeigan, _An exploration of orthogonal colourings_ , (2021), 94.
  * [8] , _Independent coverings and orthogonal colourings_ , Discrete Mathematics 344 (2021), no. 8, 112431.
  * [9] , _Orthogonal colourings of tensor graphs_ , arXiv preprint arXiv:2009.13576 (2022), 8.
  * [10] Colin McDiarmid, _Random channel assignment in the plane_ , Random Structures & Algorithms 22 (2003), no. 2, 187–212.
  * [11] Mathew D Penrose, _On k-connectivity for a geometric random graph_ , Random Structures & Algorithms 15 (1999), no. 2, 145–164.


# Statistical Mechanical Interpretation of 2D Pauli Crystals

Aditya Mishra<EMAIL_ADDRESS>Department of Physics, Birla
Institute of Technology, Mesra, Ranchi - 835215, India
Swarnava Mitra<EMAIL_ADDRESS>Department of Physics, Birla Institute
of Technology, Mesra, Ranchi - 835215, India

###### Abstract

A manifestation of the Pauli Exclusion Principle is observed when fermions are
trapped in the ground state of a 2D harmonic oscillator trap at very low
temperatures. This non-interaction of fermions results in the formation of
Pauli crystals. This work introduces a statistical mechanical interpretation
of the principles that led to the observation of Pauli crystals by calculating
the energy, radius and other parameters of the non-interacting arrangement of
ultra-cold fermions. This model approaches the problem from two different
directions, namely fermion degeneracy and harmonic oscillator treatment.
Unifying the two different approaches gives a more comprehensive and robust
description of the various parameters of Pauli crystals.

##  I Introduction

Fermions, i.e., particles with half-integer spin, are known to obey the Pauli
Exclusion Principle (PEP) which is a consequence of the Fermi-Dirac
statistics. PEP simply states that no two fermions with the same spin can ever
exist in the same quantum state simultaneously. In their paper, Gajda et al.
gajda16  had theorised crystal structures as a result of this non-interaction
between fermions due to the PEP and the resulting formation of structures due
to their geometric arrangement. Although they are called Pauli crystals, the
name itself is a misnomer. Pauli crystals have no translational symmetry and
lack long range order- properties that are present in any crystal. Pauli
crystals were first observed in May, 2020 by a group led by M. Holten from the
University of Heidelberg, Germany. These crystals form an interesting topic
for study and this paper presents an alternative point of view from the
existing literature. The novelty of this paper lies in the statistical
mechanical description of radius, energy and other parameters of the crystals.
The results presented in subsequent sections match closely with the
experimental values obtained by Holten et al. in their paper. holten

Previous attempts have been made to come up with a model to explain the
behaviour and properties of Pauli crystals.anal  This paper is an attempt to
describe a more accurate theoretical interpretation of the higher order
correlations arising due to PEP. Unlike the previous attempts, this paper has
stressed on fermion degeneracy and used it as a stepping stone to derive the
parameters. Pauli crystals have always been approached by the harmonic
oscillator treatment. This paper takes a different approach and takes the
fermion degeneracy route. Finally, unifying the two different approaches forms
a robust and succinct description of Pauli crystals.

##  II Origin and imaging of Pauli crystals

This section is based on the work done in Refs. holten ; nandini ; gajda17 ;
chiu ; prev ; gajda20 ; gajda21 . PEP states that no two identical fermions
can ever occupy the same quantum state simultaneously. PEP applies to only
fermions, bosons do not obey this; they have the freedom to crowd. A more
appropriate mathematical and quantum mechanical approach can be presented with
the use of the Slater determinant.

Fermions are described by antisymmetric wave functions. An antisymmetric wave
function can be mathematically described as follows:

$\Psi(\mathbf{x}_{1},\mathbf{x}_{2})=-\Psi(\mathbf{x}_{2},\mathbf{x}_{1})$ (1)

To approximate the wave function of a two-particle case with coordinates
$\mathbf{x}_{1}$ and $\mathbf{x}_{2}$, we have the Slater determinant. It can
be expressed as

$\displaystyle\Psi(\mathbf{x}_{1},\mathbf{x}_{2})$
$\displaystyle=\frac{1}{\sqrt{2}}\\{\chi_{1}(\mathbf{x}_{1})\chi_{2}(\mathbf{x}_{2})-\chi_{1}(\mathbf{x}_{2})\chi_{2}(\mathbf{x}_{1})\\}$
(2)
$\displaystyle=\frac{1}{\sqrt{2}}\begin{vmatrix}\chi_{1}(\mathbf{x}_{1})&\chi_{2}(\mathbf{x}_{1})\\\
\chi_{1}(\mathbf{x}_{2})&\chi_{2}(\mathbf{x}_{2})\end{vmatrix},$

Where the coefficient is the Normalization factor. This wave function is now
antisymmetric and no longer distinguishes between fermions. Moreover, it also
goes to zero if any two spin orbitals of two fermions are the same. This is
equivalent to satisfying the Pauli exclusion principle.

The expression can be generalised to any number of fermions by writing it as a
determinant. For an N-electron system, the Slater determinant is defined as

$\displaystyle\Psi(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{N})$
$\displaystyle=\frac{1}{\sqrt{N!}}\begin{vmatrix}\chi_{1}(\mathbf{x}_{1})&\chi_{2}(\mathbf{x}_{1})&\cdots&\chi_{N}(\mathbf{x}_{1})\\\
\chi_{1}(\mathbf{x}_{2})&\chi_{2}(\mathbf{x}_{2})&\cdots&\chi_{N}(\mathbf{x}_{2})\\\
\vdots&\vdots&\ddots&\vdots\\\
\chi_{1}(\mathbf{x}_{N})&\chi_{2}(\mathbf{x}_{N})&\cdots&\chi_{N}(\mathbf{x}_{N})\end{vmatrix}$
(3)

The normalization constant is implied by noting the number N, and only the
one-particle wavefunction is written.

As a consequence of the PEP, a few noninteracting fermions trapped by
untracold lasers self-organize into a periodic structure called a Pauli
crystal. Pauli crystals represent the most probable arrangement of fermions
when they have to fill ground state energy levels in an N-fermion system after
being cooled to low temperatures. These geometric structures are not symmetric
as one would expect ’crystals’ to be (at least in the 2D case) and lack the
regularity of 2D polyhedral structures. Pauli Crystals are unique in this way.

The N-fermion system should ideally be a very weakly interacting system. In
case of an interacting system, the crystals would not be visible. For an
N-particle system, as mentioned before, the wave function can be determined by
the Slater determinant. Here too the same can be done and will be given by

$\Psi(r_{1},...,r_{N})=\sqrt{\frac{1}{N!}}\det{[\psi_{i}(r_{k})]}$ (4)

The single particle wave functions of an oscillator bound in a 2D harmonic
trap is given by

$\Psi_{p,q}(x,y)=\frac{e^{-(\frac{x^{2}+y^{2}}{2})}H_{p}(x)H_{q}(y)}{\sqrt{2^{p+q}p!q!\pi}}$
(5)

where $H_{p}$ is the $p^{th}$ order Hermite polynomial and $x,y$ are in
harmonic oscillator units. The single-particle energy corresponding to these
states is $E_{pq}=(p+q+1)\hbar\omega=(n+1)\hbar\omega$ where $n=p+q$ is the
total excitation number and each energy level is $(n+1)$-fold degenerate. This
wave function in turn gives the probability density function which can be
maximised using the Monte-Carlo algorithm. This gives us the theoretical
arrangement of the fermions in the crystal.

The experimental detection and imaging of a Pauli crystal has two important
parts. The first one is N non-interacting ultracold fermions trapped in a 2D
harmonic potential and the second one is single shot imaging of the resulting
geometric structure in terms of either position or momentum. Each single shot
of the system of fermions determines the existence of a particular
correlation. This process is repeated to recover all such correlations formed
by the particles. Due to the rotational symmetry being broken with each
individual experiment, the images obtained are found to be rotated by some
angle with respect to an arbitrary axis. All N images have slightly different
angular orientation so they will have to be rotated and then averaged together
about the centre of mass of the system to reveal the correlations that we term
Pauli crystals. Holten et al. holten  have taken the particle momentum into
consideration to determine the geometries arising out of the Pauli crystal and
their experiment presents a practical showcase of the PEP.

##  III Total energy from fermion degeneracy

In this section, we derive the total energy of Pauli crystals from the fermion
degeneracy approach.

###  III.1 Energy of the crystal

Consider a fermion is captured in a 2-D box of sides L. This box can also be
thought of as an area of zero potential surrounded by walls of infinitely high
potential. The fermion cannot penetrate infinitely high potential barriers.

Solving the Schrödinger equation for a 2-D well we get,

$\psi_{n_{x}n_{y}}=\frac{2}{L}\sin{\left(\frac{n_{x}\pi}{L}x\right)}\sin{\left(\frac{n_{y}\pi}{L}y\right)}$
(6)

The corresponding energy eigenvalues are:

$E_{n_{x}n_{y}}=\frac{\pi^{2}\hbar^{2}}{2mL^{2}}(n_{x}^{2}+n_{y}^{2})$ (7)

Fermions with the highest allowed energy in this system will be at the Fermi
Energy $E_{f}$

$E_{f}=\frac{\pi^{2}\hbar^{2}}{2mL^{2}}R^{2}$ (8)

Where $R^{2}=n_{x}^{2}+n_{y}^{2}$ is the radius in R-space.

Therefore, number of energy eigen value points in R-space is given by

$N=\pi R^{2}\times
2\times\left(\frac{1}{2}\times\frac{1}{2}\right)=\frac{\pi}{2}R^{2}$ (9)

The factor of 2 is multiplied for the two spins and the halves are introduced
to remove redundant $\pm n_{i}$.
Hence the value of $R^{2}$ becomes,

$R^{2}=\frac{2}{\pi}N$ (10)

And, the value of $E_{f}$ becomes,

$E_{f}=\frac{\pi^{2}\hbar^{2}}{2mL^{2}}\left(\frac{2N}{\pi}\right)=\frac{\pi\hbar^{2}}{m}\left(\frac{N}{L^{2}}\right)$
(11)

The number density of the fermions is given by

$\sigma=\frac{N}{L^{2}}=\frac{N}{V}$ (12)

Where $V=L^{2}$ has been chosen to represent the area; analogous to the volume
for 3-D systems.
Substituting the value of $\sigma$ in eqn (6) we get

$E_{f}=\frac{\pi\hbar^{2}}{m}\sigma$ (13)

The density of states for a 2-D system is given by

$g(E)=\frac{m}{\pi\hbar^{2}}$ (14)

This can be easily derived using a treatment similar to what we have done
above. However, it can be concluded logically that the density of states for a
2-D system is independent of the energy. Since, as soon as some energy is
provided to the particles, a significant number of states are available to
them.

The total energy can be computed by integrating the combined energy of all the
states below the state that has the Fermi energy

$U=\int_{0}^{E_{f}}E.g(E)\,dE=\frac{mL^{2}}{\pi\hbar^{2}}\frac{E_{f}^{2}}{2}=\frac{mL^{2}}{2\pi\hbar^{2}}\left(\frac{\pi\hbar^{2}}{m}\right)^{2}\sigma^{2}=\frac{\pi\hbar^{2}}{2m}\sigma^{2}L^{2}$
(15)

The equation can be rearranged in the form

$U=\frac{\pi\hbar^{2}}{2m}\left(\frac{N^{2}}{V}\right)$ (16)

Eqn (16) gives the total energy of a Pauli crystal.

###  III.2 Energy in harmonic oscillator units

We use natural harmonic oscillator units. The linear unit of the ground state
wavefunction in a cartesian direction is given by
$a_{0}=\sqrt{\hbar/m\omega}$.pathria

Energy is in units of $E_{0}=\hbar\omega$.

Converting Eqn (16) into natural harmonic oscillator units would somewhat
simplify it and make it more comprehensive. Also, the data in Holten et al.
holten  is given in units of harmonic oscillator. This makes it easier for
comparison with experimental values.

Let the radius of the crystal in harmonic oscillator units be $r$.

Therefore, the actual radius of the crystal $R=ra_{0}$.

Thus, the actual area of the crystal becomes

$V=\pi R^{2}=r^{2}\frac{\pi\hbar}{m\omega}$ (17)

According to Eqn (16), the total energy is given by

$U=\frac{\pi\hbar^{2}}{2m}\left(\frac{N^{2}}{V}\right)=\frac{\pi\hbar^{2}}{2m}\left(\frac{N^{2}}{r^{2}\frac{\pi\hbar}{m\omega}}\right)=\frac{N^{2}}{2r^{2}}\hbar\omega$
(18)

Therefore, in harmonic oscillator units the total energy of a Pauli crystal is
given by

$U=\frac{N^{2}}{2r^{2}}$ (19)

Where $N$ is the total number of particles in the crystal and $r$ is the
radius of the crystal in harmonic oscillator units.

###  III.3 Comparison with experimental data

The total number of fermions $N=6$ and the radius is $r\approx 1.14$. The
exact figure was not reported in Ref. holten . This value has been taken from
Figure 2c of Ref. holten .

According to Eqn (19), the total energy of the crystal (in units of $E_{0}$)
turns out to be

$U=13.85$ (20)

The theoretical value in Ref. holten (in units of $E_{0}$) is

$U=14$ (21)

This is very close to the value from our calculations with an error of only
$1.1\%$. The error stems solely from the value of the radius.
And, the experimentally determined value is

$U=13.1$ (22)

The experimental value deviates from our calculated value by about $7.1\%$.

It must be noted that the paper itself quoted an experimental error of $6\%$.

One can be quite apprehensive of the utility of this treatment of a Pauli
crystal. This only gives an approximate value that is also dependent on the
measured radius of the crystal system. Moreover, treating the fermions in the
crystal as harmonic oscillators would eliminate the above two drawbacks.
However, if we have some patience we shall observe this will help us to
predict the radius as well as the energy independent of each other.

##  IV Total energy from harmonic oscillator treatment

In this section, we derive the total energy of Pauli crystals by treating the
fermions as harmonic oscillators. To ease out this process, we define a
quantity called the order of the crystal.

###  IV.1 Order of crystal

Due to the Pauli exclusion principle, fermions are filled into the energy
levels in an ordered fashion. They progress in series of natural numbers as
1,2,3,…

Therefore, total number of fermions in a Pauli crystal is of form

$N=1+2+3+...+k=\frac{k(k+1)}{2}$ (23)

Where, $k$ is a natural number i.e., $k\in\mathbb{N}$ .

Here $k$ can be deemed as the order of the Pauli crystal that gives us the
total number of fermions in the crystal.

Figure 1: Crystals of (a) order 1 (b) order 2 (c) order 3. Image from Ref.
holten

For a crystal of order 1 the total number of fermions is 1 i.e., only one at
the center. For a crystal of order 2 the total number of fermions is 3, all
residing in one single orbit. For a crystal of order 3, total number of
fermions is 6 with one at the centre and the other five in an orbit around the
centre.

###  IV.2 Energy of the $k$-th order crystal

The energy of the single particle states is given by $E=(n+1)\hbar\omega$,
where $n$ is total excitation number of the degenerate energy levels. The
$n$-th energy level is $(n+1)$-fold degenerate.

For the total energy of the $k$-th order or $N=\frac{k(k+1)}{2}$ ground state,
we need to sum over the energies of all $N$ fermions. Keeping the mind the
degeneracy, the $n$-th energy level can be occupied by $(n+1)$ fermions.

The result is as follows :

1 fermion in the n=0 level : $E=1\hbar\omega$

2 fermions in the n=1 level: $E=(2\times 2)\hbar\omega=4\hbar\omega$

3 fermions in the n=2 level: $E=(3\times 3)\hbar\omega=9\hbar\omega$

Total energy for $N=1+2+...+n=\frac{n(n+1)}{2}$ fermions is
$[1^{2}+2^{2}+3^{2}+...+n^{2}]\hbar\omega$.

Clearly, $\frac{n(n+1)}{2}=\frac{k(k+1)}{2}$ implies $n=k$.

Therefore, the total energy of the $k$-th order

$U=(1^{2}+2^{2}+3^{2}+...+k^{2})\hbar\omega=\frac{k(k+1)(2k+1)}{6}\hbar\omega$
(24)

Rewriting Eq (24) in terms of $N$ and in harmonic oscillator units, we get

$U=\frac{N}{3}\sqrt{8N+1}$ (25)

Despite containing a square root and division by 3, U will always be an
integer since it is the sum of the squares of natural numbers.

###  IV.3 Comparison with data

The following energies are in harmonic oscillator units.

From Eq (25), the total energy of a 2nd order crystal with $N=3$ is $U=5$.

The total energy of a 3rd order crystal with $N=6$ is $U=14$.

The total energy of a 4th order crystal with $N=10$ is $U=30$.

##  V Radius of a Pauli crystal

From Eq (19) and (25),

$\frac{N^{2}}{2r^{2}}=\frac{N}{3}\sqrt{8N+1}$ (26)

Therefore, the radius in harmonic oscillator units

$r=\left(\frac{3N}{2\sqrt{8N+1}}\right)^{\frac{1}{2}}$ (27)

In Eq (27), the radius depends on one variable only. We can calculated the
radius of crystal by knowing only the number of fermions it contains.

Rewriting Eq (27) in terms of order $k$

$r=\sqrt{\frac{3k(k+1)}{4(2k+1)}}$ (28)

For $N=3$, the radius $r=0.949$.

For $N=6$, the radius $r=1.134$. This is quite close to the data from Ref.
holten .

In non-natural units, Eq (27) becomes

$R=r\sqrt{\frac{\hbar}{m\omega}}=\left(\frac{3\hbar}{2m\omega}.\frac{N}{\sqrt{8N+1}}\right)^{\frac{1}{2}}$
(29)

##  VI Density of a Pauli crystal

In Sec. (III), the number density of the fermions in a Pauli crystal has been
denoted as $\sigma=N/V$.

Therefore, in natural units

$\sigma={\frac{N}{\pi r^{2}}}=\frac{2}{3\pi}\sqrt{8N+1}$ (30)

In non-natural units,

$\sigma=\frac{2m\omega}{3\pi\hbar}\sqrt{8N+1}$ (31)

##  VII Number of fermions in a shell

Here shell refers to the circuital arrangement of the fermions in the crystal;
not to be confused with energy levels or orbitals.

In a Pauli crystal, the fermions arrange themselves in a way maximizing the
N-body probability distribution. This is usually calculated using the Monte
Carlo algorithm. However, we can take note of the fact there is a particular
pattern to the arrangement of these fermions as shown in Fig. 1 of Ref.
gajda17 .

Figure 2: Pauli crystals of (a) order 2 (b) order 3 (c) order 4. The even
ordered crystals progress as $1,5,9,..$, and the odd ordered crystals progress
as $3,7,11,..$. Image from Ref. gajda17

The number of fermions in the $i$-th orbit of a crystal or $k$-th order, can
be expressed as

$f_{i}=4i+2(k\ mod\ 2)-3$ (32)

Where $mod$ is the modulo function that gives the least positive residue
(i.e., remainder of Eucledian division). $(a\ mod\ b)$ gives remainder when
$a$ is divided by $b$.

For even $k$, $(k\ mod\ 2)=0$. Therefore, $f_{i}=4i-3$ or the number of
fermions in orbits progresses as $1,5,9,..$.

For odd $k$, $(k\ mod\ 2)=1$. Therefore, $f_{i}=4i-1$ or the number of
fermions in orbits progresses as $3,7,11,..$.

##  VIII Predictions for $N=15$ fermions

Let us try applying the above model to a system of $N=15$ fermions. $N=15$ is
a crystal of order 5. The following values are in harmonic oscillator units.

From Eq (25), the total energy of a 5th order crystal is $U=55$.

From Eq (27), the radius of the crystal is $r=1.43$.

From Eq (30), the number density of the crystal is $\sigma=2.33$

From Sec. (VII), the number of fermions in the first, second and third shells
are $1,5\ \&\ 9$ respectively.

The Monte-Carlo simulation for the same has been done in Fig.3. From the
simulation, it is crystal clear that the structure matches our predictions.

Figure 3: Monte-Carlo simulation for $N=15$ fermions

##  IX Conclusion

We made predictions for a system of $N=15$ fermions based on the model
developed in this paper. The results match closely with the results obtained
from the Monte-Carlo simulations in Fig.3.

Having said that, we would like to reiterate that the objective of this work
is to develop a simpler model for studying the qualitative and quantitative
properties of the Pauli crystals, keeping the statistical mechanical treatment
in mind. This model approaches the problem from two different directions,
namely fermion degeneracy and harmonic oscillator treatment. As a result, this
yields much more precise and accurate results compared to previous attempts.

###### Acknowledgements.

The authors would like to acknowledge Dr Sourabh Lahiri of Birla Institute of
Technology, Mesra on two grounds. Firstly, for inculcating in his students an
interest in statistical mechanics that made this work possible. Secondly, his
endorsement has made it possible for this work to be uploaded into arXiv. The
authors would also like to express their gratitude towards Dr Madhu Priya of
Birla Institute of Technology, Mesra for taking an exceptional foundational
course in statistical mechanics and assigning a project that resulted in this
work. AM would also like to thank his mother for being a constant source
inspiration for him.

## References

  * (1) Pathria, R. & Beale, P. 7 - Ideal Bose systems. Statistical Mechanics (Fourth Edition). pp. 195-246 (2022), https://www.sciencedirect.com/science/article/pii/B9780081026922000168
  * (2) Rakshit, D., Mostowski, J., Sowinski, T., Zaluska-Kotur, M. & Gajda, M. On the observability of Pauli crystals in experiments with ultracold trapped Fermi gases. Scientific Reports. 7 (2017,11), http://dx.doi.org/10.1038/s41598-017-14952-2
  * (3) Holten, M., Bayha, L., Subramanian, K., Heintze, C., Preiss, P. & Jochim, S. Observation of Pauli Crystals. Phys. Rev. Lett.. 126, 020401 (2021,1), https://link.aps.org/doi/10.1103/PhysRevLett.126.020401
  * (4) Gajda, M., Mostowski, J., Sowiński, T. & Załuska-Kotur, M. Single-shot imaging of trapped Fermi gas. EPL (Europhysics Letters). 115, 20012 (2016,7), https://doi.org/10.1209/0295-5075/115/20012
  * (5) Ciftja, O. & Batle, J. Statistical Interaction Description of Pauli Crystals in 2D Systems of Harmonically Confined Fermions. Annalen Der Physik. 531, 1900075 (2019), https://onlinelibrary.wiley.com/doi/abs/10.1002/andp.201900075
  * (6) Cheuk, L., Nichols, M., Lawrence, K., Okan, M., Zhang, H., Khatami, E., Trivedi, N., Paiva, T., Rigol, M. & Martin W. Zwierlein Observation of spatial charge and spin correlations in the 2D Fermi-Hubbard model. Science. 353, 1260-1264 (2016), https://www.science.org/doi/abs/10.1126/science.aag3349
  * (7) Chiu, C. Revealing a Pauli Crystal. Physics. 14 (2021,1), https://physics.aps.org/articles/v14/5
  * (8) Bergschneider, A., Klinkhamer, V., Becher, J., Klemt, R., Zürn, G., Preiss, P. & Jochim, S. Spin-resolved single-atom imaging of 6Li in free space. Phys. Rev. A. 97, 063613 (2018,6), https://link.aps.org/doi/10.1103/PhysRevA.97.063613
  * (9) Gajda, M., Mostowski, J., Pylak, M., Sowiński, T. & Załuska-Kotur, M. Pauli Crystals–Interplay of Symmetries. Symmetry. 12, 1886 (2020,11), http://dx.doi.org/10.3390/sym12111886
  * (10) Gampel, F., Gajda, M., Załuska-Kotur, M. & Mostowski, J. Pauli crystals in harmonic trap and on a sphere. (2021)