# On colorings of hypergraphs embeddable in $\mathbb{R}^{d}$

Seunghun Lee111Einstein Institute of Mathematics, Hebrew University,
Jerusalem, Israel<EMAIL_ADDRESS>and Eran Nevo222Einstein
Institute of Mathematics, Hebrew University, Jerusalem, Israel. Partially
supported by Israel Science Foundation grant ISF-2480/20<EMAIL_ADDRESS>
###### Abstract

The (weak) chromatic number of a hypergraph $H$, denoted by $\chi(H)$, is the
smallest number of colors required to color the vertices of $H$ so that no
hyperedge of $H$ is monochromatic. For every $2\leq k\leq d+1$, denote by
$\chi_{L}(k,d)$ (resp. $\chi_{PL}(k,d)$) the supremum $\sup_{H}\chi(H)$ where
$H$ runs over all finite $k$-uniform hypergraphs such that $H$ forms the
collection of maximal faces of a simplicial complex that is linearly (resp.
PL) embeddable in $\mathbb{R}^{d}$.

Following the program by Heise, Panagiotou, Pikhurko and Taraz, we improve
their results as follows: For $d\geq 3$, we show that A.
$\chi_{L}(k,d)=\infty$ for all $2\leq k\leq d$, B. $\chi_{PL}(d+1,d)=\infty$
and C. $\chi_{L}(d+1,d)\geq 3$ for all odd $d\geq 3$. As an application, we
extend the results by Lutz and Møller on the weak chromatic number of the
$s$-dimensional faces in the triangulations of a fixed triangulable
$d$-manifold $M$: D. $\chi_{s}(M)=\infty$ for $1\leq s\leq d$.

##  1 Introduction

Given a hypergraph $H=(V,E)$, we say that $H$ is (weakly) $m$-colorable if
there is a coloring $c:V\to[m]$ such that every hyperedge of $H$ is not
monochromatic. The (weak) chromatic number of $H$, denoted by $\chi(H)$, is
the smallest $m$ such that $H$ is $m$-colorable.

In this manuscript, we are interested in colorings of (finite) $k$-uniform
hypergraphs embeddable in $\mathbb{R}^{d}$. We consider two types of
embedding: geometric (or linear) and PL (piecewise linear) embedding.

For every $2\leq k\leq d+1$, denote by $\chi_{L}(k,d)$ (resp.
$\chi_{PL}(k,d)$) the supremum $\sup_{H}\chi(H)$ where $H$ runs over all
finite $k$-uniform hypergraphs such that $H$ forms the collection of maximal
faces of a simplicial complex that is geometrically (resp. PL) embeddable in
$\mathbb{R}^{d}$. Clearly $\chi_{L}(k,d)\leq\chi_{PL}(k,d)$. Note that for
every $2\leq k<k^{\prime}\leq d+1$ we have
$\chi_{L}(k^{\prime},d)\leq\chi_{L}(k,d)$. Indeed, if a pure
$(k^{\prime}-1)$-dimensional simplicial complex $\mathsf{K}$ geometrically
(resp. PL) embeds in $\mathbb{R}^{d}$, then so is its $(k-1)$-skeleton, and
every proper coloring of its $(k-1)$-skeleton is also a proper coloring of the
facets of $\mathsf{K}$. Further, every $(k-1)$-dimensional simplicial complex
geometrically embeds in $\mathbb{R}^{2k-1}$, and the complete $k$-uniform
hypergraph on $n$ vertices has chromatic number at least $n/(k-1)$, as no $k$
vertices can be colored the same. We obtain the trivial bound
$\chi_{L}(k,d)=\infty$ for all $2\leq k\leq(d+1)/2$.

In [13], Heise, Panagiotou, Pikhurko and Taraz slightly improved this result
by showing $\chi_{L}(k,d)=\infty$ also in the cases $d=2k-3$ and $d=2k-2$ for
$3\leq k$.

Our main results are summarized in the following theorem:

######  Main Theorem.

Fix $d\geq 3$.

A. $\chi_{L}(k,d)=\infty$ for all $2\leq k\leq d$.

B. $\chi_{PL}(d+1,d)=\infty$.

C. $\chi_{L}(d+1,d)\geq 3$ for all odd $d\geq 3$.

D. $\chi_{s}(M)=\infty$ for every triangulable $d$-manifold $M$ and $1\leq
s\leq d$, where $\chi_{s}(M)=\sup_{H}\chi(H)$ where $H$ runs over all
$(s+1)$-uniform hypergraphs such that $H$ forms the collection of
$s$-dimensional faces of a simplicial complex which triangulates $M$.

Note that Main theorem D follows from Main theorems A and B and the following
PL extension theorem by Adiprasito, with a simpler proof and a generalization
by Venturello and Yashfe. It generalizes a classical result by Bing for the
$d=3$ case [3, Theorem I.2.A].

######  Theorem 1.1 ([2]).

For every nonnegative integer $d$, if a simplicial complex $\mathsf{K}$ is PL
embeddable in $\mathbb{R}^{d}$ then there exists a (PL) triangulation
$\mathsf{T}$ of the $d$-simplex containing $\mathsf{K}$ as a subcomplex in its
interior such that the boundary of $\mathsf{T}$ is combinatorially isomorphic
to the boundary of the $d$-simplex.

Indeed, consider a triangulation $\mathsf{T}$ of $M$ and a fixed facet $F$ in
it. Now, the complexes illustrating the bounds in Main Theorems A and B PL
embed in the interior of $F$. Hence, by Theorem 1.1, for each of them, say $X$
corresponding to an $(s+1)$-uniform hypergraph, there exists a triangulation
$\mathsf{T}(X)$ of $M$ containing $X$ as a subcomplex, obtained by subdividing
the interior of $F$ appropriately. Thus $\chi_{s}(M)\geq\chi(X)$, and the
latter can be arbitrarily large.

We illustrate the new lower bounds of our Main Theorem in Table 1.

$d$\$k$ | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---
2 | 4 | 2 | $-$ | $-$ | $-$ | $-$
3 | $\infty$ |  $\infty$ [13] | 3 (Thm C) | $-$ | $-$ | $-$
4 | $\infty$ |  $\infty$ [13] |  $\infty$ (Thm A) | 2 | $-$ | $-$
5 | $\infty$ | $\infty$ |  $\infty$ [13] |  $\infty$ (Thm A) | 3 (Thm C) | $-$
6 | $\infty$ | $\infty$ |  $\infty$ [13] |  $\infty$ (Thm A) |  $\infty$ (Thm A) | 2
7 | $\infty$ | $\infty$ | $\infty$ |  $\infty$ [13] |  $\infty$ (Thm A) |  $\infty$ (Thm A)
8 | $\infty$ | $\infty$ | $\infty$ |  $\infty$ [13] |  $\infty$ (Thm A) |  $\infty$ (Thm A)
Table 1: Currently known lower bounds on weak chromatic numbers for the class
of $k$-uniform hypergraphs which are geometrically embeddable in
$\mathbb{R}^{d}$. Note that when we consider PL embeddability, then all finite
lower bounds other than the $d=2$ case will be changed into $\infty$ by Main
theorem B.

Note that we still have a large gap between Main Theorems B and C. This
motivates the following as a future research problems.

######  Problem 1.2.

(1) Is $\chi_{L}(d+1,d)=\infty$ for all $d\geq 3$?

(2) Let $\chi_{P}(d)$ be the supremum chromatic number over all hypergraphs
which are the collections of maximal faces of the boundary complexes of
$d$-polytopes, for a fixed $d\geq 4$. What is $\chi_{P}(d)$? Does
$\chi_{P}(d)\longrightarrow\infty$ as $d\longrightarrow\infty$?

Discussion of previous literature. It seems that previous related studies were
motivated by different contexts. Probably the framework of [13] is the most
similar with ours. In [13] lower and upper bounds on $\chi_{L}(k,d)$ and
$\chi_{PL}(k,d)$ are given, focusing on $\chi_{L}(k,d)$. Their lower bounds
are summarized in Table 1. Main theorems A, B and C can be considered as a
continuation and improvements upon their results.

Another group of papers investigates coloring and choosability results for the
face-hypergraph of a graph embedded in a surface, regarding weak colorings
[17, 11, 9, 24]. A face-hypergraph is constructed from a graph embedding where
every face of the embedding corresponds to a hyperedge of the hypergraph
consisting of the vertices incident to the face. Note that in this setting a
graph embedding does not necessarily give a cell structure of a simplicial
complex. The simplicial direction is explored for general simplcial manifolds
by Lutz and Møller [19]. They showed that (i) $\chi_{2}(M_{g})$, where $M_{g}$
is a genus $g$ surface, tends to infinity as the genus $g$ tends to infinity,
and (ii) $\chi_{s}(M)=\infty$ when $M$ is a triangulable $d$-dimensional
manifold with $d\geq 3$ and $s\leq\lceil d/2\rceil$. Note that Main theorem D
improves upon (ii). In particular, this also answers [4, Question 6] which
asks whether non 2-colorable simplicial $d$-spheres exist for $d>3$.

Our study is also related to the study of transversal numbers of geometric
hypergraphs, studied in [4, 20, 5] for simplicial spheres, and in [6],
equivalently, for stable sets in flag spheres. The transversal number of a
hypergraph $H$, denoted by $\tau(H)$, is the minimum size of a vertex subset
which pierces every hyperedge. The transversal ratio of $H$ is the ratio
$\tau(H)/|V(H)|$. Note that if $H$ is $m$-colorable then the transversal ratio
of $H$ is bounded above by $\frac{m-1}{m}$. This implies that a lower bound on
$\chi(H)$ is a necessary condition for corresponding lower bound on the
transversal ratio of $H$.

Outline. This manuscript is organized as follows. In Section 2, we prove Main
theorem A. In Section 3, we prove Main theorem B. Finally in Section 4, we
prove Main theorem C.

##  2 $\chi_{L}(k,d)$ is unbounded when $2\leq k\leq d$ and $d\geq 3$

In this section, we prove Main theorem A. The proof is based on the family of
hypergraphs defined by Ackerman, Keszegh and Pálvölgyi [1] which the authors
study in connection to colorings of $(AB)^{l}$-free hypergraphs and is
extended from earlier constructions in [21, 16]. We show that the hypergraph
can be geometrically embedded such that all vertices of the hypergraph are on
the moment curve $\gamma_{d}(t)=(t,t^{2},\dots,t^{d})$. Rather interestingly,
the $(AB)^{l}$-free property is related to this special type of embedding the
vertices into the moment curve. We first study the combinatorial criterion for
this embeddability concept in Subsection 2.1. In Subsection 2.2, using the
embeddability criterion, we show that the hypergraphs constructed in [1] are
desired constructions for Theorem A.

###  2.1 Combinatorial criterion for embeddability on the moment curve

We say that a $k$-uniform hypergraph $H=(V,E)$ is geometrically embeddable in
$\mathbb{R}^{d}$ if there is a function $\phi:V\to\mathbb{R}^{d}$ such that

$\displaystyle\dim\operatorname{aff}(\phi(e))=k-1\textrm{ for every $e\in E$,
and}$ (1)
$\displaystyle\operatorname{conv}(\phi(e_{1}))\cap\operatorname{conv}(\phi(e_{2}))=\operatorname{conv}(\phi(e_{1})\cap\phi(e_{2}))\textrm{
for every $e_{1},e_{2}\in E$}.$ (2)

Note that the inclusion $\supseteq$ in (2) always holds. We will need the
assertion below, which we suspect to be known. As we failed to find a
reference we include its proof.

######  Proposition 2.1.

Let $P_{1}$ and $P_{2}$ be finite point sets in $\mathbb{R}^{d}$ such that
$P_{1}\cup P_{2}$ is in general position. Suppose that

$\operatorname{conv}(P_{1})\cap\operatorname{conv}(P_{2})\supsetneq\operatorname{conv}(P_{1}\cap
P_{2}).$

Then, there exist two disjoint nonempty subsets $Q_{1}\subseteq P_{1}$ and
$Q_{2}\subseteq P_{2}$ such that $|Q_{1}\cup Q_{2}|=d+2$ and
$\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2})\neq\emptyset$.

###### Proof.

Let

$\displaystyle P_{1}\setminus P_{2}=$
$\displaystyle\\{a_{1},a_{2},\dots,a_{k}\\},\;P_{2}\setminus
P_{1}=\\{b_{1},b_{2},\dots,b_{l}\\},\textrm{ and}$ $\displaystyle P_{1}\cap
P_{2}=$ $\displaystyle\\{c_{1},c_{2},\dots,c_{m}\\}.$

By the condition, there is a point
$p\in(\operatorname{conv}(P_{1})\cap\operatorname{conv}(P_{2}))\setminus\operatorname{conv}(P_{1}\cap
P_{2})$. That is, we can represent $p$ in two convex combinations

