# Transversals and colorings of simplicial spheres

Joseph Briggs<EMAIL_ADDRESS>Department of Mathematics and Statistics,
Auburn University, Auburn, AL, USA.  Michael Gene Dobbins
<EMAIL_ADDRESS>Department of Mathematical Sciences, Binghamton
University, Binghamton, NY, USA.  Seunghun Lee
<EMAIL_ADDRESS>author Einstein Institute of
Mathematics, Hebrew University, Jerusalem, Israel.

###### Abstract

Motivated from the surrounding property of a point set in $\mathbb{R}^{d}$
introduced by Holmsen, Pach and Tverberg, we consider the transversal number
and chromatic number of a simplicial sphere. As an attempt to give a lower
bound for the maximum transversal ratio of simplicial $d$-spheres, we provide
two infinite constructions. The first construction gives infintely many
$(d+1)$-dimensional simplicial polytopes with the transversal ratio exactly
$\frac{2}{d+2}$ for every $d\geq 2$. In the case of $d=2$, this meets the
previously well-known upper bound $1/2$ tightly. The second gives infinitely
many simplicial 3-spheres with the transversal ratio greater than $1/2$. This
was unexpected from what was previously known about the surrounding property.
Moreover, we show that, for $d\geq 3$, the facet hypergraph
$\mathcal{F}(\mathsf{K})$ of a $d$-dimensional simplicial sphere $\mathsf{K}$
has the chromatic number $\chi(\mathcal{F}(\mathsf{K}))\in O(n^{\frac{\lceil
d/2\rceil-1}{d}})$, where $n$ is the number of vertices of $\mathsf{K}$. This
slightly improves the upper bound previously obtained by Heise, Panagiotou,
Pikhurko, and Taraz.

##  1 Introduction

Given a hypergraph $\mathcal{H}$ on $n$ vertices, a (weak) coloring of
$\mathcal{H}$ is a function $c:V(\mathcal{H})\to[m]=\\{1,\dots,m\\}$ such that
for every color $i\in[m]$, $c^{-1}(i)$ is an independent set of $\mathcal{H}$,
that is, $c^{-1}(i)$ does not contain any hyperedges of $\mathcal{H}$.
$\mathcal{H}$ is said to be $m$-colorable if there is a proper coloring of
$\mathcal{H}$ using $m$ colors. A subset $T$ of $V(\mathcal{H})$ is called a
transversal if for every hyperedge $e\in\mathcal{H}$ there exists a vertex
$v\in T$ such that $v\in e$, or equivalently, the complement
$V(\mathcal{H})\setminus T$ is an independent set of $\mathcal{H}$. The
minimum number of colors required in a coloring of $\mathcal{H}$ is called the
(weak) chromatic number of $\mathcal{H}$ and we denote it by
$\chi(\mathcal{H})$. The minimum size of a transversal of $\mathcal{H}$ is
called the transversal number of $\mathcal{H}$, and denoted by
$\tau(\mathcal{H})$. The independence number of $\mathcal{H}$ is defined as
the largest size of an independent set in $\mathcal{H}$, and denoted by
$\alpha(\mathcal{H})$.

For a simplicial complex $\mathsf{K}$, we denote the facet hypergraph of
$\mathsf{K}$, which consists of the facets of $\mathsf{K}$, by
$\mathcal{F}(\mathsf{K})$. We similarly define the facet hypergraph of a
polytope $\mathbf{P}$ where each facet is represented as the set of its
vertices, and denote it by $\mathcal{F}(\mathbf{P})$. One of the goals of this
note is to give a partial answer of the following question, which was
originally proposed by Andreas Holmsen (personal communication).

######  Question 1.

Let $d$ be a fixed integer. How large can the transversal ratio
$\tau(\mathcal{F}(\mathsf{K}))/n$ be as $n$ approaches to $\infty$, where
$\mathsf{K}$ is a $d$-dimensional simplicial sphere on $n$ vertices?

Question 1 for simplicial polytopes was implicitly investigated in a dual form
in [13] by Holmsen, Pach and Tverberg. They considered the following
properties which arise from combinatorial convexity. Given a finite point set
$P\subseteq\mathbb{R}^{d}$ in general position with respect to the origin $O$,
$P$ is said to be $k$-surrounding, or is said to have property $S(k)$, if any
$k$-element subset of $P$ can be extended to a $(d+1)$-element subset of $P$
such that $O\in\operatorname{conv}(P)$. By applying the Gale transform to $P$,
we can obtain a dual point set $P^{*}$ in $\mathbb{R}^{n-d-1}$, and there is
the dual property $S^{*}(k)$ of $P^{*}$ which is defined as the following:
Among any $n-k$ points of $P^{*}$, there are some $n-d-1$ that form a facet of
$\operatorname{conv}(P^{*})$. Using fundamental facts of the Gale transform,
one can easily see that $P$ has property $S(k)$ if and only if $P^{*}$
satisfies $S^{*}(k)$. Also, note that when points of $P^{*}$ are in convex
position, we have that $P^{*}$ satisfies $S^{*}(k)$ if and only if the facet
hypergraph $\mathcal{F}(\operatorname{conv}(P^{*}))$ has no transversal of
size $k$.

The $S(k)$ existence problem [13, Problem 3] asks for a point set in general
position with respect to $O$ that satisfies $S(k)$ for large values of $k$
when the dimension $d$ is fixed. In [13], such a construction was obtained
from even-dimensional cyclic polytopes $C_{d^{*}}(n)$ in the dual space which
satisfy $S^{*}(\lfloor d/2\rfloor+1)$, or equivalently
$S^{*}(\lceil(n-d^{*})/2\rceil)$, where $d^{*}=n-d-1$ is the dimension of the
dual space. Note that it is equivalent to $\tau(\mathcal{F}(C_{d^{*}}(n)))>k$.
In this way, their investigation of the dual surrounding property $S^{*}(k)$
has a connection to lower bounds on the transversal ratio of a simplicial
sphere.

The exact transversal number of a cyclic polytope is given by
$\tau(\mathcal{F}(C_{d^{*}}(n)))=\lceil(n-d^{*})/2\rceil+1$ when $d^{*}$ is
even, and $\tau(\mathcal{F}(C_{d^{*}}(n)))=2$ when $d^{*}$ is odd. See
Proposition 3.6 and a remark after the proof. This implies that, for
$d^{*}\geq 3$, the transversal ratio $\tau/n$ of $C_{d^{*}}(n)$ is bounded by
$1/2$ from above. In addition to cyclic polytopes, it can be checked from the
result in [18, Section 4.8] by Miyata and Padrol that the same bound works for
all the neighborly oriented matroids constructed in that paper. Furthermore,
all examples except for odd cycles in Section 3 satisfy 2-colorability which
is an even stronger property.

One of the examples in Section 3 is the class of 3-dimensional simplicial
polytopes. For this case, we obtain tight lower bound constructions that have
transversal ratio exactly $1/2$, which matches the upper bound for simplicial
3-polytopes. See also Proposition 3.1. This construction generalizes to higher
dimensions as follows.

######  Theorem 1.1.

For every $d\geq 2$, there are infinitely many $(d+1)$-dimensional simplicial
polytopes with the transversal ratio exactly $\frac{2}{d+2}$.

Together with even-dimensional cyclic polytopes, the constructions of Theorem
1.1 give positive lower bounds to Question 1 for every dimension.

Even though these form a rather restricted set of examples, the bound of $1/2$
on the transversal ratio holds in surprisingly many cases, so it may be very
tempting to conjecture that, for a simplicial $d$-sphere $\mathsf{K}$ and
$d\geq 3$, $\mathcal{F}(\mathsf{K})$ is 2-colorable, or at least satisfies the
bound $\tau(\mathcal{F}(\mathsf{K}))\leq n/2+o(n)$. The following result
demonstrates that this hope cannot be fulfilled.

######  Theorem 1.2.

There exist arbitrarily large PL 3-spheres with transversal ratio at least
$\frac{11}{21}$.

These PL spheres are constructed by bootstrapping the hypergraph
$\mathcal{N}_{21}$ which was obtained from computer experiments, see Theorem
5.1.

As we have already observed above, for any hypergraph $\mathcal{H}$ with $n$
vertices, we have

$\tau(\mathcal{H})=n-\alpha(\mathcal{H})\leq n-n/\chi(\mathcal{H}).$

So a lower bound on the transversal ratio $\tau(\mathcal{H})/n$ implies a
lower bound on the chromatic number $\chi(\mathcal{H})$. This motivates the
following analogue of Question 1 for chromatic numbers.

######  Question 2.

Under the same conditions of Question 1, how large can
$\chi(\mathcal{F}(\mathsf{K}))$ be?

Theorem 1.2 implies that we need at least 3 colors to properly color the facet
hypergraph of a simplicial 3-sphere in general. Unfortunately, we do not have
an upper bound for the chromatic number which closes the gap with this finite
lower bound.

The most relevant result regarding upper bounds on the chromatic number of a
simplicial sphere can be found in [12]. There, Heise, Panagiotou, Pikhurko,
and Taraz obtained an upper bound on the chromatic number of linearly
$d$-embeddable $(d+1)$-uniform hypergraphs. They used the Lovász local lemma
and the upper bound theorem by Dey and Pach [10] on the number of hyperedges
as main ingredients. Following the same argument and using Stanley’s upper
bound theorem on simplicial spheres [23] instead, one can easily get the same
asymptotic upper bound $\chi(\mathcal{F}(\mathsf{K}))\in O(n^{\frac{\lceil
d/2\rceil}{d}})$ for a simplicial $d$-sphere $\mathsf{K}$.

Our new result is a slight improvement on this by a different probabilistic
approach. Even though the result holds generally for simplicial spheres, we
state and prove it for polytopes first for simplicity of arguments. Then, we
explain how it can be generalized for simplicial spheres in Subsection 6.1.

######  Theorem 1.3.

Let $\mathbf{P}$ be a $(d+1)$-dimensional simplicial polytope on $n$ vertices.
Then, the facet hypergraph $\mathcal{F}(\mathbf{P})$ has the chromatic number

$\chi(\mathcal{F}(\mathbf{P}))\in O(n^{\frac{\lceil d/2\rceil-1}{d}}).$

This paper is organized as follows. In Section 2, we introduce relevant
notations and basic concepts. In Section 3, we consider simplicial spheres of
special classes and investigate their transversal numbers and colorability. In
Section 4, we give the construction for Theorem 1.1. In Section 5, we present
the proof of Theorem 1.2 which makes use of the construction in Appendix A
obtained by computer experiments. In Section 6, we prove Theorem 1.3 and
generalize it for simplicial spheres (see Theorem 6.7). Finally, we give
remarks on future research in Section 7.

##  2 Preliminaries

A hypergraph $\mathcal{H}$ on a vertex set $V=V(\mathcal{H})$, is a family of
subsets of $V$, which are called hyperedges. We assume that the hyperedges of
$\mathcal{H}$ cover the whole $V(\mathcal{H})$, that is,
$\bigcup_{f\in\mathcal{H}}f=V(\mathcal{H})$. A hypergraph which is a subfamily
of $\mathcal{H}$ is called a subhypergraph of $\mathcal{H}$. $\mathcal{H}$ is
called $k$-uniform if all hyperedges have the same size $k$. For two
hypergraphs $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$, we define the join
operation $*$ as

$\mathcal{H}_{1}*\mathcal{H}_{2}=\\{f_{1}\cup
f_{2}:f_{1}\in\mathcal{H}_{1},f_{2}\in\mathcal{H}_{2}\\}.$

A simplicial complex $\mathsf{K}$ on a vertex set $V$ is a hypergraph on $V$,
which satisfies the hereditary property: If $g\subseteq f$ and
$f\in\mathsf{K}$, then $g\in\mathsf{K}$. A subhypergraph of a simplicial
complex $\mathsf{K}$ which is again a simplicial complex is called a
subcomplex of $\mathsf{K}$. We call an element of $\mathsf{K}$ a face of
$\mathsf{K}$. In particular, we call a face of $\mathsf{K}$ of size 1 or 2 by
a vertex or an edge, respectively. We do not particularly distinguish an
element $v\in V(\mathsf{K})$ from a singleton $\\{v\\}$ if there is no
confusion. Maximal faces of $\mathsf{K}$ with respect to set inclusion are
called facets. The dimension of a face $f$ is $|f|-1$, and the dimension of a
simplicial complex $\mathsf{K}$ is the maximum dimension of a face in
$\mathsf{K}$.

