# The Turán Number of Surfaces

Maya Sankar

(October 20, 2022)

###### Abstract

We show that there is a constant $c$ such that any 3-uniform hypergraph
${\mathcal{H}}$ with $n$ vertices and at least $cn^{5/2}$ edges contains a
triangulation of the real projective plane as a subgraph. This resolves a
conjecture of Kupavskii, Polyanskii, Tomon, and Zakharov. Furthermore, our
work, combined with prior results, asymptotically determines the Turán number
of all surfaces.

##  1 Introduction

Turán-type questions are fundamental in the study of extremal combinatorics.
Given a fixed $r$-uniform hypergraph ${\mathcal{F}}$, its _Turán number_
$\operatorname{ex}(n,{\mathcal{F}})$ is the maximum number of edges in an
$r$-uniform hypergraph ${\mathcal{H}}$ on $n$ vertices which does not contain
${\mathcal{F}}$ as a subgraph. Estimating Turán numbers for hypergraphs
remains a largely open problem; we refer the reader to the surveys [3, 9, 1]
for a general overview.

This paper investigates a topological variant of this extremal problem. Any
$r$-uniform hypergraph ${\mathcal{H}}$ may be viewed as an $(r-1)$-dimensional
simplicial complex whose facets are the edges of ${\mathcal{H}}$. Similarly,
one may ask if any subgraph of ${\mathcal{H}}$ is homeomorphic to a given
$(r-1)$-dimensional simplicial complex $X$. This geometric perspective yields
many natural generalizations of graph properties to higher dimensions. For
example, one analogue of Hamiltonian cycles in 3-uniform hypergraphs that has
received some attention (see [2, 8]) is a spanning sub-hypergraph homeomorphic
to the 2-sphere. Additionally, one is naturally interested in the following
extremal quantity. Let $X$ be a closed $(r-1)$-dimensional manifold. Denote by
$\operatorname{ex}_{\hom}(n,X)$ the maximum number of edges in a $r$-uniform
hypergraph ${\mathcal{H}}$ on $n$ vertices such that no subgraph of
${\mathcal{H}}$ is homeomorphic (as a simplicial complex) to $X$. This is the
_Turán number_ of the topological space $X$.

As part of his program in high-dimensional combinatorics, Linial [7] asked for
the asymptotics of $\operatorname{ex}_{\hom}(n,X)$ when $r\geq 3$. Linial’s
question was partially motivated by the work of Sós, Erdős, and Brown [10]
some decades prior, which showed that
$\operatorname{ex}_{\hom}(n,X)=\Theta(n^{5/2})$ when $X$ is the 2-sphere
$\mathbb{S}^{2}$. Linial [7] sketched a new proof of the lower bound
$\operatorname{ex}_{\hom}(n,\mathbb{S}^{2})=\Omega(n^{5/2})$ which generalized
to all closed, connected 2-manifolds $X$; this proof is given rigorously in
[5, §2]. We call such a 2-manifold a _surface_.