$\displaystyle p=\sum_{a_{i}\in P_{1}\setminus
P_{2}}\kappa_{i}a_{i}+\sum_{c_{i}\in P_{1}\cap
P_{2}}\lambda_{i}c_{i}=\sum_{b_{i}\in P_{2}\setminus
P_{1}}\mu_{i}b_{i}+\sum_{c_{i}\in P_{1}\cap P_{2}}\nu_{i}c_{i},$ (3)

where

  * (i)

$\kappa_{i}$, $\lambda_{i}$, $\mu_{i}$ and $\nu_{i}$ are all nonnegative,

  * (ii)

$\sum_{i=1}^{k}\kappa_{i}+\sum_{i=1}^{m}\lambda_{i}=1$ and
$\sum_{i=1}^{l}\mu_{i}+\sum_{i=1}^{m}\nu_{i}=1$, and

  * (iii)

there exist $i\in[k]$ and $j\in[l]$ such that $\kappa_{i}>0$ and $\mu_{j}>0$.

Now, we split the index set $[m]$ for $P_{1}\cap P_{2}$ into two subsets
$I_{\lambda}$ and $I_{\nu}$, where

$\displaystyle I_{\lambda}=\\{i\in[m]:\lambda_{i}\geq\nu_{i}\\},\textrm{ and
}I_{\nu}=\\{i\in[m]:\lambda_{i}<\nu_{i}\\}.$

By moving terms in (3) and scaling, we have another pair of convex
combinations

$\displaystyle\sum_{a_{i}\in P_{1}\setminus
P_{2}}\frac{\kappa_{i}}{K}a_{i}+\sum_{i\in
I_{\lambda}}\frac{\lambda_{i}-\nu_{i}}{K}c_{i}=\sum_{b_{i}\in P_{2}\setminus
P_{1}}\frac{\mu_{i}}{K}b_{i}+\sum_{i\in
I_{\nu}}\frac{\nu_{i}-\lambda_{i}}{K}c_{i},$ (4)

where

$K=\sum_{i=1}^{k}\kappa_{i}+\sum_{i\in
I_{\lambda}}(\lambda_{i}-\nu_{i})=\sum_{i=1}^{l}\mu_{i}+\sum_{i\in
I_{\nu}}(\nu_{i}-\lambda_{i}).$

Note that there are no points appearing in both sides of (4), and at least one
of the coefficients should be positive in both sides by (iii). (4) can be
reduced into a minimal affine dependency where the points remain at the
original side (see [25, Chapter 6]). In that minimal affine dependency, both
sides should involve at least one nontrivial term. Let $Q_{1}$ and $Q_{2}$ be
the subsets of $P_{1}$ and $P_{2}$ which have positive coordinates in the
left- and the right-hand side, respectively. By the general position
assumption on $P_{1}\cup P_{2}$, we have $|Q_{1}\cup Q_{2}|=d+2$. ∎

The moment curve $\gamma_{d}(t)=(t,t^{2},\dots,t^{d})$ in $\mathbb{R}^{d}$ has
many interesting properties (see e.g. [25, Chapter 0]). For instance, every
finite point set on $\gamma_{d}$ is in general position. Furthermore, the
combinatorial type of the cyclic polytope $C_{d}(n)$, which is the convex hull
of $n$ points on $\gamma_{d}$ is characterized by the following criterion.

######  Theorem 2.2 (Gale’s evenness criterion).

$C_{d}(n)$ is a simplicial polytope. Furthermore, a $d$-subset $S$ of
$[n]=\\{1,\dots,n\\}$ forms a facet of $C_{d}(n)$ if and only if the set
$\\{k\in S:i<k<j\\}$ has even size for every $i,j\in[n]\setminus S$.

######  Proposition 2.3.

Suppose that $A$ and $B$ are disjoint point sets chosen from the moment curve
$\gamma_{d}$ such that $|A\cup B|=d+2$. Let us order the points of $A\cup B$
by $p_{1},p_{2},\dots,p_{d+2}$ as in the order on $\gamma_{d}$ where we assume
$p_{1}\in A$. Then,
$\operatorname{conv}(A)\cap\operatorname{conv}(B)\neq\emptyset$ if and only if
$A$ and $B$ are interlacing, that is, $p_{i}\in A$ for all odd $i\in[d+2]$ and
$p_{i}\in B$ for all even $i\in[d+2]$.

###### Proof.

Suppose that $\operatorname{conv}(A)\cap\operatorname{conv}(B)\neq\emptyset$.
If $A$ and $B$ are not interlacing, then $A$ or $B$ has two consecutive
points. Gale’s criterion 2.2 particularly implies that the complement of two
consecutive points among $d+2$ points on the moment curve forms a facet of
$C_{d}(d+2)$. So, the other set among $A$ and $B$ can be extended to a facet,
which means that $\operatorname{conv}(A)$ and $\operatorname{conv}(B)$ are
disjoint. This leads to a contradiction.

Now, suppose that $A$ and $B$ are interlacing. Since $|A|+|B|=d+2$, by Radon’s
lemma [22], we have a partition of $A\cup B$ into disjoint $X$ and $Y$ such
that $\operatorname{conv}(X)\cap\operatorname{conv}(Y)\neq\emptyset$. By the
previous paragraph, $X$ and $Y$ should be interlacing, so without loss of
generality, we have $A=X$ and $B=Y$. This completes the proof. ∎

We extend the above interlacing property for general hypergraphs. Let $H$ be a
hypergraph whose vertex set has a total order $\prec$. We say that $H$ is
$l$-interlacing with respect to $\prec$ if there are distinct hyperedges
$e_{1}$ and $e_{2}$, and vertices $v_{1}\prec v_{2}\prec\cdots\prec v_{l}$
such that $v_{i}\in e_{1}$ when $i$ is odd and $v_{i}\in e_{2}$ when $i$ is
even. Note that $e_{1}$ and $e_{2}$ need not be disjoint. In the latter
condition of Proposition 2.3, the hypergraph $\\{A,B\\}$ is
$(d+2)$-interlacing with respect to the order given by $\gamma_{d}$.

When a $k$-uniform hypergraph $H$ is geometrically embeddable in
$\mathbb{R}^{d}$ such that the vertices of $H$ lie on $\gamma_{d}$ and appear
on the curve in the order of $\prec$, we say that $H$ is embeddable on the
moment curve $\gamma_{d}$ with respect to $\prec$. Note that since a point set
on $\gamma_{d}$ is in general position, (1) is always satisfied as long as
$k\leq d+1$. Furthermore, since the order type of a point set on $\gamma_{d}$
is completely determined by the order of the points on $\gamma_{d}$, if $H$ is
embeddable on $\gamma_{d}$ with respect to $\prec$, then any function
$\phi:V(H)\to\gamma_{d}$ which gives the same order $\prec$ of $V(H)$ on
$\gamma_{d}$ satisfies (2).

The following lemma shows that the above two conditions are equivalent when
$l=d+2$.

######  Lemma 2.4.

Let $k$ and $d$ be positive integers such that $k\leq d+1$. For a $k$-uniform
hypergraph $H$, let $\prec$ be a total order on the vertex set $V(H)$. Then, a
hypergraph $H$ is embeddable on $\gamma_{d}$ with respect to $\prec$ if and
only if $H$ is not $(d+2)$-interlacing with respect to $\prec$.

###### Proof.

Suppose that $H$ is not embeddable on $\gamma_{d}$ with respect to $\prec$.
Let $\phi:V(H)\to\gamma_{d}$ be a function which respects the order $\prec$ on
$\gamma_{d}$. Then, there are hyperedges $e_{1}$ and $e_{2}$ such that

$\operatorname{conv}(\phi(e_{1}))\cap\operatorname{conv}(\phi(e_{2}))\supsetneq\operatorname{conv}(\phi(e_{1})\cap\phi(e_{2})).$

By Proposition 2.1, we can find two disjoint subsets
$Q_{1}\subseteq\phi(e_{1})$ and $Q_{2}\subseteq\phi(e_{2})$ such that
$|Q_{1}\cup Q_{2}|=d+2$ and
$\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2})\neq\emptyset$. By
Proposition 2.3, $Q_{1}$ and $Q_{2}$ are interlacing, so $H$ is
$(d+2)$-interlacing with respect to $\prec$.

Now, suppose that $H$ is $(d+2)$-interlacing with respect to $\prec$. Then,
there are two hyperedges $e_{1}$ and $e_{2}$ and vertices
$w_{1},\dots,w_{d+2}$ which are ordered by $\prec$ such that $w_{i}\in e_{1}$
when $i$ is odd and $w_{i}\in e_{2}$ when $i$ is even. Let
$\phi:V(H)\to\gamma_{d}$ be again a function which respects the order $\prec$
on $\gamma_{d}$. Let

$Q_{1}=\phi(\\{w_{i}:\textrm{$i$ is odd, $i\in[d+2]$}\\})\textrm{ and
}Q_{2}=\phi(\\{w_{i}:\textrm{$i$ is even, $i\in[d+2]$}\\}).$

It is easy to see that $Q_{1}$ and $Q_{2}$ are disjoint and

$\operatorname{conv}(\phi(e_{1}))\cap\operatorname{conv}(\phi(e_{2}))\supseteq\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2}).$

Since $Q_{1}$ and $Q_{2}$ are interlacing, by Proposition 2.3, we have

$\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2})\neq\emptyset.$

It is enough to show that
$\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2})$ is not a subset of
$\operatorname{conv}(\phi(e_{1})\cap\phi(e_{2}))$. Suppose the contrary and
denote $\phi(e_{1})\cap\phi(e_{2})$ by $I$. Then, we have that

$\displaystyle\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2})=\operatorname{conv}(Q_{1})\cap\operatorname{conv}(Q_{2})\cap\operatorname{conv}(I)$
$\displaystyle=$
$\displaystyle(\operatorname{conv}(Q_{1})\cap\operatorname{conv}(I))\cap(\operatorname{conv}(Q_{2})\cap\operatorname{conv}(I))$
$\displaystyle=$ $\displaystyle\operatorname{conv}(Q_{1}\cap
I)\cap\operatorname{conv}(Q_{2}\cap I)=\emptyset,$

where the last two equalities come from that $Q_{i}$ and $I$ are subsets of
$\phi(e_{i})$ which forms a $(k-1)$-simplex in $\mathbb{R}^{d}$ for $i\in[2]$,
and that $Q_{1}\cap I$ and $Q_{2}\cap I$ are disjoint in $I$ which again forms
a simplex. This leads to a contradiction. ∎

###  2.2 Proof of Theorem A

For two hyperedges $A$ and $B$ in a hypergraph whose vertex set is totally
ordered by $\prec$, the vertices $v_{1}\prec\cdots\prec v_{l}$ of $A\cup B$
can be encoded as a word $w\in\\{A,B,I\\}^{|A\cup B|}$, where $w(i)=A$ if
$v_{i}\in A\setminus B$, $w(i)=B$ if $v_{i}\in B\setminus A$, and $w(i)=I$ if
$v_{i}\in A\cap B$ for $i\in[l]$ (here, $w(i)$ is the $i$th letter of $w$). We
call $w$ the pattern of $A$ and $B$ with respect to $\prec$. We omit the order
if it is clear from the context. For a word $w$, we denote the word obtained
by concatenating $w$ $k$ times by $w^{k}$.

######  Example 2.5.

Let $A=\\{v_{1},v_{2},v_{5}\\}$ and $B=\\{v_{3},v_{4},v_{5}\\}$ where the
vertices are ordered by their indices. Then the pattern of $A$ and $B$ is
$AABBI$. It can be also written concisely as $A^{2}B^{2}I$.

Now we recall the family of hypergraphs from [1, Section 3] (see also [21,
16]).

Let $T(a,b)$ denote a full $b$-ary tree of depth $a-1$, that is, every non-
leaf vertex has $b$ children and every leaf is at distance $a-1$ from the
root. $H(a,b)$ is the hypergraph on the vertex set $V(T(a,b))$ whose
hyperedges are of two types: either the set of all children of a non-leaf
vertex of $T(a,b)$, or the vertex set of the unique path from a leaf to the
root, equivalently a maximal chain of $T(a,b)$.

######  Lemma 2.6.

When $3\leq a\leq b$, $H(a,b)$ is not $(a+2)$-interlacing with respect to any
DFS (depth first search) order on $T(a,b)$.

###### Proof.

For $T=T(a,b)$ we fix a DFS order $\prec_{T}$. We choose two distinct
hyperedges $A$ and $B$ and consider the following exhaustive three cases.

Case I. $A$ and $B$ are both maximal chains: The order $\prec_{T}$ implies
that the pattern of the chains $A$ and $B$ is either of the form
$I^{l}A^{a-l}B^{a-l}$ or $I^{l}B^{a-l}A^{a-l}$ for some $1\leq l\leq a-1$
($l\geq 1$ as both $A$ and $B$ contain the root of $T$). So $\\{A,B\\}$ is at
most $(a+1)$-interlacing (when $l=a-1$), but cannot be $(a+2)$-interlacing.