For a simplicial complex $\mathsf{K}$, we can correspond a topological space
to $\mathsf{K}$ which is unique up to homeomorphism. We call the space the
realization of $\mathsf{K}$ and denote it by $||\mathsf{K}||$. For example,
the power set of a set $V$ of size $d+1$, which we denote by $2^{V}$, is a
simplicial complex whose realization is homeomorphic to the regular
$d$-dimensional simplex. To emphasize that it is a simplicial complex, we use
a different notation $\Delta(V)$ to denote $2^{V}$ and call it the abstract
simplex on $V$, or simply just an abstract simplex. Furthermore, when
$|V|=d+1$, we call it an abstract $d$-simplex. We call $\mathsf{K}$ a
simplicial $d$-sphere or a simplicial $(d+1)$-ball if $||\mathsf{K}||$ is
homeomorphic to the $d$-dimensional unit sphere or the $(d+1)$-dimensional
unit ball, respectively.

A simplicial complex $\mathsf{K}$ is a PL $d$-sphere if it is PL homeomorphic
to the boundary of an abstract $(d+1)$-simplex. Similarly, a simplicial
complex $\mathsf{B}$ is a PL $(d+1)$-ball if $\mathsf{B}$ is PL homeomorphic
to an abstract $(d+1)$-simplex. PL spheres and PL balls have nice properties
so that they match better with our intuition than general simplicial spheres
and balls. One of the properties is that the link of a face $f$ of a PL
$(d+1)$-ball $\mathsf{B}$ defined as

$\mathsf{lk}_{\mathsf{B}}(f)=\\{g\in\mathsf{B}:g\cup f\in\mathsf{B},g\cap
f=\emptyset\\}$

is either a PL ball or a PL sphere. In the former case, we call $f$ a boundary
face of $\mathsf{B}$, and in the latter case, $f$ is called an interior face
of $\mathsf{B}$. The boundary complex of a PL ball $\mathsf{B}$, denoted by
$\partial\mathsf{B}$, is the subcomplex of $\mathsf{B}$ which consists of all
boundary faces of $\mathsf{B}$. For details of PL topology, see [14].

Given a hypergraph $\mathcal{H}$, we can correspond the simplicial complex
$\mathsf{K}(\mathcal{H})$ to $\mathcal{H}$ by

$\mathsf{K}(\mathcal{H})=\bigcup_{f\in\mathcal{H}}\Delta(f).$

We can also correspond the facet hypergraph $\mathcal{F}(\mathsf{K})$, which
consists of all facets of $\mathsf{K}$, to a simplicial complex $\mathsf{K}$.

A simplicial polytope is a polytope whose faces are simplices. For a polytope
$\mathbf{P}$, we can easily correspond the facet hypergraph
$\mathcal{F}(\mathbf{P})$ to $\mathbf{P}$ where each hyperedge is the set of
all vertices of a facet $f$ of $\mathbf{P}$. Especially when $\mathbf{P}$ is
simplicial, the simplicial complex
$\mathsf{K}(\mathbf{P})=\mathsf{K}(\mathcal{F}(\mathbf{P}))$, which we call
the boundary complex of $\mathbf{P}$, is a PL sphere, and this is our primary
information we consider about a polytope.

For simple notations and conventions, when we consider the colorability and
transversals of $\mathcal{F}(\mathsf{K})$ where $\mathsf{K}$ is a simplicial
complex, we directly refer to $\mathsf{K}$ rather than
$\mathcal{F}(\mathsf{K})$ if there is no confusion. In the same manner, we
directly refer to a polytope $\mathbf{P}$ for colorability and transversals,
rather than referring to the corresponding simplicial complex
$\mathsf{K}(\mathbf{P})$ or the facet hypergraph $\mathcal{F}(\mathbf{P})$.

##  3 The transversal numbers and colorability for some special classes of
simplicial spheres

In this section, we consider simplicial spheres of some special classes and
investigate their transversal numbers and colorability. In particular, we show
that every simplicial sphere considered here, except for odd cycles, is
2-colorable.

###  3.1 2-dimensional simplicial spheres

We first consider the chromatic number of a simplicial 2-sphere.

######  Proposition 3.1.

Simplicial 2-spheres are 2-colorable.

###### Proof.

Let $\mathsf{K}$ be a simplicial 2-sphere. Since the graph $G=G(\mathsf{K})$
of $\mathsf{K}$ is planar, by the four color theorem [7], we have a proper
coloring of $G$ which has color classes $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$.
For every face $f$ of $\mathsf{K}$, the vertices of $f$ attain distinct colors
from the coloring of $G$, since $f$ is a triangle. This implies that the
vertex sets $W_{1}=V_{1}\cup V_{2}$ and $W_{2}=V_{3}\cup V_{4}$ are
independent sets in the facet hypergraph $\mathcal{F}(\mathsf{K})$, which form
a 2-coloring of $\mathcal{F}(\mathsf{K})$. ∎

In the literature, Proposition 3.1 is well-known and has many different
proofs, see [16, Section 2] for details. Note that Proposition 3.1 does not
lose generality when it is stated for simplicial 3-polytopes since every
simplicial 2-sphere can be realized as the boundary of a 3-polytope, which is
an easy consequence from Steinitz’ theorem [25] and Whitney’s theorem [26].

Proposition 3.1 implies that $\tau(\mathsf{K})\leq n/2$ where $\mathsf{K}$ is
a simplicial 2-sphere and $n$ is the number of vertices of $\mathsf{K}$. We
show that this bound is tight in Section 4.

###  3.2 Stacked balls and spheres

A simplicial complex $\mathsf{B}$ is called a stacked $(d+1)$-ball if there
are sequences of abstract $(d+1)$-simplices $\Delta_{1},\dots,\Delta_{m}$ such
that, with a notation $\mathsf{B}_{k}=\bigcup_{i=1}^{k}\Delta_{i}$, the
intersection $\mathsf{B}_{k}\cap\Delta_{k+1}$ is an abstract $d$-simplex whose
maximal face is a $d$-dimensional face of both $\partial\mathsf{B}_{k}$ and
$\Delta_{k+1}$ for every $1\leq k\leq m-1$. A simplicial complex $\mathsf{K}$
is called a stacked $d$-sphere if $\mathsf{K}=\partial\mathsf{B}$ for some
stacked $(d+1)$-ball $\mathsf{B}$.

Stacked $(d+1)$-balls and stacked $d$-spheres form fundamental classes of
simplicial complexes. They can be realized by polytopes, which are called
stacked $(d+1)$-polytopes. This in particular implies that they are PL
$(d+1)$-balls and PL $d$-spheres, respectively. Stacked balls and spheres are
closely related to neighborly spheres, see Section 3.4 below.

The following is an easy observation.

######  Proposition 3.2.

Let $d\geq 2$. For a given stacked $(d+1)$-ball $\mathsf{B}$ on $n$ vertices
and $\mathsf{K}=\partial\mathsf{B}$, we have
$\tau(\mathsf{B})\leq\frac{1}{d+2}n$ and $\tau(\mathsf{K})\leq\frac{2}{d+2}n$.
Furthermore, $\mathsf{B}$ and $\mathsf{K}$ are both 2-colorable.

###### Proof.

By the inductive construction of $\mathsf{B}$, one can easily see that the
graph of $\mathsf{B}$, or equivalently the graph of $\mathsf{K}$, is
$(d+2)$-colorable. Since every facet of $\mathsf{B}$ attains all $d+2$ colors
from the coloring, choosing a color class of the minimum size gives a
transversal of size at most $n/(d+2)$ for $\mathsf{B}$. For a transversal of
$\mathsf{K}$, we choose the two smallest color classes. Then the union of the
two color classes is a transversal of size at most $2n/(d+2)$ for
$\mathsf{K}$. For both $\mathsf{B}$ and $\mathsf{K}$, the transversals we
found and their complements form proper 2-colorings. ∎

The following example gives the largest transversal ratio we know for general
stacked balls and spheres.

######  Example 3.3.

Let $\mathsf{B}^{d+1}_{n}$ be a stacked $(d+1)$-ball which has the facet
hypergraph

$\mathcal{F}(\mathsf{B}^{d+1}_{n})=\\{\\{1,2,\dots,d+2\\},\\{2,3,\dots,d+3\\},\dots,\\{n-d-1,n-d,\dots,n\\}\\}.$

When $n=(d+2)k$ for some $k\geq 1$, $\mathsf{B}^{d+1}_{n}$ has the transversal
number exactly $\frac{1}{d+2}n$. Since we already obtained the upper bound in
Proposition 3.2, we only need to show that a transversal of
$\mathsf{B}^{d+1}_{n}$ has size at least $\frac{1}{d+2}n$. Note that there are
$n-d-1=(d+2)(k-1)+1$ facets in $\mathsf{B}^{d+1}_{n}$, and each vertex of
$\mathsf{B}^{d+1}_{n}$ can only traverse at most $(d+2)$ facets. Therefore, a
transversal of $\mathsf{B}^{d+1}_{n}$ requires at least

$\geq\left\lceil\frac{(d+2)(k-1)+1}{d+2}\right\rceil=k=\frac{n}{d+2}$

vertices.

Now, let $\mathsf{K}^{d}_{n}=\partial\mathsf{B}^{d+1}_{n}$. We show that the
stacked $d$-sphere $\mathsf{K}^{d}_{n}$ has the transversal number exactly
$\frac{2}{d+3}n$ when $n=(d+3)k$ for some $k\geq 1$. Note that
$\mathsf{K}^{d}_{n}$ has the facet hypergraph

$\mathcal{F}(\mathsf{K}^{d}_{n})=\\{g\setminus\\{w\\}:g\in\mathcal{F}(\mathsf{B}^{d+1}_{n}),w\notin\\{\max(g),\min(g)\\}\\}\cup\\{\\{1,\dots,d+1\\},\\{n-d,\dots,n\\}\\}.$

We partition the vertex set $[n]$ into the subsets

$\\{1,2,\dots,d+3\\},\\{d+4,d+5,\dots,2(d+3)\\},\dots,\\{(k-1)(d+3)+1,\dots,k(d+3)\\}.$

Let us call the subsets $V_{1},\dots,V_{k}$ in order. We show that the set $T$
which consists of all maximums and minimums of $V_{1},\dots,V_{k}$ is a
transversal of $\mathsf{K}^{d}_{n}$. Suppose otherwise that there is a facet
$f$ of $\mathsf{K}^{d}_{n}$ which is not traversed by $T$. If $f$ is contained
in $V_{i}$ for some $i\in[k]$, then $f$ should miss $\max(V_{i})$ and
$\min(V_{i})$. Then, $f$ should consist of the middle elements of $V_{i}$
which is impossible. So $f$ needs to intersect two subsets $V_{i}$ and
$V_{i+1}$ for some $i\in[k-1]$. Then, $f$ should miss two consecutive
elements, which is also impossible. This shows that
$\tau(\mathsf{K}^{d}_{n})\leq\frac{2}{d+3}n$.

We can also easily see that the induced subhypergraph
$\mathcal{F}(\mathsf{K}^{d}_{n})[V_{i}]$ requires at least two vertices to
traverse all facets in the subhypergraph for each $i\in[k]$. Together with the
upper bound, this shows that $\tau(\mathsf{K}^{d}_{n})=\frac{2}{d+3}n$.∎

Example 3.3 shows that the upper bound for stacked $(d+1)$-balls in
Proposition 3.2 is tight. However for stacked $d$-spheres, it only shows that
the exact maximum transversal ratio is in somewhere between $\frac{2}{d+3}$
and $\frac{2}{d+2}$.

######  Question 3.

What is the following value

$\sigma_{d}:=\limsup_{n\to\infty}\max\\{\tau(\mathsf{K})/n:\textrm{$\mathsf{K}$
is a stacked $(d-1)$-sphere on $n$ vertices}\\}$

for a fixed dimension $d$?

######  Remark 3.4.