All surfaces fall into one of three categories: the sphere $\mathbb{S}^{2}$,
the connected sum of $g\geq 1$ tori, or the connected sum of $k\geq 1$ real
projective planes. Until recently, it was unknown if the lower bound of
$n^{5/2}$ was asymptotically tight for the latter two classes. Indeed, Linial
[6, 7] repeatedly conjectured a matching upper bound for the torus
$\mathbb{T}^{2}$, i.e. that
$\operatorname{ex}_{\hom}(n,\mathbb{T}^{2})=O(n^{5/2})$. Kupavskii,
Polyanskii, Tomon, and Zakharov[5] proved Linial’s conjecture in 2020.
Additionally, they showed that if two surfaces $X_{1},X_{2}$ satisfy
$\operatorname{ex}_{\hom}(n,X_{i})=O(n^{5/2})$, their connected sum
$X_{1}\\#X_{2}$ also satisfies
$\operatorname{ex}_{\hom}(n,X_{1}\\#X_{2})=O(n^{5/2})$, thereby extending the
upper bound $\operatorname{ex}_{\hom}(n,X)=O(n^{5/2})$ to orientable surfaces
of the form $X=\mathbb{T}^{2}\\#\cdots\\#\mathbb{T}^{2}$. They were unable to
derive the corresponding result for any non-orientable surfaces, but
conjectured that the same bound applies to all surfaces.

Our main result is the resolution of this conjecture. We show that Linial’s
lower bound is asymptotically tight for the real projective plane
${\mathbb{R}\mathbb{P}}^{2}$.

######  Theorem 1.1.

We have $\operatorname{ex}_{\hom}(n,{\mathbb{R}\mathbb{P}}^{2})=O(n^{5/2})$.

By Kupavskii, Polyanskii, Tomon, and Zakharov’s result on connected sums, this
bound generalizes to all non-orientable surfaces
$X={\mathbb{R}\mathbb{P}}^{2}\\#\cdots\\#{\mathbb{R}\mathbb{P}}^{2}$.
Combining our work with the results of Sós, Erdős, and Brown [10] for the
sphere and Kupavskii, Polyanskii, Tomon, and Zakharov[5] for all other
orientable surfaces, we completely determine the asymptotics of
$\operatorname{ex}_{\hom}(n,X)$ for any surface $X$.

######  Theorem 1.2.

Let $X$ be any surface. Then $\operatorname{ex}_{\hom}(n,X)=\Theta(n^{5/2})$,
where the constant coefficients may depend on the surface $X$.

The remainder of this paper is organized as follows. Section 2 describes how
simpler substructures of a 3-uniform hypergraph ${\mathcal{H}}$ may be
combined to obtain a subgraph homeomorphic to ${\mathbb{R}\mathbb{P}}^{2}$.
Section 3 introduces probabilistic methods, proving three lemmas used to bound
the probability that a random subset of $V({\mathcal{H}})$ contains one of
these structures. We prove Theorem 1.1 in Section 4 and discuss some open
problems in Section 5.

#### Notation.

Let ${\mathcal{H}}$ be a 3-uniform hypergraph. If $u$ is a vertex of
${\mathcal{H}}$, its _link graph_ ${\mathcal{H}}_{u}$ is the graph on
$V({\mathcal{H}})\setminus\\{u\\}$ whose edges $vw$ correspond to 3-edges
$uvw\in E({\mathcal{H}})$. For distinct vertices $u$ and $u^{\prime}$ of
${\mathcal{H}}$, we write
${\mathcal{H}}_{u,u^{\prime}}={\mathcal{H}}_{u}\cap{\mathcal{H}}_{u^{\prime}}$;
that is, ${\mathcal{H}}_{u,u^{\prime}}$ is the graph on
$V({\mathcal{H}})\setminus\\{u,u^{\prime}\\}$ with edge set
$E({\mathcal{H}}_{u})\cap E({\mathcal{H}}_{u^{\prime}})$.

For convenience, we do not always distinguish between a hypergraph and its
associated simplicial complex. For instance, we call ${\mathcal{H}}$ a disk,
or say ${\mathcal{H}}$ is homeomorphic to the disk, if its associated
simplicial complex is homeomorphic to the disk $\mathbb{D}^{2}$. Where the
distinction is essential, we write $X({\mathcal{H}})$ for the simplicial
complex associated to the hypergraph ${\mathcal{H}}$.

##  2 Finding ${\mathbb{R}\mathbb{P}}^{2}$ in a Hypergraph

Our proof of Theorem 1.1 begins by identifying conditions under which a
3-uniform hypergraph ${\mathcal{H}}$ contains a subgraph homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$. The main result of this section is Lemma 2.2,
which allows us to build such a subgraph from smaller substructures of
${\mathcal{H}}$. We first discuss our techniques in Section 2.1, then state
and prove Lemma 2.2 in Section 2.2.

###  2.1 Deconstructing ${\mathbb{R}\mathbb{P}}^{2}$

To motivate our strategy for building a copy of ${\mathbb{R}\mathbb{P}}^{2}$,
let us first describe how Sós, Erdős, and Brown [10] located copies of the
sphere $\mathbb{S}^{2}$. Suppose ${\mathcal{H}}$ is a 3-uniform hypergraph
with $n$ vertices and $cn^{5/2}$ edges, where $c$ is a sufficiently large
constant. By an averaging argument, one may find vertices $u,u^{\prime}$ such
that ${\mathcal{H}}_{u,u^{\prime}}$ has at least $n$ edges. This implies that
there is a cycle $C=v_{1}\cdots v_{k}$ in ${\mathcal{H}}_{u,u^{\prime}}$. One
obtains a subgraph of ${\mathcal{H}}$ homeomorphic to $\mathbb{S}^{2}$
comprising the $2k$ edges

$\bigcup_{e\in
E(C)}\\{ue,u^{\prime}e\\}=\\{uv_{1}v_{2},u^{\prime}v_{1}v_{2},\ldots,uv_{k}v_{1},u^{\prime}v_{k}v_{1}\\}.$

Such a triangulation of $\mathbb{S}^{2}$ is called a _double pyramid_.

The double pyramid may be viewed as the union of two interior-disjoint disks
with edge sets $\\{ue:e\in E(C)\\}$ and $\\{u^{\prime}e:e\in E(C)\\}$, glued
together along their shared boundary $C$. The sphere has a corresponding
decomposition as a CW complex, given by attaching two copies of the disk
$\mathbb{D}^{2}$ to a circle $\mathbb{S}^{1}$. These decompositions are
pictured side by side in Fig. 1.

$u$$u^{\prime}$ Figure 1: At left, a double pyramid obtained from a cycle of
length 6 in ${\mathcal{H}}_{u,u^{\prime}}$. At right, the decomposition of the
sphere $\mathbb{S}^{2}$ into two disks attached to $\mathbb{S}^{1}$. The
corresponding top disks are shaded in both images.

We decompose ${\mathbb{R}\mathbb{P}}^{2}$ in a similar fashion, as two copies
of $\mathbb{D}^{2}$ attached to $\mathbb{S}^{1}\vee\mathbb{S}^{1}$. Consider
the standard representation of ${\mathbb{R}\mathbb{P}}^{2}$ as a disk with
boundary glued to itself antipodally — this is pictured in Fig. 2. Let $a$ and
$b$ be the loops in ${\mathbb{R}\mathbb{P}}^{2}$ depicted, with $a$ traversing
half the boundary of the disk and $b$ a diameter of the disk. The union of $a$
and $b$, shown in Fig. 3, is a subspace of ${\mathbb{R}\mathbb{P}}^{2}$
homeomorphic to $\mathbb{S}^{1}\vee\mathbb{S}^{1}$. Moreover,
${\mathbb{R}\mathbb{P}}^{2}$ can be recovered from this subspace by attaching
two copies of $\mathbb{D}^{2}$ — one corresponding to each semicircular region
of Fig. 2 — to the concatenated loops $ab$ and $a^{-1}b$. This is summarized
in the following proposition.

$a$$a$$b$$v_{0}$$v_{0}$ Figure 2: Two loops $a$ and $b$ in
${\mathbb{R}\mathbb{P}}^{2}$ based at the point $v_{0}$. Here,
${\mathbb{R}\mathbb{P}}^{2}$ is depicted as a disk with boundary points
identified antipodally.

######  Proposition 2.1.

Let $a$ and $b$ be the two loops in $\mathbb{S}^{1}\vee\mathbb{S}^{1}$ shown
in Fig. 3. Form a CW complex from $\mathbb{S}^{1}\vee\mathbb{S}^{1}$ by
attaching one disk to the loop $ab$ and another disk to the loop $a^{-1}b$.
The resulting topological space is homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$.

$b$$a$$v_{0}$ Figure 3: Two loops $a$ and $b$ in
$\mathbb{S}^{1}\vee\mathbb{S}^{1}$ sharing the same basepoint $v_{0}$.

Let $\mathbb{D}^{2-}$ be the quotient of $\mathbb{D}^{2}$ obtained by gluing
together two points $x,y$ on the boundary of $\mathbb{D}^{2}$. Proposition 2.1
decomposes ${\mathbb{R}\mathbb{P}}^{2}$ as a union of two copies of
$\mathbb{D}^{2-}$ intersecting on their shared boundary, a subspace of
${\mathbb{R}\mathbb{P}}^{2}$ homeomorphic to
$\mathbb{S}^{1}\vee\mathbb{S}^{1}$.

One might attempt to build ${\mathbb{R}\mathbb{P}}^{2}$ using the following
naïve approach. Choose vertices $u,u^{\prime}$ and cycles
$C,C^{\prime}\subseteq{\mathcal{H}}_{u,u^{\prime}}$ so that $C$ and
$C^{\prime}$ intersect in a single vertex $v_{0}$, implying that $C\cup
C^{\prime}$ is homeomorphic to $\mathbb{S}^{1}\vee\mathbb{S}^{1}$. Let
${\mathcal{A}},{\mathcal{A}}^{\prime}\subseteq{\mathcal{H}}$ be subgraphs
induced by the edge sets $E({\mathcal{A}})=\\{ue:e\in E(C)\cup
E(C^{\prime})\\}$ and $E({\mathcal{A}}^{\prime})=\\{u^{\prime}e:e\in E(C)\cup
E(C^{\prime})\\}$. One hopes that ${\mathcal{A}}$ and ${\mathcal{A}}^{\prime}$
are copies of $\mathbb{D}^{2-}$ whose union is homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$, and indeed this is almost true. However, the
1-simplex $uv_{0}$ (resp. $u^{\prime}v_{0}$) is contained in four different
edges of ${\mathcal{A}}$ (resp. ${\mathcal{A}}^{\prime}$), so neither
${\mathcal{A}}$ nor ${\mathcal{A}}^{\prime}$ is homeomorphic to
$\mathbb{D}^{2-}$.

To obtain a homeomorphic copy of ${\mathbb{R}\mathbb{P}}^{2}$, we alter the
hypergraphs ${\mathcal{A}}$ and ${\mathcal{A}}^{\prime}$ to avoid these four-
way intersections. The resulting construction is pictured in Fig. 4. Let
$v_{1},v_{2}$ be the two neighbors of $v_{0}$ in $C$, and let $v_{3},v_{4}$ be
the two neighbors of $v_{0}$ in $C^{\prime}$. Consider the edge subsets
$D=\\{uv_{0}v_{1},uv_{0}v_{3}\\}\subseteq E({\mathcal{A}})$ and
$D^{\prime}=\\{u^{\prime}v_{0}v_{2},u^{\prime}v_{0}v_{3}\\}\subseteq
E({\mathcal{A}}^{\prime})$, which correspond to disks with boundaries
$v_{0}v_{1}uv_{3}v_{0}$ and $v_{0}v_{2}u^{\prime}v_{3}v_{0}$ respectively. We
locate alternate disk subgraphs
${\mathcal{D}},{\mathcal{D}}^{\prime}\subseteq{\mathcal{H}}$ having the same
boundaries, and replace $D$ and $D^{\prime}$ with them. If ${\mathcal{D}}$ and
${\mathcal{D}}^{\prime}$ are chosen appropriately, the altered hypergraphs
$({\mathcal{A}}\setminus D)\cup{\mathcal{D}}$ and
$({\mathcal{A}}^{\prime}\setminus D^{\prime})\cup{\mathcal{D}}^{\prime}$ are
homeomorphic to $\mathbb{D}^{2-}$ with shared boundary $C\cup C^{\prime}$. In
fact, they are created by attaching disks to $C\cup C^{\prime}$ along the
loops
$v_{0}v_{2}\,\overset{{}_{C}}{\cdots}\,v_{1}v_{0}v_{3}\,\overset{{}_{C^{\prime}}}{\cdots}\,v_{4}v_{0}$
and
$v_{0}v_{1}\,\overset{{}_{C}}{\cdots}\,v_{2}v_{0}v_{3}\,\overset{{}_{C^{\prime}}}{\cdots}\,v_{4}v_{0}$,
respectively. Using Proposition 2.1, one can show that their union is
homeomorphic to ${\mathbb{R}\mathbb{P}}^{2}$.

Lemma 2.2, stated in the next subsection, formalizes this construction. It
gives explicit conditions on
$C,C^{\prime},{\mathcal{D}},{\mathcal{D}}^{\prime}$ under which the union
$({\mathcal{A}}\setminus
D)\cup{\mathcal{D}}\cup({\mathcal{A}}^{\prime}\setminus
D^{\prime})\cup{\mathcal{D}}^{\prime}$ yields a copy of
${\mathbb{R}\mathbb{P}}^{2}$ in ${\mathcal{H}}$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$u$$u^{\prime}$${\mathcal{D}}$${\mathcal{D}}^{\prime}$$C$$C^{\prime}$
Figure 4: Building ${\mathbb{R}\mathbb{P}}^{2}$ from cycles
$C,C^{\prime}\subseteq{\mathcal{H}}_{u,u^{\prime}}$ and disks
${\mathcal{D}},{\mathcal{D}}^{\prime}\subseteq{\mathcal{H}}$.

###  2.2 Building a Homeomorphic Copy of ${\mathbb{R}\mathbb{P}}^{2}$

We are almost ready to state Lemma 2.2, which is the focus of this section.
However, we must first introduce some basic notation.

Suppose $X$ is a simplicial complex homeomorphic to $\mathbb{D}^{2}$ or
$\mathbb{D}^{2-}$. (Recall that $\mathbb{D}^{2-}$ is the quotient of
$\mathbb{D}^{2}$ obtained by gluing together two points on the boundary of
$\mathbb{D}^{2}$.) Its _boundary_ $\partial X$ is a sub-simplicial complex
homeomorphic to $\mathbb{S}^{1}$ or $\mathbb{S}^{1}\vee\mathbb{S}^{1}$,
respectively. We say that $X$ has _induced boundary_ if every simplex $\Delta$
in $X$ with $\Delta\subseteq V(\partial X)$ is also a simplex of $\partial X$.
We write $V^{\circ}(X)=V(X)\setminus V(\partial X)$ for the set of _interior
vertices_ of $X$. For convenience, if $X=X({\mathcal{D}})$ is the simplicial
complex associated to a 3-uniform hypergraph ${\mathcal{D}}$, we may simply
refer to $\partial{\mathcal{D}}$ or $V^{\circ}({\mathcal{D}})$, or say that
${\mathcal{D}}$ has induced boundary.

These definitions allow us to state and prove Lemma 2.2, providing conditions
under which a 3-uniform hypergraph contains a subgraph homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$. Fig. 4 provides a visual depiction of this
lemma.

######  Lemma 2.2.

Let ${\mathcal{H}}$ be a 3-uniform hypergraph. Let $u,u^{\prime}\in
V({\mathcal{H}})$ and write $G={\mathcal{H}}_{u,u^{\prime}}$. Let
$v_{0},v_{1},v_{2},v_{3}\in V(G)$ be distinct vertices with
$v_{1},v_{2},v_{3}\in N_{G}(v_{0})$. Suppose

  1. (i)

$C$ and $C^{\prime}$ are cycles in $G$ with $v_{1}v_{0}v_{2}$ a subpath of $C$
and $v_{0}v_{3}$ an edge of $C^{\prime}$; and

  2. (ii)

${\mathcal{D}}$ and ${\mathcal{D}}^{\prime}$ are subgraphs of ${\mathcal{H}}$
homeomorphic to $\mathbb{D}^{2}$ with induced boundaries
$\partial{\mathcal{D}}=v_{0}v_{1}uv_{3}v_{0}$ and
$\partial{\mathcal{D}}^{\prime}=v_{0}v_{2}u^{\prime}v_{3}v_{0}$.

Suppose further that the five sets $V(C)\setminus\\{v_{0},v_{1}\\}$,
$V(C^{\prime})\setminus\\{v_{0},v_{3}\\}$, $V^{\circ}({\mathcal{D}})$,
$V^{\circ}({\mathcal{D}}^{\prime})$, and
$W=\\{u,u^{\prime},v_{0},v_{1},v_{3}\\}$ are all disjoint. Then
${\mathcal{H}}$ contains a subgraph homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$.

###### Proof.

Write $C=v_{0}w_{1}\cdots w_{k}v_{0}$ with $w_{1}=v_{1}$ and $w_{k}=v_{2}$.
Write $C^{\prime}=v_{0}x_{1}\cdots x_{\ell}v_{0}$ with $x_{\ell}=v_{3}$. By
hypothesis, the vertices
$u,u^{\prime},v_{0},w_{1},\ldots,w_{k},x_{1},\ldots,x_{\ell}$ are distinct and
are not contained in $V^{\circ}({\mathcal{D}})$ or
$V^{\circ}({\mathcal{D}}^{\prime})$.

Our proof proceeds as follows. We first locate subgraphs
${\mathcal{A}},{\mathcal{A}}^{\prime}\subseteq{\mathcal{H}}$ homeomorphic to
$\mathbb{D}^{2-}$ with induced boundaries
$\partial{\mathcal{A}}=\partial{\mathcal{A}}^{\prime}=C\cup C^{\prime}$ and
interior vertex sets
$V^{\circ}({\mathcal{A}})=V^{\circ}({\mathcal{D}})\cup\\{u\\}$ and
$V^{\circ}({\mathcal{A}}^{\prime})=V^{\circ}({\mathcal{D}}^{\prime})\cup\\{u^{\prime}\\}$.
Then, using Proposition 2.1, we deduce that the union
${\mathcal{A}}\cup{\mathcal{A}}^{\prime}$ is homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$.

Let $P$ be the path $w_{1}\cdots w_{k}v_{0}x_{1}\cdots x_{\ell}=(C\cup
C^{\prime})\setminus\\{v_{0}v_{1},v_{0}v_{3}\\}$ with endpoints $v_{1}=w_{1}$
and $v_{3}=x_{\ell}$. Consider the subgraph
${\mathcal{A}}_{0}\subseteq{\mathcal{H}}$ with edge set
$E({\mathcal{A}}_{0})=\\{ue:e\in E(P)\\}$. Because $P$ repeats no vertices,
${\mathcal{A}}_{0}$ is a disk with boundary
$\partial{\mathcal{A}}_{0}=uv_{1}\,\overset{{}_{P}}{\cdots}\,v_{3}u$. Take
${\mathcal{A}}={\mathcal{A}}_{0}\cup{\mathcal{D}}$.

We claim that the simplicial complexes $X({\mathcal{A}}_{0})$ and
$X({\mathcal{D}})$ only intersect at the vertex $v_{0}$ and the path
$v_{1}uv_{3}$. Because ${\mathcal{D}}$ has induced boundary and
$V({\mathcal{A}}_{0})=\\{u\\}\cup V(P)$ is disjoint from
$V^{\circ}({\mathcal{D}})$, we have $X({\mathcal{A}}_{0})\cap
X({\mathcal{D}})\subseteq\partial{\mathcal{D}}=v_{0}v_{1}uv_{3}v_{0}$. Clearly
$X({\mathcal{A}}_{0})$ contains $v_{0}$ and $v_{1}uv_{3}$. Moreover, because
$v_{0}v_{1}$ and $v_{0}v_{3}$ are not edges of $P$, they are not 1-simplices
of $X({\mathcal{A}}_{0})$. Thus, $X({\mathcal{A}}_{0})\cap X({\mathcal{D}})$
is the disjoint union of $v_{0}$ and $v_{1}uv_{3}$, as described.

We conclude that ${\mathcal{A}}$ is formed by gluing the disks
${\mathcal{A}}_{0}$ and ${\mathcal{D}}$ together at a point $v_{0}$ and
disjoint subpath $v_{1}uv_{3}$ of their boundaries. Alternatively,
${\mathcal{A}}$ is formed by attaching the boundary of a disk to the closed
walk $v_{0}v_{1}\,\overset{{}_{P}}{\cdots}\,v_{3}v_{0}=v_{0}w_{1}\cdots
w_{k}v_{0}x_{1}\cdots x_{\ell}v_{0}$. This yields that ${\mathcal{A}}$ is
homeomorphic to $\mathbb{D}^{2-}$ with $\partial A=C\cup C^{\prime}$.
Moreover, $V^{\circ}({\mathcal{A}})=(V({\mathcal{A}}_{0})\cup
V^{\circ}({\mathcal{D}})\cup V(\partial{\mathcal{D}}))\setminus
V(\partial{\mathcal{A}})=\\{u\\}\cup V^{\circ}({\mathcal{D}})$.

Lastly, we verify that ${\mathcal{A}}$ has induced boundary, by checking which
simplices of $X({\mathcal{A}}_{0})$ and $X({\mathcal{D}})$ are fully contained
in $V(\partial{\mathcal{A}})$. Because $u\notin V(\partial{\mathcal{A}})$, the
only simplices of $X({\mathcal{A}}_{0})$ fully contained in
$V(\partial{\mathcal{A}})$ are the vertices and edges of $P$, which are
simplices of $\partial{\mathcal{A}}=C\cup C^{\prime}$. Now, notice that
$V({\mathcal{D}})\cap
V(\partial{\mathcal{A}})=\\{v_{1},v_{0},v_{3}\\}\subseteq
V(\partial{\mathcal{D}})$. Because ${\mathcal{D}}$ has induced boundary, the
only simplices of $X({\mathcal{D}})$ fully contained in
$V(\partial{\mathcal{A}})$ are those simplices of
$\partial{\mathcal{D}}=v_{0}v_{1}uv_{3}v_{0}$ fully contained in
$\\{v_{1},v_{0},v_{3}\\}$, i.e. the vertices and edges of the path
$v_{1}v_{0}v_{3}$. These are all simplices of $\partial{\mathcal{A}}=C\cup
C^{\prime}$, so ${\mathcal{A}}$ has induced boundary.

The construction of ${\mathcal{A}}^{\prime}$ is analogous. Let
$P^{\prime}=w_{k}\cdots w_{1}v_{0}x_{1}\cdots x_{\ell}=(C\cup
C^{\prime})\setminus\\{v_{0}v_{2},v_{0}v_{3}\\}$. Let
${\mathcal{A}}_{0}^{\prime}\subseteq{\mathcal{H}}$ have edge set
$E({\mathcal{A}}_{0}^{\prime})=\\{u^{\prime}e:e\in E(P^{\prime})\\}$ and take
${\mathcal{A}}^{\prime}={\mathcal{A}}^{\prime}_{0}\cup{\mathcal{D}}^{\prime}$.
An analogous argument shows that ${\mathcal{A}}^{\prime}$ is formed by
attaching the boundary of a disk to the closed walk
$v_{0}v_{2}\,\overset{{}_{P^{\prime}}}{\cdots}\,v_{3}v_{0}=v_{0}w_{k}\cdots
w_{1}v_{0}x_{1}\cdots x_{\ell}v_{0}$, and that ${\mathcal{A}}^{\prime}$ has
induced boundary $\partial{\mathcal{A}}^{\prime}=C\cup C^{\prime}$ and
interior vertex set $V^{\circ}({\mathcal{A}}^{\prime})=\\{u^{\prime}\\}\cup
V({\mathcal{D}}^{\prime})$.

We end our proof by showing that the union
${\mathcal{A}}\cup{\mathcal{A}}^{\prime}$ is homeomorphic to
${\mathbb{R}\mathbb{P}}^{2}$. Because ${\mathcal{A}}$ and
${\mathcal{A}}^{\prime}$ induce their boundaries and have disjoint interior
vertex sets $V^{\circ}({\mathcal{A}})=\\{u\\}\cup V^{\circ}({\mathcal{D}})$
and $V^{\circ}({\mathcal{A}}^{\prime})=\\{u^{\prime}\\}\cup
V^{\circ}({\mathcal{D}}^{\prime})$, the simplicial complexes
$X({\mathcal{A}})$ and $X({\mathcal{A}}^{\prime})$ only intersect on their
shared boundary $C\cup C^{\prime}$. Thus,
${\mathcal{A}}\cup{\mathcal{A}}^{\prime}$ is formed by attaching two interior-
disjoint copies of $\mathbb{D}^{2}$ to $C\cup C^{\prime}$, identifying the
disks’ boundaries with the two closed walks $v_{0}w_{1}\cdots
w_{k}v_{0}x_{1}\cdots x_{\ell}v_{0}$ and $v_{0}w_{k}\cdots
w_{1}v_{0}x_{1}\cdots x_{\ell}v_{0}$. By Proposition 2.1, the resulting
topological space is homeomorphic to ${\mathbb{R}\mathbb{P}}^{2}$. ∎

##  3 Probabilistic Preliminaries

Lemma 2.2 reduces Theorem 1.1 to finding substructures
$C,C^{\prime},{\mathcal{D}},{\mathcal{D}}^{\prime}$ of a 3-uniform hypergraph
${\mathcal{H}}$ satisfying the relevant hypotheses. We locate these
substructures via a probabilistic approach, analyzing the likelihood that a
randomly chosen subset of $V({\mathcal{H}})$ will contain each of these
substructures. To quantify these probabilities, we require some new
definitions. The terms _admissible_ and _semi-admissible_ (Definitions 3.1 and
3.2 below) were introduced by Kupavskii, Polyanskii, Tomon, and Zakharov[5]
and were crucial to their upper bound on the Turán number of the torus, which
also used probabilistic methods.

This section proves three technical lemmas — Lemmas 3.3, 3.4 and 3.6 — which
rely on this terminology. When combined, these lemmas allow us to bound the
probability that each of the above substructures exists in a randomly chosen
subset of $V({\mathcal{H}})$, paving the way for the proof of Theorem 1.1 in
Section 4.

Let $p\in[0,1]$ and let $V$ be a set. The notation $U\sim_{p}V$ indicates that
$U$ is a random subset of $V$ which independently contains each $v\in V$ with
probability $p$. Now, let $G$ be a graph, and let $U\subseteq V(G)$ be a set
of vertices. Given $x,y\in V(G)$, a path from $x$ to $y$ _through $U$_ is a
path from $x$ to $y$ of length at least 2 in $G[U\cup\\{x,y\\}]$.

######  Definition 3.1.

Fix $p,\epsilon\in(0,1]$ and let $k$ be a positive integer. Let $G$ be a graph
and $e=xy$ an edge of $G$. Sample $U\sim_{p}V(G)$ and let $A_{e}$ be the event
that there are at least $k$ internally vertex-disjoint paths from $x$ to $y$
through $U$. We say the edge $e$ is _$(p,\epsilon,k)$ -admissible_ if
$\Pr[A_{e}]\geq 1-\epsilon$.

######  Definition 3.2.

Let ${\mathcal{H}}$ be a 3-uniform hypergraph and let $e=xyz$ and
$f=x^{\prime}yz$ be neighboring edges of ${\mathcal{H}}$. Say the pair $(e,f)$
is _$(p,\epsilon,k)$ -admissible_ if $yz$ is $(p,\epsilon,k)$-admissible in
the graph ${\mathcal{H}}_{x,x^{\prime}}$. Also, for a positive integer $r$,
say that $(e,f)$ is _$(p,\epsilon,k,r)$ -semi-admissible_ if there exist at
least $r$ edges $g=x^{\prime\prime}yz$ such that $(e,g)$ and $(g,f)$ are both
$(p,\epsilon,k)$-admissible.

We remark that, although Definitions 3.1 and 3.2 seem convoluted at first
glance, they are in fact quite convenient to work with. Our first technical
lemma, which locates disks within random subsets of $V({\mathcal{H}})$,
illustrates their use.

Suppose $(e,f)=(xyz,x^{\prime}yz)$ is a pair of $(p,\epsilon,k)$-admissible
edges in ${\mathcal{H}}$. One corollary of the admissibility condition is that
that there are many double pyramids $\SS$ containing $e$ and $f$, each
obtained from a cycle in ${\mathcal{H}}_{x,x^{\prime}}$ containing $yz$.
Cutting any such $\SS$ along the loop $yxzx^{\prime}y$ partitions $\SS$ into
two disks $\\{e,f\\}$ and $\SS\setminus\\{e,f\\}$, both having boundary
$yxzx^{\prime}y$. Furthermore, it is not difficult to see that
${\mathcal{D}}=\SS\setminus\\{e,f\\}$ has induced boundary. Lemma 3.3 extends
this idea to a more general setting: given only a semi-admissibility condition
on $(e,f)$, we locate such a disk ${\mathcal{D}}$ within a randomly chosen
subset of $V({\mathcal{H}})$.

######  Lemma 3.3.

Fix $p,\epsilon\in(0,\frac{1}{2}]$ and positive integers $k,r$. Let
${\mathcal{H}}$ be a 3-uniform hypergraph. Let $(e,f)=(xyz,x^{\prime}yz)$ be a
pair of $(p,\epsilon,k+2,r)$-semi-admissible edges in ${\mathcal{H}}$, and fix
a set $W\subseteq V({\mathcal{H}})$ with $|W|\leq k$. Randomly sample
$U\sim_{2p}V({\mathcal{H}})$. Then with probability at least
$1-2r\epsilon-(1-2p)^{r-k}$, there is ${\mathcal{D}}\subseteq{\mathcal{H}}$
homeomorphic to $\mathbb{D}^{2}$ with induced boundary
$\partial{\mathcal{D}}=yxzx^{\prime}y$ and interior vertex set
$V^{\circ}({\mathcal{D}})\subseteq U\setminus W$.

###### Proof.

Let $T$ be a set of $r$ vertices such that for each $w\in T$, the triple
$g=wyz$ is an edge of ${\mathcal{H}}$ with $(e,g)$ and $(g,f)$ both
$(p,\epsilon,k+2)$-admissible.

Sample $U_{1}\sim_{\frac{1}{2}}U$ and let $U_{2}=U\setminus U_{1}$. For each
$w\in T$, consider the following three events.

  * ($A_{w}$)

$w\in U\setminus W$.

  * ($B_{w}$)

There is a path $P_{w}\subseteq{\mathcal{H}}_{x,w}$ from $y$ to $z$ through
$U_{1}\setminus(W\cup\\{x^{\prime}\\})$.

  * ($C_{w}$)

There is a path $Q_{w}\subseteq{\mathcal{H}}_{w,x^{\prime}}$ from $y$ to $z$
through $U_{2}\setminus(W\cup\\{x\\})$.

Suppose $A_{w}$, $B_{w}$, and $C_{w}$ hold for some $w\in T$. Write
$P_{w}=ya_{1}\cdots a_{s}z$ and $Q_{w}=yb_{1}\cdots b_{t}z$ with $s,t\geq 1$.
For convenience, set $a_{0}=b_{0}=y$ and $a_{s+1}=b_{t+1}=z$. Consider the
subgraph ${\mathcal{D}}$ of $H$ with edge set

$E({\mathcal{D}})=\left(\bigcup_{i=0}^{s}\\{xa_{i}a_{i+1},wa_{i}a_{i+1}\\}\right)\cup\left(\bigcup_{j=0}^{t}\\{wb_{j}b_{j+1},x^{\prime}b_{j}b_{j+1}\\}\right)$

as pictured in Fig. 5. Because the $5+s+t$ vertices pictured are all distinct,
it follows that ${\mathcal{D}}$ is a disk with boundary
$\partial{\mathcal{D}}=yxzx^{\prime}y$. Notice that each simplex of
$X({\mathcal{D}})$ contains at most one vertex of $\\{x,x^{\prime}\\}$ and at
most one vertex in $\\{y,z\\}$, the latter because $s,t\geq 1$. It follows
that the only simplices of $X({\mathcal{D}})$ that are fully contained in
$V(\partial{\mathcal{D}})$ are the 1-simplices $xy,x^{\prime}y,xz,x^{\prime}z$
and their vertices, implying that ${\mathcal{D}}$ has induced boundary.
Lastly, notice that conditions $A_{w}$, $B_{w}$, and $C_{w}$ together imply
that

$V^{\circ}({\mathcal{D}})=\\{w,a_{1},\ldots,a_{s},b_{1},\ldots,b_{t}\\}\subseteq
U\setminus W.$

We conclude that if the events $A_{w}$, $B_{w}$, and $C_{w}$ simultaneously
hold for some $w\in T$, then there is a disk
${\mathcal{D}}\subseteq{\mathcal{H}}$ with induced boundary
$\partial{\mathcal{D}}=yxzx^{\prime}y$ and interior vertex set
$V^{\circ}({\mathcal{D}})\subseteq U\setminus W$. It remains to bound the
probability that $A_{w}$, $B_{w}$, and $C_{w}$ hold simultaneously for some
$w\in T$.

$x$$w$$x^{\prime}$$y$$z$ Figure 5: A disk
${\mathcal{D}}\subseteq{\mathcal{H}}$ constructed from the semi-admissible
pair $(xyz,x^{\prime}yz)$.

Because $(e,g)$ is $(p,\epsilon,k+2)$-admissible and $U_{1}\sim_{p}V$, there
are $k+2$ internally vertex-disjoint paths in ${\mathcal{H}}_{x,w}$ from $y$
to $z$ through $U_{1}$ with probability at least $1-\epsilon$. At least one of
these paths avoids every vertex in $W\cup\\{x^{\prime}\\}$, so $\Pr[B_{w}]\geq
1-\epsilon$. Similarly, $\Pr[C_{w}]\geq 1-\epsilon$ for each $w\in T$. A union
bound yields that the events $B_{w}$ and $C_{w}$ hold simultaneously for all
$w\in T$ with probability at least $1-2r\epsilon$.

It remains to bound the probability that $A_{w}$ holds for some $w\in T$. This
is the probability that $T\cap(U\setminus W)=(T\setminus W)\cap U$ is
nonempty, which is $1-(1-2p)^{|T\setminus W|}$. Thus, another union bound
yields

$\displaystyle\Pr[$ $\displaystyle\exists w\in T\colon A_{w},B_{w},C_{w}\text{
all hold}]$ $\displaystyle\geq\Pr[\text{($B_{w}$ and $C_{w}$ hold for all
$w\in T$) and ($A_{w}$ holds for some $w\in T$)}]$ $\displaystyle\geq
1-2r\epsilon-(1-2p)^{|T\setminus W|}\geq 1-2r\epsilon-(1-2p)^{r-k}.\qed$

The remaining two lemmas in this section help us find the vertices
$u,u^{\prime},v_{0},v_{1},v_{2},v_{3}$ described in Lemma 2.2. Lemma 3.4
locates vertices $u,u^{\prime}$ and a large subgraph
$G\subseteq{\mathcal{H}}_{u,u^{\prime}}$ which gives rise to many semi-
admissible edge pairs. Lemma 3.6 then identifies incident edges $v_{0}v_{1}$
and $v_{0}v_{3}$ in $G$ satisfying admissibility conditions in a subgraph
$H\subseteq G$. Lemma 3.6 also upper-bounds $\deg_{H}(v_{0})$; this allows us
to randomly select $v_{2}$ from $N_{H}(v_{0})$ while lower-bounding the
probability that $v_{2}$ takes on any fixed value.

######  Lemma 3.4.

Fix $p,\epsilon\in(0,1]$, integers $r,k$, and a large constant $d$. There is a
constant $c=c(p,\epsilon,r,k,d)$ such that the following holds.

Suppose ${\mathcal{H}}$ is a 3-uniform hypergraph on $n$ vertices with at
least $cn^{5/2}$ edges. Then there are vertices $u,u^{\prime}\in
V({\mathcal{H}})$ and a graph $G\subseteq{\mathcal{H}}_{u,u^{\prime}}$ with at
least $dn/4$ edges such that, for any incident edges $vw,vw^{\prime}\in E(G)$,
the pairs $(uvw,uvw^{\prime})$ and $(u^{\prime}vw,u^{\prime}vw^{\prime})$ are
both $(p,\epsilon,k,r)$-semi-admissible in ${\mathcal{H}}$.

The proof of Lemma 3.4 relies on the following lemma of Kupavskii, Polyanskii,
Tomon, and Zakharov[5], which finds a positive-density subset of
$E({\mathcal{H}})$ with many semi-admissible pairs.

######  Lemma 3.5 (Lemma 3.3 in [5]).

Let $p,\epsilon\in(0,1]$ and let $k,r,n$ be positive integers. Let
${\mathcal{H}}$ be a 3-uniform hypergraph with $n$ vertices and at least
$\frac{12r}{p}\sqrt{\frac{k}{\epsilon}}n^{5/2}$ edges. Then $E({\mathcal{H}})$
contains a subset $F$ of at least $\frac{1}{2}|E({\mathcal{H}})|$ edges such
that any pair of neighboring edges in $F$ is $(p,\epsilon,k,r)$-semi-
admissible in ${\mathcal{H}}$.

###### Proof of Lemma 3.4.

Choose
$c=\max\left(\frac{12r}{p}\sqrt{\frac{k}{\epsilon}},\sqrt{\frac{d}{12}}\right)$.
By Lemma 3.5, there is a subset $F\subseteq E({\mathcal{H}})$ of size at least
$\frac{c}{2}n^{5/2}$ with the property that any neighboring edges
$xyz,x^{\prime}yz\in F$ are $(p,\epsilon,k,r)$-semi-admissible in
${\mathcal{H}}$. Let ${\mathcal{H}}^{\prime}\subseteq{\mathcal{H}}$ be the
3-uniform hypergraph on $V({\mathcal{H}})$ with edge set $F$. We use an
averaging argument to show that $e({\mathcal{H}}^{\prime}_{u,u^{\prime}})\geq
dn/4$ for some $u,u^{\prime}\in V({\mathcal{H}})$. In this case,
$G={\mathcal{H}}^{\prime}_{u,u^{\prime}}$ satisfies the desired conditions.

Set $V=V({\mathcal{H}})$ and randomly choose $(u,u^{\prime})\in V^{2}$
uniformly among all pairs of distinct vertices. Given an unordered pair of
vertices $vw\in\binom{V}{2}$, let $T_{vw}=|\\{u^{\prime\prime}\in
V:u^{\prime\prime}vw\in F\\}|$. We have

$\displaystyle{\mathbb{E}}[e({\mathcal{H}}_{u,u^{\prime}})]$
$\displaystyle=\sum_{vw\in\binom{V}{2}}\Pr[vw\in
E({\mathcal{H}}_{u,u^{\prime}})]=\frac{1}{n(n-1)}\sum_{vw\in\binom{V}{2}}T_{vw}(T_{vw}-1).$

The average of the $T_{vw}$ is

$T=\frac{2}{n(n-1)}\sum_{vw\in\binom{V}{2}}T_{vw}=\frac{2}{n(n-1)}\times
3|F|\geq 3c\sqrt{n}.$

Then, by convexity,

${\mathbb{E}}[e({\mathcal{H}}_{u,u^{\prime}})]\geq\frac{1}{n(n-1)}\times\binom{n}{2}T(T-1)\geq\frac{1}{2}(3c\sqrt{n})(3c\sqrt{n}-1).$

Because $c\geq\max\left(1,\sqrt{\frac{d}{12}}\right)$ and $n\geq 1$, we have

${\mathbb{E}}[e({\mathcal{H}}_{u,u^{\prime}})]\geq\frac{1}{2}(3c\sqrt{n})(2c\sqrt{n})=3c^{2}n\geq\frac{dn}{4}.$

Thus, there are vertices $u,u^{\prime}\in V$ such that
$G={\mathcal{H}}^{\prime}_{u,u^{\prime}}$ has at least $dn/4$ edges. Moreover,
for any incident edges $vw,vw^{\prime}\in E(G)$, the four edges
$uvw,uvw^{\prime},u^{\prime}vw,u^{\prime}vw^{\prime}$ are all in $F$, implying
that the pairs $(uvw,uvw^{\prime})$ and $(u^{\prime}vw,u^{\prime}vw^{\prime})$
are both $(p,\epsilon,k,r)$-semi-admissible in ${\mathcal{H}}$. ∎

######  Lemma 3.6.

Fix $p,\epsilon\in(0,1]$ and fix a positive integer $k$. There is a constant
$d=d(p,\epsilon,k)$ such that the following holds.

Suppose $G$ is a graph with $n$ vertices and at least $dn/4$ edges. Then there
is a subgraph $H\subseteq G$ containing two incident edges
$v_{0}v_{1},v_{0}v_{3}\in E(H)$ which are both $(p,\epsilon,k)$-admissible in
$H$. Moreover, $\deg_{H}(v_{0})\leq d$.

Proving Lemma 3.6 requires another preliminary result from [5], stated below.
It asserts that almost all edges of a sufficiently dense graph are admissible.

######  Lemma 3.7 (Lemma 3.1 in [5]).

Fix $p,\epsilon\in(0,1]$ and integers $k,n$. If $G$ is a graph on $n$
vertices, all but at most $\frac{2k}{p^{2}\epsilon}|V(G)|$ edges of $G$ are
$(p,\epsilon,k)$-admissible.

###### Proof of Lemma 3.6.

Set $\alpha=\frac{2k}{p^{2}\epsilon}$ and set $d=4(1+2\alpha)$.

Let us induct on $n$. For the base case, suppose $n\leq d$, and take $H=G$. By
Lemma 3.7, the number of $(p,\epsilon,k)$-admissible edges in $G$ is at least

$e(G)-\alpha n\geq\left(\frac{d}{4}-\alpha\right)n=(1+\alpha)n>\frac{n}{2},$

so there is some vertex $v_{0}\in V(G)$ incident to at least two
$(p,\epsilon,k)$-admissible edges $v_{0}v_{1}$ and $v_{0}v_{3}$. Moreover,
$\deg_{H}v_{0}<n\leq d$.

Now, suppose that $n>d$. Delete edges so that $\frac{dn}{4}\leq
e(G)\leq\frac{dn}{4}+1$. Partition $V(G)$ into $V_{1}=\\{v\in V(G):\deg v\leq
d\\}$ and $V_{2}=\\{v\in V(G):\deg v>d\\}$. Observe that

$(d+1)|V_{2}|\leq\sum_{v\in V_{2}}\deg v\leq
2e(G)\leq\frac{dn}{2}+2<\frac{(d+1)n}{2},$

where the last inequality holds because $n>d>4$. Thus, $|V_{2}|<\frac{n}{2}$
and $|V_{1}|>\frac{n}{2}$.

Let $m_{1}$ be the number of edges of $G$ with at least one endpoint in
$V_{1}$ and let $m_{2}=e(G)-m_{1}$ be the number of edges with both endpoints
in $V_{2}$. We have that

$m_{1}+m_{2}=e(G)\geq\frac{d}{4}n=|V_{1}|+2\alpha|V_{1}|+\frac{d}{4}|V_{2}|>|V_{1}|+\alpha
n+\frac{d}{4}|V_{2}|.$

Thus, either $m_{1}>|V_{1}|+\alpha n$ or $m_{2}>\frac{d}{4}|V_{2}|$.

If $m_{1}>|V_{1}|+\alpha n$, we take $H=G$. By Lemma 3.7, at most $\alpha n$
edges of $G$ are not $(p,\epsilon,k)$-admissible. Hence, more than $|V_{1}|$
edges with an endpoint in $V_{1}$ are $(p,\epsilon,k)$-admissible. It follows
that there is a vertex $v_{0}\in V_{1}$ incident to two
$(p,\epsilon,k)$-admissible edges $v_{0}v_{1},v_{0}v_{3}\in E(G)$. By
definition of $V_{1}$, we have $\deg v_{0}\leq d$.

Now, suppose $m_{2}>\frac{d}{4}|V_{2}|$. In this case $0<|V_{2}|<\frac{n}{2}$,
the former because the induced subgraph $G^{\prime}=G[V_{2}]$ is nonempty.
Thus, we may apply the inductive hypothesis in $G^{\prime}$. As desired, this
yields a subgraph $H\subseteq G^{\prime}$ containing two
$(p,\epsilon,k)$-admissible incident edges $v_{0}v_{1}$ and $v_{0}v_{3}$ whose
shared endpoint $v_{0}$ has degree at most $d$ in $H$. ∎

##  4 Proof of Theorem 1.1

We are now ready to present the proof of Theorem 1.1, which is restated here
as follows.

######  Theorem 4.1.

There is a constant $c$ such that the following holds. If ${\mathcal{H}}$ is a
3-uniform hypergraph with at least $cn^{5/2}$ edges, then ${\mathcal{H}}$
contains a triangulation of ${\mathbb{R}\mathbb{P}}^{2}$.

###### Proof.

Set $p=\frac{1}{6}$ and $\epsilon^{\prime}=\frac{1}{3}$, and let
$d=d(p,\epsilon^{\prime},2)$ be the constant from Lemma 3.6. Let $r$ be a
large integer and $\epsilon$ a small constant, to be determined later. Let
$c=c(p,\epsilon,r,7,d)$ be the constant from Lemma 3.4.

Our goal is to find vertices $u,u^{\prime},v_{0},v_{1},v_{2},v_{3}$; cycles
$C,C^{\prime}$; and disks ${\mathcal{D}},{\mathcal{D}}^{\prime}$ satisfying
the hypotheses of Lemma 2.2. We encourage the reader to revisit Fig. 4, which
depicts this setup.

Choose $u,u^{\prime}\in V({\mathcal{H}})$ and
$G\subseteq{\mathcal{H}}_{u,u^{\prime}}$ according to Lemma 3.4. That is,
$e(G)\geq dn/4$ and, for any incident edges $vw,vw^{\prime}\in E(G)$, the
pairs $(uvw,uvw^{\prime})$ and $(u^{\prime}vw,u^{\prime}vw^{\prime})$ are both
$(p,\epsilon,7,r)$-semi-admissible. Applying Lemma 3.6 to $G$, we locate a
subgraph $H\subseteq G$ containing two incident
$(p,\epsilon^{\prime},2)$-admissible edges $v_{0}v_{1},v_{0}v_{3}\in E(H)$
whose shared endpoint $v_{0}$ satisfies $\deg_{H}(v_{0})\leq d$. Set
$W=\\{u,u^{\prime},v_{0},v_{1},v_{3}\\}$.

We introduce two independent sources of randomness. Partition
$V({\mathcal{H}})=U_{1}\cup U_{2}\cup U_{3}\cup U_{4}$, such that each vertex
$v\in V({\mathcal{H}})$ is independently contained in $U_{1}$ or $U_{2}$ with
probability $p=\frac{1}{6}$ each, and in $U_{3}$ or $U_{4}$ with probability
$2p=\frac{1}{3}$ each. Independently, choose $v_{2}\in
N_{H}(v_{0})\setminus\\{v_{1},v_{3}\\}$ uniformly at random. (This set is
nonempty: we have $|N_{H}(v_{0})\setminus\\{v_{1}\\}|\geq 2$ because
$v_{0}v_{1}$ is $(p,\epsilon^{\prime},2)$-admissible in $H$.)

The following two claims lower-bound the probabilities that substructures
$C,C^{\prime}$ (Claim 4.2) and ${\mathcal{D}},{\mathcal{D}}^{\prime}$ (Claim
4.3) exist as described in Lemma 2.2.

######  Claim 4.2.

With probability at least $1/3d$, there are cycles $C,C^{\prime}$ in $H$
satisfying (i) and (ii).

  1. (i)

$C$ contains $v_{1}v_{0}v_{2}$ as a subpath. Moreover,
$V(C)\setminus\\{v_{0},v_{1}\\}\subseteq U_{1}\setminus W$.

  2. (ii)

$C^{\prime}$ contains the edge $v_{0}v_{3}$. Moreover,
$V(C^{\prime})\setminus\\{v_{0},v_{3}\\}\subseteq U_{2}\setminus W$.

###### Proof.

Consider the following two events.

  1. ($A_{1}$)

There are two internally vertex-disjoint paths in $H$ from $v_{0}$ to $v_{1}$
through $U_{1}$.

  2. ($A_{2}$)

There are two internally vertex-disjoint paths in $H$ from $v_{0}$ to $v_{3}$
through $U_{2}$.

Because the edges $v_{0}v_{1}$ and $v_{0}v_{3}$ are both
$(p,\epsilon^{\prime},2)$-admissible, events $A_{1}$ and $A_{2}$ each hold
with probability at least $1-\epsilon^{\prime}$, and a union bound yields
$\Pr[A_{1}\cap A_{2}]\geq 1-2\epsilon^{\prime}=\frac{1}{3}$.

Fix $U_{1}$ and $U_{2}$ such that $A_{1}$ and $A_{2}$ hold. By $A_{1}$, there
is a path $P\subseteq H$ from $v_{0}$ to $v_{1}$ through $U_{1}$ which avoids
$v_{3}$. Consider the third event

  1. ($A_{3}$)

The second vertex of $P$ is $v_{2}$, i.e. $v_{0}v_{2}\in E(P)$.

Recall that $v_{2}$ is chosen uniformly from
$N_{H}(v_{0})\setminus\\{v_{1},v_{3}\\}$, and is independent of the events
$A_{1}$ and $A_{2}$. It follows that

$\Pr[A_{1}\cap A_{2}\cap A_{3}]=\Pr[A_{1}\cap
A_{2}]\times\frac{1}{\deg_{H}(v_{0})-2}\geq\frac{1}{3}\times\frac{1}{d-2}>\frac{1}{3d}.$

To finish the proof, we assume $A_{1}$, $A_{2}$, and $A_{3}$ hold
simultaneously, and use this to construct $C$ and $C^{\prime}$. Set $C=P\cup
v_{0}v_{1}$. By $A_{2}$, there is a path $P^{\prime}$ from $v_{0}$ to $v_{3}$
through $U_{2}$ which avoids $v_{1}$; we set $C^{\prime}=P^{\prime}\cup
v_{0}v_{3}$.

Let us check condition (i). By $A_{3}$, it is immediate that $v_{1}v_{0}v_{2}$
is a subpath of $C$. By construction, $V(P)\subseteq
U_{1}\setminus\\{v_{3}\\}$, yielding that

$V(C)\setminus\\{v_{0},v_{1}\\}=V(P)\setminus\\{v_{0},v_{1}\\}\subseteq
U_{1}\setminus\\{v_{0},v_{1},v_{3}\\}.$

Moreover, because $C\subseteq H\subseteq{\mathcal{H}}_{u,u^{\prime}}$, we see
that $u,u^{\prime}\notin V(C)$. Thus,

$V(C)\setminus\\{v_{0},v_{1}\\}\subseteq
U_{1}\setminus\\{v_{0},v_{1},v_{3},u,u^{\prime}\\}=U_{1}\setminus W,$

completing the proof of (i). The proof of (ii) is analogous. ∎

######  Claim 4.3.

The following two events simultaneously occur with probability at least
$1-4r\epsilon-2\times\left(\frac{2}{3}\right)^{r-5}$.

  1. (i)

There is ${\mathcal{D}}\subseteq{\mathcal{H}}$ homeomorphic to
$\mathbb{D}^{2}$ with induced boundary
$\partial{\mathcal{D}}=v_{0}v_{1}uv_{3}v_{0}$ and interior vertex set
$V^{\circ}({\mathcal{D}})\subseteq U_{3}\setminus W$.

  2. (ii)

There is ${\mathcal{D}}^{\prime}\subseteq{\mathcal{H}}$ homeomorphic to
$\mathbb{D}^{2}$ with induced boundary
$\partial{\mathcal{D}}^{\prime}=v_{0}v_{2}u^{\prime}v_{3}v_{0}$ and interior
vertex set $V^{\circ}({\mathcal{D}}^{\prime})\subseteq U_{4}\setminus W$.

###### Proof.

We show that (i) and (ii) each occur with probability at least
$1-2r\epsilon-\left(\frac{2}{3}\right)^{r-5}$. Then, a union bound implies the
desired result.

(i) is a direct application of Lemma 3.3. Recall that
$U_{3}\sim_{2p}V({\mathcal{H}})$. The pair $(uv_{0}v_{1},uv_{0}v_{3})$ is
$(p,\epsilon,7,r)$-admissible in ${\mathcal{H}}$ because
$v_{0}v_{1},v_{0}v_{3}\in E(H)\subseteq E(G)$. Applying Lemma 3.3 shows that
${\mathcal{D}}$ exists with probability at least
$1-2r\epsilon-\left(\frac{2}{3}\right)^{r-5}$.

The bound for (ii) is analogous, but requires more care because $v_{2}$ is
chosen randomly. Fix any $v^{*}_{2}\in
N_{H}(v_{0})\setminus\\{v_{1},v_{3}\\}$. The pair
$(u^{\prime}v_{0}v^{*}_{2},u^{\prime}v_{0}v_{3})$ is
$(p,\epsilon,7,r)$-admissible in ${\mathcal{H}}$ because
$v_{0}v^{*}_{2},v_{0}v_{3}\in E(H)\subseteq E(G)$. Moreover, because $v_{2}$
and $U_{4}$ are chosen independently, the distribution of $U_{4}$ conditioned
on the event $v_{2}=v_{2}^{*}$ is still $U_{4}\sim_{2p}V({\mathcal{H}})$.
Applying Lemma 3.3 while conditioning on the event $v_{2}=v_{2}^{*}$, we have

$\Pr[\exists{\mathcal{D}}^{\prime}\text{ as in (ii)}\mid v_{2}=v_{2}^{*}]\geq
1-2r\epsilon-\left(\frac{2}{3}\right)^{r-5}.$

Averaging over all possible $v_{2}^{*}\in
N_{H}(v_{0})\setminus\\{v_{1},v_{3}\\}$ yields the desired bound:

$\Pr[\exists{\mathcal{D}}^{\prime}\text{ as in
(ii)}]=\sum_{v_{2}^{*}}\Pr[v_{2}=v_{2}^{*}]\times\Pr[\exists{\mathcal{D}}^{\prime}\text{
as in (ii)}\mid v_{2}=v_{2}^{*}]\geq
1-2r\epsilon-\left(\frac{2}{3}\right)^{r-5}.\qed$

Combining Claims 4.2 and 4.3 via a union bound shows that the following four
structures exist simultaneously with probability at least
$\frac{1}{3d}-4r\epsilon-2\times\left(\frac{2}{3}\right)^{r-5}$.

  * •

A cycle $C\subseteq{\mathcal{H}}_{u,u^{\prime}}$ containing the subpath
$v_{1}v_{0}v_{2}$ with $V(C)\setminus\\{v_{0},v_{1}\\}\subseteq U_{1}\setminus
W$.

  * •

A cycle $C^{\prime}\subseteq{\mathcal{H}}_{u,u^{\prime}}$ containing the
subpath $v_{3}v_{0}$ with $V(C)\setminus\\{v_{0},v_{3}\\}\subseteq
U_{2}\setminus W$.

  * •

A subgraph ${\mathcal{D}}\subseteq{\mathcal{H}}$ homeomorphic to
$\mathbb{D}^{2}$ with induced boundary
$\partial{\mathcal{D}}=v_{0}v_{1}uv_{3}v_{0}$ and interior vertex set
$V^{\circ}({\mathcal{D}})\subseteq U_{3}\setminus W$.

  * •

A subgraph ${\mathcal{D}}^{\prime}\subseteq{\mathcal{H}}$ homeomorphic to
$\mathbb{D}^{2}$ with induced boundary
$\partial{\mathcal{D}}^{\prime}=v_{0}v_{2}u^{\prime}v_{3}v_{0}$ and interior
vertex set $V^{\circ}({\mathcal{D}}^{\prime})\subseteq U_{4}\setminus W$.

Fix $r$ large enough that
$2\times\left(\frac{2}{3}\right)^{r-5}<\frac{1}{6d}$. Choose $\epsilon$ small
enough (in terms of $r$) that $4r\epsilon<\frac{1}{6d}$. It follows that

$\frac{1}{3d}-4r\epsilon-2\times\left(\frac{2}{3}\right)^{r-5}>0.$

Thus, for some choice of the random partition $U_{1},\ldots,U_{4}$ and random
vertex $v_{2}$, there are structures
$C,C^{\prime},{\mathcal{D}},{\mathcal{D}}^{\prime}$ satisfying the four bullet
points.

We obtain a triangulation of ${\mathbb{R}\mathbb{P}}^{2}$ in ${\mathcal{H}}$
by applying Lemma 2.2. By construction, the vertices $v_{0},v_{1},v_{2},v_{3}$
are distinct. Moreover the five sets $V(C)\setminus\\{v_{0},v_{1}\\}$,
$V(C^{\prime})\setminus\\{v_{0},v_{3}\\}$, $V^{\circ}({\mathcal{D}})$,
$V^{\circ}({\mathcal{D}}^{\prime})$, and $W$ are disjoint, as they are
respectively contained in the five disjoint sets $U_{1}\setminus W$,
$U_{2}\setminus W$, $U_{3}\setminus W$, $U_{4}\setminus W$, and $W$. Thus,
Lemma 2.2 yields that ${\mathcal{H}}$ contains a triangulation of
${\mathbb{R}\mathbb{P}}^{2}$. ∎

##  5 Concluding Remarks

Although our upper bound on
$\operatorname{ex}_{\hom}(n,{\mathbb{R}\mathbb{P}}^{2})$ and the upper bound
on $\operatorname{ex}_{\hom}(n,\mathbb{T}^{2})$ given in [5] are both
asymptotically $O(n^{5/2})$, we remark that neither proof naturally
generalizes to all surfaces. Indeed, our work is tied to the decomposition of
${\mathbb{R}\mathbb{P}}^{2}$ given in Section 2, whereas the strategy of [5]
is inherently limited to orientable surfaces. However, there are some
fundamental similarities: both results follow a probabilistic approach, and
the $n^{5/2}$ term can be traced back to Lemma 3.5 (which is Lemma 3.3 in [5])
in both cases. This suggests that there may be a proof of Theorem 1.2 that
unifies the two strategies.

######  Question 5.1.

Can Theorem 1.2 be proven without extensive case-specific arguments? That is,
is there a single unified approach that works for all orientable and non-
orientable surfaces $X$?

A positive answer to 5.1 would have further implications. Notice that the
quantity $\operatorname{ex}_{\hom}(n,X)$ can be defined for any _homogenous_
$(r-1)$-dimensional simplicial complex $X$, i.e. any simplicial complex
$X=X({\mathcal{F}})$ homeomorphic to some $r$-uniform hypergraph
${\mathcal{F}}$. When $r=3$, Keevash, Long, Narayanan, and Scott [4] recently
showed that $\operatorname{ex}_{\hom}(n,X)=O(n^{2.8})$ for any homogenous
2-dimensional simplicial complex $X$, and conjectured that the exponent could
be brought down to $\frac{5}{2}$.

######  Conjecture 5.2.

Let $X$ be any homogenous 2-dimensional simplicial complex. Then we have
$\operatorname{ex}_{\hom}(n,X)=O(n^{5/2})$.

This conjecture was reiterated by Kupavskii, Polyanskii, Tomon, and
Zakharov[5] and previously alluded to by Linial [6, 7]. An affirmative answer
to 5.1 would mark an important next step towards its proof.

Lastly, we ask about $\operatorname{ex}_{\hom}(n,X)$ in higher dimensions.

######  Question 5.3.

Let $r\geq 4$ and let $X$ be a $(r-1)$-dimensional manifold. What can we say
about the asymptotics of $\operatorname{ex}_{\hom}(n,X)$? What if $X$ is an
arbitrary homogenous $(r-1)$-dimensional simplicial complex?

#### Acknowledgements.

The author is grateful to Nikhil Pandit for suggesting the proof of
Proposition 2.1 presented in Section 2.1. The author is supported by a Fannie
and John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship
(grant number DGE-1656518).

## References

  * [1] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in _Erdős centennial_ , _Bolyai Soc. Math. Stud._ , vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 169–264.
  * [2] A. Georgakopoulos, J. Haslegrave, R. Montgomery, and B. Narayanan, Spanning surfaces in 3-graphs, _J. Eur. Math. Soc._ 24 (2022), 303–339.
  * [3] P. Keevash, Hypergraph Turán problems, in _Surveys in combinatorics 2011_ , _London Math. Soc. Lecture Note Ser._ , vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 83–139.
  * [4] P. Keevash, J. Long, B. Narayanan, and A. Scott, A universal exponent for homeomorphs, _Israel J. Math._ 243 (2021), 141–154.
  * [5] A. Kupavskii, A. Polyanskii, I. Tomon, and D. Zakharov, The extremal number of surfaces, _Int. Math. Res. Not._ 2022 13246–13271.
  * [6] N. Linial, What is high-dimensional combinatorics?, Random-Approx, 2008.
  * [7] N. Linial, Challenges of high-dimensional combinatorics, Lovász’s Seventieth Birthday Conference, 2018.
  * [8] Z. Luria and R. J. Tessler, A sharp threshold for spanning 2-spheres in random 2-complexes, _Proc. Lond. Math. Soc._ 119 (2019), 733–780.
  * [9] D. Mubayi, O. Pikhurko, and B. Sudakov, Hypergraph Turán problem: some open questions, in _AIM workshop problem lists, manuscript_ , 2011.
  * [10] V. T. Sós, P. Erdős, and W. G. Brown, On the existence of triangulated spheres in $3$-graphs, and related problems, _Period. Math. Hungar._ 3 (1973), 221–228.