Case II. Exactly one of $A$ and $B$ is a maximal chain: We may assume that $A$
is a maximal chain. When $A$ and $B$ intersect, the order $\prec_{T}$ implies
that the pattern of $A$ and $B$ is in the form of
$A^{l}B^{r}IA^{a-l-1}B^{b-r-1}$ where $1\leq l\leq a$ and $0\leq r\leq b$
($l\geq 1$ as the root of $T$ cannot be in $B$). Then $\\{A,B\\}$ is at most
4-interlacing, thus $\\{A,B\\}$ is not $(a+2)$-interlacing as $a\geq 3$. When
$A$ and $B$ are disjoint, the pattern of $A$ and $B$ with respect to
$\prec_{T}$ is $A^{l}B^{b}A^{a-l}$ for $1\leq l\leq a$, hence $\\{A,B\\}$ is
at most 3-interlacing.

Case III. Neither $A$ nor $B$ is a chain: Let $A$ and $B$ be the set of
children of non-leaf vertices $v$ and $w$, respectively. If $w$ is a
descendant of $v$, then $\prec_{T}$ implies that the pattern of $A$ and $B$ is
$A^{l}B^{b}A^{b-l}$ where $0\leq l\leq b$. If $v$ is a descendant of $w$ the
pattern of $A$ and $B$ with respect to $\prec_{T}$ is $B^{l}A^{b}B^{b-l}$
where $0\leq l\leq b$. In both cases $\\{A,B\\}$ is just at most
3-interlacing. Else, $v$ and $w$ are not in the same maximal chain, then the
pattern of $A$ and $B$ is either $A^{b}B^{b}$ or $B^{b}A^{b}$ , hence
$\\{A,B\\}$ is just at most 2-interlacing. In either case, $\\{A,B\\}$ is not
$(a+2)$-interlacing for $a\geq 3$. ∎

For a positive integer $k\geq 3$, the $k$-uniform hypergraph $H^{k,m}$ and the
order $\prec^{k,m}$ on $V(H^{k,m})$ are constructed recursively as follows.

  * •

We let $H^{k,2}=H(k,k)$. We fix a DFS order of $T(k,k)$ and denote it by
$\prec^{k,2}$.

  * •

Upon previously constructed $H^{k,m-1}$, we define $H^{k,m}$ as the hypergraph
on the vertex set of $T=T(k,|V(H^{k,m-1})|)$ as follows. We make a copy
$H^{k,m-1}_{v}$ of $H^{k,m-1}$ for every non-leaf vertex $v$ in $T$ where the
vertices of $H^{k,m-1}_{v}$ are exactly the children of $v$ in $T$. The
children of $v$ are ordered by $\prec^{k,m-1}_{v}$ which is isomorphic to
$\prec^{k,m-1}$. The set of hyperedges of $H^{k,m}$ are (i) the collection of
hyperedges of $H^{k,m-1}_{v}$ for each non-leaf vertex $v$ and (ii) the
maximal chains of $T$. We fix a DFS order $\prec^{k,m}$ of $T$ which is
compatible with $\prec^{k,m-1}_{v}$ for every non-leaf vertex $v$ of $T$.

By defintion, $H(k,|V(H^{k,m-1})|)$ and $H^{k,m}$ are constructed from the
same tree $T=T(k,|V(H^{k,m-1})|)$, so they have the same vertex set $V(T)$.
The difference is that, for each non-leaf vertex $v$ of $T$, while
$H(k,|V(H^{k,m-1})|)$ takes all children of $v$ to be a single hyperedge,
$H^{k,m}$ have several (smaller) hyperedges for the children of $v$, coming
from $H^{k,m-1}_{v}$.

The following proposition, on colorability of these hypergraphs, is shown in
[1].

######  Proposition 2.7 ([1, Proposition 3.1]).

$H^{k,m}$ is not $m$-colorable.

Next we study interlacing for these ordered hypergraphs.

######  Proposition 2.8.

For every $k\geq 3$ and $m\geq 2$, $H^{k,m}$ is not $(k+2)$-interlacing with
respect to $\prec^{k,m}$.

###### Proof of Theorem A.

Fix positive integers $d$, $k$ with $d\geq 3$ and $2\leq k\leq d$. The case
$k=2$ is trivial, since a complete graph $K_{n}$ is embeddable on $\gamma_{d}$
for every $d\geq 3$ (and any order $\prec$ on $V(K_{n})$). Let $k\geq 3$. By
Proposition 2.7, it is enough to show that $H^{k,m}$ is embeddable on
$\gamma_{d}$. By Lemma 2.4, it is sufficient to show that $H^{k,m}$ is not
$(d+2)$-interlacing. This follows directly from Proposition 2.8 and the
condition $k\leq d$. ∎

###### Proof of Proposition 2.8.

Fix a positive integer $k\geq 3$. We use induction on $m$. The base case $m=2$
follows from Lemma 2.6 by plugging $a=b=k$. Now, suppose $m>2$ and assume that
$H^{k,m^{\prime}}$ is not $(k+2)$-interlacing with respect to
$\prec^{k,m^{\prime}}$ for every $2\leq m^{\prime}<m$.

Let $A$ and $B$ be two distinct hyperedges of $H^{k,m}$. If $A$ and $B$ are
contained in the same $H^{k,m-1}_{v}$, then by the induction hypothesis
$\\{A,B\\}$ is not $(k+2)$-interlacing with respect to $\prec^{k,m-1}_{v}$.
So, $\\{A,B\\}$ is not $(k+2)$-interlacing with respect to $\prec^{k,m}$.
Else, let $M=H(k,|V(H^{k,m-1})|)$ and $T=T(k,|V(H^{k,m-1})|)$. For a hyperedge
$e$ of $H^{k,m}$ let $f(e)$ be the unique hyperedge of $M$ which contains $e$.
(Thus $f(e)=e$ when $e$ is a maximal chain of $T$, and otherwise $f(e)$
strictly contains $e$.) Note that $f(A)\neq f(B)$ as $A$ and $B$ are not
contained in the same $H^{k,m-1}_{v}$ for all vertices $v\in T$. By Lemma 2.6,
$\\{f(A),f(B)\\}$ is not $(k+2)$-interlacing with respect to $\prec^{k,m}$.
Since $A\subseteq f(A)$ and $B\subseteq f(B)$, $\\{A,B\\}$ is not
$(k+2)$-interlacing with respect to $\prec^{k,m}$ either. This completes the
proof. ∎

######  Remark 2.9 (Tightness).

In [1, 16], the authors studied $(AB)^{l}$-free hypergraphs. $(AB)^{l}$-free
hypergraphs are defined similar to non-$(2l)$-interlacing hypergraphs: a
hypergraph $H$ with fixed total order $\prec$ on its vertex set is _$(AB)^{l}$
-free_ if it has no two hyperedges $A$ and $B$, and ordered vertex subset
$\\{v_{1}\prec\dots\prec v_{2l}\\}\subseteq A\cup B$ such that $v_{i}\in
A\setminus B$ when $i$ is odd and $v_{i}\in B\setminus A$ when $i$ is even.
Thus, the non-interlacing property is stronger. In [1], it is shown that the
hypergraphs $H^{k,m}$ are $ABABA$-free. Note that $H^{k,m}$ is not
$(k+2)$-interlacing but is $(k+1)$-interlacing as shown in Case I of the proof
of Proposition 2.8. Note that, when $d\geq 2$, $H^{d+1,m}$ contains “a book
with three pages”, namely a subhypergraph consisting of 3 hyperedges whose
pairwise intersections are all equal to the same subset of size $d$; hence
$H^{d+1,m}$ is not embeddable in $\mathbb{R}^{d}$ when $d\geq 2$.

As an approach to Problem 1.2, we propose the following problem.

######  Problem 2.10.

Is there a family of $(d+1)$-uniform hypergraphs with unbounded chromatic
numbers where each hypergraph is embeddable on $\gamma_{d}$?

######  Remark 2.11.

In [1, Sec.7], the authors ask if there is a connection between Radon
partitions and $(AB)^{l}$-freeness in higher dimensions. Lemma 2.4 describes
such connection between the related interlacing property and Radon partitions.

##  3 $\chi_{PL}(d+1,d)$ is unbounded when $d\geq 3$

In this section, we prove Main theorem B.

First we recall some definitions: a hypergraph $H$ is linear if every pair of
distinct hyperedges of $H$ has intersection of size at most one. A simplicial
(or polyhedral) complex $\mathsf{K}$ is PL embeddable in $\mathbb{R}^{d}$ if
there is a simplicial subdivision $\mathsf{L}$ of $\mathsf{K}$ which is
geometrically embeddable in $\mathbb{R}^{d}$. The proof of Theorem B relies on
the following lemma.

Figure 1: Illustration of the construction in the proof of Lemma 3.1 when
$d=3$. Here, $f_{1}=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
$f_{2}=\\{v_{4},v_{5},v_{6},v_{7}\\}$. The tetrahedrons $\sigma_{f_{i}}$ are
indicated by bolt edges, and their respective facets $\tau_{f_{i}}$ are
indicated by light blue.

######  Lemma 3.1.

For $d\geq 3$, every linear $(d+1)$-uniform hypergraph is PL embeddable in
$\mathbb{R}^{d}$.

###### Proof.

Let $H$ be a linear $(d+1)$-uniform hypergraph. Incidences between facets and
vertices in $H$ can be recorded as a bipartite graph $G$, where one color
class $F$ represents the set of hyperedges of $H$, and the other $V$
represents the set of vertices of $H$. We embed $G$ into $\mathbb{R}^{d}$ with
straight lines (which is possible because $d\geq 3$) so that the vertices are
in general position. We abuse notation and identify each vertex of $G$ with
its location in $\mathbb{R}^{d}$ and each vertex $f\in F$ with its
corresponding hyperedge in $H$. Now “inflate” each vertex $f\in F$ into a
$d$-dimensional polyhedral cell $C_{f}$, in the following way: place a regular
$d$-simplex $\sigma_{f}$ of radius $\epsilon>0$ whose center of mass is $f$,
and fix a facet $\tau_{f}$ of $\sigma_{f}$. Let $C_{f}$ be the subspace
$\sigma_{f}\bigcup\cup_{v\in f}\operatorname{conv}(v\cup\tau_{f})$. For
$\epsilon>0$ small enough, for each pair of edges $f,g\in H$, $C_{f}\cap
C_{g}=f\cap g$, which is either the empty set or a single vertex shared by
both, as $H$ is linear. See Figure 1 for illustration.

It is left to show that $C_{f}$ has a simplicial subdivision which is
combinatorially isomorphic to a subdivision of the $d$-simplex whose vertices
are the vertices of $f$; compare with Hudson’s [15, I.Lem.1.12] for the convex
polytope case. To see this, we first give a simplicial subdivision
$\mathsf{K}_{f}^{\prime}$ of the boundary $\partial C_{f}$. This is possible
because $\partial C_{f}$ is a compact polyhedron (see [23, Theorem 2.11]).
Now, pick a point in the relative interior of the facet $\tau_{f}$, and in
case $\tau_{f}$ is contained in the boundary of $C_{f}$ perturb this point
slightly to obtain an interior point $x$ of $C_{f}$, so that $C_{f}$ is star
shaped at $x$, namely, for every point $y\in C_{f}$ the line segment $[x,y]$
is contained in $C_{f}$. Indeed, such $x$ exists since $C_{f}$ is the union of
$d+2$ $d$-simplices all sharing the same facet $\tau_{f}$. We may additionally
assume that $x$ and the vertices of $G$ are in general position.

We denote the vertices of $f$ by $v_{1},\dots,v_{d+1}$. By the general
position assumption, $\operatorname{conv}\\{v_{1},\dots,v_{d+1}\\}$ is a
$d$-simplex which we call $P$. We also introduce another polytope $Q$ which is
differently defined by two cases: When $x\notin P$, we find an additional
point $w$ so that $\operatorname{conv}\\{v_{1},\dots,v_{d+1},w\\}$ contains
$x$ in its interior. Let $Q=\operatorname{conv}\\{v_{1},\dots,v_{d+1},w\\}$ in
this case. When $x\in P$, we let $Q=P$. We may assume that all faces of $Q$
are simplices in both cases.

Let $\pi_{x}:\partial C_{f}\to\partial Q$ be the radial projection with
respect to $x$. Note that $\pi_{x}$ is well-defined and a homeomorphism
because $x$ is contained in the interior of $Q$ in both cases. Then

$\mathsf{K}_{Q}^{\prime}=\\{\sigma\cap\pi_{x}(\tau):\textrm{$\sigma$ is a
proper face of $Q$, }\tau\in\mathsf{K}_{f}^{\prime}\\}$