Regarding Question 3, the following two results were recently obtained by
Minho Cho and Jinha Kim, as well as general results for higher dimensions [9].
(i) They showed that $\sigma_{3}\geq 6/13$. (ii) Define

$\displaystyle\sigma_{d}^{\textrm{path}}:=$
$\displaystyle\limsup_{n\to\infty}\max\\{\tau(\partial\mathsf{B})/n:\textrm{$\mathsf{B}$
is a stacked $d$-ball on $n$ vertices, $G^{*}(\mathsf{B})$ is a path}\\}.$

They obtained $\sigma_{3}^{\textrm{path}}=3/7$. (In the definition of
$\sigma_{d}^{\textrm{path}}$, $G^{*}(\mathsf{B})$ is the facet-ridge graph of
$\mathsf{B}$, where vertices are facets of $\mathsf{B}$ and two facets of
$\mathsf{B}$ are adjacent in $G^{*}(\mathsf{B})$ if and only if they share a
codimension 1 face.) The former result is based on computer experiments while
the latter has a hand-written proof.

###  3.3 Cyclic polytopes

The moment curve $\gamma_{d}:\mathbb{R}\rightarrow\mathbb{R}^{d}$ in
$\mathbb{R}^{d}$ is defined as

$\gamma_{d}(t)=(t,t^{2},\dots,t^{d})\in\mathbb{R}^{d}.$

Given $n$ real numbers $t_{1}<t_{2}<\cdots<t_{n}$ where $n\geq d+1$, we define
the cyclic polytope $C_{d}(t_{1},\dots,t_{n})$ as

$C_{d}(t_{1},\dots,t_{n})=\operatorname{conv}\\{\gamma_{d}(t_{1}),\dots,\gamma_{d}(t_{n})\\}.$

In fact, the following criterion gives a full combinatorial description of
$C_{d}(t_{1},\dots,t_{n})$. In particular, it shows that the combinatorial
type of $C_{d}(t_{1},\dots,t_{n})$ is independent from the choice of real
parameters $t_{1},\dots,t_{n}$. By this, we use a simpler notation $C_{d}(n)$
and call it the cyclic $d$-polytope on $n$ vertices. Furthermore, we label the
vertices $\gamma_{d}(t_{1}),\dots,\gamma_{d}(t_{n})$ of $C_{d}(n)$ by
$1,\dots,n$ in order.

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

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

Using Gale’s criterion, one can obtain the following fact.

######  Proposition 3.6.

$C_{d}(n)$ is 2-colorable for every $d\geq 3$. Furthermore,

$\tau(C_{d}(n))=\left\lceil\frac{n-d}{2}\right\rceil+1$

when $d$ is even, and $\tau(C_{d}(n))=2$ when $d$ is odd.

###### Proof.

We can obtain a proper 2-coloring of $C_{d}(n)$ by alternating colors of
vertices as we move from the vertex 1 to the vertex $n$. We can also easily
see that when $d$ is odd, $\tau(C_{d}(n))=2$ and $\\{1,n\\}$ is a transversal
of $C_{d}(n)$ of the minimum size.

We now compute the transversal number when $d$ is even. We first show that
there are no transversals of size $\lceil\frac{n-d}{2}\rceil$. Suppose
otherwise that there is such a transversal $T$. Then we have
$|T|\leq\frac{n-(d-1)}{2}$. We will lead a contradiction by finding a facet
$f$ of $C_{d}(n)$ which is contained in the complement $R=[n]\setminus T$ and
has size at least $\frac{n+(d-1)}{2}$.

Note that $T$ divides the vertices of $R$ into “intervals” of consecutive
vertices. Among those intervals, there are at most $\frac{n-(d-1)}{2}-1$
“inner” intervals which do not have the ending vertices 1 and $n$. We can
choose a subset $g\subseteq R$ of the maximum size such that for each inner
interval $I$ the intersection $g\cap I$ consists of an even number of
consecutive vertices. Note that $g$ only misses at most 1 vertex at each inner
interval. Therefore, $g$ has the size at least

$\frac{n+(d-1)}{2}-\left(\frac{n-(d-1)}{2}-1\right)=d.$

We can choose a subset $f\subseteq g$ so that $|f|=d$, and for each inner
interval $I$, $f\cap I$ consists of an even number of consecutive vertices. By
Gale’s criterion, $f$ forms a facet which leads to a contradiction.

Finally, we find a transversal of size $\lceil\frac{n-d}{2}\rceil+1$. Let
$I_{1}$ and $I_{n}$ be some intervals of consecutive vertices which contain 1
and $n$ resepectively. We further assume that $|I_{1}|+|I_{n}|=d-1$. We
alternatingly choose vertices for a transversal, starting from the vertex
right after $I_{1}$ before we arrive at $I_{n}$. More precisely, when
$n-(d-1)$ is odd, we choose a transversal as

$I_{1}\;*\;-\;*\;-\;\dots\;*\;-\;*\;I_{n},$

where “$*$” denotes a vertex chosen for a transversal, and “$-$” denotes one
of the other vertices. Using the same notation, when $n-(d-1)$ is even, we
choose a transveral as

$I_{1}\;*\;-\;*\;-\;\dots\;*\;-\;*\;*\;I_{n}.$

This completes the proof. ∎

In particular, the fact $\tau(C_{d}(n))>\lceil\frac{n-d}{2}\rceil$ when $d$ is
even is already observed in [13]. This fact is equivalent to saying that
$C_{d}(n)$ satisfies the dual surrounding property
$S^{*}(\lceil\frac{n-d}{2}\rceil)$. Using the Gale transform, this implies
there exist arbitrarily large point sets in $\mathbb{R}^{\overline{d}}$ in
general position with respect to the origin with property
$S(\lfloor\frac{\overline{d}}{2}\rfloor+1)$ in the “primal” space, see [13,
Theorem 4].

###  3.4 Neighborly spheres obtained from a cyclic polytope by one single
element extension

A simplicial complex $\mathsf{K}$ on the vertex set $V$ is called
$k$-neighborly if every $k$-subset of $V$ is a face of $\mathsf{K}$. A
simplicial $d$-sphere is called a neighborly $d$-sphere if it is
$\lfloor(d+1)/2\rfloor$-neighborly. Using Gale’s evenness criterion 3.5, one
can show that a cyclic polytope is a neighborly polytope, that is,
$\mathsf{K}(C_{d}(n))$ is a neighborly sphere for all positive integers $d$
and $n$ with $n\geq d+1$.

Neighborly spheres form an interesting class of simplicial spheres because
they satisfy extremal properties. For example, the upper bound theorem [17,
23] asserts that a neighborly sphere attains the maximum number of faces.

There is a well-known inductive method which given a neighborly sphere
constructs a new neighborly sphere with an additional vertex. To do that we
need a more general concept than the stackedness we defined at Section 3.2. We
call a PL $d$-ball $\mathsf{B}$ $k$-stacked if all faces of $\mathsf{B}$ of
dimension at most $d-k-1$ are in $\partial\mathsf{B}$. Note that $\mathsf{B}$
is 1-stacked if and only if $\mathsf{B}$ is stacked.

######  Proposition 3.7 (Lemma 4.1 in [19]).

Let $\mathsf{K}$ be a neighborly PL $d$-sphere on $V$. Let $\mathsf{B}$ be a
$(\lfloor(d+1)/2\rfloor-1)$-neighborly (with respect to $V$) and
$(\lfloor(d+1)/2\rfloor-1)$-stacked PL $d$-ball which is contained in
$\mathsf{K}$ as a subcomplex. Then for a new vertex $w\notin V$, the new
simplicial complex

$(\mathsf{K}\setminus\mathsf{B})\cup(\partial\mathsf{B}*\\{\emptyset,\\{w\\}\\})$

is a neighborly PL $d$-sphere.

Also, check [6, Theorem 1] for the converse for neighborly $4$-polytopes. We
call the process described in Proposition 3.7 a single element extension.

In the literature, it seems that enumerating all neighborly $d$-spheres is a
very challenging task even for small size already in dimension $d=3$, for
example, see [6, 5]. Hence, it looks difficult to obtain full combinatorial
characterizations of neighborly spheres and colorability results of neighborly
spheres from them. However, it is still possible to obtain the results for
spheres obtained by applying just one single element extension to a cyclic
polytope. The resulting neighborly sphere shares many faces with the original
cyclic polytope, and this is the key property to prove the following
proposition.

######  Proposition 3.8.

Let $d\geq 2$. Let $\mathsf{K}$ be a neighborly $d$-sphere which is obtained
from a cyclic polytope $C_{d+1}(n)$ by applying one single element extension
which adds a new vertex $w$. Then $\mathsf{K}$ is 2-colorable.

###### Proof.

The case when $d=2$ is easily obtained from Proposition 3.1. So we assume
$d\geq 3$. We identify the vertices of a cyclic polytope $C_{d+1}(n)$ with
$1,\dots,n$ in order. We show how we can extend the alternating coloring
$c:[n]\to\\{R,B\\}$ of $C_{d+1}(n)$ to a proper 2-coloring of $\mathsf{K}$.

In fact, we only need to consider a facet which is newly added in the single
element extension. Such a facet has the form $f\cup\\{w\\}$ where $|f|=d\geq
3$ and $f$ is a face of some facet in $C_{d+1}(n)$. Among such faces $f$,
again, it is enough to only consider monochromatic ones in the coloring $c$.
By Gale’s evenness criterion 3.5 and the choice of $c$, we should have
$|f\setminus\\{1,n\\}|\leq 1$ otherwise there is no way to extend $f$ to a
facet of $C_{d+1}(n)$. This only leaves the case when $d=3$,
$\\{1,n\\}\subseteq f$ and $c(1)=c(n)$. Now, we color $w$ with the color
different from $c(1)$. ∎

In [19], Novik and Zheng constructed many neighborly spheres and counted the
number of them. With their result (see [19, Theorem 1.2] and the proof), we
can conclude that there are at least $2^{\Omega(n^{\lfloor d/2\rfloor})}$
neighborly $d$-spheres which are 2-colorable when $d$ is odd and $d\geq 5$.

######  Remark 3.9.

In [18], Miyata and Padrol enumerated all neighborly oriented matroids of rank
$r$ on $n$ elements for some small values of $r$ and $n$. Using the result,
they tested many properties of oriented matroids, including the dual
surrounding property $S^{*}(k)$. Their results particularly imply that every
neighborly oriented matroid $\mathcal{M}$ constructed in [18] satisfies
$\tau(\mathcal{F}(\mathcal{M}))\leq n/2$ where $\mathcal{F}(\mathcal{M})$
denotes the facet hypergraph of $\mathcal{M}$, which records incidences
between the facets and elements of $\mathcal{M}$, and $n$ is the number of
elements of $\mathcal{M}$.

##  4 Constructions of $(d+1)$-polytopes with transversal ratio
$\frac{2}{d+2}$

In this section we prove Theorem 1.1. We first begin by introducing a notion
which will be useful in the constructions of Theorem 1.1 and 1.2.

######  Definition 4.1.

Let $\mathsf{K}_{1}$ and $\mathsf{K}_{2}$ be PL $d$-spheres, and let $f_{i}$
be a facet of $\mathsf{K}_{i}$ for each $i\in[2]$. Given a bijection
$\psi:f_{1}\to f_{2}$, we define the connected sum
$\mathsf{K}_{1}\\#_{\psi}\mathsf{K}_{2}$ of $\mathsf{K}_{1}$ and
$\mathsf{K}_{2}$ with respect to $\psi$ as

$\mathsf{K}_{1}\\#_{\psi}\mathsf{K}_{2}=(\mathsf{K}_{1}\setminus\\{f_{1}\\})\sqcup(\mathsf{K}_{2}\setminus\\{f_{2}\\})/\sim_{\psi},$

where $\sqcup$ denotes disjoint union and every proper subface $g_{1}$ of
$f_{1}$ is identified with $\psi(g_{1})$.

######  Lemma 4.2.

The connected sum $\mathsf{K}_{1}\\#_{\psi}\mathsf{K}_{2}$ is also a PL
$d$-sphere.

###### Proof.