is a collection of polytopal cells whose union is $\partial Q$. Hence
$\partial Q$ has a simplicial subdivision $\mathsf{K}_{Q}$ which contains a
subdivision of each convex cell in $\mathsf{K}_{Q}^{\prime}$ (see [15, Lemma
1.5]), e.g. the derived subdivision of $\mathsf{K}_{Q}^{\prime}$. When $Q=P$,
we let $\mathsf{K}_{P}=\mathsf{K}_{Q}$. When $P\subsetneq Q$, we choose an
interior point $y$ of $P$ and let $\pi_{y}:\partial Q\to\partial P$ be the
radial projection with respect to $y$ which is again a homeomorphism.
Similarly with the above, we project down $\mathsf{K}_{Q}$ to $\partial P$ via
$\pi_{y}$ and make a simplicial subdivision $\mathsf{K}_{P}$ which is a common
refinement of the boundary complex of $P$ and of $\pi_{y}(\mathsf{K}_{Q})$.

In each of the two cases, we map $\mathsf{K}_{P}$ back to $\partial C_{f}$ via
the inverse map $\pi_{x}^{-1}$ or $(\pi_{y}\circ\pi_{x})^{-1}$, and this gives
a simplicial subdivision $\mathsf{K}_{f}$ of $\partial C_{f}$ which is a
refinement of $\mathsf{K}_{f}^{\prime}$. It is easy to see that
$\mathsf{K}_{f}$ is combinatorially isomorphic to $\mathsf{K}_{P}$, and it can
be extended to the whole $C_{f}$ and $P$ by coning the complexes over suitable
interior points, either $x$ or $y$.

Thus, we described a PL embedding of $H$. ∎

A second ingredient is the Hales-Jewett theorem [12]. For positive integers
$t,n$, a subset $L$ of the $n$-dimensional hypercube $[t]^{n}$ is called a
combinatorial line if there exist a non-empty set of indices
$I=\\{i_{1},...,i_{k}\\}\subseteq[n]$ and a choice of $a_{i}\in[t]$ for every
$i\in[n]\setminus I$ such that

$L=\\{(x_{1},\dots,x_{n})\in[t]^{n}:x_{i_{1}}=\cdots=x_{i_{k}}\textrm{ and
}x_{i}=a_{i}\textrm{ for }i\notin I\\}.$

The indices in $I$ (outside of $I$) are called the active (fixed, resp.)
coordinates of $L$. Let us call the hypergraph on $[t]^{n}$ whose hyperedges
are exactly combinatorial lines of $[t]^{n}$ the Hales-Jewett hypergraph on
$[t]^{n}$.

######  Theorem 3.2 (Hales-Jewett).

For every positive integers $t$ and $m$ there exists $n$ such that every
$m$-coloring of $[t]^{n}$ contains a monochromatic combinatorial line. In
other words, the Hales-Jewett hypergraph on $[t]^{n}$ is not $m$-colorable.

###### Proof of Theorem B.

By Lemma 3.1 and the Hales-Jewett theorem 3.2 with $t=d+1$, it is enough to
show that the Hales-Jewett hypergraph on $[t]^{n}$ is linear for every
positive integers $t$ and $n$. Suppose otherwise that two distinct
combinatorial lines $L_{1}$ and $L_{2}$ intersect at two vertices. Then, by
comparing the values of those two vertices in each coordinate, $L_{1}$ and
$L_{2}$ must have the same active and fixed coordinates, and further, at the
fixed coordinates, the fixed values $a_{i}$ must be the same for $L_{1}$ and
$L_{2}$. This means that $L_{1}$ and $L_{2}$ are determined by the same
conditions, hence $L_{1}=L_{2}$, a contradiction. ∎

######  Remark 3.3.

In the literature, there are more examples of classes of linear hypergraphs
which have unbounded chromatic number. For example, a balanced incomplete
block design of order $n$, block size $k$ and index $\lambda$ (or
$(n,k,\lambda)$-BIBD in short) is a $k$-uniform hypergraph on $n$ vertices and
each unordered pair of vertices is contained in exactly $\lambda$ hyperedges.
It is easy to see that a $(n,k,1)$-BIBD is a linear hypergraph. It is known
that for fixed $m\geq 2$, $k\geq 3$ and $\lambda$, there is a
$(n,k,\lambda)$-BIBD for a suitable $n$ which is not $m$-colorable, see [14,
18, 7].

##  4 $\chi_{L}(d+1,d)\geq 3$ for odd $d\geq 3$

In this section, we prove Main theorem C by constructing a non 2-colorable
$(d+1)$-uniform hypergraph $L_{d}$ which is geometrically embeddable in
$\mathbb{R}^{d}$ for every odd $d\geq 3$.

We use abstract join and geometric join for the construction; both are denoted
by the same symbol $*$, but it will be clear which join operator it means by
context. For hypergraphs $H_{1},\dots,H_{l}$ on disjoint ground sets, the
abstract join of $H_{1},\dots,H_{l}$ is

$H_{1}*\cdots*H_{l}=\\{e_{1}\cup\cdots\cup e_{l}:e_{i}\in H_{i}\textrm{ for
all $i\in[l]$}\\}.$

We say that subsets $S_{1},\dots,S_{l}\subseteq\mathbb{R}^{d}$ are in skewed
position if

$\dim\left(\operatorname{aff}\left(\bigcup_{i=1}^{l}S_{i}\right)\right)=l-1+\sum_{i=1}^{l}\dim(\operatorname{aff}(S_{i})).$

The geometric join of $S_{1},\dots,S_{l}$ which are in skewed position is
defined as their convex hull:

$S_{1}*\cdots*S_{l}=\left\\{\sum_{i=1}^{l}\lambda_{i}p_{i}:\sum_{i=1}^{l}\lambda_{i}=1,\lambda_{i}\geq
0,\textrm{ and }p_{i}\in S_{i}\textrm{ for every $i\in[l]$}\right\\}.$

Note that every $k$ disjoint edges in the boundary of the cyclic polytope
$C_{2k}(n)$ are in skewed position, and their images under the projection from
$\mathbb{R}^{2k}$ to $\mathbb{R}^{2k-1}$ that forgets the last coordinate are
in skewed position, with vertices on $\gamma_{2k-1}$, and with geometric join
a $(2k-1)$-simplex.

###  4.1 Construction of $L_{d}$

First, we construct $L_{d}$. Fix a positive integer $k\geq 2$ and set
$d=2k-1$.

  1. (1)

For $i\in[d]=[2k-1]$, let

$V_{i}=\\{v_{1}^{i},\dots,v_{4k-2}^{i}\\}$

be a set of $4k-2$ vertices. Let $P_{i}$ be the edge set of the path on
$V_{i}$ where the vertices appear in order, that is,

$P_{i}=\\{\\{v_{1}^{i},v_{2}^{i}\\},\dots,\\{v_{4k-3}^{i},v_{4k-2}^{i}\\}\\}.$

  2. (2)

Let

$K_{1}=\bigcup_{1\leq i_{1}<\cdots<i_{k}\leq d}P_{i_{1}}*\cdots*P_{i_{k}},$

where $*$ denotes the abstract join operation. Note that $K_{1}$ is a
$(d+1)$-uniform hypergraph.

  3. (3)

We define $K_{2}$ in a similar way. Let

$\displaystyle W_{i}$
$\displaystyle=\\{w_{1}^{i},\dots,w_{4k-2}^{i}\\},\textrm{ and}$
$\displaystyle Q_{i}$
$\displaystyle=\\{\\{w_{1}^{i},w_{2}^{i}\\},\dots,\\{w_{4k-3}^{i},w_{4k-2}^{i}\\}\\}$

for every $i\in[d]$. Then, let

$K_{2}=\bigcup_{1\leq i_{1}<\cdots<i_{k}\leq d}Q_{i_{1}}*\cdots*Q_{i_{k}}.$

  4. (4)

Let

$\displaystyle M_{1}$
$\displaystyle=\\{\\{v_{1}^{i},v_{3}^{i},\dots,v_{2k-1}^{i}\\},\\{v_{2k}^{i},v_{2k+2}^{i},\dots,v_{4k-2}^{i}\\}:i\in[d]=[2k-1]\\},\textrm{
and}$ $\displaystyle M_{2}$
$\displaystyle=\\{\\{w_{1}^{i},w_{3}^{i},\dots,w_{2k-1}^{i}\\},\\{w_{2k}^{i},w_{2k+2}^{i},\dots,w_{4k-2}^{i}\\}:i\in[d]=[2k-1]\\}.$

That is, $M_{1}$ is the collection whose elements are the subset of $V_{i}$
which consists of the vertices with the first $k$ odd indices and the subset
of $V_{i}$ which consists of the vertices with the last $k$ even indices for
every $i\in[d]$. $M_{2}$ is defined similarly. Note that $M_{1}$ and $M_{2}$
are $k$-uniform hypergraphs.

  5. (5)

Finally, we define

$L_{d}=K_{1}\cup K_{2}\cup M_{1}*M_{2}.$

Note that $L_{d}$ is a $(d+1)$-uniform hypergraph.

###  4.2 Non-2-colorability of $L_{d}$

######  Proposition 4.1.

Let $d\geq 3$ be odd. Then $L_{d}$ is not 2-colorable.

###### Proof.

Suppose otherwise and we color all vertices of $L_{d}$ by RED and BLUE so that
no hyperedge is monochromatic. In $K_{1}$, note that not all $2k-1$ vertex
sets $V_{i}$ have consecutive vertices of the same color: Othersiwe, without
loss of generality, we can assume that RED was used in $V_{1},\dots,V_{k}$ in
consecutive vertices. By definition of $K_{1}$, this gives a hyperedge of
$K_{1}$ which is monochromatic, a contradiction. So at least one $V_{i}$ has
an alternating coloring, say $V_{1}$ does. The same also holds for $K_{2}$, so
at least one $W_{j}$ has an alternating coloring, say $W_{1}$ does. By the
alternating colorings given to $V_{1}$ and $W_{1}$, at least one (in fact,
there are exactly two) of the 4 hyperedges of $M_{1}*M_{2}$ which are subsets
of $V_{1}\cup W_{1}$ should be monochromatic. ∎

Note that $L_{d}$ is 3-colorable: For each $i\in[d]$, we color the vertices of
$P_{i}$ by RED, BLUE and GREEN alternatingly in order. We do the same for
every $Q_{i}$. It is easy to see that each of the hyperedges in $K_{1}$,
$K_{2}$, and $M_{1}*M_{2}$ has at least two colors from this coloring.

###  4.3 Embeddability of $L_{d}$

In this subsection we prove the following proposition. Recall that $L_{d}$ is
defined only for odd $d\geq 3$.

######  Proposition 4.2.

For every odd $d\geq 3$, $L_{d}$ is geometrically embeddable in
$\mathbb{R}^{d}$.

The following lemma is useful in the proof (see also [8, Section 6.1]).

######  Lemma 4.3 ([10, Lemma 2.3]).

Let $p_{1},\dots,p_{n}$ be the vertices of $C_{d+1}(n)$ indexed by their order
along the moment curve $\gamma_{d}$. Let $\hat{0}_{n,d}$ be the set of facets
in the lower envelope of $C_{d+1}(n)$, namely the facets of the boundary of
$C_{d+1}(n)$ which are visible from any point on the $x_{d+1}$-axis with
sufficiently small $(d+1)$-coordinate. Then,