By Newman’s theorem [8, Theorem 4.7.21 (iii)],
$\mathsf{K}_{i}\setminus\\{f_{i}\\}$ is a PL $d$-ball for every $i\in[2]$.
Since those two PL $d$-balls are attached along their entire boundaries, the
connected sum is a PL $d$-sphere by [8, Theorem 4.7.21 (ii)]. ∎

Let $d\geq 2$ be a fixed integer. Let us denote the boundary complex of the
abstract $(d+1)$-simplex on a vertex set $\\{v_{1},v_{2},\dots,v_{d+2}\\}$ by
$\mathsf{S}^{d}$, that is, let

$\mathsf{S}^{d}=\partial\Delta(\\{v_{1},v_{2},\dots,v_{d+2}\\}).$

Let $\mathsf{C}^{d}$ be the boundary complex of the $(d+1)$-dimensional cross
polytope, that is, $\mathsf{C}^{d}$ is the $(d+1)$-fold join

$\mathsf{C}^{d}=\mathsf{S}^{0}*\cdots*\mathsf{S}^{0}.$

Note that $\mathsf{C}^{d}$ has a natural antipodal action.

Now, let us choose arbitrary facets $f$ and $g$ from $\mathsf{C}^{d}$ and
$\mathsf{S}^{d}$, and let $\psi_{\mathsf{S}}:f\to g$ be an arbitrary
identification map. We denote
$\mathsf{C}^{d}\\#_{\psi_{\mathsf{S}}}\mathsf{S}^{d}$ by $\mathsf{C}^{d}_{+}$.
Note that by symmetry, $\mathsf{C}^{d}_{+}$ is independent from the choice of
the facets $f$ and $g$, and the identification map $\psi_{\mathsf{S}}$. The
apex vertex of $\mathsf{C}^{d}_{+}$ is the vertex $w$ that was opposite to $g$
in $\mathsf{S}^{d}$, and the base facet of $\mathsf{C}^{d}_{+}$ is the facet
that was antipodal to $f$ in $\mathsf{C}^{d}$. Since $\mathsf{S}^{d}$ and
$\mathsf{C}^{d}$ have $d+2$ and $2(d+1)$ vertices respectively, and they share
$d+1$ vertices in common at $\mathsf{C}^{d}_{+}$, $\mathsf{C}^{d}_{+}$ has

$(d+2)+2(d+1)-(d+1)=2d+3$

vertices.

Using the simplicial sphere $\mathsf{C}^{d}_{+}$, we inductively construct
simplicial $d$-spheres $\mathsf{X}^{d}_{k}$ as follows.

  * •

Let $\mathsf{X}^{d}_{1}=\mathsf{S}^{d}$. We choose an arbitrary vertex of
$\mathsf{X}^{d}_{1}$ as the apex vertex of $\mathsf{X}^{d}_{1}$. Obviously
$\mathsf{X}^{d}_{1}$ has $d+2$ vertices.

  * •

When $k\geq 2$, let
$\mathsf{X}^{d}_{k}=\mathsf{X}^{d}_{k-1}\\#_{\psi^{d}_{k}}\mathsf{C}^{d}_{+}$,
where $\psi^{d}_{k}$ is an arbitrary bijection from a face $f_{k-1}$ which
contains the apex vertex of $\mathsf{X}^{d}_{k-1}$ to the base facet of
$\mathsf{C}^{d}_{+}$. We choose the apex vertex of $\mathsf{C}^{d}_{+}$ as the
apex vertex of $\mathsf{X}^{d}_{k}$. This connected sum operation adds

$(2d+3)-(d+1)=d+2$

vertices to $\mathsf{X}^{d}_{k-1}$ since $\mathsf{C}^{d}_{+}$ has $2d+3$
vertices and shares $d+1$ vertices with $\mathsf{X}^{d}_{k-1}$ in
$\mathsf{X}^{d}_{k}$. Using induction, we can conclude that
$\mathsf{X}^{d}_{k}$ has $k(d+2)$ vertices.

For our purpose, it does not matter which face $f_{k-1}$ and identification
map $\psi^{d}_{k}$ we choose.

Figure 1: A Schlegel diagram of $\mathsf{X}^{2}_{3}$. The three triangles with
thick green edges surround Schlegel diagrams of the complexes
$\mathsf{X}^{2}_{k}$ for $k\in[3]$. Here, red squares describe the apex
vertices of $\mathsf{X}^{2}_{k}$.

Note that each of $\mathsf{S}^{d}$ and $\mathsf{C}^{d}_{+}$ can be realizable
as the boundary of a $(d+1)$-dimensional polytope. Using these observations,
the following lemma gives a stronger conclusion than Lemma 4.2 that
$\mathsf{X}^{d}_{k}$ can be realized as the boundary of a $(d+1)$-polytope.

######  Lemma 4.3.

Suppose that each of simplicial $d$-spheres $\mathsf{K}_{1}$ and
$\mathsf{K}_{2}$ is realizable as the boundary of a $(d+1)$-polytope. Then the
connected sum $\mathsf{K}_{1}\\#_{\psi}\mathsf{K}_{2}$ is realizable as the
boundary of a $(d+1)$-polytope for any map $\psi$ from a facet of
$\mathsf{K}_{1}$ to a facet of $\mathsf{K}_{2}$.

This is a special case of [22, Lemma 3.2.4]. Since there are $k(d+2)$ vertices
in $\mathsf{X}_{k}^{d}$, it is enough to show the following claim to prove
Theorem 1.1.

######  Claim.

We have $\tau(\mathsf{X}^{d}_{k})=2k$. Furthermore, there is no minimum
transversal of $\mathsf{X}^{d}_{k}$ containing a facet incident to the apex
vertex of $\mathsf{X}^{d}_{k}$.

To prove the claim, we use induction on $k$. When $k=1$, by definition
$\mathsf{X}^{d}_{1}$ is the boundary of an abstract $(d+1)$-simplex. Hence,
$\tau(\mathsf{X}^{d}_{1})=2$. Since every facet of $\mathsf{X}^{d}_{1}$ has
size $d+1>2$, the second claim also holds for this case.

Now let us assume that the claim holds for $\mathsf{X}^{d}_{k-1}$ where $k\geq
2$. Let $n=|V(\mathsf{X}^{d}_{k})|$, that is, let $n=k(d+2)$. We denote by
$\mathsf{C}^{d}_{k}$ the complex $\mathsf{C}^{d}_{+}$ which is glued at
$\mathsf{X}^{d}_{k-1}$ to form $\mathsf{X}^{d}_{k}$. Note that there is a
natural antipodal action on non-apex vertices of $\mathsf{C}^{d}_{k}$.

We first show that $\tau(\mathsf{X}^{d}_{k})\leq\frac{2}{d+2}n=2k$. In fact,
it is easy to show that the graph of $\mathsf{X}^{d}_{k}$ is $(d+2)$-colorable
by induction: Suppose a proper $(d+2)$-coloring was already given to the graph
of $\mathsf{X}^{d}_{k-1}$. When we glue $\mathsf{C}^{d}_{k}$ at
$\mathsf{X}^{d}_{k-1}$, the colors of $d+1$ vertices of $\mathsf{C}^{d}_{k}$
in the base facet, which are necessarily distinct, are already determined by
the precoloring of $\mathsf{X}^{d}_{k-1}$ via identification. We color each of
the remaining non-apex vertices of $\mathsf{C}^{d}_{k}$ with the same color of
the antipodal vertex of it in the base facet. We complete the extension by
assigning to the apex vertex of $\mathsf{C}^{d}_{k}$ the color which was not
used on the base facet of $\mathsf{C}^{d}_{k}$. The union of any two among
$d+2$ color classes of the coloring is a transversal of $\mathsf{X}^{d}_{k}$,
and choosing a minimum-sized union among them gives the bound.

Next, we show that a transversal of $\mathsf{X}^{d}_{k}$ requires at least
$\frac{2}{d+2}n=2k$ vertices. Suppose that $T$ is a minimum transversal of
$\mathsf{X}^{d}_{k}$. Let $f_{k-1}^{-}$ be the set of non-apex vertices of
$\mathsf{C}^{d}_{k}$ which are not in the base facet (which is identified with
$f_{k-1}$) of $\mathsf{C}^{d}_{k}$. Let $\mathcal{F}$ be the set of facets of
$\mathsf{X}^{d}_{k}$ which are contained in $f_{k-1}\cup f_{k-1}^{-}$. Note
that $\mathsf{K}(\mathcal{F})$ is isomorphic to the boundary complex of a
cross polytope with a pair of antipodal facets removed. There are 3 cases to
consider.

  1. 1.

When $T$ does not contain any vertex of $f_{k-1}$: In this case, we need at
least $2(k-1)-1=2k-3$ vertices to traverse all facets of
$\mathsf{X}^{d}_{k-1}\setminus\\{f_{k-1}\\}$ by induction. To traverse all
facets in $\mathcal{F}$, we need all vertices of $f_{k-1}^{-}$, which has size
$d+1$. Hence,

$|T|\geq(2k-3)+(d+1)\geq(2k-3)+3=2k.$

Note that this case never happens when $d\geq 3$, because we already have
$\tau(\mathsf{X}^{d}_{k})\leq 2k$, but for $d\geq 3$, the above bound becomes
$|T|\geq(2k-3)+(d+1)\geq 2k+1$, contradicting $T$ is a minimum transversal.

  2. 2.

When $T$ contains a vertex of $f_{k-1}$ but not all vertices: Note that in
this case, $T\cap V(\mathsf{X}^{d}_{k-1})$ is also a transversal of
$\mathsf{X}^{d}_{k-1}$. This requires at least $2(k-1)=2k-2$ vertices for
$T\cap V(\mathsf{X}^{d}_{k-1})$. Since $T$ does not contain $f_{k-1}$, there
is at least one facet in $\mathcal{F}$ not covered by $T\cap
V(\mathsf{X}_{k-1}^{d})$, and $T$ must contain some vertex $w\in f_{k-1}^{-}$
in order to cover that facet. Additionally, $T$ must have at least one further
vertex to cover the facet $\\{v\\}\cup f_{k-1}^{-}\setminus\\{w\\}$, where $v$
is the apex vertex of $\mathsf{X}_{k}^{d}$. Hence,

$|T|\geq(2k-2)+2=2k.$

  3. 3.

When $T$ uses all vertices of $f_{k-1}$: Again, $T\cap
V(\mathsf{X}^{d}_{k-1})$ is a transversal of $\mathsf{X}^{d}_{k-1}$. By the
second claim for $\mathsf{X}^{d}_{k-1}$, $T\cap V(\mathsf{X}^{d}_{k-1})$ is
not a minimum transversal of $\mathsf{X}^{d}_{k-1}$. This gives $|T\cap
V(\mathsf{X}^{d}_{k-1})|\geq 2(k-1)+1=2k-1$. Note that $T$ should use the apex
vertex of $\mathsf{X}^{d}_{k}$ to satisfy the minimality. Therefore, we have

$|T|\geq(2k-1)+1=2k.$

The three scenarios described above show that if $T$ is a transversal of
$\mathsf{X}_{k}^{d}$ of size $2k$ then $T$ cannot contain any facet which
includes the apex vertex $v$, since in the first case $T$ does not contain $v$
and in the others $T$ contains at most two vertices from
$f_{k-1}^{-}\cup\\{v\\}$. This completes the proof of the claim. ∎

Particularly for the 2-dimensional case, the construction of Theorem 1.1 is
not the only one with transversal ratio exactly $1/2$. The boundary complex of
the regular icosahedron is another example. The reader may verify this.

Note that a simplicial 2-sphere $\mathsf{K}$ with transversal ratio exactly
$1/2$ has a strong symmetry, for example, every proper 4-coloring of the graph
of $\mathsf{K}$ has color classes of equal size. It might be interesting to
investigate such simplicial 2-spheres further.

######  Question 4.

Can we characterize all simplicial 2-spheres with transversal ratio exactly
$\frac{1}{2}$? What properties do they have?

##  5 Constructions of 3-spheres with transversal ratios larger than
$\frac{1}{2}$

In this section, we prove Theorem 1.2. The proof relies on the following
computational result.

######  Theorem 5.1.