$\displaystyle\hat{0}_{n,d}=\left\\{\begin{array}[]{lr}\\{p_{1}\\}*D(d/2,\\{p_{2},\dots,p_{n}\\})&\text{when
$d$ is even,}\\\ D((d+1)/2,\\{p_{1},\dots,p_{n}\\})&\text{when $d$ is
odd,}\end{array}\right.$

where

$D(k,\\{a_{1},\dots,a_{n}\\})=\\{\\{a_{i_{1}},a_{i_{1}+1},\dots,a_{i_{k}},a_{i_{k}+1}\\}:i_{j+1}\geq
i_{j}+2\textrm{ for $j\in[k-1]$}\\}$

for an ordered set $\\{a_{1},\dots,a_{n}\\}$. Furthermore, $\hat{0}_{n,d}$
gives a triangulation of $C_{d}(n)$.

Figure 2: Illustration of the geometric embedding of $L_{3}$. A small circle
around each end vertex of $s_{i}$ and $s_{i}^{\prime}$ describes a small
neighborhood where the other vertices are introduced. The blue lines indicate
a thin tetrahedron in the realization of $M_{1}*M_{2}$. The other notations
are introduced in the proof below.

We first overview how we geometrically embed $L_{d}$ in $\mathbb{R}^{d}$.
Recall $d=2k-1$. For $K_{1}$, we begin with the cyclic polytope $C_{d}(2d)$,
denoted by $B_{1}$. The vertices of $B_{1}$ are exactly the end vertices
$v_{1}^{i}$ and $v_{4k-2}^{i}$ of the paths $P_{i}$ for $i\in[d]$, ordered
$v_{1}^{1},v_{4k-2}^{1},v_{1}^{2},v_{4k-2}^{2}\ldots,v_{1}^{d},v_{4k-2}^{d}$
on $\gamma_{d}$; internal vertices of $P_{i}$ are not introduced yet. Denote
the line segment $[v_{1}^{i},v_{4k-2}^{i}]$ by $s_{i}$. It follows from Lemma
4.3 that the geometric joins, which equal the convex hulls, of
$s_{i_{1}},\dots,s_{i_{k}}$, for all $k$-subsets
$\\{i_{1},\dots,i_{k}\\}\subseteq[d]=[2k-1]$ form a subcollection of the
facets in the triangulation $\hat{0}_{2d,d}$ of $B_{1}$ . Hyperedges of
$K_{1}$ will eventually appear in a subdivision of this triangulation after a
perturbation of the vertices. In this way we will embed $K_{1}$.

Then $B_{2}$ is defined as a reflected copy of $B_{1}$ w.r.t. some hyperplane
$H$. Denote by $s^{\prime}_{i}$ the reflected image of $s_{i}$. A crucial
assumption is that $B_{1}$ and $B_{2}$ are far enough from each other so that
there exist hyperplanes $H_{i}$ (resp. $H^{\prime}_{i}$) which weakly separate
$B_{1}$ and $B_{2}$, and $B_{1}\cap H_{i}=s_{i}$ (resp. $B_{2}\cap
H^{\prime}_{i}=s^{\prime}_{i}$) for every $i\in[d]$. These hyperplanes will be
used to separate hyperedges in $K_{1}$ (resp. $K_{2}$) from hyperedges in
$M_{1}*M_{2}$.

In $B_{1}$, we subdivide each $s_{i}$ to introduce internal vertices of
$P_{i}$, and similarly in $B_{2}$. We perturb these points so that hyperedges
of $M_{1}*M_{2}$ become full-dimensional and we can still use the hyperplane
separators we previously constructed. Also, we assume that the first half
(resp. last half) of the internal vertices of $P_{i}$ were chosen very close
to $v_{1}^{i}$ (resp. to $v_{4k-2}^{i}$), and we do the same for $B_{2}$. This
is to ensure that every two disjoint hyperedges of $M_{1}*M_{2}$ do not
intersect in the embedding. We give some additional assumptions for the other
pairs of hyperedges in $M_{1}*M_{2}$. Thus, these final positions will provide
a geometric embedding of $L_{d}$. We now proceed to the details.

###### Proof of Proposition 4.2.

The construction of the geometric embedding progresses through several steps.
For notational simplicity, we use the same notation for the vertices of
$L_{d}$ and their embedded images in $\mathbb{R}^{d}$ even when their
locations are modified, for instance, by perturbing them.

Step 1. Constructing the polytope $B_{1}$. We first construct the polytope
$B_{1}$ for $K_{1}$ in $\mathbb{R}^{d}$ which has the combinatorial type of
$C_{d}(2d)$. Let $\gamma_{d}$ be the moment curve in $\mathbb{R}^{d}$. We
choose $2d$ vertices

$v_{1}^{1},v_{4k-2}^{1},v_{1}^{2},v_{4k-2}^{2},\dots,v_{1}^{d},v_{4k-2}^{d}$

in that order on $\gamma_{d}$. We denote the set of those vertices by
$V^{\prime}$ and let $B_{1}=\operatorname{conv}(V^{\prime})$. Let

$H_{V^{\prime}}=\left\\{\\{v_{1}^{i_{1}},v_{4k-2}^{i_{1}},v_{1}^{i_{2}},v_{4k-2}^{i_{2}},\dots,v_{1}^{i_{k}},v_{4k-2}^{i_{k}}\\}:1\leq
i_{1}<\cdots<i_{k}\leq d\right\\}.$

One can easily see that $H_{V^{\prime}}\subseteq D((d+1)/2,V^{\prime})$, hence
by Lemma 4.3, $H_{V^{\prime}}$ forms a part of this triangulation of $B_{1}$,
and in particular, $H_{V^{\prime}}$ is embedded on the moment curve.

Step 2. Making a reflected copy $B_{2}$ of $B_{1}$ and separating hyperplanes
$H_{i}$ and $H_{i}^{\prime}$. Now, we want to construct the polytope $B_{2}$
similarly for $K_{2}$ and suitably locate $B_{1}$ and $B_{2}$. Recall that we
denote the segment $[v_{1}^{i},v_{4k-2}^{i}]$ by $s_{i}$ for every $i\in[d]$.

By Lemma 4.3 every $s_{i}$ belongs to the lower envelope of $B_{1}$, that is,
$s_{i}$ is visible from the point $p_{i}=(0,\dots,0,z_{i})$ for every negative
$z_{i}$ with large enough absolute value $|z_{i}|$. For each $i\in[d]$ we
choose a facet $f_{i}$ in the lower envelope of $B_{1}$ which contains
$s_{i}$. Then, by slightly rotating $\operatorname{aff}(f_{i})$ while
containing $s_{i}$, we obtain a supporting hyperplane $H_{i}$ of $B_{1}$ at
$s_{i}$ (so $B_{1}\cap H_{i}=s_{i}$) which satisfies the extra property that
it separates $B_{1}$ from $p_{i}$.

Let $B_{2}$ be a reflected copy of $B_{1}$ with respect to the hyperplane

$P_{z}=\\{(x_{1},\dots,x_{d-1},z):x_{1},\dots,x_{d-1}\in\mathbb{R}\\}$

for a fixed $z\in\mathbb{R}$. We denote the vertices of $B_{2}$ with the same
notation of $K_{2}$. That is, the vertex set of $B_{2}$ is

$W^{\prime}=\\{w_{1}^{1},w_{4k-2}^{1},w_{1}^{2},w_{4k-2}^{2},\dots,w_{1}^{d},w_{4k-2}^{d}\\},$

where each $w^{j}_{l}$ is the reflection of $v^{j}_{l}$ w.r.t. $P_{z}$. Let
$s_{i}^{\prime}=\operatorname{conv}(\\{w_{1}^{i},w_{4k-2}^{i}\\})$ and

$H_{W^{\prime}}=\left\\{\\{w_{1}^{i_{1}},w_{4k-2}^{i_{1}},w_{1}^{i_{2}},w_{4k-2}^{i_{2}},\dots,w_{1}^{i_{k}},w_{4k-2}^{i_{k}}\\}:1\leq
i_{1}<\cdots<i_{k}\leq d\right\\}.$

We denote the supporting hyperplane for $s_{i}^{\prime}$ by $H_{i}^{\prime}$,
which are chosen as the reflection of $H_{i}$ by $P_{z}$. We assume that $z$
is chosen to be negative with sufficiently large $|z|$ so that every $H_{i}$
separates $B_{1}$ and $B_{2}$ such that $B_{2}$ is in an open halfsapce of
$H_{i}$ for every $i\in[d]$. By symmetry, $H_{i}^{\prime}$ also separtates
$B_{1}$ and $B_{2}$ such that $B_{1}$ is in an open halfspace of
$H_{i}^{\prime}$ for every $i\in[d]$.

Step 3. Introducing remaining vertices of $L_{d}$ in the embedding via general
position assumptions. We subdivide each $s_{i}$ by introducing $4k-4$ new
vertices $v_{1}^{i},v_{2}^{i},\dots,v_{4k-2}^{i}$ in order. We also subdivide
$s_{i}^{\prime}$ using $w_{1}^{i},\dots,w_{4k-2}^{i}$ in order. This
subdivision of line segments induces a subdivision of the simplices

$s_{i_{1}}*\cdots*s_{i_{k}},\textrm{ and
}s_{i_{1}}^{\prime}*\cdots*s_{i_{k}}^{\prime}$

where $1\leq i_{1}<\cdots<i_{k}\leq d$, which are exactly the simplices in the
geometric realization of $H_{V^{\prime}}$ of Step 1. Therefore, this gives a
geometric realization of $K_{1}$ and $K_{2}$. Denote the
$\epsilon$-neighborhood of $p\in\mathbb{R}^{d}$ by $N_{\epsilon}(p)$. On
$s_{i}$, we first locate the vertices $v_{2}^{i},v_{3}^{i},\dots,v_{2k-1}^{i}$
in $N_{\epsilon}(v_{1}^{i})$ and locate $v_{2k}^{i},\dots,v_{4k-3}^{i}$ in
$N_{\epsilon}(v_{4k-2}^{i})$, where $\epsilon>0$ is chosen such that the
neighborhoods $N_{\epsilon}(v)$, over all vertices of $B_{1}\cup B_{2}$, are
pairwise disjoint, and further, for every four distinct vertices $u,v,w,x$ of
$B_{1}\cup B_{2}$, the joins $N_{\epsilon}(u)*N_{\epsilon}(v)$ and
$N_{\epsilon}(w)*N_{\epsilon}(x)$ are disjoint. (These joins are “thin
thickening” of the segments $uv$ and $wx$ resp.) This is possible after we
slightly perturb the vertices of $B_{1}\cup B_{2}$ so that they are in general
position.

We also perturb the hyperplanes $H_{i}$ and $H_{j}^{\prime}$ for each
$i,j\in[d]$ as well as the vertices of $B_{1}\cup B_{2}$ if necessary to fix
$(k-1)$-dimensional flats $F_{i}$ and $F_{j}^{\prime}$ such that $F_{i}$ and
$F_{j}^{\prime}$ are in skewed position,

$s_{i}\subseteq F_{i}\subseteq H_{i}\textrm{ and }s_{j}^{\prime}\subseteq
F_{j}^{\prime}\subseteq H_{j}^{\prime},$

and $H_{i}$ and $H_{j}^{\prime}$ satisfies the separating property described
above. We further assume that for every distinct $w_{1},w_{2}\in W^{\prime}$
(resp. $v_{1},v_{2}\in V^{\prime}$) and every $F_{i}$ (resp.
$F_{j}^{\prime}$), $F_{i}\cup\\{w_{1},w_{2}\\}$ (resp.
$F_{j}^{\prime}\cup\\{v_{1},v_{2}\\}$) is in general position. By this, we can
require $\epsilon$ to be sufficiently small so that for every $F_{i}$ (resp.
$F_{j}^{\prime}$) and $w_{1},w_{2}\in W^{\prime}$ (resp. $v_{1},v_{2}\in
V^{\prime}$), there is a hyperplane which contains $F_{i}$ (resp.
$F_{j}^{\prime}$) and strictly separates $N_{\epsilon}(w_{1})$ from
$N_{\epsilon}(w_{2})$ (resp. $N_{\epsilon}(v_{1})$ from
$N_{\epsilon}(v_{2})$). Clearly this is possible.

Now, for every $i\in[d]$, we perturb the new vertices
$v_{2}^{i},v_{3}^{i},\dots,v_{2k-1}^{i}$ within $N_{\epsilon}(v_{1}^{i})$ and
perturb $v_{2k}^{i},\dots,v_{4k-3}^{i}$ within $N_{\epsilon}(v_{4k-2}^{i})$ as
follows: For the odd-indexed vertices
$O_{i}=\\{v_{1}^{i},v_{3}^{i},\dots,v_{2k-1}^{i}\\}$, we additionally require
that they are only perturbed within the flat $F_{i}$ and are in general
position, which implies that the resulting vertices affinely span $F_{i}$. We
require the same for the even-indexed vertices
$E_{i}=\\{v_{2k}^{i},v_{2k+2}^{i},\dots,v_{4k-2}^{i}\\}$. Note that the sets
$O_{i}$ and $E_{i}$, for all $i\in[d]$, are exactly the hyperedges of $M_{1}$.
The other vertices on $s_{i}$ are perturbed so that they are contained in
$H_{i}^{+}$, the open halfspace which contains the interior of $B_{1}$. This
perturbation should be small enough so that it also gives a geometric
embedding of $K_{1}$. The vertices $w_{j}^{i}$ are perturbed to satisfy the
same properties w.r.t. the flats $F_{i}^{\prime}$ and halfspaces
$H_{i}^{\prime+}$, so they give a geometric embedding of $K_{2}$. Finally, we
add the simplices of $M_{1}*M_{2}$. This completes the construction.

Now we show that our construction gives an embedding. Condition (1) is easily
satisfied: Hyperedges of $K_{1}$ and $K_{2}$ are in general position;
hyperedges of $M_{1}*M_{2}$ are also in general position by the skewedness of
each pair $F_{i}$ and $F^{\prime}_{j}$ and as hyperedges in $M_{1}$ and
$M_{2}$ are spanning their corresponding flats.

We now show that Condition (2) is satisfied. Let $e_{1}$ and $e_{2}$ be two
distinct hyperedges of $L_{d}$. There are three cases to consider: (i) $e_{1}$
and $e_{2}$ are from $K_{1}\cup K_{2}$. When they are from the same $K_{i}$ we
already showed that our construction gives an embedding of $K_{i}$. Else,
without loss of generality $e_{i}\in K_{i}$ for $i\in[2]$. Since $K_{1}$ and
$K_{2}$ are separated by a hyperplane then the realizations of $e_{1}$ and
$e_{2}$ do not intersect.

(ii) $e_{1}\in K_{i}$ and $e_{2}\in M_{1}*M_{2}$; without loss of generality
$i=1$. Then, $e_{2}=f_{1}\cup f_{2}$ where $f_{i}\in M_{i}$ for $i\in[2]$.
From the construction, we can find the hyperplane $H_{i}$ which contains
$f_{1}$ and the end vertex $v$ of the segment $s_{i}$ such that $f_{1}$ is
contained in $N_{\epsilon}(v)$. Note that $f_{2}\subseteq H_{i}^{-}$, hence
$e_{2}$ is realized in the closed halfspace $H_{i}\cup H_{i}^{-}$. On the
other hand, $e_{1}$ is realized in the closed halfspace $H_{i}\cup H_{i}^{+}$.
Thus,

$\displaystyle\operatorname{conv}(e_{1})\cap\operatorname{conv}(e_{2})=(\operatorname{conv}(e_{1})\cap
H_{i})\cap(\operatorname{conv}(e_{2})\cap H_{i})$ $\displaystyle=$
$\displaystyle\operatorname{conv}(e_{1}\cap
H_{i})\cap\operatorname{conv}(e_{2}\cap H_{i}).$

But $e_{1}\cap H_{i}$ consists of at most two vertices, consecutive on the
path subdividing $s_{i}$, so at most one of them belong to $f_{1}$. It follows
that
$\operatorname{conv}(e_{1})\cap\operatorname{conv}(e_{2})=\operatorname{conv}(e_{1}\cap
e_{2})$, which is either empty or equals a single vertex.

(iii) Finally, $e_{1},e_{2}\in M_{1}*M_{2}$. There exist unique partitions
$e_{1}=f_{1}^{1}\cup f_{2}^{1}$ and $e_{2}=f_{1}^{2}\cup f_{2}^{2}$, where
$f_{1}^{1},f_{1}^{2}\in M_{1}$ and $f_{2}^{1},f_{2}^{2}\in M_{2}$. If these
four sets $f_{j}^{i}$ are distinct, then each is contained in
$N_{\epsilon}(v)$ for a distinct vertex $v\in L_{d}$, and as the joins
$N_{\epsilon}(u)*N_{\epsilon}(v)$ and $N_{\epsilon}(w)*N_{\epsilon}(x)$ are
disjoint for every distinct vertices $u,v,w,x\in L_{d}$ we conclude that
$\operatorname{conv}(e_{1})\cap\operatorname{conv}(e_{2})$ is empty.

Else, without loss of generality, $f_{1}^{1}=f_{1}^{2}$; we find the flat
$F_{i}$ which contains $f_{1}^{1}$, and the vertices of $W^{\prime}$
corresponding to $f_{2}^{1}$ and $f_{2}^{2}$, say $w_{1}$ and $w_{2}$. Now,
there exists a hyperplane $H^{\prime\prime}$ containing $F_{i}$ which
separates $N_{\epsilon}(w_{1})$ from $N_{\epsilon}(w_{2})$, hence
$H^{\prime\prime}$ separates $f_{2}^{1}$ from $f_{2}^{2}$. If follows that the
intersection $\operatorname{conv}(e_{1})\cap\operatorname{conv}(e_{2})$ is
contained in $H$ and equals
$\operatorname{conv}(f_{1}^{1})=\operatorname{conv}(e_{1}\cap e_{2})$.

This completes the proof. ∎

## Acknowledgement

We thank Karim Adiprasito and Geva Yashfe for their illustrations of Theorem
1.1.

## References

  * [1] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi.  Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs.  SIAM J. Discrete Math., 34(4):2250–2269, 2020.
  * [2] Karim Adiprasito, Lorenzo Venturello, and Geva Yashfe.  Personal communication.  Also see the blogpost https://kaguprasetya.com/2022/11/03/kubrick-schoolification-science-education-flattening-pl-maps-and-ronly-honly-bing/#more-460, Nov.2022.
  * [3] R. H. Bing.  The geometric topology of 3-manifolds, volume 40 of American Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 1983.
  * [4] Joseph Briggs, Michael Gene Dobbins, and Seunghun Lee.  Transversals and colorings of simplicial spheres.  Discrete Comput. Geom., 2023, arXiv:2111.06560.
  * [5] Minho Cho and Jinha Kim.  Transversal numbers of stacked spheres.  2023, arXiv:2305.08716.
  * [6] Maria Chudnovsky and Eran Nevo.  Stable sets in flag spheres.  European J. Combin., 110:Paper No. 103699, 9, 2023.
  * [7] Marcia de Brandes, Kevin T. Phelps, and Vojtěch Rödl.  Coloring Steiner triple systems.  SIAM J. Algebraic Discrete Methods, 3(2):241–249, 1982.
  * [8] Jesús A. De Loera, Jörg Rambau, and Francisco Santos.  Triangulations, volume 25 of Algorithms and Computation in Mathematics.  Springer-Verlag, Berlin, 2010.  Structures for algorithms and applications.
  * [9] Zdeněk Dvořák, Daniel Král, and Riste Škrekovski.  Coloring face hypergraphs on surfaces.  European J. Combin., 26(1):95–110, 2005.
  * [10] Paul H. Edelman and Victor Reiner.  The higher Stasheff-Tamari posets.  Mathematika, 43(1):127–154, 1996.
  * [11] Kengo Enami and Kenta Noguchi.  Embeddings of a graph into a surface with different weak chromatic numbers.  Graphs Combin., 37(2):435–444, 2021.
  * [12] A. W. Hales and R. I. Jewett.  Regularity and positional games.  Trans. Amer. Math. Soc., 106:222–229, 1963.
  * [13] Carl Georg Heise, Konstantinos Panagiotou, Oleg Pikhurko, and Anusch Taraz.  Coloring $d$-embeddable $k$-uniform hypergraphs.  Discrete Comput. Geom., 52(4):663–679, 2014.
  * [14] Daniel Horsley and David A. Pike.  On balanced incomplete block designs with specified weak chromatic number.  J. Combin. Theory Ser. A, 123:123–153, 2014.
  * [15] J. F. P. Hudson.  Piecewise linear topology.  W. A. Benjamin, Inc., New York-Amsterdam, 1969.  University of Chicago Lecture Notes prepared with the assistance of J. L. Shaneson and J. Lees.
  * [16] Balázs Keszegh and Dömötör Pálvölgyi.  An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes.  J. Comput. Geom., 10(1):1–26, 2019.
  * [17] André Kündgen and Radhika Ramamurthi.  Coloring face-hypergraphs of graphs on surfaces.  J. Combin. Theory Ser. B, 85(2):307–337, 2002.
  * [18] Václav Linek and Evan B. Wantland.  Coloring BIBDs with block size 4.  J. Combin. Des., 6(6):403–409, 1998.
  * [19] Frank H. Lutz and Jesper M. Møller.  Chromatic numbers of simplicial manifolds.  Beitr. Algebra Geom., 61(3):419–453, 2020.
  * [20] Isabella Novik and Hailun Zheng.  Neighborly spheres and transversal number.  to appear in the AMS volume on Open Problems in Algebraic Combinatorics, 2022.  Available at http://www.samuelfhopkins.com/OPAC/files/proceedings/novik_zheng.pdf.
  * [21] János Pach, Gábor Tardos, and Géza Tóth.  Indecomposable coverings.  Canad. Math. Bull., 52(3):451–463, 2009.
  * [22] Johann Radon.  Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.  Math. Ann., 83(1-2):113–115, 1921.
  * [23] Colin Patrick Rourke and Brian Joseph Sanderson.  Introduction to piecewise-linear topology. Springer-Verlag, Berlin-New York,,, 1982.  Reprint.
  * [24] Carsten Thomassen.  2-list-coloring planar graphs without monochromatic triangles.  J. Combin. Theory Ser. B, 98(6):1337–1348, 2008.
  * [25] Günter M. Ziegler.  Lectures on polytopes, volume 152 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1995.


# Brownian Motion & The Stochastic Behaviour of Stocks

Yorgos Protonotarios  Department of Mathematics, University College London
Pantelis Tassopoulos  Department of Mathematics, Imperial College London

(September 2021)

##  1 Introduction

###  1.1 Robert Brown

In 1827, a botanist by the name of Robert Brown was examining the motion of
grains of pollen suspended under water from a species of plants. Brown
observed the motion of the particles ejected from these pollen grains which
followed a seemingly ”jittery” motion; this was the first ever recorded case
of Brownian motion, named after Robert Brown. The idea behind this type of
motion being that the trajectory follows a completely random and
”unpredictable” path. Since then, the concept of an unpredictable and random
trajectory has been utilized in numerous fields including financial
mathematics in the modeling of stock behaviour [5].

###  1.2 Louis Bachelier

Several decades later, in 1900, Louis Bachelier built the foundation of
mathematical finance by integrating Brownian motion with the fluctuation in
the price of a stock. He postulated that two ideas should be considered when
exploring the future value of an asset. First, how a collection of _anterior_
(past) events influence the asset and second, how the probability of unknown
future events could affect it [2]. For example, the C.E.O of Apple just got
replaced yesterday; that is an _anterior_ event that could influence the
future price of an Apple stock. On the other hand, if a power outage occurs
tomorrow in one of Apple’s factories and halts production, that is an unknown
future event that might affect the price of the stock and falls into the
second category. It is said that the fluctuation in the price of a stock
attributed to the latter follows Brownian motion as it is seemingly
unpredictable and random. Bachelier only focused on the second idea since the
_anterior_ events were not meaningful because Bachelier defined the
mathematical expectation for an asset to rise or fall to be zero since the
market constitutes of a pool of people that trade with opposite beliefs on the
future value of an asset [2]. For example, suppose a person is buying a call
option for an asset, they hence believe that its price will rise. The person
on the other side of the option believes it will fall otherwise they would not
be selling the option. Hence, since they are both aware of past events that
can influence the asset and have contradictory beliefs on how the it will
perform, the mathematical expectation of gold is neither positive nor
negative. The market is therefore said to be _fair_. [2]

###  1.3 Norbert Wiener

The above considerations by Bachelier were made concrete and expanded upon
within a physics framework by American mathematician Norbert Wiener in his
seminal work on ’differential spaces’ [9]. This was justified by arguments
pertaining to the motion of a particle suspended in a fluid, where the
movement of the said particle depended on impulses by fluid particulates and
the initial velocity of the particle, although the influence of the latter was
deemed negligible by Einstein. For the sake of simplicity, one can assume that
the particle is constrained in one dimension and so are the impulses. Due to
the nature of the situation, Wiener, following Einstein assumed that the
displacement of the particle between any two time instants had no bias in any
direction and large movements relative to the time scale were unlikely. This
prompted the use of the normal distribution as a way of describing this
behaviour. A key assumption of the paper in the construction of Brownian
motion is that these displacements are independent and normally distributed
constitute the ’dimensions’, or independent variable of the motion.

##  2 Definition of Brownian Motion

In probability theory, one usually considers three objects when setting up a
probability space; namely, the sample space $\Omega$\- the collection of
outcomes of a random process, a sigma algebra $\mathscr{F}$\- the set of all
measurable events and the probability measure $\mathbb{P}$ that measures the
probability of said events that obeys certain axioms as laid out by Kolmogorov
[7]. Consider the probability space $(\Omega,\mathscr{F},\mathbb{P})$.

A stochastic process defined on the probability space
$(\Omega,\mathscr{F},\mathbb{P})$ is a measurable function
$X:[0,\infty)\times\Omega\rightarrow\mathbb{R}$. Such a process
$\mathfrak{B}(t,\omega)$ is called a Brownian motion if it satisfies the
following conditions [1]:

  1. I

$\mathbb{P}(\omega;\mathfrak{B}(0,t)=0)=1$

  2. II

For any $0\leq s<t$, the random variable $\mathfrak{B}(t)-\mathfrak{B}(s)$ is
normally distributed with mean $0$ and variance $t-s$, i.e

$\mathbb{P}(a\leq\mathfrak{B}(t)-\mathfrak{B}(s)\leq
b)=\displaystyle\frac{1}{\sqrt{2\pi(t-s)}}\int_{a}^{b}e^{{\frac{-x^{2}}{2(t-s)}}}dx$

  3. III

$\mathfrak{B}(t,\omega)$ has independent increments, i.e for any $0\leq
t_{1}\leq t_{2}\leq...\leq t_{n}$, the random variables

$\mathfrak{B}(t_{1}),\mathfrak{B}(t_{2})-\mathfrak{B}(t_{1}),...,\mathfrak{B}(t_{n})-\mathfrak{B}(t_{n-1})$

are independent and identically distributed, as per II.

  4. IV

Almost all sample paths of $\mathfrak{B}(t,\omega)$ are continuous functions,
i.e:

$\mathbb{P}(\omega;\mathfrak{B}(.,\omega)$ is continuous) $=1$

Note that the dependence on $\omega$ was dropped in property II and III for
simplicity reasons.

##  3 Applications to the Stock Market

###  3.1 Stochastic Differential Equations

We now consider a stock that is tradable on a stock market, such as an S&P 500
stock like Apple and model it by a stochastic process
$Y_{t}(\omega):[0,\infty)\times\Omega\rightarrow\mathbb{R}$ on the probability
space $(\Omega,\mathscr{F},\mathbb{P})$.

So what factors drive the process $\mathscr{Y}_{t}$?

Well, an attempt at answering the above is to view the stock price
$\mathscr{Y}_{t}$ as a sum of a deterministic component and a stochastic
component containing ’noise’ meant to represent an underlying uncertainty.
Thus, for a small increment in time from $t$ to $t+dt$, the change in
$\log\mathscr{Y}_{t}$ i.e., $d\log\mathscr{Y}_{t}$ is given by

$d\log\mathscr{Y}_{t}=\gamma(t)\cdot dt+\sigma(t,\mathscr{Y}_{t})\cdot$
”noise”

where $\gamma(t)$ is the growth rate of a stock which is deterministic and
$\sigma(t,\mathscr{Y})\cdot$ ”noise” is the volatility of the stock and is the
stochastic component. [8]. The noise part can be modeled by a Brownian motion
$\mathfrak{B}_{t}$, following Bachelier and Wiener. Thus, the above equation
can be recast in the following form [6]

$d\log\mathscr{Y}_{t}=\gamma(t)\cdot dt+\sigma(t,\mathscr{Y}_{t})\cdot
d\mathfrak{B}(t)$ (1)

where $d\mathfrak{B}_{t}=\mathfrak{B}_{t+dt}-\mathfrak{B}_{t}$. Equation (1)
is an example of a stochastic differential equation [8]. In order to make
precise what we mean by (1), we consider a discretisation of the problem and
consider the interval $[0,t]$ where $t\geq 0$. We further impose a partition
$t_{0}=0<t_{1}<t_{2}<...<t_{k-1}<t=t_{n}$ of the interval and read (1) to
mean:

$\displaystyle\log\mathscr{Y}_{t_{k}}-\log\mathscr{Y}_{t_{k-1}}$
$\displaystyle=\gamma(t_{k-1})\cdot(t_{k}-t_{k-1})+\sigma(t_{k-1},\mathscr{Y}_{t_{k-1}})\cdot(\mathfrak{B}_{t_{k}}-\mathfrak{B}_{t_{k-1}})$

for $k$ ranging from $0$ to $n-1$. A summation of the index $k$ yields the
process

$\displaystyle\displaystyle
I_{n}[\mathscr{Y}_{t}](.)=\log\mathscr{Y}_{t_{n}\equiv
t}-\log\mathscr{Y}_{t_{0}}$
$\displaystyle=\sum_{k=0}^{n-1}\gamma(t_{k-1})\cdot(t_{k}-t_{k-1})+\sum_{k=0}^{n-1}\sigma(t_{k-1},\mathscr{Y}_{t_{k-1}})\cdot(\mathfrak{B}_{t_{k}}-\mathfrak{B}_{t_{k-1}})$

[8]. Now, in a certain sense, we have ’integrated the process’ and have
obtained an expression for the process at some time $t$, given an initial time
$t_{0}$. Indeed, two summations that appear are reminiscent of discrete
approximations to Riemann-Stieltjes integrals. One is tempted to take a limit
of such partitions $\pi_{n}$ with mesh
$|\pi_{n}|\equiv\max(t_{i}-t_{i-1})\rightarrow 0$ and obtain the corresponding
equation

$\displaystyle\displaystyle\log\mathscr{Y}_{t_{n}\equiv
t}-\log\mathscr{Y}_{t_{0}}=\int_{0}^{t}\gamma(t)dt+"\int_{0}^{t}\sigma(t,\mathscr{Y}_{t})d\mathfrak{B}_{t}"$

The aim of the next chapter is to show that for suitably well behaved
$\gamma(t)(\omega)$ and $f(t,\omega)\equiv\sigma(t,\mathscr{Y}_{t}(\omega))$,
such a limit exists in the space $L^{2}(\Omega)$, the space of all square
integrable random variables. This intuition will be made precise and explored
in the next section, as we explore the Itô Integral.

##  4 Preliminaries

###  4.1 $\sigma$-algebras

Consider the space $(X,\mathscr{A})$. A $\sigma$-algebra $\mathscr{A}$ [4] is
a set of subsets in $X$ satisfying the following conditions:

  1. I

$X,\emptyset\in\mathscr{A}$

  2. II

if $A\in\mathscr{A}$ then $\overline{A}\in\mathscr{A}$

  3. III

if $A_{j}\in\mathscr{A}$ for $j\in\mathbb{N}$ then
$\displaystyle\bigcup_{j\in\mathbb{N}}A_{j}\in\mathscr{A}$

A _generator_ $\mathscr{G}$ is a set of arbitrary subsets such that these
subset generate a $\sigma$-algebra denoted by $\sigma(\mathscr{G})$ [4]. This
$\sigma$-algebra is also known as the smallest or _minimal_ $\sigma$-algebra.
It is defined as:

$\sigma(\mathscr{G}):=\bigcap_{\begin{subarray}{c}\hskip
2.8903pt\mathscr{H}_{k}\hskip 2.8903pt\text{is a}\hskip
2.8903pt\sigma-\text{alg}\\\ \hskip
7.22743pt\mathscr{G}\subset\mathscr{H}_{k}\end{subarray}}\mathscr{H}_{k}$

for an arbitrary index $k$.

###  4.2 Filtrations & $\mathscr{F}_{t}$ \- adapted processes

The family $\mathbb{F}:=\\{\mathscr{F}_{t}\\}_{t\in\bf{T}}$ of
$\sigma$-algebras of $\mathscr{F}$ defined on a measurable space
$(\Omega,\mathscr{F})$ is called a filtration if for all $s,t\in\bf{T}$ such
that $s\leq t$,

$\mathscr{F}_{s}\subseteq\mathscr{F}_{t}$

where $\bf{T}$ is an index set in any of the following:
$\mathbb{R},\mathbb{R}_{+},\mathbb{N},\mathbb{Z}$. [4]
An $\mathscr{F}_{t}$-measurable random variable signifies that:

$Z^{-1}(\mathscr{B}(\mathbb{R}))\subset\mathscr{F}_{t}$

which is a shorthand notation for:

$Z^{-1}(B)\in\mathscr{F}_{t},\forall B\in\mathscr{B}(\mathbb{R})$

Where $\mathscr{B}(\mathbb{R})=\sigma({[a,\infty)})$ for some
$a\in\mathbb{R}$.
Define a function $h:[0,\infty)\times\Omega\rightarrow\mathbb{R}$ with a
filtration $\mathbb{F}\subset\Omega$. The function is then called
$\mathscr{F}_{t}$-adapted if it is $\mathscr{F}_{t}$-measurable $\forall t\geq
0$. [4]

###  4.3 A.M - G.M Inequality & Lebesgue Integral

The A.M - G.M inequality states the following:

$\frac{a^{{}^{\prime}}+b^{{}^{\prime}}}{2}\geq\sqrt{a^{{}^{\prime}}b^{{}^{\prime}}}$

for $a^{{}^{\prime}},b^{{}^{\prime}}\in\mathbb{R^{+}}$. Now replace
$a^{{}^{\prime}}=a^{2}$ and $b^{{}^{\prime}}=b^{2}$. The inequality then
becomes:

$\frac{a^{2}+b^{2}}{2}\geq|ab|.$

for $a,b\in\mathbb{R}$. Using the fact that the Lebesgue integral with respect
to the probability measure is monotonic, we can apply it to the inequality as
follows:

$\displaystyle\int a^{2}+b^{2}d\mathbb{P}\geq 2\int|ab|d\mathbb{P}$
$\displaystyle\mathbb{E}[a^{2}+b^{2}]\geq 2\mathbb{E}[|ab|]$

###  4.4 $L^{p}$ Spaces

Suppose $X:\Omega\rightarrow\mathbb{R}^{n}$ is a random variable and
$p\in[1,\infty)$. The $L^{p}$ norm of $X$, $\|X\|_{L^{p}}$ is defined as [8] :

$\displaystyle\displaystyle\|X\|_{L^{p}}=\Bigg{(}\int_{\Omega}|X(\omega)|^{p}d\mathbb{P}(\omega)\Bigg{)}^{1/p}=\Big{(}\mathbb{E}(|X|^{p})\Big{)}^{1/p}$

##  5 Itô Integration

A process $\phi:[0,\infty)\times\Omega\rightarrow\mathbb{R}$ is called
_elementary_ if:

$\displaystyle\phi(t,\omega)=\sum_{j=1}^{K-1}Z_{j}(\omega)\mathbbm{1}_{(t_{i},t_{i+1}]}(t)\\\
$

where $0\leq t_{1}<t_{2}<...<t_{K}<\infty$ and where $Z_{j}$ $(1\leq i\leq K)$
is a complex square-integrable $\mathscr{F}_{t_{i}}$-measurable random
variable. [4]

$\displaystyle\int_{S}^{T}\phi(t,\omega)d\mathfrak{B}_{t}=\sum_{j=1}^{K-1}Z_{j}(\omega)[\mathfrak{B}_{t_{j+1}}-\mathfrak{B}_{t_{j}}](\omega)$

In our case, a square integrable random process is defined as

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|\phi(t)|^{2}dt\Bigg{]}<\infty$
(2)

Define $\mathfrak{L}(S,T)$ to be the class of functions [8]:

$f:[0,\infty)\times\Omega\rightarrow\mathbb{R}$ (3)

such that:

  1. I

$f(t,\omega)$ is $\mathscr{B}(\mathbb{R}^{+})\times\mathscr{F}$ \- measurable

  2. II

$f(t,\omega)$ is $\mathscr{F}_{t}$-adapted

  3. III

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}f(t,\omega)^{2}dt\Bigg{]}<\infty$

###  5.1 Construction of the Itô Integral

We will know construct the Itô integral. We will omit the proofs of the steps
needed for such a construction for the purpose of brevity. In brief, the
construction comprises of approximation lemmas for processes
$g\in\mathfrak{L}(S,T)$ in terms of elementary functions, and then utilise the
isometry property of the ito integral for elementary processes and the
completeness of the metric space $L^{2}(\Omega)$ to define a limit and call it
the Itô integral.
STEP I
Let $g\in\mathfrak{L}(S,T)$ be bounded and continuous for all
$\omega\in\Omega$. Then there exists elementary processes
$\phi_{n}\in\mathfrak{L}(S,T)$ such that [8]

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}(g-\phi_{n})^{2}dt\Bigg{]}\rightarrow
0\text{, as }n\rightarrow\infty$