There is a 4-uniform hypergraph $\mathcal{N}_{21}$ on 21 vertices such that
$\mathsf{K}(\mathcal{N}_{21})$ is obtained by removing a single facet
$\hat{g}$ from a neighborly PL 3-sphere $\mathsf{K}_{21}$ and
$\tau(\mathcal{N}_{21})=11$.

###  5.1 An infinite construction based on Theorem 5.1

Assuming Theorem 5.1, we first show how we can obtain an infinite construction
which satisfies the conclusion of Theorem 1.2. Similarly with Section 4, we
inductively construct simplicial 3-spheres using connected sums. Let $f$ be an
arbitrary facet of $\mathsf{C}^{3}$, the boundary complex of the 4-dimensional
cross polytope which has 8 vertices, and $\psi_{\mathsf{K}}:f\to\hat{g}$ be an
arbitrary identification map for the facet $\hat{g}$ from Theorem 5.1.

We denote $\mathsf{C}^{3}\\#_{\psi_{\mathsf{K}}}\mathsf{K}_{21}$ by
$\mathsf{C}_{\mathsf{K}}$. Note that $\mathsf{C}_{\mathsf{K}}$ has $8+21-4=25$
vertices. Also note that by symmetry the isomorphism type of
$\mathsf{C}_{\mathsf{K}}$ is independent from the choice of $f$ and
$\psi_{\mathsf{K}}$. We call the facet of $\mathsf{C}_{\mathsf{K}}$ which was
the antipodal facet to $f$ in $\mathsf{C}^{3}$ the base facet of
$\mathsf{C}_{\mathsf{K}}$.

We inductively construct 3-dimensional simplicial complexes $\mathsf{Y}_{k}$
as follows.

  * •

Let $\mathsf{Y}_{1}=\mathsf{K}_{21}$. So $\mathsf{Y}_{1}$ has 21 vertices. We
choose $\hat{g}$ as the base facet of $\mathsf{Y}_{1}$.

  * •

When $k\geq 2$, let
$\mathsf{Y}_{k}=\mathsf{Y}_{k-1}\\#_{\varphi_{k}}\mathsf{C}_{\mathsf{K}}$,
where $\varphi_{k}$ is an arbitrary bijection from the base facet of
$\mathsf{Y}_{k-1}$ to the base facet of $\mathsf{C}_{\mathsf{K}}$. We choose a
facet from $\mathsf{C}_{\mathsf{K}}$ which was neither the base facet nor a
facet in the copy of $\mathsf{K}_{21}\setminus\\{\hat{g}\\}$ to be the base
facet of $\mathsf{Y}_{k}$.

Figure 2: A 2-dimensional illustration of the complexes $\mathsf{Y}_{k}$. The
triangles with thick green edges surround Schlegel diagrams of the complexes
$\mathsf{Y}_{k}$ for $k\in[3]$.

Every time we conduct the connected sum operation with
$\mathsf{C}_{\mathsf{K}}$ to $\mathsf{Y}_{k}$, we introduce $25-4=21$
additional vertices to $\mathsf{Y}_{k}$. So, $\mathsf{Y}_{k}$ has $21k$
vertices. This naturally partitions the vertex set $V(\mathsf{Y}_{k})$ into
$V_{1},\dots,V_{k}$, where $V_{i}$ is the set of vertices introduced in the
$i$th step. When $k\geq 2$, the induced subcomplex $\mathsf{Y}_{k}[V_{i}]$ has
a facet hypergraph isomorphic to $\mathcal{N}_{21}$. Hence, by Theorem 5.1, we
need at least 11 vertices for each $V_{i}$ to traverse all facets of
$\mathsf{Y}_{k}[V_{i}]$, which implies that the transversal ratio of
$\mathsf{Y}_{k}$ is at least $11/21$.

Since $\mathsf{K}_{21}$ and $\mathsf{C}^{3}$ are all PL spheres, each
$\mathsf{Y}_{k}$ is a PL 3-sphere by Lemma 4.2. This completes the proof of
Theorem 1.2. ∎

###  5.2 The experimental construction of $\mathsf{K}_{21}$

We now explain how we constructed the neighborly PL 3-sphere $\mathsf{K}_{21}$
in Theorem 5.1. The exact computational results are stated in Appendix A.

Neighborly spheres have a large number of facets relative to the number of
vertices, which might give a better chance to find a simplicial sphere of a
larger transversal ratio. We simplify and restate Proposition 3.7 for our
case, which describes an inductive method to construct neighborly spheres.
Note that we do not particularly state the PL condition since every simplicial
$d$-sphere is PL for $d\leq 3$ (see the paragraph after [8, Definition
4.7.20]).

######  Proposition 5.2 (Restatement of Proposition 3.7 when $d=3$).

Let $\mathsf{K}$ be a neighborly $3$-sphere on $V$. Let $\mathsf{B}$ be a
subcomplex of $\mathsf{K}$ on $V$ which is a stacked $3$-ball. Then for a new
vertex $w\notin V$, the new simplicial complex

$(\mathsf{K}\setminus\mathsf{B})\cup(\partial\mathsf{B}*\\{\emptyset,\\{w\\}\\})$

is a neighborly $3$-sphere.

Recall that we call the process of Proposition 5.2 a single element extension.

Here is how we applied Proposition 5.2: Starting from the boundary complex of
a cyclic polytope $\mathsf{K}(C_{4}(7))$, we applied many single element
extensions and obtained a neighborly sphere of size one larger than the
previous one at a time. This resulting neighborly sphere at each step was
chosen to be optimal in a parameter $\varepsilon(\cdot)$ among all spheres of
the same size randomly sampled in that step. We iterated this process until we
got the complex $\mathsf{K}_{21}$.

The purpose of the $\varepsilon$ parameter is to choose a neighborly sphere
which is more likely to have a large transversal number. It is defined as
follows.

######  Definition 5.3 (The degree of an edge (of size 2) and
$\varepsilon(\mathsf{K})$).

For a simplicial sphere $\mathsf{K}$ and an edge $e$ of $\mathsf{K}$,
$\deg_{\mathsf{K}}(e)$ counts the number of facets of $\mathsf{K}$ which
contains $e$ as a subset. We define a parameter $\varepsilon(\mathsf{K})$ of a
simplicial sphere $\mathsf{K}$ on $n$ vertices as the sum of the $n$ largest
values of the degrees of edges of $\mathsf{K}$.

######  Example 5.4 (The $\varepsilon$ value for cyclic 4-polytopes).

By Gale’s evenness criterion (Theorem 3.5), one can see that a subset of the
form $\\{i,i+1\\}$ modulo $n$ has degree $n-2$ in $C_{4}(n)$, which is the
maximum possible value for the degree of an edge in a simplicial 3-sphere.
Since there are $n$ such 2-subsets, we have
$\varepsilon(\mathsf{K}(C_{4}(n)))=n(n-2)$. ∎

In the construction, we kept the $\varepsilon$ value as low as possible. We
briefly give a justification for this heuristic. The face numbers of a
neighborly $d$-sphere are determined by its initial condition being
$\lfloor(d+1)/2\rfloor$-neighborly and the Dehn–Sommerville equations ([27,
Theorem 8.21], check also the remark before Corollary 8.31 in [27]). So it is
impossible to distinguish one neighborly 3-sphere from another by just
comparing vertex degrees. Rather, the degree of an edge is more suitable to
distinguish neighborly 3-spheres.

Recall that our purpose is to obtain a simplicial sphere on $n$ vertices with
the transversal number larger than $n/2$. A necessary condition of this is
that the simplicial sphere is not 2-colorable. Here is a simple observation on
2-colorability of a simplicial sphere.

######  Proposition 5.5.

For a simplicial sphere $\mathsf{K}$, $\mathcal{F}(\mathsf{K})$ is 2-colorable
if and only if there is a bipartite subgraph $G$ of the graph (or the
1-skeleton) of $\mathsf{K}$ such that for every facet $f$ of $\mathsf{K}$
there is an edge $e\in E(G)$ such that $e\subseteq f$.

In other words, in order to have 2-colorability of $\mathsf{K}$, $\mathsf{K}$
needs to have a bipartite graph which covers all facets of $\mathsf{K}$. The
chance that there is such a covering bipartite graph might become higher when
we can choose edges with large degrees. One example is a cyclic polytope as
described in Example 5.4. In fact, those edges in Example 5.4 cover all facets
of $C_{4}(n)$ even without using the edge $\\{1,n\\}$, and in this sense
cyclic polytopes are extremal. As opposed to cyclic polytopes, we keep the
$\varepsilon$ value low as possible, in order to find a neighborly sphere with
different characteristics from cyclic polytopes, which is not 2-colorable, or
even has the transversal number larger than $n/2$.

######  Remark 5.6.

We also constructed a non-2-colorable neighborly 3-sphere on 13 vertices with
a similar method. It should also be noted that optimizing the $\varepsilon$
parameter does not look essential in finding a desirable construction, but it
seems to make the process more efficient.

###  5.3 Non-realizability of $\mathsf{K}_{21}$

If $\mathsf{K}_{21}$ can be realized as the boundary of a polytope, then, by
using Lemma 4.3 rather than Lemma 4.2, we can show that the constructions we
obtained in this section can be all realizable by polytopes. Unfortunately,
$\mathsf{K}_{21}$ is not realizable, so it does not have direct implications
to the $k$-surrounding property $S(k)$. This observation is based on
computational constructions by Miyata and Padrol [18] and the following
proposition. The following proposition and its proof are essentially from [6].

######  Proposition 5.7.

Let $\mathsf{K}_{1}$ and $\mathsf{K}_{2}$ be two neighborly 3-spheres where
$\mathsf{K}_{2}$ is obtained from $\mathsf{K}_{1}$ by a single element
extension which adds a new vertex $w$. Suppose that $\mathsf{K}_{2}$ is
realizable as the boundary of a polytope. Then $\mathsf{K}_{1}$ is also
realizable by a polytope.

As we mentioned before Proposition 5.2, every simplicial $d$-sphere is PL for
$d\leq 3$. Hence, we do not particularly state the PL condition in Proposition
5.7.

We use the following lemma to prove Proposition 5.7.

######  Lemma 5.8.

Let $\mathsf{L}_{2}$ be a neighborly 3-sphere on a vertex set $V\cup\\{w\\}$.
If there is another simplicial 3-sphere $\mathsf{L}_{1}$ on $V$ which has all
faces of $\mathsf{L}_{2}[V]$, then the facets in
$\mathsf{L}_{1}\setminus\mathsf{L}_{2}[V]$ form a stacked 3-ball.

For a set of simplices $\mathsf{K}$, denote the number of $i$-dimensional
faces of $\mathsf{K}$ by $f_{i}(\mathsf{K})$. For a neighborly sphere
$\mathsf{K}$, recall that $f_{i}(\mathsf{K})$ is completely determined by
$f_{0}(\mathsf{K})$ using the Dehn-Sommerville equations [27, Theorem 8.21].
Especially when $\mathsf{K}$ is a neighborly 3-sphere,

$\displaystyle f_{2}(\mathsf{K})=2\binom{f_{0}(\mathsf{K})-1}{2}-2,\textrm{
and }f_{3}(\mathsf{K})=\binom{f_{0}(\mathsf{K})-1}{2}-1.$ (1)

###### Proof of Lemma 5.8.

Let $n=|V|$. We first count how many new faces should be added to
$\mathsf{L}_{2}[V]$ in order to form $\mathsf{L}_{1}$. Let $\mathcal{N}$ be
the set of those new faces, that is, let
$\mathcal{N}=\mathsf{L}_{1}\setminus\mathsf{L}_{2}[V]$. Note that
$\mathsf{L}_{1}$ is also neighborly since the 1-skeleton of
$\mathsf{L}_{2}[V]$ is complete and it is contained in $\mathsf{L}_{1}$. In
particular, $f_{0}(\mathcal{N})=f_{1}(\mathcal{N})=0$. So we only consider 2-
and 3-faces.

Let $\mathcal{S}$ be the set of faces in $\mathsf{L}_{2}$ which contains $w$.
Note that each face of $\mathcal{S}$ corresponds to a face in the link

$\mathsf{lk}_{\mathsf{L}_{2}}(w):=\\{g\in\mathsf{L}_{2}:g\cup\\{w\\}\in\mathsf{L}_{2},\,w\notin
g\\}$

which is 1 dimension lower. Since $\mathsf{L}_{2}$ is a PL sphere, every link
in $\mathsf{L}_{2}$ is a simplicial sphere (see [8, Theorem 4.7.21 (iv)]). In
particular, $\mathsf{lk}_{\mathsf{L}_{2}}(w)$ is a simplicial 2-sphere which
contains all the other vertices of $\mathsf{L}_{2}$ other than $w$, so

$\displaystyle f_{2}(\mathcal{S})=3n-6,\textrm{ and }f_{3}(\mathcal{S})=2n-4.$
(2)

Hence, we have

$\displaystyle
f_{2}(\mathcal{N})=f_{2}(\mathsf{L}_{1})-f_{2}(\mathsf{L}_{2}[V])=f_{2}(\mathsf{L}_{1})-(f_{2}(\mathsf{L}_{2})-f_{2}(\mathcal{S}))$
$\displaystyle\stackrel{{\scriptstyle(\ref{eqn_face_number_neighborly}),(\ref{eqn_link_face_number})}}{{=}}$
$\displaystyle\left(2\binom{n-1}{2}-2\right)-\left(2\binom{n}{2}-2\right)+(3n-6)=3n-6-2(n-1)=n-4,$

and similarly

$\displaystyle
f_{3}(\mathcal{N})=f_{3}(\mathsf{L}_{1})-(f_{3}(\mathsf{L}_{2})-f_{3}(\mathcal{S}))$
$\displaystyle\stackrel{{\scriptstyle(\ref{eqn_face_number_neighborly}),(\ref{eqn_link_face_number})}}{{=}}$
$\displaystyle\left(\binom{n-1}{2}-1\right)-\left(\binom{n}{2}-1\right)+(2n-4)=2n-4-(n-1)=n-3.$

Let $G$ be the graph which has the 3-faces of
$\mathcal{N}=\mathsf{L}_{1}\setminus\mathsf{L}_{2}[V]$ as vertices, and where
a pair of 3-faces are adjacent when they share a common 2-face. Note that the
conclusion is equivalent to $G$ being a tree. Let $N$ (resp. $S$) be the
complement of the geometric realization $||\mathsf{L}_{2}[V]||$ of
$\mathsf{L}_{2}[V]$ as a subspace of a geometric realization of
$\mathsf{L}_{1}$ (resp. $\mathsf{L}_{2}$). Let $\widetilde{H}_{i}(X)$ denote
the $i$-th reduced homology group of a space $X$ and let
$\widetilde{H}^{i}(X)$ denote the $i$-th reduced cohomology group of $X$.
Since $\mathsf{L}_{2}[V]$ is a finite simplicial complex,
$||\mathsf{L}_{2}[V]||$ is compact and locally contractible [11, Proposition
A.4], so by Alexander Duality [11, Theorem 3.44], $\widetilde{H}_{0}(N)$ is
isomorphic to $\widetilde{H}^{2}(||\mathsf{L}_{2}[V]||)$, which is isomorphic
to $\widetilde{H}_{0}(S)$, which is the trivial group, since $S$ is the
interior of a cone over a 2-sphere. Hence, $N$ is path connected, and
therefore we can always choose a path between two interior points from
different facets of $N$. This corresponds to a path in $G$ since $\mathcal{N}$
only has 2- and 3-faces, and 2-faces of $\mathcal{N}$ correspond to edges in
$G$. Thus, $G$ is a connected graph with $n-3$ vertices and $n-4$ edges, so
$G$ is a tree, which means that the facets of $\mathcal{N}$ forms a stacked
3-ball.

∎

###### Proof of Proposition 5.7.

Let $\mathbf{P}_{2}$ be a realization of $\mathsf{K}_{2}$ as a polytope. For
simplicity, we identify the vertex sets of $\mathsf{K}_{2}$ and
$\mathbf{P}_{2}$, and denote $V(\mathsf{K}_{2})\setminus\\{w\\}$ by $V$, that
is, $V=V(\mathsf{K}_{1})$. Let $\mathbf{P}_{1}=\operatorname{conv}(V)$. We
claim that $\mathsf{K}(\mathbf{P}_{1})=\mathsf{K}_{1}$.

Note that $\mathsf{K}_{1}\cap\mathsf{K}_{2}=\mathsf{K}_{2}[V]$: The inclusion
$\subseteq$ is clear because every face of $\mathsf{K}_{1}$ is contained in
$V$. The other inclusion $\supseteq$ also holds because $\mathsf{K}_{2}$ is
obtained from $\mathsf{K}_{1}$ by a single element extension. Also note that
$\mathsf{K}(\mathbf{P}_{1})\cap\mathsf{K}(\mathbf{P}_{2})=\mathsf{K}(\mathbf{P}_{2})[V]$:
$\subseteq$ holds by the same reason. $\supseteq$ also holds because every
face of $\mathbf{P}_{2}$ whose vertices are in $V$ is also extreme in
$\mathbf{P}_{1}$. As a conclusion, we get

$\displaystyle\mathsf{K}_{1}\cap\mathsf{K}_{2}=\mathsf{K}_{2}[V]=\mathsf{K}(\mathbf{P}_{2})[V]=\mathsf{K}(\mathbf{P}_{1})\cap\mathsf{K}(\mathbf{P}_{2}).$
(3)

It is enough to show that this identity extends to the rest of
$\mathsf{K}_{1}$ and $\mathsf{K}(\mathbf{P}_{1})$.

By Lemma 5.8, the facets of both $\mathsf{K}_{1}\setminus\mathsf{K}_{2}$ and
$\mathsf{K}(\mathbf{P}_{1})\setminus\mathsf{K}(\mathbf{P}_{2})$ are stacked
3-balls. Every stacked 3-ball has a vertex whose link is a triangle, namely
the last vertex added in the stacking, so by induction, a stacked 3-ball is
completely determined by its boundary. The stacked 3-balls
$\mathsf{K}_{1}\setminus\mathsf{K}_{2}$ and
$\mathsf{K}(\mathbf{P}_{1})\setminus\mathsf{K}(\mathbf{P}_{2})$ have the same
boundary, so
$\mathsf{K}_{1}\setminus\mathsf{K}_{2}=\mathsf{K}(\mathbf{P}_{1})\setminus\mathsf{K}(\mathbf{P}_{2})$,
and therefore $\mathsf{K}_{1}=\mathsf{K}(\mathbf{P}_{1})$. ∎

By Proposition 5.7, if $\mathsf{K}_{21}$ were realizable, then
$\mathsf{K}_{11}$, the intermediate neighborly sphere with 11 vertices, should
be also realizable by a neighborly 4-polytope. However, while we have
$\varepsilon(\mathsf{K}_{11})=74$, the minimum among $\varepsilon$ values of
all neighborly oriented matroids of rank 5 with 11 elements, which in
particular include all neighborly 4-polytopes, is $81$. This computation was
done by a computer. We went through the supplementary data file
“neighborly11_5.zip”111This file is available at
https://sites.google.com/site/hmiyata1984/neighborly_polytopes. of [18] and
calculated $\varepsilon$ values for each facet list. This shows that
$\mathsf{K}_{21}$ is not realizable. ∎

######  Question 5.

For every integer $d\geq 3$, is there a $(d+1)$-polytope $\mathbf{P}$ such
that $\tau(\mathbf{P})>|V(\mathbf{P})|/2$?

##  6 An upper bound on the chromatic number of simplicial spheres

In this section, we prove Theorem 1.3, that is, we prove that if $\mathbf{P}$
is a $(d+1)$-dimensional simplicial polytope on $n$ vertices, then
$\chi(\mathbf{P})\in O(n^{\frac{\lceil d/2\rceil-1}{d}})$. Later we generalize
it for simplicial spheres (see Theorem 6.7) in Subsection 6.1.

For Theorem 1.3, we prove the following more general statement. A hypergraph
$\mathcal{H}$ is called linearly $d$-embeddable if there is a linear embedding
$\psi:||\mathsf{K}(\mathcal{H})||\to\mathbb{R}^{d}$.

######  Theorem 6.1.

Let $\mathcal{H}$ be a $(d+1)$-uniform hypergraph on $n$ vertices which is
linearly $d$-embeddable. Then, we have

$\chi(\mathcal{H})\in O(n^{\frac{\lceil d/2\rceil-1}{d}}).$

We first show that Theorem 6.1 implies Theorem 1.3.

###### Proof of Theorem 1.3.

Let $\mathbf{P}$ be a polytope, and $\mathcal{H}$ be a $(d+1)$-uniform
hypergraph obtained by removing one hyperedge of $\mathcal{F}(\mathbf{P})$. By
using an appropriate Schlegel diagram of $\mathbf{P}$, we can easily see that
$\mathcal{H}$ is linearly $d$-embeddable. By Theorem 6.1,
$\chi(\mathcal{H})\in O(n^{\frac{\lceil d/2\rceil-1}{d}})$, which implies
$\chi(\mathbf{P})\in O(n^{\frac{\lceil d/2\rceil-1}{d}})$. ∎

Now we begin to prove Theorem 6.1. The only implication from linear
embeddability we use is the following upper bound theorem by Dey and Pach [10,
Theorem 2.1].

######  Theorem 6.2.

Let $\mathcal{H}$ be a $(d+1)$-uniform hypergraph on $n$ vertices which is
linearly embeddable into $\mathbb{R}^{d}$. Then we have
$|\mathcal{H}|<(d+1)n^{\lceil d/2\rceil}$.

We also need the following lemmas. A graph version of the first lemma is well-
known, see for example [4, Theorem 3.2.1]. Our lemma can be proved in a
similar way using the alteration method.

######  Lemma 6.3.

Let $\mathcal{H}$ be a $(d+1)$-uniform hypergraph on $n$ vertices such that
$|\mathcal{H}|\leq cn^{k}$. Then
$\alpha(\mathcal{H})\geq\beta_{d,c}n^{\frac{(d+1)-k}{d}}$, where $\beta_{d,c}$
depends only on $d$ and $c$.

For completeness, we include a modified proof here.

###### Proof.

Let $S\subseteq V(\mathcal{H})$ be a random subset obtained by including each
vertex in $S$ independently with a fixed probability $p$ determined later. Let
$X=|S|$ and $Y$ be the number of hyperedges of $\mathcal{H}$ contained in $S$.
Then removing one vertex from each hyperedge $f\subseteq S$ of $\mathcal{H}$
leaves an independent set of size at least $X-Y$. For each $f\in\mathcal{H}$,
let $Y_{f}$ be the indicator random variable for the event $f\subseteq S$.
Then $E[Y_{f}]=p^{d+1}$. Using linearity of expectation, we get

$E[Y]=\sum_{f\in\mathcal{H}}E[Y_{f}]=|\mathcal{H}|p^{d+1}\leq cn^{k}p^{d+1},$

which implies

$E[X-Y]=E[X]-E[Y]\geq np-cn^{k}p^{d+1}=np(1-cn^{k-1}p^{d})=:f(p).$

In the domain $0\leq p\leq 1$, we get the maximum of $f(p)$ at
$p_{0}=1/\sqrt[d]{c(d+1)n^{k-1}}$, and

$f(p_{0})=\frac{d}{(1+d)^{\frac{d+1}{d}}c^{\frac{1}{d}}}n^{\frac{(d+1)-k}{d}}$

is a lower bound on $\alpha(\mathcal{H})$. ∎

For a function $f:\mathbb{R}\to\mathbb{R}$ and a real number $n$, let
$s_{f}(n)$ be the smallest non-negative integer such that $f^{s_{f}(n)}(n)<1$,
that is, iterated applications of $f$ on $n$ for $s_{f}(n)$ times makes the
value less than 1. If there are no such numbers, we set $s_{f}(n)=\infty$.

######  Lemma 6.4.

Let $t<1$ and $\beta$ be positive reals. Define a function $h:\mathbb{R}_{\geq
0}\to\mathbb{R}_{\geq 0}$ as $h(x)=\max(x-\beta x^{t},0)$. Suppose
$(n=n_{0},n_{1},\dots,n_{M})$ is a sequence of non-negative real numbers with
$M\geq 1$ such that

  * •