STEP II
Let $h\in\mathfrak{L}(S,T)$ be bounded. Then there exist bounded functions
$g_{n}\in\mathfrak{L}(S,T)$ such that they are continuous for all $\omega$ and
$n$ and [8]

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}(h-g_{n})^{2}dt\Bigg{]}\rightarrow
0\text{, as }n\rightarrow\infty\\\ $

STEP III
Let $f\in\mathfrak{L}(S,T)$. Then there exists a sequence
$\\{h_{n}\\}\subset\mathfrak{L}(S,T)$ such that $h_{n}$ is bounded for each
$n$ and [8]

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}(f-h_{n})^{2}dt\Bigg{]}\rightarrow
0\text{, as }n\rightarrow\infty\\\ $

Now, using the above steps we show that for $f,\phi_{n}\in\mathfrak{L}(S,T)$:

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|f-\phi_{n}|^{2}dt\Bigg{]}\rightarrow
0\text{, as }n\rightarrow\infty\\\ $

First, maintain the definition for $f,\phi_{n},g$ and $h$ as they were in
steps I, II and III. We have:

$\displaystyle\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|f-\phi_{n}|^{2}dt\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|(f-h_{k})+(h_{k}-g_{m})+(g_{m}-\phi_{n})|^{2}dt\Bigg{]}$
$\displaystyle\leq
2\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|f-h_{k}|^{2}dt\Bigg{]}+4\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|h_{k}-g_{m}|^{2}dt\Bigg{]}+4\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|g_{m}-\phi_{n}|^{2}dt\Bigg{]}$

By Step III, fix a $k$ large enough such that:

$\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|f-h_{k}|^{2}dt\Bigg{]}<\frac{\epsilon}{6}\\\
$

By Step II, fix an $m$ large enough such that:

$\displaystyle\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|h_{k}-g_{m}|^{2}dt\Bigg{]}<\frac{\epsilon}{12}$

By Step I, fix an $N$ large enough such that for all $n\geq N$:

$\displaystyle\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|g_{m}-\phi_{n}|^{2}dt\Bigg{]}<\frac{\epsilon}{12}$

Hence, for all $n\geq N$, combining the above parts yields that

$\displaystyle\mathbb{E}\Bigg{[}\displaystyle\int_{S}^{T}|f-\phi_{n}|^{2}dt\Bigg{]}<\epsilon$

We now will state without proof a key property of the Itô integral for
elementary processes $\phi\in\mathfrak{L}(S,T)$, known as Itô Isometry and
states the following and can be found in [8]