$n_{i}\geq 1$ for every $0\leq i\leq M-1$,

  * •

$n_{M}<1$, and

  * •

$n_{i+1}\leq h(n_{i})$ for every $i\in[M-1]$.

Then, we have

$M\leq\frac{1}{\beta(1-t)}n^{1-t}+1.$

###### Proof.

Let $g(x)=\frac{x^{1-t}}{\beta(1-t)}+1$. We first show that $s_{h}(x)\leq
g(x)$ for every $x\geq 0$. For a contradiction, suppose it fails for some non-
negative values of $x$, that is, we suppose the set $F=\\{x\in\mathbb{R}_{\geq
0}:s_{h}(x)>g(x)\\}$ is non-empty. Let $y_{0}=\inf F$.

We claim that $y_{0}>\beta^{\frac{1}{1-t}}$. Observe the followings:

  1. (i)

$h(x)=0$ for $x\in[0,\beta^{\frac{1}{1-t}}]$.

  2. (ii)

$g(x)$ is strictly increasing and $g(x)\geq 1$ for $x\geq 0$.

  3. (iii)

$h(x)=x-\beta x^{t}$ and $h(x)$ is strictly increasing for
$x\geq\beta^{\frac{1}{1-t}}$.

By (i) and continuity of $h$, we know that $s_{h}(x)\leq 1$ for
$x\in[0,\beta^{\frac{1}{1-t}}+\delta]$ where $\delta>0$ is sufficiently small.
By (ii), we know that $g(x)\geq 1$ on the same interval
$[0,\beta^{\frac{1}{1-t}}+\delta]$. Combining these two, we have that
$g(x)\geq s_{h}(x)$ for $x\in[0,\beta^{\frac{1}{1-t}}+\delta]$, which implies

$y_{0}\geq\beta^{\frac{1}{1-t}}+\delta>\beta^{\frac{1}{1-t}}>0.$

By this and (iii), we have $h(x)=x-\beta x^{t}$, $x>0$ and $h(x)>0$ for every
$x\in F\cup\\{y_{0}\\}$. In particular, these imply that $y_{0}>h(y_{0})$. By
using continuity of $h$, we can choose $x_{0}\in F$ near $y_{0}$ such that
$h(x_{0})<y_{0}$, which implies $h(x_{0})\notin F$, that is,

$s_{h}(h(x_{0}))\leq g(h(x_{0})).$

Since $h(x_{0})>0$, the function $g(x)$ is well-defined and continuous on
$[h(x_{0}),x_{0}]$ and differentiable on $(h(x_{0}),x_{0})$. Hence, by the
mean value theorem, there is $\theta\in(h(x_{0}),x_{0})$ such that

$\displaystyle g(x_{0})-g(h(x_{0}))$ $\displaystyle=g(x_{0})-g(x_{0}-\beta
x_{0}^{t})$ $\displaystyle=\beta x_{0}^{t}g^{\prime}(\theta)=\frac{\beta
x_{0}^{t}}{\beta\theta^{t}}=\left(\frac{x_{0}}{\theta}\right)^{t}\geq 1.$

Putting these together, we obtain

$s_{h}(x_{0})\leq 1+s_{h}(h(x_{0}))\leq 1+g(h(x_{0}))\leq g(x_{0}),$

contradicting $x_{0}\in F$.

Next, we show that $M\leq s_{h}(n)$. With the inequality $s_{h}(n)\leq g(n)$,
this gives the desired result. It is enough to show this by $h^{i}(n)\geq
n_{i}$ for every $0\leq i\leq M$ using induction on $i$. The claim obviously
holds for $i=0$. Suppose $h^{i}(n)\geq n_{i}$ holds for some $0\leq i\leq
M-1$. Since $h$ is monotonically increasing by (i) and (iii) above, we have

$h^{i+1}(n)=h(h^{i}(n))\geq h(n_{i})\geq n_{i+1},$

by using the induction hypothesis and the assumption on the numbers $n_{i}$.
This completes the proof. ∎

###### Proof of Theorem 6.1.

Let $\mathcal{H}=\mathcal{H}_{0}$ be a linearly $d$-embeddable $(d+1)$-uniform
hypergraph on $n$ vertices. Starting from the index $i=0$, we conduct the
following iterative procedure inductively until we meet an empty hypergraph:

  1. 1.

Select an independent set $S_{i}$ of maximum size in $\mathcal{H}_{i}$, and

  2. 2.

let $\mathcal{H}_{i+1}=\mathcal{H}_{i}-S_{i}$, that is, let
$\mathcal{H}_{i+1}$ be the hypergraph obtained from $\mathcal{H}_{i}$ by
removing $S_{i}$ from $\mathcal{H}_{i}$.

This process terminates after a finite number of steps, say $M$. So, we obtain
$\mathcal{H}_{M}$ as the final empty hypergraph in this process. Note that
$S_{0},\dots,S_{M-1}$ are pairwise disjoint independent sets of $\mathcal{H}$
which cover all vertices of $V(\mathcal{H})$. Hence $S_{0},\dots,S_{M-1}$ form
a proper $M$-coloring of $\mathcal{H}$.

Let $n_{i}=|V(\mathcal{H}_{i})|$ for every $0\leq i\leq M$. Note that
$n_{i}\geq 1$ for $0\leq i\leq M-1$ and $n_{M}=0$. Also, by Theorem 6.2 and
Lemma 6.3, we have

$\alpha(\mathcal{H}_{i})\geq\beta_{d,d+1}n_{i}^{\frac{(d+1)-\lceil
d/2\rceil}{d}},$

which implies

$n_{i+1}\leq n_{i}-\beta_{d,d+1}n_{i}^{\frac{(d+1)-\lceil d/2\rceil}{d}}$

for every $0\leq i\leq M-1$. Hence, the sequence $(n_{0},n_{1},\dots,n_{M})$
satisfies all conditions in Lemma 6.4 with $t=\frac{(d+1)-\lceil
d/2\rceil}{d}$ and $\beta=\beta_{d,d+1}$. Therefore, using Lemma 6.4, we have

$\chi(\mathcal{H})\leq
M\leq\gamma_{t,\beta}n^{1-t}+1=\gamma_{t,\beta}n^{\frac{\lceil
d/2\rceil-1}{d}}+1$

where $\gamma_{t,\beta}=\frac{1}{\beta(1-t)}$. ∎

######  Remark 6.5.

In [12], the authors obtained the bound $\chi(\mathcal{H})\in
O(n^{\frac{\lceil d/2\rceil}{d}})$ for a $(d+1)$-uniform hypergraph
$\mathcal{H}$ on $n$ vertices which is linearly $d$-embeddable. Theorem 6.1 is
a slight improvement on this upper bound for such hypergraphs.

###  6.1 Generalization of Theorem 1.3 for simplicial spheres

######  Remark 6.6.

After the first version of this paper was available, it was first noticed by
Andreas Holmsen that Theorem 1.3 should hold more generally by the hard
Lefschetz property of simplicial spheres. This subsection is mainly based on
Eran Nevo’s accounts commnunicated with us, and also on insightful discussions
with Vasiliki Petrotou and Geva Yashfe.

The same asymptotic upper bound in Theorem 6.2 holds for subcomplexes of a
simplicial $d$-sphere, where we count only $d$-dimensional faces: In [15],
Kalai already obtained such an upper bound theorem for subcomplexes of the
boundary complex of a polytope. One of the ingredients in the proof is the
hard Lefschetz property for polytopes which Stanely proved in [24]. By using
the same argument by Kalai with the recent breakthroughs of the hard Lefschetz
property of simplicial spheres [1, 21, 2], we obtain the desired upper bound
theorem for subcomplexes of a simplicial $d$-sphere. By using the same
argument in Section 6 with this upper bound theorem, we conclude the
following.

######  Theorem 6.7.

Let $\mathsf{K}$ be a simplicial $d$-sphere on $n$ vertices. Then, the facet
hypergraph $\mathcal{F}(\mathsf{K})$ has the chromatic number

$\chi(\mathcal{F}(\mathsf{K}))\in O(n^{\frac{\lceil d/2\rceil-1}{d}}).$

##  7 Final remarks

We close with some additional problems for future study.

An obvious open problem we can ask is to improve the lower and upper bounds
for the transversal ratio and the chromatic number of a simplicial sphere
regarding Questions 1 and 2. More precisely, for a transversal ratio we are
interested in the parameter (which we similarly defined at Question 3 for
stacked spheres, and was also introduced in [20] recently)

$\mu_{d}:=\limsup_{n\to\infty}\max\\{\tau(\mathsf{K})/n:\textrm{$\mathsf{K}$
is a simplicial $(d-1)$-sphere on $n$ vertices}\\}$

for every $d\geq 4$. In terms of $\mu_{d}$, results in this paper can be
summarized as follows.

  * •

$\mu_{3}=1/2$ by Proposition 3.1 and Theorem 1.1.

  * •

$\mu_{4}\geq 11/21$ by Theorem 1.2.

  * •

For $d\geq 5$, when $d$ is even $\mu_{d}\geq 1/2$ by Proposition 3.6 (which is
originally from [13]), and when $d$ is odd $\mu_{d}\geq 2/(d+1)$ by Theorem
1.1.

These lower bounds might not be tight for $d\geq 4$. More seriously, we do not
have any non-trivial upper bound for $\mu_{d}$. Unfortunately, Theorems 1.3
and 6.7 only give a trivial upper bound $\mu_{d}\leq 1$. While this trivial
upper bound might be tight, it seems that we are far from completely closing
the gaps between upper and lower bounds. To understand behaviour of $\mu_{d}$,
we need to understand more about incidences between facets and vertices of a
simplicial sphere, and how they differ from the incidence structure of a
general hypergraph.

######  Remark 7.1.

In [20], Novik and Zheng recently gave two constructions which shows
$\mu_{d}\geq 2/5$ for every odd $d\geq 5$. This, together with Proposition
3.6, gives a constant positive lower bound on $\mu_{d}$ for all dimensions
$d\geq 5$.

For colorings, recall that we found infinitely many simplicial 3-spheres which
are not 2-colorable. We ask if we can also find non 2-colorable simplicial
spheres for higher dimensions $d>3$.

######  Question 6.

For every dimension $d>3$, is there a non 2-colorable simplicial $d$-sphere?

For a fixed odd dimension $d>3$, it might be possible to construct a non
2-colorable simplicial $d$-sphere using the similar inductive computational
process. However, the process might not easily work for even dimensions,
because even dimensional cyclic polytopes have totally different behaviours on
transversals from odd dimensional ones. So, to find a non 2-colorable
simplicial $d$-sphere for even $d$, we might need a different approach to
obtain it.

On the other hand, it is natural to ask similar problems on 2-dimensional
surfaces beyond spheres. Albertson and Hutchinson showed [3] that given an
$n$-vertex triangulation $\mathsf{K}$ of an orientable surface of genus $g$,
which we denote by $S_{g}$, there exists a cycle in the graph $G(\mathsf{K})$
of length $\leq\sqrt{2n}$ which is non-separating and non-contractible. It
follows that there is a set $T$ of $\leq g\sqrt{2n}$ vertices whose removal
leaves a planar simplicial complex $\mathsf{K}^{\prime}$. Since
$\mathsf{K}^{\prime}$ in turn has a transversal of size at most
$|V(\mathsf{K}^{\prime})|/2$ by Proposition 3.1, we obtain the following.

######  Proposition 7.2.

Any $n$-vertex triangulation $\mathsf{K}$ of $S_{g}$ has $\tau(\mathsf{K})\leq
n/2+g\sqrt{2n}$.

Moreover, the connected sum of a minimal triangulation of $S_{g}$ and the
tight spherical example from Theorem 1.1 yields that the leading term $n/2$
above is asymptotically tight. However, we do not know if the second term
$g\sqrt{2n}$ can be reduced to a constant or not, when $g$ is fixed. So we ask
the following question.

######  Question 7.

What is the behaviour of the function

$\tau_{g}(n)=\max\\{\tau(\mathsf{K}):\textrm{$\mathsf{K}$ is an $n$-vertex
triangulation of $S_{g}$}\\}$

as $n\to\infty$ when $g$ is fixed?

## Acknowledgments