$\displaystyle\displaystyle
E\left[\left(\int_{S}^{T}\phi(t)d\mathfrak{B}_{t}\right)^{2}\right]=E\left[\int_{S}^{T}\phi(t)^{2}dt\right]$

Now, armed with the above results, we are going to show that the sequence
$\left\\{\displaystyle\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\right\\}_{n\in\mathbb{N}}$
is Cauchy in $L^{2}(\Omega)$, where the $\phi_{n}(t,\omega)$ are elementary
approximants of $f(t,\omega)$ in the sense that
$E\left[\int_{S}^{T}(f-\phi_{n})^{2}dt\right]\rightarrow 0$ as
$n\rightarrow\infty$. For the above to be Cauchy, one needs

$\displaystyle\displaystyle\Bigg{\|}\int_{S}^{T}(\phi_{n}(t,\omega)-\phi_{m}(t,\omega))d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}=E\left[\left(\int_{S}^{T}(\phi_{n}(t,\omega)-\phi_{m}(t,\omega))d\mathfrak{B}_{t}\right)^{2}\right]$
$\displaystyle=E\left[\int_{S}^{T}\left(\phi_{n}(t,\omega)-\phi_{m}(t,\omega)\right)^{2}dt\right]$
$\displaystyle\leq
2E\left[\int_{S}^{T}\left(f(t,\omega)-\phi_{n}(t,\omega)\right)^{2}dt\right]+2E\left[\int_{S}^{T}\left(f(t,\omega)-\phi_{m}(t,\omega)\right)^{2}dt\right]\rightarrow
0$

as $n,m\rightarrow\infty$ by the A.M-G.M. inequality, the approximation lemma
and the isometry property of the Itô integral. The completeness of
$L^{2}(\Omega)$ implies that there is a random variable $I[f]_{S}^{T}\in
L^{2}(\Omega)$ such that

$\displaystyle\displaystyle
E\left[\left(I[f]_{S}^{T}-\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\right)^{2}\right]\rightarrow
0$

as $n\rightarrow\infty$. We can now define the Itô integral of $f(t,\omega)$
as

$\displaystyle\displaystyle\int_{S}^{T}f(t,\omega)d\mathfrak{B}_{t}:=I[f]_{S}^{T}\stackrel{{\scriptstyle
L^{2}(\Omega)}}{{=\joinrel=}}\displaystyle\lim_{n\rightarrow\infty}\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}$

It is also important to mention that the above limit does not depend on the
choice of approximants. So suppose the approximants $\phi_{n}(t,\omega)$ and
$\psi_{n}(t,\omega)$ converge in the $L^{2}(\Omega)$ sense to
$I_{1}[f]_{S}^{T}$ and $I_{2}[f]_{S}^{T}$ respectively, then we have

$\displaystyle\Bigg{\|}I_{1}[f]_{S}^{T}-I_{2}[f]_{S}^{T}\Bigg{\|}_{L^{2}(\Omega)}^{2}$
$\displaystyle\leq\Bigg{\|}\left(I_{1}[f]_{S}^{T}-\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\right)-\left(I_{2}[f]_{S}^{T}-\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\right)\Bigg{\|}_{L^{2}(\Omega)}^{2}$
$\displaystyle\leq\Bigg{\|}I_{1}[f]_{S}^{T}-\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}+\Bigg{\|}I_{2}[f]_{S}^{T}-\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}$
$\displaystyle\leq\Bigg{\|}I_{1}[f]_{S}^{T}-\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}+\Bigg{\|}I_{2}[f]_{S}^{T}-\int_{S}^{T}\psi_{n}(t,\omega)d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}+$
$\displaystyle\Bigg{\|}\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}-\int_{S}^{T}\psi_{n}(t,\omega)d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}\rightarrow
0$

as $n\rightarrow\infty$. This is because

$\displaystyle\Bigg{\|}\int_{S}^{T}\phi_{n}(t,\omega)d\mathfrak{B}_{t}-\int_{S}^{T}\psi_{n}(t,\omega)d\mathfrak{B}_{t}\Bigg{\|}_{L^{2}(\Omega)}^{2}=\mathbb{E}\left[\int_{S}^{T}(\phi_{n}-\psi_{n})^{2}(t,\omega)dt\right]$
$\displaystyle\leq
2\mathbb{E}\left[\int_{S}^{T}(\phi_{n}-f)^{2}(t,\omega)dt\right]+2\mathbb{E}\left[\int_{S}^{T}(\psi_{n}-f)^{2}(t,\omega)dt\right]\rightarrow
0$

by the fact that $\phi_{n}$ and $\psi_{n}$ are approximants to $f$ and the
definition of the ito integral. This shows that
$\Bigg{\|}I_{1}[f]_{S}^{T}-I_{2}[f]_{S}^{T}\Bigg{\|}_{L^{2}(\Omega)}^{2}=0$
which means that
$\displaystyle\mathbb{P}\Big{(}\Big{\\{}\omega\in\Omega\Big{|}I_{1}[f]_{S}^{T}(\omega)=I_{2}[f]_{S}^{T}(\omega)\Big{\\}}\Big{)}=1$,
that is that the limits are ’almost surely’ equal, hence the same in
$L^{2}(\Omega)$.

##  6 Numerical Results

Now, for some numerical results to buttress the theory, we consider the case
where the stock price process $\mathscr{Y}_{t}$ from some initial time $t=0$
to some final time $t=T$ follows the law

$\displaystyle\log\mathscr{Y}_{t}-\log\mathscr{Y}_{0}=\int_{0}^{t}\Gamma
dt+\int_{0}^{t}\Sigma d\mathfrak{B}_{t}$ (4)

for $t\in[0,T]$, where $\gamma(t)=\Gamma$ and
$\sigma(\mathscr{Y}_{t},t)=\Sigma$ are constants. The above formula is well
defined as constant functions are members of the space $\mathfrak{L}(0,T)$ for
which the Itô integral is defined. The above can be solved analytically, but a
numerical treatment will be explored within the context of Apple’s stock
price.

In the following example, the model will be tested against historical data
from January 1 2020 to December 31 2020. $\Gamma$ and $\Sigma$ will be
computed using historical daily log-returns from 11 October 2007. By daily
log-returns at a given date, we mean the natural logarithm of the ratio of the
price at said day by the price at the previous date.

First, we partition the period from 1 January 2020 to 31 December 2020 into
$\mathfrak{T}=\\{T_{i}\\}_{i\equiv i^{th}\text{trading day in the year}}$
starting from $i=0$ and we call the collection of log-returns
$\mathfrak{logR}=\\{\log R_{t_{i}}\\}_{t_{i}\in\mathfrak{T}\char
92\relax\\{T_{0}\\}}$ where $R=\frac{X_{i}}{X_{i-1}}$ and $X_{i}$ is the price
of Apple’s stock at some $t_{i}\in\mathfrak{T}\char 92\relax\\{T_{0}\\}$. We
use the above to compute $\Gamma$ and $\Sigma$:

$\displaystyle\centering\left\\{\begin{array}[]{@{}ll@{}}\Gamma\\\
\Sigma\end{array}\right.=\left\\{\begin{array}[]{@{}ll@{}}\overline{\mathfrak{LogR}}-\frac{\text{Var}(\mathfrak{LogR})^{2}}{2}\\\
\text{Var}(\mathfrak{LogR})\end{array}\right.\@add@centering$

where $\overline{\mathfrak{logR}}$ is the (sample) mean and
$\text{Var}(\mathfrak{logR})$ the (sample) variance of $\mathfrak{logR}$
respectively.

We are now in a position to consider discrete approximation to equation 1. As
per section 3, we consider the discrete stock price process
$\mathscr{Y}_{t}|_{\mathfrak{T}}:\mathfrak{T}\times\Omega\rightarrow\mathbb{R}$
given by:

$\displaystyle\mathscr{Y}_{t_{n}}|_{\mathfrak{T}}(\omega)$
$\displaystyle=H_{t_{0}}\times\exp{\left(\sum_{k=0}^{n-1}\gamma(t_{k-1})(\omega)\cdot(t_{k}-t_{k-1})\right)}$
$\displaystyle\times\exp{\left(\sum_{k=0}^{n-1}\sigma(t_{k-1},\mathscr{Y}_{t_{k-1}}(\omega))\cdot(\mathfrak{B}_{t_{k}}(\omega)-\mathfrak{B}_{t_{k-1}}(\omega))\right)}$

where $\mathscr{Y}_{t_{0}}|_{\mathfrak{T}}=H_{t_{0}}$, $t_{n}\in\mathfrak{T}$
and $\omega\in\Omega$.

It is clear from the sub-figure on the right of figure 1, the simulated paths
capture most of the historical time series of Apple’s stock price which is
another indicator that the model is qualitatively speaking, a good
approximation. However, only ten projections were performed, justifiably
casting doubt on the statistical significance of the above result.

To try and quantify the above intuition, we will try and compute numerically
the expected value, a central tendency indicator,
$\mathbb{E}\left[\text{Cor}(\mathscr{Y}_{t}|_{\mathfrak{T}},H_{t})\right]$ of
the correlation between $\mathscr{Y}_{t}|_{\mathfrak{T}}$ and $H_{t}$.

To achieve this, we consider $N$ independent and identically distributed
copies of the discrete process $\mathscr{Y}_{t}|_{\mathfrak{T}}$,
$\mathscr{Y}_{t}^{n}|_{\mathfrak{T}}$ where $n\in[1,N]\cap\mathbb{N}$;
intuitively, they correspond to $N$ distinct projections. The correlation
between the historical data and the $n^{\text{th}}$ projection is denoted by

$\text{Cor}(\mathscr{Y}_{t}^{n}|_{\mathfrak{T}},H_{t})$

with cumulative mean

$\displaystyle\mathfrak{Cor}^{N}=\frac{\sum_{n=1}^{N}\text{Cor}(\mathscr{Y}_{t}^{n},H_{t})}{N}$

taking $N\rightarrow\infty$, we obtain figure 2.

Figure 1: Plots of (Left) Apple Stock Price (Black) from January 2020 to
December 31 2020 and projections (coloured) and (Right) historical Apple stock
price from January 2020 to January 2021 and the area between the projections
assuming the law in equation (4) with $\Gamma=0.0008316271$ and
$\Sigma=0.01648899$.

According to basic probability theory, $\mathfrak{Cor}^{N}$ converge in the
sense of probability to the expected value of the correlation between the
discretised path and the historical trial data
$\mathbb{E}\left[\text{Cor}(\mathscr{Y}_{t}|_{\mathfrak{T}},H_{t})\right]$
[3]. This means that considering progressively larger values of N (that is
taking $N\rightarrow\infty$), $\mathfrak{Cor}^{N}$ should approach a constant
value (see figure 2).

Figure 2: Plot of mean correlation $\mathfrak{Cor}^{N}$ for values of N in
$\\{1,2,3,....,1000\\}$. The plot seems to converge to a value of
approximately $0.36$

Figure 2 suggests that
$\mathbb{E}\left[\text{Cor}(\mathscr{\mathscr{missing}}{Y}_{t}|_{\mathfrak{T}},H_{t})\right]\approx\mathfrak{Cor}^{N}$
tends to a constant value of $0.36$ for $N$ large. This suggests, in a rather
heuristic way, that the model ’captures’ 36% of the variability in stock
prices. Granted, further investigation is warranted over different stocks and
more involved models could of course be considered.

##  7 Conclusion

Through the course of the above, it has become palpable how Brownian Motion
encapsulates and can be used to model a crucial part of the uncertainty
inherent in financial markets paving way for a stochastic analysis,
culminating in the development of the Itô integral.

## References

  * [1] Introduction to Stochastic Integration.  Springer-Verlag, 2006.
  * [2] Louis Bachelier.  Théorie de la spéculation.  In Annales scientifiques de l’École normale supérieure, volume 17, pages 21–86, 1900.
  * [3] Joseph K Blitzstein and Jessica Hwang.  Introduction to probability.  Chapman and Hall/CRC, 2019.
  * [4] Pierre Brémaud.  Probability Theory and Stochastic Processes.  Springer Nature, 2020.
  * [5] Robert Brown.  Xxvii. a brief account of microscopical observations made in the months of june, july and august 1827, on the particles contained in the pollen of plants; and on the general existence of active molecules in organic and inorganic bodies.  The philosophical magazine, 4(21):161–173, 1828.
  * [6] E Robert Fernholz.  Stochastic portfolio theory.  In Stochastic portfolio theory, pages 1–24. Springer, 2002.
  * [7] Andrei Nikolaevich Kolmogorov and Albert T Bharucha-Reid.  Foundations of the theory of probability: Second English Edition.  Courier Dover Publications, 2018.
  * [8] Bernt Øksendal.  Stochastic differential equations.  In Stochastic differential equations, pages 65–84. Springer, 2003\.
  * [9] Norbert Wiener.  Differential-space.  Journal of Mathematics and Physics, 2(1-4):131–174, 1923.