We would like to thank Andreas Holmsen for introducing Question 1. We are also
grateful to Minho Cho, Chris Eppolito, Jinha Kim, Minki Kim, Eran Nevo,
Isabella Novik, Vasiliki Petrotou, Geva Yashfe and Hailun Zheng for insightful
discussions. The authors thank the anonymous referees for their helpful
comments that improved the quality of the manuscript.

## References

  * [1] Karim Adiprasito.  Combinatorial Lefschetz theorems beyond positivity.  arXiv:1812.10454, 2018.
  * [2] Karim Adiprasito, Stavros Argyrios Papadakis, and Vasiliki Petrotou.  Anisotropy, biased pairings, and the Lefschetz property for pseudomanifolds and cycles.  arXiv:2101.07245, 2021.
  * [3] Michael O. Albertson and Joan P. Hutchinson.  On the independence ratio of a graph.  Journal of Graph Theory, 2(1):1–8, 1978.
  * [4] Noga Alon and Joel H. Spencer.  The probabilistic method.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.
  * [5] A. Altshuler, J. Bokowski, and L. Steinberg.  The classification of simplicial $3$-spheres with nine vertices into polytopes and nonpolytopes.  Discrete Math., 31(2):115–124, 1980.
  * [6] Amos Altshuler and Leon Steinberg.  Neighborly $4$-polytopes with $9$ vertices.  J. Combinatorial Theory Ser. A, 15:270–287, 1973.
  * [7] K. Appel and W. Haken.  Every planar map is four colorable.  Bull. Amer. Math. Soc., 82(5):711–712, 1976.
  * [8] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler.  Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, second edition, 1999.
  * [9] Minho Cho and Jinha Kim.  Transversal numbers of stacked spheres.  2023, arXiv:2305.08716.
  * [10] T. K. Dey and J. Pach.  Extremal problems for geometric hypergraphs.  Discrete Comput. Geom., 19(4):473–484, 1998.
  * [11] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, 2002.
  * [12] Carl Georg Heise, Konstantinos Panagiotou, Oleg Pikhurko, and Anusch Taraz.  Coloring $d$-embeddable $k$-uniform hypergraphs.  Discrete Comput. Geom., 52(4):663–679, 2014.
  * [13] Andreas F. Holmsen, János Pach, and Helge Tverberg.  Points surrounding the origin.  Combinatorica, 28(6):633–644, 2008.
  * [14] 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.
  * [15] Gil Kalai.  The diameter of graphs of convex polytopes and $f$-vector theory.  In Applied geometry and discrete mathematics, volume 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 387–411. Amer. Math. Soc., Providence, RI, 1991.
  * [16] André Kündgen and Radhika Ramamurthi.  Coloring face-hypergraphs of graphs on surfaces.  J. Combin. Theory Ser. B, 85(2):307–337, 2002.
  * [17] P. McMullen.  The maximum numbers of faces of a convex polytope.  Mathematika, 17:179–184, 1970.
  * [18] Hiroyuki Miyata and Arnau Padrol.  Enumerating neighborly polytopes and oriented matroids.  Exp. Math., 24(4):489–505, 2015.
  * [19] Isabella Novik and Hailun Zheng.  Many neighborly spheres.  Mathematische Annalen, 2022.  arXiv:2104.04476.
  * [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] Stavros Argyrios Papadakis and Vasiliki Petrotou.  The characteristic 2 anisotropicity of simplicial spheres.  arXiv:2012.09815, 2020.
  * [22] Jürgen Richter-Gebert.  Realization spaces of polytopes, volume 1643 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1996.
  * [23] Richard P. Stanley.  The upper bound conjecture and Cohen-Macaulay rings.  Studies in Appl. Math., 54(2):135–142, 1975.
  * [24] Richard P. Stanley.  The number of faces of a simplicial convex polytope.  Adv. in Math., 35(3):236–238, 1980.
  * [25] Ernst Steinitz.  Polyeder und raumeinteilungen.  Encyclophdie der mathematischen Wissenschaften, Band 3 (Geometrie):1–139, 1922.  Teil 3AB12.
  * [26] Hassler Whitney.  2-Isomorphic Graphs.  Amer. J. Math., 55(1-4):245–254, 1933.
  * [27] Günter M. Ziegler.  Lectures on polytopes, volume 152 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1995.

##  Appendix A Construction of the neighborly sphere $\mathsf{K}_{21}$

Here we list the computational results on Theorem 5.1. The neighborly sphere
$\mathsf{K}_{21}$ was constructed from the cyclic polytope $C_{4}(7)$ using
single element extensions. We denote the facets of $C_{4}(7)$ as follows.

$\displaystyle\mathcal{F}(C_{4}(7))=$
$\displaystyle\\{\\{0,1,2,3\\},\\{0,1,2,6\\},\\{0,1,3,4\\},\\{0,1,4,5\\},\\{0,1,5,6\\},\\{0,2,3,6\\},$
$\displaystyle\\{0,3,4,6\\},\\{0,4,5,6\\},\\{1,2,3,4\\},\\{1,2,4,5\\},\\{1,2,5,6\\},\\{2,3,4,5\\},$
$\displaystyle\\{2,3,5,6\\},\\{3,4,5,6\\}\\}$

Since the facet hypergraph $\mathcal{F}(\mathsf{K}_{21})$ is quite large, we
only list stacked balls which were used to construct $\mathsf{K}_{21}$ for
each step. Note that facets $\Delta_{1},\dots,\Delta_{m}$ in each stacked ball
are ordered as described at the beginning of Subsection 3.2 where a stacked
ball is defined.

$\displaystyle n=7:\;$
$\displaystyle\\{\\{0,1,4,5\\},\\{0,1,3,4\\},\\{0,3,4,6\\},\\{1,2,4,5\\}\\}$
$\displaystyle n=8:\;$
$\displaystyle\\{\\{2,3,5,6\\},\\{0,2,3,6\\},\\{1,2,5,6\\},\\{0,3,6,7\\},\\{0,4,6,7\\}\\}$
$\displaystyle n=9:\;$
$\displaystyle\\{\\{0,2,3,8\\},\\{0,2,6,8\\},\\{0,4,6,8\\},\\{1,2,6,8\\},\\{4,6,7,8\\},\\{2,3,5,8\\}\\}$
$\displaystyle n=10:\;$
$\displaystyle\\{\\{1,2,6,9\\},\\{1,6,8,9\\},\\{0,1,2,6\\},\\{6,7,8,9\\},\\{4,7,8,9\\},\\{0,1,2,3\\},$
$\displaystyle\\{1,5,6,8\\}\\}$ $\displaystyle n=11:\;$
$\displaystyle\\{\\{1,2,4,7\\},\\{1,3,4,7\\},\\{1,2,5,7\\},\\{0,1,5,7\\},\\{3,4,6,7\\},\\{4,6,7,9\\},$
$\displaystyle\\{4,7,9,10\\},\\{1,2,5,8\\}\\}$ $\displaystyle n=12:\;$
$\displaystyle\\{\\{1,3,4,11\\},\\{1,2,4,11\\},\\{3,4,6,11\\},\\{2,4,7,11\\},\\{2,5,7,11\\},\\{0,5,7,11\\},$
$\displaystyle\\{2,5,8,11\\},\\{2,5,8,9\\},\\{4,7,10,11\\}\\}$ $\displaystyle
n=13:\;$
$\displaystyle\\{\\{1,2,8,9\\},\\{1,2,9,10\\},\\{1,2,3,10\\},\\{1,2,3,4\\},\\{0,1,3,10\\},\\{2,8,9,12\\},$
$\displaystyle\\{2,6,9,10\\},\\{0,1,3,7\\},\\{2,8,11,12\\},\\{5,8,9,12\\}\\}$
$\displaystyle n=14:\;$
$\displaystyle\\{\\{3,4,5,6\\},\\{0,4,5,6\\},\\{0,4,5,7\\},\\{3,5,6,8\\},\\{3,5,8,9\\},\\{0,5,7,12\\},$
$\displaystyle\\{2,3,5,9\\},\\{0,1,5,6\\},\\{0,7,11,12\\},\\{5,8,9,13\\},\\{7,10,11,12\\}\\}$
$\displaystyle n=15:\;$
$\displaystyle\\{\\{2,11,12,13\\},\\{1,2,11,12\\},\\{1,2,4,12\\},\\{1,2,8,11\\},\\{2,4,7,12\\},$
$\displaystyle\\{1,3,11,12\\},\\{4,7,10,12\\},\\{2,4,5,7\\},\\{7,10,12,14\\},\\{2,9,12,13\\},$
$\displaystyle\\{2,6,9,13\\},\\{0,2,6,9\\}\\}$ $\displaystyle n=16:\;$
$\displaystyle\\{\\{0,5,11,12\\},\\{0,5,12,14\\},\\{5,8,11,12\\},\\{0,1,5,14\\},\\{8,11,12,13\\},$
$\displaystyle\\{2,8,11,13\\},\\{2,11,13,15\\},\\{5,7,12,14\\},\\{4,5,7,14\\},\\{2,6,13,15\\},$
$\displaystyle\\{2,6,10,13\\},\\{3,4,5,14\\},\\{6,9,13,15\\}\\}$
$\displaystyle n=17:\;$
$\displaystyle\\{\\{2,5,7,12\\},\\{2,7,12,15\\},\\{5,7,12,16\\},\\{2,9,12,15\\},\\{5,8,12,16\\},$
$\displaystyle\\{9,12,13,15\\},\\{7,12,14,15\\},\\{0,2,9,15\\},\\{0,2,6,15\\},\\{5,8,11,16\\},$
$\displaystyle\\{1,5,8,11\\},\\{0,2,3,9\\},\\{1,5,8,10\\},\\{4,5,7,16\\}\\}$

$\displaystyle n=18:\;$
$\displaystyle\\{\\{0,6,15,17\\},\\{2,6,15,17\\},\\{0,6,9,15\\},\\{2,7,15,17\\},\\{2,5,7,17\\},$
$\displaystyle\\{0,4,6,9\\},\\{2,5,12,17\\},\\{0,4,6,14\\},\\{5,8,12,17\\},\\{2,6,15,16\\},$
$\displaystyle\\{5,8,10,17\\},\\{5,8,12,13\\},\\{4,6,9,11\\},\\{0,1,6,14\\},\\{3,4,6,14\\}\\}$
$\displaystyle n=19:\;$
$\displaystyle\\{\\{6,9,10,13\\},\\{6,7,9,10\\},\\{6,10,13,16\\},\\{6,7,9,11\\},\\{2,6,10,16\\},$
$\displaystyle\\{1,9,10,13\\},\\{2,6,16,18\\},\\{1,8,9,13\\},\\{0,2,6,10\\},\\{3,6,7,11\\},$
$\displaystyle\\{3,6,11,12\\},\\{3,11,12,15\\},\\{8,9,13,14\\},\\{0,2,6,17\\},\\{5,8,13,14\\},$
$\displaystyle\\{4,6,11,12\\}\\}$ $\displaystyle n=20:$
$\displaystyle\\{\\{11,12,13,15\\},\\{11,12,15,19\\},\\{4,11,12,19\\},\\{3,12,15,19\\},\\{3,6,12,19\\},$
$\displaystyle\\{11,12,13,16\\},\\{8,12,13,16\\},\\{4,10,11,12\\},\\{8,12,16,17\\},\\{8,12,13,18\\},$
$\displaystyle\\{7,12,16,17\\},\\{0,11,12,16\\},\\{10,11,12,14\\},\\{0,5,11,16\\},\\{0,1,5,16\\},$
$\displaystyle\\{2,8,13,16\\},\\{4,9,10,11\\}\\}$

The resulting $\mathsf{K}_{21}$ is a neighborly sphere on 21 vertices. The
hypergraph $\mathcal{N}_{21}$ is obtained from $\mathcal{F}(\mathsf{K}_{21})$
by removing the hyperedge $\\{2,3,4,5\\}$. $\mathcal{N}_{21}$ has transversal
number 11 and so does $\mathcal{F}(\mathsf{K}_{21})$. One example of a minimum
transversal of $\mathcal{F}(\mathsf{K}_{21})$ is

$\\{0,1,2,3,4,5,9,10,16,17,20\\}.$