# Covering-based numbers related to the LS-category of finite spaces

M. Cárdenas, R. Flores, A. Quintero and M.T. Villar-Liñán

###### Abstract.

In this paper, Lusternik-Schinrelmann and geometric category of finite spaces
are considered. We define new numerical invariants of these spaces derived
from the geometric category and present an algorithmic approach for its
effective computation. The analysis is undertaken by combining homotopic
features of the spaces, algorithms and tools from the theory of graphs and
hypergraphs. We also provide a number of examples.

##  1\. Introduction

In [2], P. Alexandrov observed that finite spaces are the natural topological
setting for ordered structures on finite sets. More precisely, the class of
finite of posets can be identified with the class of finite $T_{0}$-spaces.

Though these spaces are not relevant from the metric viewpoint, they are far
from being irrelevant in Algebraic Topology: in fact, M. McCord proved in [25]
that any compact polyhedron is weakly homotopy equivalent to a finite
$T_{0}$-space. In particular, weak homotopy types of finite $T_{0}$-spaces
coincide with homotopy types of compact polyhedra.

After years of oblivion, finite spaces have been recently considered with
renewed interest: see [24] and [3] as comprehensive references and [10], [22]
and [28] for more specific aspects of the homotopy theory of such spaces. In
particular, the notion of Lusternik-Schnirelmann category (LS-category) in the
context of finite spaces was introduced in [15] in connection with the so-
called simplicial LS-category of a simplicial complex, and also in [31] in
connection with the approach to the simplicial complexity in [20] via finite
spaces. The present paper goes further in the study of numerical invariants
for the class of finite spaces on its own.

Recall that given a topological space $X$, the LS-category $cat(X)$ of $X$ is
defined as the minimal number of open sets that are contractible in $X$ and
cover $X$, while the geometric category $gcat(X)$ is the minimal number of
contractible open sets that cover $X$. The latter is not a homotopy invariant,
and this leads to the definition of the strong category $Cat(X)$ of $X$ as the
smallest value of the geometric category in the homotopy type of $X$. See
Section 2 for more details of these definitions, and Table 1 for a brief
summary of the different definitions of category that appear in the paper.

Besides $cat$ and $Cat$, we introduce other covering-based numbers
specifically for the class of finite $T_{0}$-spaces. Properties of these
numbers, as well as for $cat$ and $Cat$, are given, including the special
features of spaces whose Hasse diagrams have height 1. After this analysis, we
propose a systematic procedure which allows us to compute or bound some of
these numbers using algorithms based on the structure of the space. Attention
is paid, in particular, to the complexity of the calculations. It should be
pointed out that the lack of an analog to such a procedure in the case of
$cat(X)$ makes more difficult the development of an algorithmic approach for
this case. See the explanation at the beginning of Section 8.

Now we describe with detail the contents of the paper. The preliminary Section
2 contains the necessary definitions and results of the topology of finite
spaces and some observations about their LS category. In Section 3 we study
the behaviour of the function $gcat$ on the homotopy type of a finite space
$X$; in particular it is showed that the gap between $cat(X)$ and $gcat(X)$
can be arbitrarily large for finite spaces. Furthermore, the maximum of $gcat$
on the homotopy type of $X$ coincides with its value on the core of $X$. This
provides a specific LS-type invariant for finite spaces ($Cat_{u}$). Prime
open sets of a finite space are defined in Section 4 where it is proved that
the geometric category given by them yields a new numerical invariant of LS-
type in the class of finite spaces ( $gcat_{p}$). Section 5 is devoted to the
finite spaces of height 1, which reveal interesting features: their category
is related with the arboricity of the graph given by the Hasse diagram;
moreover, all numerical invariants considered in the paper agree on them, and
this number is in turn bounded above by the arboricity of a canonically
associated multigraph.

The remainder of the paper is devoted to develope a strategy to compute
$gcat(X)$ and the other related invariants $Cat_{u}$ and $gcat_{p}$ for any
finite space $X$. In Section 6 we describe a preliminary algorithm that
decides if a finite space $X$ is contractible or not, and also identifies the
core of $X$. It is checked that the time complexity of the algorithm is at
most quartic in the number of points of $X$. Using this algorithm, different
procedures (deterministic and heuristic) are designed in Section 7 in order to
describe the compatibility structure of $X$ with respect to $gcat(X)$. As a
byproduct, bounds for $gcat(X)$ can be obtained in polynomial time. In Section
8 we generalize the notion of compatibility structure in terms of Boolean
functions and define a category associated to such a structure (being natural
examples the categories studied in our paper). Moreover, we show that a
compatibility structure of a finite space $X$ always gives rise to a
hypergraph, in such a way that the associated category corresponds to the
covering number of the hypergraph. We conclude by discussing the problem of
representing a compatibility structure in a finite space as the compatibility
structure of a finite space of height 1.

Notation. We warn the reader that we adopt here the classical definition of
LS-category (and its variations); that is, the precise number of open sets
involved in the definition instead of the normalized definition which is given
by this number minus one. Moreover, the finite spaces that will appear in the
text will always be $T_{0}$, although sometimes this separation condition will
not be explicitly quoted.

Data availability statement. Data sharing not applicable to this article as no
datasets were generated or analysed during the current study.

##  2\. Preliminaries

Finite spaces are examples of _Alexandrov spaces_ ; that is, topological
spaces whose points admit a minimal open neighbourhood or, equivalently, whose
topologies are closed under arbitrary intersections. If $X$ is an Alexandrov
space, the minimal open set containing $x\in X$ is denoted $U_{x}$. Then an
ordering can defined on $X$ by setting $x\leq y$ if $U_{x}\subseteq U_{y}$.
Alexandrov showed in [2] that this ordering yields an equivalence between the
class of Alexandrov $T_{0}$-spaces and the class of posets. Moreover, the
homotopy class of an arbitrary Alexandrov space can be represented by an
Alexandrov $T_{0}$-space.

A finite poset $X=(X,\leq)$ is usually represented by its _Hasse diagram_ ,
which turns to be the transitive reduction of $X$. Recall that the _transitive
reduction_ of a poset $X$ is the acyclic directed graph whose vertex set is
$X$ and a directed edge is drawn from $x$ to $y$ when $x<y$ and there is no
$z$ with $x<z<y$ (see [3] or [24]). In this way, $X$ is then recovered as the
transitive closure of the reflexive antisymmetric non-transitive relation
defined by the edges of its Hasse diagram, termed the _covering relation_ of
the poset $X$. Notice that such a diagram, and more generally any acyclic
directed graph, admits a decomposition by levels. Namely, minimals of $X$ are
placed at level zero and the level assigned to a non-source element $a$ is the
number of edges of a maximal directed path from a source to $a$. The _height
of $X$_ is the maximal height of its elements.

Henceforth we will identify a finite $T_{0}$-space $X$ with the Hasse diagram
of the corresponding poset without further comment. So, by the height of $X$
we will mean the height of its Hasse diagram.

It is worth pointing out that after removing a point $x\in X$ from a finite
space $X$, the resulting Hasse diagram of $X-\\{x\\}$ is not in general a
subgraph of the original one. In fact all edges incident at $x$ in the latter
disappear in the former; and moreover, any pair of edges in the Hasse diagram
of $X$ corresponding to $y<x<z$ (if any) is replaced by a directed edge $y<z$
in the Hasse diagram of $X-\\{x\\}$.

The Hasse diagram of a poset is the $1$-skeleton of the so-called _order
complex_ of $X$, denoted $\mathcal{O}(X)$. This is the simplicial complex with
the elements of $X$ as vertices and the totally ordered subsets of $X$ as
simplices. Conversely, any simplicial complex $K$ has associated its face
poset $F(K)$ consisting of the set of simplices of $K$ ordered by the face
relation. McCord theorem in [25] shows that there exist weak homotopy
equivalences $\psi_{X}:X\to|\mathcal{O}(X)|$ and $\varphi_{K}:|K|\to F(K)$
where $|K|$ denotes the underlying polyhedron of the complex $K$. The
existence of such weak equivalences show that homotopy types of polyhedra
correspond to weak homotopy types of finite $T_{0}$-spaces.

The natural order on a finite $T_{0}$-space $Y$ induces an order on the sets
of maps $f:X\to Y$ by setting $f\leq g$ if $f(x)\leq g(x)$ for all $x\in X$.
In fact, this order characterizes the homotopies between maps, as proved in
[3, Corollary 1.2.6]. Namely, two maps $f,g:X\to Y$ are homotopic if and only
if there exists a sequence of maps $f_{i}:X\to Y$ ($0\leq i\leq m$) such that
$f_{0}=f$, $f_{m}=g$ and $f_{i}$ and $f_{i+1}$ are related; that is,
$f_{i}\leq f_{i+1}$ or $f_{i}\geq f_{i+1}$. Moreover, by ([3, Lemma 2.1.1]),
we can assume in addition that there exist points $x_{0},\dots,x_{m}\in X$
such that $f_{i-1}=f_{i}$ on $X-\\{x_{i-1}\\}$ and
$f_{i-1}(x_{i-1})<f_{i}(x_{i-1})$ or $f_{i-1}(x_{i-1})>f_{i}(x_{i-1})$ for
$1\leq i\leq m-1$.

Recall that (co)homology and other algebraic constructions are weak homotopy
invariants. In particular, the (co)homology of any compact polyhedron can be
realized as the (co)homology of a finite $T_{0}$-space. However, the LS-
category $cat(X)$ of a space $X$ is a homotopy invariant but not a weak
homotopy invariant. Recall that the number $cat(X)$ is defined as the smallest
integer $n$ for which there exists an open covering $\\{U_{i}\\}_{i=1}^{n}$ of
$X$ such that for each $i$ the inclusion $U_{i}\subseteq X$ is homotopically
trivial. If such a number does not exist, it is written $cat(X)=\infty$.

Since the LS-category is not a weak homotopy invariant it should not be
expected that McCord’s theorem yields the equality between $cat(X)$ and
$cat(|\mathcal{O}(X)|)$. Indeed, by iterating the face order operator $F(-)$
and the order complex operator $\mathcal{O}(-)$ we get new finite spaces
$sd^{n}X=(F\mathcal{O})^{n}(X)$, termed the _iterated subdivisions_ of $X$
($n\geq 0$, $sd^{0}X=X$), such that their corresponding order complexes
$\mathcal{O}(sd^{n}X)$ coincides with the barycentric subdivision
$sd^{n}\mathcal{O}(X)$. Then, as it was observed in [15] the following
sequence of inequalities holds:

(2.1) $cat(X)\geq scat(\mathcal{O}(X))\geq cat(sdX)\geq
scat(sd\mathcal{O}(X))\geq cat(sd^{2}X)\geq\dots\geq cat(|\mathcal{O}(X)|).$

Here $scat(K)$ stands for the _simplicial category_ of a simplicial complex
$K$; that is, the smallest integer $n$ for which there exists a covering
$\\{K_{i}\\}_{i=1}^{n}$ of $K$ by subcomplexes such that for each $i$ the
inclusion $K_{i}\subseteq K$ is in the contiguity class of a constant map. All
these notions in the simplicial setting can be found in [1] and [15]).

It is worth pointing out that given a finite $T_{0}$-space $X$, we can derive
from the sequence of inequalities in (2.1) two new invariants of $X$. Namely,

######  Definition 2.1.

The _weak LS-category_ of $X$ is the LS-category of the underlying polyhedron
of its order complex; that is, the number $cat_{w}(X)=cat(|\mathcal{O}(X)|)$.
Similarly we can define the _stable LS-category_ of $X$ as the number
$cat_{s}(X)=\min\\{cat(sd^{k}X);k\geq 0\\}$.

######  Proposition 2.2.

The weak LS-category is a weak homotopy invariant, while the stable LS-
category is a homotopy invariant.

###### Proof.

If $f:X\to Y$ is a weak homotopy, then the induce simplicial map
$\mathcal{O}(f):|\mathcal{O}(X)|\to|\mathcal{O}(Y)|$ is a homotopy equivalence
(see [3, Corollary 1.4.18]) and so $cat_{w}(X)=cat_{w}(Y)$. Besides, if $f$ is
a homotopy equivalence then $\mathcal{O}(f)$ is a strong equivalence and then
$sd(f)=\mathcal{O}F(f):sdX=\mathcal{O}F(X)\to\mathcal{O}F(Y)=sdY$ is again a
homotopy equivalence by [3, Theorem 5.2.1]. Therefore, by iterating the
argument, we get $cat(sd^{k}X)=cat(sd^{k}Y)$ for all $k\geq 0$ and so
$cat_{s}(X)=cat_{s}(Y)$. ∎

######  Remark 2.3.

Obviously one has the inequalities $cat_{w}(X)\leq cat_{s}(X)\leq cat(X)$.
Moreover, the gap between $cat(X)$ and $cat_{w}(X)$ can be arbitrarily large.
Indeed, for each $n\geq 2$, let $X$ be the finite space of height 1 whose
Hasse diagram is the bipartite graph $K(n,2)$ as shown in the left of Figure
1. It is readily checked that $cat(X)=n$ since any open set with two or more
maximal points is not contractible in $X$, while it is well known that
$cat_{w}(X)=cat(|\mathcal{O}(X)|)=2$.

In fact the same example shows that the gap between $cat(X)$ and
$scat(\mathcal{O}(X))$ (and so $cat_{s}(X)$) can also be arbitrarily large
since $scat(\mathcal{O}(X))=2$ according to [15].

Notice also that the space $X$ in [3, Example 4.2.1] (see the at the right in
Figure 1) is not contractible but $|\mathcal{O}(X)|$ is. Hence $sd^{k}X$ is
not contractible for all $k\geq 0$ by [3, Corollary 5.2.7], whence
$cat_{s}(X)\geq 2>cat_{w}(X)=1$. Furthermore, one easily checks that
$cat(X)=2$ and so $cat(X)=cat_{s}(X)=2>1=cat_{w}(X)$.

Figure 1.

Open Question: Find a finite $T_{0}$-space $X$ with
$cat(X)>cat_{s}(X)>cat_{w}(X)$.

If we consider the LS category of maps, Tanaka shows in [32] the equality
$cat_{w}(X)=cat_{s}(id)$, where, for a map between finite spaces $f:X\to Y$,
$cat_{s}(f)=\min\\{cat(f\circ\tau^{k});k\geq 0\\}$ with $\tau^{k}$ the
iterated subdivision map $\tau^{k}:sd^{k}X\to sd^{k-1}X\to\dots\to sdX\to X$.

##  3\. The geometric category and the strong category of finite spaces

If we use open sets which are contractible in themselves, we get the
_geometric category_ $gcat(X)$ of $X$, which is the minimal $n\geq 1$ such
that there is a covering of $X$ with $n$ contractible open sets. It turns out
that, in general, the geometric category is not a homotopy invariant. However,
it is defined a new homotopy invariant, termed the _strong category_ of $X$
and denoted $Cat(X)$, by considering the minimal value of $gcat(Y)$ for all
spaces $Y$ with the homotopy type of $X$. We refer to [11] for a comprehensive
treatment of these (and others) numerical invariants in Homotopy Theory.

A distinctive property of finite spaces is the fact that the homotopy type of
any finite $T_{0}$-space is represented up to homeomorphism by a minimal
space. i.e. a space without beat points. Recall that a point $x\in X$ is
termed an _up beat point_ if the set of points which are greater than $x$ has
a minimum. Similarly, $x$ is said to be a _down beat point_ if the set of
points below it has a maximum. If we do not distinguish if $x$ is an up or a
down beat point, we simply say that $x$ is a beat point. It is immediate that
if $x\in X$ is a beat point, there exists $y\in X$, $y\neq x$, such that any
point which is comparable with $x$ is also comparable with $y$. In [30], R.
Stong showed that for any beat point $x\in X$, the inclusion
$X-\\{x\\}\subseteq X$ is a strong deformation retract and that after removing
the beat points, one at a time, we obtain a strong deformation retract of X
with no beat points, called the _core_ of $X$, which is unique up to
homeomorphism. A $T_{0}$-space is called _minimal_ if it has no beat point,
and the homotopy type of a finite $T_{0}$-space contains a unique minimal
space up to homeomorphism (see [3]).

As the LS-category is a homotopy invariant, it will suffice to compute it for
minimal spaces. In contrast, as observed in [15], the removal of beat points
may increase the geometric category. In fact, the following proposition shows
that this may occur only for up beat points.

######  Proposition 3.1.

Let $b$ be a down beat point in a finite $T_{0}$-space $X$. Then
$gcat(X)=gcat(Y)$ for $Y=X-\\{b\\}$.

###### Proof.

We may assume that $X-Y$ reduces to a down beat point $b$.

Let $\mathcal{V}=\\{V_{1},\dots,V_{n}\\}$ be an open covering of $Y$
consisting of contractible sets. Since $b$ is a down beat point, let $c$ be
the maximum of the points below $b$ in $X$. Let $m\in Max(X)$ with $b\leq m$.
If $b=m$, then choose $V_{i}$ with $c\in V_{i}$. The open set
$V^{\prime}_{i}=V_{i}\cup\\{b\\}$ is contractible in $X$ ($b$ is a down beat
point in $V^{\prime}_{i}$) and $\\{V_{1},\dots,V^{\prime}_{i},\dots V_{n}\\}$
covers $X$. Otherwise, if $b<m$, take $V_{i}$ with $m\in V_{i}$ and so
$U^{Y}_{m}\subseteq V_{i}$, where $U^{Y}_{m}$ is the minimal open set of $m$
in $Y$. Then $U^{X}_{m}=U^{Y}_{m}\cup\\{b\\}$ and
$V^{\prime}_{i}=V_{i}\cup\\{b\\}$ is an open set in $X$. Moreover, $b$ remains
a down beat point in $V^{\prime}_{i}$, and so by replacing $V_{i}$ by
$V^{\prime}_{i}$ in $\mathcal{V}$ we get an open covering of $X$ consisting of
contractible sets. This shows that $gcat(X)\leq gcat(Y)$.

On the other hand, it is easy to see that given any covering
$\mathcal{W}=\\{W_{1},\dots,W_{n}\\}$ of $X$ by contractible open sets one can
obtain a covering of $Y$ by contractible open sets of the same cardinality.
Indeed, if $b\in W_{i}$ then $b$ is also a down beat point of $W_{i}$ and
hence $W_{i}^{\prime}=W_{i}-\\{b\\}$ is an open contractible open set in $Y$.
Hence $gcat(X)=gcat(Y)$. ∎

In contrast, as mentioned above, removing up beat points may increase $gcat$.
See Example 3.2(2) below.

######  Example 3.2.

  1. (1)

The following example shows a finite $T_{0}$-space such that $gcat(X)=3$ but
$cat(X)=2$ since the union $U_{a}\cup U_{c}$, although it is not contractible
in itself, it is contractible in $X$.

Figure 2.

  2. (2)

The gap between $gcat$ and $cat$ can be arbitrarily large. Indeed, given any
integer $s\geq 1$, for the space $X(s)$ depicted in Figure 3, whose core is
showed in Figure 3, one checks $cat(X(s))=gcat(X(s))=2$ since the contractible
open sets $U_{b}$ and $U_{e}\cup U_{j_{0}}\cup\cdots\cup U_{j_{s}}$ cover
$X(s)$. However by deleting the up beat point $e$ from $X(s)$, for
$Y(s)=X(s)-\\{e\\}$ in Figure 3 it is verified that $cat(Y(s))=cat(X(s)=2$
while $gcat(Y(s))=s+2$ since the open sets $U_{j_{t}}$ are disjoint from each
other and $U_{b}\cup U_{j_{t}}$ are not contractible, for $t=0,\dots,s$.
Notice that $gcat(Y(s))=gcat(Z(s))$ since the removing any of the up beat
points $c_{0},\dots,c_{s}$ and $l_{0},\dots,l_{s}$ does not change $gcat$.

Figure 3.

Recall that, by definition, $Cat(X)$ is the minimum of the function $gcat$ on
the homotopy type of $X$. Moreover, as observed above the removal of beat
points never diminishes the geometric category, and so the maximum of $gcat$
on the homotopy type of $X$ is precisely $gcat(X_{0})$ where $X_{0}\subseteq
X$ is the core of $X$. Moreover, as $X_{0}$ is unique up to homeomorphism
within the homotopy class of $X$, we have a new numerical homotopy invariant
for finite $T_{0}$-spaces. Namely,

######  Definition 3.3.

Given a finite $T_{0}$-space $X$, we define the _upper strong category_ of
$X$, $Cat_{u}(X)$, to be geometric category of its core $X_{0}\subseteq X$.

######  Example 3.4.

Notice that the gap between $Cat(X)$ and $Cat_{u}(X)$ can also be arbitrarily
large as the following example shows.

This minimal space of height $1$ satisfies $Cat_{u}(X)=gcat(X)=n+1$. However
one can show that $Cat(X)=cat(X)=2$ by using the space
$Y=X\cup\\{p^{\prime}_{k}\\}_{k=1}^{n-1}$, with the ordering generated by the
one of $X$ and $q_{2k},q_{2k+1}\leq p^{\prime}_{k}\leq p_{0}$ for $1\leq k\leq
n-1$.

######  Remark 3.5.

In a similar fashion to Remark 2.3, by using [15][Prop.6.2 and Prop6.5] and
[4][Th.5.2.1], and letting $Cat_{s}(X)=min\\{Cat(sd^{k}(X)):k\geq 0\\}$ and
$gcat_{s}(X)=min\\{gcat(sd^{k}(X)):k\geq 0\\}$, we obtain the following
diagram of inequalities with similar considerations.

(3.2) $cat(X)$ | $\geq$ | $cat_{s}(X)$ | $\geq$ | $cat_{w}(X)$
---|---|---|---|---
$\leq$ |  |  $\leq$ |  |  $\leq$
$Cat(X)$ | $\geq$ | $Cat_{s}(X)$ | $\geq$ | $Cat(|\mathcal{O}(X)|)$
$\leq$ |  |  $\leq$ |  |  $=$
$gcat(X)$ | $\geq$ | $gcat_{s}(X)$ | $\geq$ | $Cat(|\mathcal{O}(X)|)$

Open Question: Find a finite $T_{0}$-space $X$ holding strict inequalities in
some (or any) of the lines and/or columns of the diagram above.

######  Remark 3.6.

A strong LS type parameter specially devised for finite spaces and its
combinatorial counterpart in the class of cell complexes are defined in [31].

##  4\. Numerical invariants and the maximal set of a finite space

Another distinctive property of a finite space $X$ is the existence of its set
of maximal points, $Max(X)$. Notice that for any beat point $x\in X$, one gets
$Max(X-\\{x\\})\leq Max(X)$ and so $Max(X_{0})\leq Max(X)$ for the core of
$X$, $X_{0}$. Moreover, as $X_{0}$ is determined up to homeomorphism by the
homotopy type of $X$, the cardinal number $|Max(X_{0})|$ is a numerical
homotopy invariant of $X$. Furthermore, as minimal open sets in a finite
$T_{0}$-space $X$ are contractible in themselves, we get

$cat(X)\leq Cat(X)\leq Cat_{u}(X)=gcat(X_{0})\leq|Max(X_{0})|\leq|Max(X)|.$

The maximal set of a finite space yields a special type of open sets. Namely,
we define a _prime open set_ in $X$ as an open set $U_{J}=\cup_{x\in J}U_{x}$,
where $J\subseteq Max(X)$. Then the following lemma holds.

######  Lemma 4.1.

Any open cover $\mathcal{U}$ of $X$ admits a refinement $\mathcal{V}$
consisting of prime open sets with $|\mathcal{V}|\leq|\mathcal{U}|$.

###### Proof.

For each $U$ let $V_{U}$ be the (possibly empty) open set
$V_{U}=\cup\\{U_{x};x\in Max(X)\cap U\\}$. As any $x\in Max(X)$ belongs to
some $U\in\mathcal{U}$, the family $\mathcal{V}$ of non-empty sets in
$\\{V_{U};U\in\mathcal{U}\\}$ is the required refinement. ∎

This immediately implies:

######  Lemma 4.2.

For any finite $T_{0}$-space $X$, $cat(X)$ is the least cardinal number of
those coverings of $X$ consisting of prime open sets contractible in $X$.

Lemma 4.2 does not hold for the geometric category since subsets of
contractible sets need not be contractible. For instance, for the space $X$ in
Example 3.2(1), the minimal open set $U_{a}$ contains the non-contractible
open set $U_{a}-\\{a\\}$.

As observed in Example 3.2(2) above, the geometric category of a space can be
altered by introducing up beat points and considering non-prime open sets. It
is then natural to state a specialized version of the geometric category by
restricting to those coverings consisting of prime open sets. More precisely,

######  Definition 4.3.

The _prime geometric category_ of a finite $T_{0}$-space $X$ is the least
cardinal number, $gcat_{p}(X)$, of coverings of $X$ by prime open sets which
are contractible in themselves.

######  Example 4.4.

For each $t\geq 1$ we now construct a space $X(t)$ with $gcat(X(t))\neq
gcat_{p}(X(t))$. In fact it shows that the gap between $gcat$ and $gcat_{p}$
can be arbitrarily large.

It is clear that $X(t)$ is a minimal space; moreover, the open set $U_{a}\cup
U_{c}\cup U_{d_{1}}\cup\dots\cup U_{d_{t}}$ retracts onto $U_{c}$ and so
$gcat(X(t))=Cat_{u}(X(t))=2$. However, $gcat_{p}(X(t))=t+1$ since the union
$U_{a}\cup U_{b}$ is the only prime open set which is contractible in itself
and is not minimal.

In contrast to ordinary geometric category the prime version is a homotopy
invariant. More precisely,

######  Proposition 4.5.

Let $X$ and $Y$ be finite $T_{0}$-spaces. Then the equality
$gcat_{p}(X)=gcat_{p}(Y)$ holds whenever $X$ and $Y$ are homotopy equivalent.

###### Proof.

We can assume that $Y$ is the core of $X$ and so homeomorphic to the core of
any finite space with the homotopy type of $X$. By an inductive argument, we
can assume that $X-Y$ reduces to a beat point $b$. Moreover, by Proposition
3.1 we can assume that $b$ is an up beat point (whence, $b\notin Max(X)$). Let
$d$ be the minimum of the points greater than $b$ and
$\mathcal{V}=\\{V_{1},\dots,V_{n}\\}$ be a covering of $Y$ consisting of
contractible prime open sets. Take $V_{i}$ with $d\in V_{i}$; then the minimal
open set $U_{d}$ of $d$ in $Y$ is contained in $V_{i}$. It is immediate that
$U^{\prime}_{d}=U_{d}\cup\\{b\\}$ is the minimal open set of $d$ in $X$ and
$b$ is an up beat point in $V^{\prime}_{i}=V_{i}\cup\\{b\\}$. Thus,
$\mathcal{V}^{\prime}=(\mathcal{V}-\\{V_{i}\\})\cup\\{V^{\prime}_{i}\\}$ is a
covering of $X$ by contractible prime open sets, and therefore
$gcat_{p}(X)\leq gcat_{p}(Y)$.

Conversely, given a covering of $X$ consisting of contractible prime open sets
$\mathcal{W}=\\{W_{1},\dots,W_{m}\\}$, let $d$ denote again the minimum of the
points above $b$ in $X$. Then $b$ is an up beat point in any $W_{i}$ with
$d\in W_{i}$, and $W^{\prime}_{i}=W_{i}-\\{b\\}$ is a contractible prime open
set in $Y$ since $b$ is not in $Max(X)$. Thus,
$\mathcal{W}^{\prime}=\\{W^{\prime}_{j};d\in W_{j}\\}\cup\\{W_{j};d\notin
W_{j}\\}$ is a covering of $Y$ consisting of contractible prime open sets of
$Y$. We have proved $gcat_{p}(Y)\leq gcat_{p}(X)$, and hence
$gcat_{p}(X)=gcat_{p}(Y)$. ∎

######  Remark 4.6.

Given a finite $T_{0}$-space $X$, if infinite Alexandrov spaces are allowed to
represent the homotopy type of $X$ we do not know whether Proposition 4.5
holds.

As a consequence of Proposition 4.5, the prime geometric category of a finite
$T_{0}$-space $X$ is a new numerical homotopy invariant which bounds
$Cat_{u}(X)$ from above, since the equality $gcat_{p}(X)=gcat_{p}(X_{0})$
holds for the core $X_{0}$ of $X$. Then we have:

$Cat_{u}(X)=gcat(X_{0})\leq gcat_{p}(X_{0})=gcat_{p}(X).$

Notice that the prime LS-category of $X$ coincides with the usual LS-category
by Lemma 4.2 and the following inequalities relate the numerical invariants
defined above.

(4.3) $cat(X)\leq Cat(X)\leq Cat_{u}(X)\leq
gcat_{p}(X)\leq|Max(X_{0})|\leq|Max(X)|.$

######  Example 4.7.

For each $n\geq 2$, let $X_{n}$ be the finite space of height 1 in Example
2.3. It is readily checked that $cat(X_{n})=gcat_{p}(X_{n})=|Max(X_{n})|=n$ .
Incidentally, $X_{n}$ is the smallest finite space with LS-category $n$. More
generally, the smallest finite space of height $k$ with LS-category $n$ is the
finite space whose Hasse diagram has two elements at each level $\leq k-1$ and
$n$ maximal elements; see Figure 4

Figure 4.

The problem of measuring the gaps in the sequence of inequalities in (4.3)
arises naturally. We have already observed in Examples 3.4 and 4.4 that the
intervals $[Cat(X),Cat_{u}(X)]$ and $[Cat_{u}(X),gcat_{p}(X)]$ can be
arbitrarily large. It is obvious that for a height $1$ space $X$ whose Hasse
diagram is a cycle and $|Max(X)|=k+2$ the interval $[gcat_{p}(X),|Max(X)|]$
has length $k$.

Open Question: Estimate the interval $[cat(X),Cat(X)]$ for finite
$T_{0}$-spaces.

Recall that a well-known result due to Fox [11] states that $Cat(X)\leq
cat(X)+1$ for a CW-complex $X$. In the next section we will show that $cat$
and $Cat$ coincide in the class of height 1 spaces.

Notation | Definition
---|---
$cat$ | Minimal number of contractible open sets in $X$ that cover $X$
$gcat$ | Minimal number of contractible open sets that cover $X$
$Cat$ | Minimal value of $gcat$ in the homotopy type of $X$
$cat_{w}$ | Value of $cat$ of the underlying polyhedron to the order complex of $X$
$cat_{s}$ | Minimal value of $cat$ on the successive barycentric subdivisions of $X$
$Cat_{u}$ | Value of $gcat$ on the core of $X$
$gcat_{p}$ | Minimal number of contractible prime open sets that cover $X$
Table 1. Different versions of the category

##  5\. Spaces of height 1

Spaces of height 0 are exactly finite discrete spaces and so their LS-category
is trivially the number of points of the spaces. Also any positive integer can
be realized as any of the LS-type numbers defined above of a finite space of
height 1; see Example 4.7.

We will next show that the strong category equals the LS-category in the class
of height 1 spaces. Namely,

######  Theorem 5.1.

Let $X$ be a finite $T_{0}$-space of heigth $1$. Then $Cat(X)=cat(X)$.
Moreover, the equaility is achived by a height $2$ space homotopy equivalent
to $X$.

######  Remark 5.2.

Actually, the result is valid for any finite $T_{0}$-space whose core has
height $1$.

The proof of Theorem 5.1 is a consequence of the two following lemmas.

######  Lemma 5.3.

Let $X$ be a connected finite space of height 1. Given $J\subseteq Max(X)$,
the prime open set $U_{J}$ is contractible in $X$ if and only if each
component of $U_{J}$ is contractible in itself.

###### Proof.

Obviously $U_{J}$ is contractible in $X$ if all its components are
contractible in themselves. Conversely, let $C\subseteq U_{J}$ be a component.
Then $C=U_{J^{\prime}}$ is also a prime open set for some $J^{\prime}\subseteq
J$ and contractible in $X$.

Let $C_{0}\subseteq C$ be the core of $C$. Next, we show that $C_{0}$ reduces
to a point and so $C$ is contractible.

As $C_{0}$ remains contractible in $X$, there exists a sequence
$f_{0},f_{1},\cdots,f_{n}:C_{0}\to X$, of comparable maps with $f_{0}$, the
inclusion $C_{0}\subseteq X$, and a constant map $f_{n}$. Moreover, we can
assume that there exist points $x_{0},\dots,x_{n}\in C_{0}$ such that
$f_{i-1}=f_{i}$ on $C_{0}-\\{x_{i-1}\\}$ and $f_{i-1}(x_{i-1})<f_{i}(x_{i-1})$
or $f_{i-1}(x_{i-1})>f_{i}(x_{i-1})$ ($1\leq i\leq n-1$).

If $C_{0}$ were not just a point, we arrive to a contradiction.

First assume that $x_{0}$ is at level $0$. Then
$x_{0}=f_{0}(x_{0})<f_{1}(x_{0})=m\in Max(X)$. Moreover, by connectedness
$\\{y\in C_{0};y>x_{0}\\}\neq\emptyset$, and there exists $m^{\prime}\in
Max(C_{0})\subseteq Max(X)$ such that $x_{0}\leq m^{\prime}$ and $m\neq
m^{\prime}$, since otherwise $x_{0}$ would be an up beat point in $C_{0}$.
Then by continuity we reach the contradiction $m=f_{1}(x_{0})\leq
f_{1}(m^{\prime})=f_{0}(m^{\prime})=m^{\prime}$.

Assume now that $x_{0}$ lies at level $1$. Then $f_{1}(x_{0})\in Min(X)$ and
$y=f_{1}(x_{0})<f_{0}(x_{0})=x_{0}$. Again by connectedness $Min(C_{0})\cap
U_{x_{0}}\neq\emptyset$, and there exists $y^{\prime}\in Min(C_{0})\subseteq
Min(X)$ with $y^{\prime}<x_{0}$. Moreover $y^{\prime}\neq y$, since otherwise
$x_{0}$ would be a down beat point in $C_{0}$. By continuity,
$y=f_{1}(x_{0})\geq f_{1}(y^{\prime})=f_{0}(y^{\prime})=y^{\prime}$, which is
contradiction. ∎

######  Lemma 5.4.

Let $\\{U_{1},\dots,U_{n}\\}$ be an open covering of a finite connected
$T_{0}$-space $X$ such that $U_{1}$ decomposes in $s$ connected components
which are contractible in themselves. Then there exists a finite $T_{0}$-space
$Y$ and an open covering $\\{U^{\prime}_{1},U^{\prime}_{2},\dots
U^{\prime}_{n}\\}$ of $Y$ such that $X$ and $U_{i}$ are deformation retracts
of $Y$ and $U^{\prime}_{i}$, respectively, for $2\leq i\leq n$, and
$U^{\prime}_{1}$ consists of $s-1$ connected components contractible in
themselves. Moreover, $height(Y)=max\\{2,height(X)\\}$.

###### Proof.

Firstly we observe that all minimal open sets in a finite $T_{0}$-space meets
$Min(X)$ and moreover, given any two minimal elements $p,q\in Min(X)$ there
exists a path in $X$

(5.4) $p=x_{0}\leq x_{1}\geq x_{2}\leq\dots\leq x_{2m-1}\geq x_{2m}=q$

with $x_{2k}\in Min(X)$ and $x_{2k-1}\in Max(X)$ for all $k\leq m$. Indeed,
given any path $L$ between $p$ and $q$: $L\equiv
p=y_{0}<y_{1}>y_{2}\dots<y_{2m+1}>y_{2m}=q$, choose $x_{2k}\in Min(X)\cap
U_{y_{2k}}$ ($0\leq k\leq m$). Notice that $x_{0}=y_{0}=p$, $x_{2m}=y_{2m}=q$
and the desired path in obtained by replacing the $y_{2k}$’s by $x_{2k}$’s in
$L$ since $y_{2k+1}$ remains greater than both $x_{2k}$ and $x_{2k+2}$ for all
$0\leq k\leq m$. Finally we replace each $y_{2k-1}$ by some
$x_{2k-1}\in\overline{\\{y_{2k-1}\\}}\cap Max(X)$, $1\leq k\leq m$.

Assume that $\\{C_{j}\\}_{l=1}^{s}$ is the family of connected components of
$U_{1}$. Let $\Gamma$ be a path as in (5.4) joining some $p\in Min(X)\cap
C_{1}$ to some $q\in Min(X)\cap C_{l}$ for some $2\leq l\leq s$. We can assume
that $\Gamma$ is an arc (that is, $x_{i}\neq x_{j}$ if $i\neq j$) by removing
all cycles in $\Gamma$.

We can also assume without loss of generality that $\Gamma\cap U_{1}$ reduces
to $\\{p,q\\}$ since otherwise we can consider the subarc
$\Gamma^{\prime}\subseteq\Gamma$ running from the last element of $\Gamma$ in
$Min(X)\cap C_{1}$ to the first element of $\Gamma$ in
$Min(X)\cap(U_{1}-C_{1})$. In particular, $x_{2k-1}\notin U_{1}$ for all
$1\leq k\leq m$.

For each $0\leq k\leq m-1$, we will write $j=j(k)$ if $x_{2k+1}\in U_{j}$,
with $j=2,\dots,n$, and take some point $q_{k}\notin X$. Consider the space
$Y=X\cup\\{q_{k}\\}_{k=1}^{m}$ with the ordering generated by the one on $X$
and $x_{2k},x_{2k+2}<q_{k}<x_{2k+1}$ ($0\leq k\leq m-1$). Notice that the
minimal open sets of $q_{k}$ and $x_{2k+1}$ in $Y$ are
$U^{Y}_{q_{k}}=\\{q_{k},x_{2k},x_{2k+2}\\}$ and
$U^{Y}_{x_{2k+1}}=U_{x_{2k+1}}\cup\\{q_{k}\\}$. This determines a new arc
$\widehat{\Gamma}\equiv p=y_{0}<q_{1}>y_{2}\dots<q_{2m+1}>y_{2m}=q$ between
$p$ and $q$. Notice that $\widehat{\Gamma}$ is open in $Y$ and, clearly,
contractible.

Let $U^{\prime}_{1}=U_{1}\cup\widehat{\Gamma}$ and
$U^{\prime}_{j}=U_{j}\cup\\{q_{k};j=j(k)\\}$ ($2\leq j\leq n$). These sets are
open sets in $Y$ and all the points $q_{k}$ are up beat points in $Y$ and
those $q_{k}$ with $j=j(k)$ are, in addition, up beat points in
$U^{\prime}_{j}$. Hence $Y$ and $U^{\prime}_{j}$ retract onto $X$ and $U_{j}$,
respectively. Moreover, the family of connected components of $U^{\prime}_{1}$
consists of the union $C_{1}\cup\widehat{\Gamma}\cup C_{l}$ and the former
components $C_{i}$ with $i\neq 1,l$.

Finally, as $(C_{1}\cap C_{l})\cap\widehat{\Gamma}=\\{p,q\\}$ and $C_{1}$,
$C_{l}$ and $\widehat{\Gamma}$ are contractible, so is the component
$C_{1}\cup\widehat{\Gamma}\cup C_{l}$.

Finally we observe that, since the $x_{2k-1}$’s are maximal elements, one gets
$height(Y)=height(X)$ if $height(X)\geq 2$ and $height(Y)=2$ otherwise. ∎

###### Proof.

(Theorem 5.1) Assume $cat(X)=n$ and let $X=\cup_{j=1}^{n}U_{j}$ be an open
covering where each $U_{j}$ is contractible in $X$. Then Lemma 5.3 yields that
each $U_{j}$ is a disjoint union of open sets contractible in themselves.

By applying Lemma 5.4 recursively on the number of connected components of
$U_{1}$ we construct a finite space $X_{1}$ with the same homotopy type as $X$
such that $X_{1}=\cup_{j=1}^{n}U^{1}_{j}$ where $U^{1}_{j}$ is contractible
and each $U^{1}_{j}$ is homotopy equivalent to $U_{j}$ for $j\geq 2$. In
particular each $U^{1}_{j}$ has the same number of (contractible) components
as $U_{j}$ for $j\geq 2$.

Now one applies recursively Lemma 5.4 to $U^{1}_{2}$ in $X_{1}$ to get a new
space $X_{2}$ with the same homotopy type as $X_{1}$ such that
$X_{2}=\cup_{j=1}^{n}U^{2}_{j}$ is an open covering of $X_{2}$ where
$U^{2}_{j}$ is contractible and $U^{2}_{j}$ is homotopy equivalent to
$U^{1}_{j}$ whenever $j\neq 2$. In particular $U^{2}_{1}$ is contractible.

This way we proceed inductively on $n$ to get a space $X_{n}$ within the
homotopy class of $X$ such that $X_{n}$ admits an open covering
$\\{U^{n}_{j}\\}_{j=1}^{n}$ where each $U^{n}_{j}$ is contractible. Hence
$Cat(X)\leq n=cat(X)$ and so $Cat(X)=cat(X)$. As observed Lemma 5.4, we have
$height(X_{n})=\max\\{2,height(X_{n-1})\\}=\dots=\max\\{2,height(X)\\}=2$. ∎

######  Remark 5.5.

As an immediate consequence of Lemma 5.3 we get that an open set $U$ is
contractible in a finite space of height 1 if an only if it does not contain a
cycle, that is, there is no sequence of the form
$x_{1},y_{1},x_{2},y_{2},\dots,x_{n}$ with $x_{1}=x_{n}$ and
$x_{i}>y_{i}<x_{i+1}$ for $1\leq i\leq n-1$.

Cycles are special instances of the configurations termed crowns; see [29][Th.
on p. 310]and [12].

As mentioned in Section 2, a lower bound for the LS-category of a finite
$T_{0}$-space is given by the simplicial category of its order complex
$\mathcal{O}(X)$, $scat(\mathcal{O}(X))$. Moreover, if $K$ is a graph, then
$scat(K)$ is equal to the vertex arboricity $va(K)$ of $K$, see [15]. Recall
that given a graph $G$ the _vertex arboricity_ $va(G)$ of $G$ is the minimum
$n$ for which the vertex set of $G$ admits a partition
$P_{n}=\\{V_{1},\ldots,V_{n}\\}$ such that for every $i=1,\dots,n$ the
subgraph of $G$ induced by the vertices of $V_{i}$ is acyclic.

On the other hand, an upper bound for the LS-category of finite spaces of
height 1 can be obtained in terms of vertex arboricity for multigraphs.

Given a space $X$ of height 1, let us define the multigraph $\Gamma(X)$
associated to $X$ in the following way: the vertex set of $\Gamma(X)$ is
$Max(X)$; a simple edge exists between any two vertices $v,w\in Max(X)$ if the
corresponding minimal open sets $U_{v}$ and $U_{w}$ have exactly one common
neighbour; and a double edge connects two vertices $v,w\in Max(X)$ if the
corresponding minimal open sets $U_{v}$ and $U_{w}$ have more than one common
neighbour.

A description of the LS-category in the terms of graph arboricity is
accomplished by a sort of relative arboricity as follows. Given a graph
$G=(V,E)$, a _domination set_ of $G$ is a set $D\subseteq V$ such that each
vertex in $V\backslash D$ is adjacent to some vertex of $D$. Then the _$D$
-arboricity $a_{D}(G)$ of $G$_, is the minimum $n$ for which $D$ admits a
partition $\\{D_{1},\ldots,D_{n}\\}$ such that for every $i=1,\dots,n$ the
subgraph of $G$ given by the union of the edges of $G$ incident to the
vertices in $D_{i}$ is acyclic. The previous remarks are summarized in the
following proposition:

######  Proposition 5.6.

The following (in)equalities hold for any finite space of height 1,

$va(\mathcal{O}(X))\leq cat(X)=a_{Max(X)}(\mathcal{O}(X))\leq va(\Gamma(X)).$

###### Proof.

Observe that the first inequality is already known. The equality in the middle
follows from the fact that if $U_{J}$ is a prime open set, then the
corresponding subgraph $G_{J}\subseteq\mathcal{O}(X)$ generated by the edges
incident at vertices of $J$ is acyclic if and only if each component of
$U_{J}$ is contractible. We conclude by Lemma 5.3.

To check the second inequality, let $\\{J_{1},\dots,J_{n}\\}$ be a partition
of $Max(X)$ such that $\Gamma_{i}(X)=\cup_{j\in\Lambda_{i}}T_{j}$ is a forest.
Let $V_{j}$ be the vertex set of the tree $T_{j}$, and $U_{j}=\cup_{x\in
V_{j}}U_{x}$. Now observe that the open sets
$U_{i}=\cup_{j\in\Lambda_{i}}U_{j}$ do not contain cycles (see Remark 5.5).
Indeed, any such cycle yields a cycle in $T_{j}$, in the classical graph-
theoretic sense. Therefore, $U_{i}$ is contractible in $X$ by Remark 5.5, and
then $cat(X)\leq va(\Gamma(X))$. ∎

The upper bound provided by the multigraph $\Gamma(X)$ may not be very
accurate, as the following example shows:

######  Example 5.7.

For $n=2k$, let $X$ be the finite space of height 1 with
$A=\\{a_{0},a_{1},\dots a_{n}\\}$ as points at level $0$,
$\\{b_{0},\dots,b_{n}\\}$ as points at level $1$, and such that
$U_{b_{0}}=\\{b_{0}\\}\cup A$, while $U_{b_{i}}=\\{b_{i},a_{0},a_{i}\\}$ for
$i\geq 1$. Then $U_{1}=\cup_{i=1}^{n}U_{b_{i}}$ and $U_{2}=U_{b_{0}}$ are
contractible open sets such that $U_{1}\cup U_{2}=X$, so that $cat(X)=2$. In
contrast, no set with three or more $b_{i}$ ($i\geq 1$) as well as no set
containing $b_{0}$ and some $b_{i}$ ($i\neq 0$) generates an acyclic graph in
$\Gamma(X)$, and so $va(\Gamma(X))=k+1$.

##  6\. A contractibility algorithm

In this section we present an algorithm to obtain the core of a finite
$T_{0}$-space $X$, and in particular deciding whether $X$ is eventually
contractible or not. The algorithm is based on the following basic observation
which is an immediate consequence of the homotopical properties of beat
points.

Fact. If $X$ is a contractible space and $x$ is a beat point of $X$, then
$X-\\{x\\}$ is contractible.

We next describe the procedure.

Algorithm: Contractibility Test (CT)

Input: A finite $T_{0}$-space $X$ as a poset.

Output: The core of $X$ and the answer to the question “Is $X$ contractible?”

  1. (1)

Identify all the beat points of $X$.

  2. (2)

If $X$ has no beat points and is itself a point, STOP. Otherwise, go to 3).

  3. (3)

If $X$ has no beat points and is not a point, STOP (and we have reached the
core of $X$). Otherwise, go to 4).

  4. (4)

Remove the beat points identified in 1).

  5. (5)

Rename the obtained space as $X$.

  6. (6)

Go to 1).

As we are dealing with finite spaces, the algorithm terminates. If it
terminates in some iteration at Step 2, the original space was contractible,
while if it stops in some iteration at Step 3, the original space was not.
Next we prove that this procedure finishes in polynomial time.

######  Lemma 6.1.

For a finite space $X$ of cardinal $n$, obtaining its core and detecting its
contractibility has time complexity of order ${\mathcal{O}}(n^{4})$.

###### Proof.

Firstly, the transitive reduction algorithm described in [21] must be
performed in order to obtain a Hasse diagram of the space $X$. Let $D=(V,E)$,
$V=\\{v_{1},\,v_{2},\dots,v_{n}\\}$, be the digraph representing the Hasse
diagram of $X$. By abuse of notation, we say that a vertex $b$ is a beat point
of $D$ if it corresponds to a beat point of $X$. A vertex $b$ of $D$ is a beat
point if and only if $b$ has indegree or outdegree (possibly both) equal to
one in $D$.

Let us consider the adjacency matrix $A=(a_{ij})_{n\times n}$ of $D$, defined
by $a_{ij}=1$ if $(v_{i},v_{j})\in E$ and $a_{ij}=0$ in other case. For each
beat point $b$ with indegree $\delta_{i}(b)=1$ and outdegree
$\delta_{o}(b)=k>0$ let us consider the edge $(a,b)$ providing the only in-
edge. Removing a beat point produces a sequence of operations over the matrix
$A$ that consists of:

  1. (1)

Replacing the row of $a$ by the addition of the rows of $a$ and $b$ and any
out-edge $(b,v_{j})$ by a new out-edge $(a,v_{j})$.

  2. (2)

Deleting the column and the row corresponding to $b$.

For each beat point $b$ with $\delta_{o}(b)=1$ and $\delta_{i}(b)=h>0$ an
analogous method is used, by interchanging the roles of columns and rows in
operations (1) and (2).

This way, after the removal of all beat points of $D$, a new acyclic digraph
$D^{\prime}=(V^{\prime},E^{\prime})$ is obtained verifying
$|V^{\prime}|\leq|V|-1$ and $|E^{\prime}|\leq|E|-1$. Two situations are
possible:

  1. (1)

$D^{\prime}$ is the Hasse diagram of a new space $X^{\prime}$, that is, the
transitivity property of $X^{\prime}$ is reflected in $D^{\prime}$
($(a,b),(b,c)\in E^{\prime}$ implies $(a,c)\notin E^{\prime}$).

  2. (2)

$D^{\prime}$ is not the Hasse diagram of any space since there are three edges
$(a,b),(b,c),(a,c)\in E^{\prime},$ for some vertices $a,b,c\in V^{\prime}.$

In (1) new beat points must be searched for $D^{\prime}$, while in (2) the
transitive reduction algorithm must be performed again in order to obtain a
new digraph corresponding to a Hasse diagram of a new space $X^{\prime}$.

Now, we study the time complexity of the entire procedure. Detecting the set
of beat points of $D$ can be done in ${\mathcal{O}}(n^{2})$ time, since it
suffices to find out in the matrix $A$ arrows with only one 1 and columns with
only one 1. It is clear that, for a beat point $b$, operations (1) and (2)
have time complexity of constant order. According to [21], the time complexity
for obtaining the transitive reduction of an acyclic digraph is
${\mathcal{O}}(n^{3})$, being $n$ the order of the digraph. In the worst case,
only one beat point is eliminated in each step, and the vertex set decreases
by one after each removal. Hence we can conclude that the total time
complexity in the worst case is of order
$\sum_{k=1}^{n}k^{3}=\frac{n^{2}(n+1)^{2}}{4}$, that is
${\mathcal{O}}(n^{4}).$ ∎

##  7\. An algorithmic approach to the geometric category

In this section we explore possible algorithmic treatments of the geometric
category and the other related numerical parameters $Cat_{u}$ and $gcat_{p}$
for a finite $T_{0}$-space $X$. With this purpose we introduce the following
definition: a subset $J\subset X$ is said to be _compatible_ if the open set
$U_{J}=\cup_{x\in J}U_{x}$ is contractible.

We next proceed to analyze the compatibilities. By using the CT-algorithm,
which allows us to decide whether $J$ is compatible or not. Moreover, in order
to determine $Cat_{u}(X)$ we first apply the CT-algorithm to find the core
$X_{0}$ of $X$. For the prime strong geometric category $gcat_{p}(X)$, we
first reduce $X$ to its set of maximal elements and then analyse the
compatibilities among them.

There are two possible approaches when undertaking this calculation. The first
one consists in identifying the compatibility (or not) of _all_ subsets of $X$
for $gcat(X)$, $Max(X)$ for $gcat_{p}$ and $Max(X_{0})$ for $Cat_{u}(X)$, and
then deriving from this information the exact value of the corresponding
numerical parameter (or, equivalently, the covering number of an appropriate
hypergraph associated to $X$ in Section 8). We describe below greedy
algorithms that work in this context. Unfortunately, there will be instances
of spaces for which these procedures will need exponential time to solve the
problem, although they should be useful for “small” cases. On the other hand,
we may investigate bounds for these numerical parameters without computing the
compatibility (or not) of _all_ subsets of $X$ ($Max(X)$ or $Max(X_{0})$,
respectively) but only of a number of them that involve a polynomial number of
operations. This can be achieved by restricted applications of the mentioned
algorithm, as we will also see below.

We will proceed to describe the algorithm for the geometric category
$gcat(X)$. In a similar way we can deal with $gcat_{p}(X)$ ($Cat_{u}(X)$,
respectively) simply by taking below the smaller set $Max(X)$ ($Max(X_{0})$,
respectively) in the place of $X$ and prime open sets in the place of all open
sets of $X$ ($X_{0}$, respectively).

Observe that, for $|X|=n$, there are $2^{n}-1$ non-empty different collections
of such open sets. As singletons are clearly compatible, in principle we
should take account of $2^{n}-n-1$ collections.

###  7.1. Greedy strategies

Given $k\geq 2$, we present two systematic greedy procedures to check the
compatibility of collections of $k$ minimal open sets that at the same time
provides upper bounds for $gcat(X)$.

Notation. For simplicity, given a finite $T_{0}$-space with $|X|=n$, we will
write $X=\\{1,\dots,n\\}$ so that for $J=\\{i_{1},i_{2},\dots,i_{k}\\}$ with
$1\leq i_{1}<i_{2}<\dots<i_{k}\leq n$, we denote $U_{J}=\cup_{i\in J}U_{i}$
simply by $(i_{1},i_{2},\dots,i_{k})$. The number $k$ will be called the
_length_ of the collection $J$.

Let us now describe the first algorithm, which we will call _U-algorithm_ ;
the name comes from the fact that we check sets of prime open sets with
growing length, “going up”.

$U$-Algorithm:

Input: The family of minimal open sets $U_{J}$ with $J\subset X$, $|X|=n$.

Output: An upper bound for $gcat(X)$, or $gcat(X)=n$.

  1. (1)

Set $k=2$; $bound=n$.

  2. (2)

For $k\leq n$ check CT for the $\binom{n}{k}$ different collections of minimal
open sets of length $k$.

If at least one is compatible, then set $bound=n-k+1$, $gcat(X)\leq bound$

else $gcat(X)\leq bound.$

$k=k+1$.

  3. (3)

If $bound<n$ set $gcat(X)\leq bound$ and STOP

else set $gcat(X)=n$ and STOP.

######  Remark 7.1.

If there is a collection $C=\\{i_{1},\dots,i_{k}\\}$ of length $k$ that is
compatible, then the covering given by $(i_{1},\dots,i_{k})$ and the remaining
open sets assures that $gcat(X)\leq n-k+1$. The algorithm does not give in
general an exact value for the $gcat(X)$, because the coverings whose length
gives $gcat(X)$ could not be identified by the algorithm. The exceptions are
the cases $k=n-1$ and $k=n$, where the equality $gcat(X)=2$ or $gcat(X)=1$ is
immediately deduced from the corresponding inequality.

Note that a dual algorithm ($D$-Algorithm) is possible, starting from the
unique collection of length $n$, continuing with the collections of length
$n-1$ and so on. The output in this case in an upper bound for the category.
Although the algorithms are basically symmetric, there is an difference
between them. In the $U$-algorithm, every step can improve the bound obtained
in the previous one. In the dual version, however, the occurrence of a value
for the bound of the category in some step implies immediately that the
algorithm stops, as the bound cannot be improved in subsequent steps.

On the other hand, the compatibility structure of the minimal open sets is
completely described when you run until the end any of the two algorithms;
this is important in order to get an exact computation of $gcat(X)$ using the
tools of hypergraph theory described in last section.

In general, the complexity of the algorithms (when computing the whole
compatibility structure) is exponential in the number $n$ of open minimal
sets, as $2^{n}-n-1$ collections of open minimal sets must be checked.
However, if we are only interested in bounds for the category and we run the
algorithm only until some fixed length, the complexity is _polynomial_ in $n$.
For a certain length $k$, we will call $U(k)$ and $D(n-k)$ the shortened
versions of the $U$-algorithm and its dual, respectively. In the case of the
$U(k)$-algorithm, the fact that there are $\binom{n}{k}$ different collections
of $k$ minimal open sets and that checking the CT-algorithm for a collection
of $k$ minimal open sets has complexity $O(k^{4})$ (Lemma 6.1) implies that
the complexity of this algorithm is $O(n^{k}k^{4})$. A similar reasoning for
the $D(n-k)$-algorithm gives a complexity of $O(n^{k+4})$, bigger than the
previous one. So from the point of view of the complexity, the $U$-algorithm
is better than its dual, the $D$-algorithm.

It could be also interesting to combine both approaches, starting from the set
of all minimal open sets, then checking pairs, then checking collections of
length $n-1$, then triplets, and so on. Alternatively, one can start by
checking compatibilities over a random sample of collections of minimal open
sets, to get a clue over the number of compatibilities: a high number of them
would recommend to use the first algorithm, while a low number would indicate
that the dual version would be more useful.

###  7.2. Heuristics

In this subsection we suggest heuristic ways of obtaining bounds for the
geometric category of $X$. Recall that $X=\\{1,\ldots,n\\}$ and contractible
open sets are identified as ordered compatible subsets of $X$. The goal is to
find a covering of $X$ consisting of a number of contractible open sets as
close as possible to $gcat(X)$. We follow the notation described at the
beginning of Section 7.1.

Heuristic 1. First apply the CT-algorithm to $(1,2)$. If this set is
contractible, then apply the CT-algorithm to $(1,2,3)$, and iterate the
process until the smallest $k$ such that $\\{1,2,3,\ldots,k\\}$ is not
compatible is found. Then one can proceed in different ways, in order to
identify a covering, which in general have linear or at most polynomial
complexity. For example, consider the following scheme. The first element of
our covering will be $(1,2,3,\ldots,k-1)$. Apply the CT-algorithm to
$(k,k+1)$. If this set is contractible, apply the CT-algorithm to
$(k,k+1,k+2)$, and iterate the process until you find the smallest $j$ such
that $\\{k,k+1,\ldots,(k+j)\\}$ is not compatible. The second element of the
covering will then be $(k,k+1,\ldots,k+j-1)$. Now iterate the process starting
with the contractibility of $(k+j,k+j+1)$. The process finishes when $\\{n\\}$
has been assigned to a member of the covering. It is easy to develope
variations of this scheme, checking for example $(1,2,\ldots,k-1,k+1)$ after
$(1,2,3,\ldots,k-1)$ at first, and/or considering different ways of perform
the updating in the covering.

Heuristic 2. A different approach is to fix a certain $k<n/2$, and to check
the compatibility of all the subcollections of length smaller or equal than
$k$. This can be always undertaken in polynomial time of degree $k$. Observe
that $k$ should be independent of $n$ in order to get the polynomial
complexity. After all these compatibilities have been checked, we give an
order to the set ${\mathcal{A}}$ of compatible subcollections (where the
unitary ones are included), and we call $A_{i}$ the $i$-th subcollection in
this ordered set. Now we can define a covering $\\{U_{1},\ldots,U_{j}\\}$ in
the following way: $U_{1}=U_{A_{1}}$; $U_{2}=U_{A_{i_{1}}}$ where
$A_{i_{1}}\in{\mathcal{A}}$ with smallest subindex such that $A_{i_{1}}\cap
A_{1}=\emptyset$ (alternatively, $A_{i_{1}}-A_{1}\neq\emptyset$);
$U_{3}=U_{A_{i_{2}}}$ with $A_{i_{2}}\in{\mathcal{A}}$ with smallest subindex
such that $A_{i_{2}}\cap A_{1}=A_{i_{2}}\cap A_{i_{1}}=\emptyset$
(alternatively, $A_{i_{2}}-(A_{1}\cup A_{i_{1}})\neq\emptyset$); and so on.
Observe that different orders give rise to different coverings, and that
checking all the possible order allows to obtain the covering of smallest
cardinal that can be constructed with collections of length smaller or equal
than $k$.

Let us also remark that in Heuristic 1 the CT-algorithm is applied a linear
number of times (precisely $n-1$ times) while in Heuristic 2 the complexity
time needed to check the compatibilities is of polynomial order.

##  8\. Compatibility structures, Boolean functions and hypergraphs

The structures of compatibility defined by the geometric category and the
related LS-type numbers $Cat_{u}$ and $gcat_{p}$ can be modeled by a Boolean
function that sends compatible sets (possibly empty) to $0$ and incompatible
sets to $1$. An analogous notion of compatibility can be defined for $cat(X)$
on $\mathcal{P}(Max(X))$ by considering a prime open set $J\subseteq Max(X)$
to be _$cat$ -compatible_ if $U_{J}$ is contractible inside of $X$ (see Lemma
4.2).

Observe that if an open set $U$ is contractible inside of $X$, every subset of
$U$ is so. Hence, subsets of compatible collections in the sense of $cat$ are
always compatible, and the Boolean function for $cat$ is monotonic. This is
not the case for the other LS-type numbers since open subsets of contractible
open sets need not be contractible (for instance, the open set $U_{d_{1}}\cup
U_{d_{2}}$ in the space of Example 3.2 is not contractible but it is part of
the contractible minimal open set $U_{b}$).

Although the $cat$-compatibility structure yields a monotonic Boolean
function, the algorithmic approach in Section 6 does not apply to $cat$ since
a starting algorithm similar to the Contractibility Test is quite more complex
for the LS-category because checking whether or not a certain subset
$U\subseteq X$ is contractible in $X$ requires devising an algorithm which
explores all possible homotopies starting from the inclusion of $U$. It is
worth pointing out that Tanaka [32] describes homotopies between finite spaces
in terms of relation matrices.

Notice also that the strong category $Cat(X)$ requires, in principle,
analyzing the geometric category of all spaces within the homotopy type of
$X$.

The following definition provides a general framework in terms of Boolean
functions for the LS-type invariants in this paper except for the strong
category. Let $\sigma:\mathcal{P}(Z)\to\\{0,1\\}$ be a (monotonic) Boolean
function on a set $Z$. We call $\sigma$-_category_ of $Z$ and denote
$\sigma$-$cat(Z)$ the smallest integer $n$ for which there exists a covering
$\\{U_{i}\\}_{i=1}^{n}$ of $Z$ such that each $U_{i}$ is $\sigma$-compatible;
that is, $\sigma(U_{i})=0$.

There is a natural hypergraph arising from a compatibility structure on a
finite $T_{0}$-space $X$. More generally, any Boolean function
$\sigma:\mathcal{P}(Z)\to\\{0,1\\}$ has associated a hypergraph such that
$\sigma$-$cat(Z)$ coincides with the covering number of the hypergraph as
defined in graph theory.

Recall that given a finite set $V=\\{v_{1},\dots,v_{r}\\}$ an _hypergraph_ $H$
in $V$ is a family $E=\\{E_{1},\dots,E_{m}\\}$ of subsets of $V$ so that
$E\neq\emptyset$ and $V=\cup_{i=1}^{m}E_{i}$. The elements $v_{i}\in V$ are
called _vertices_ and the sets $E_{j}\in E$ are the _hyperedges_ of ${H}$. A
hypergraph is termed _simple_ or a _Sperner hypergraph_ if all its hyperedges
are maximal, that is, if $e^{\prime}\subseteq e\in E$ then $e=e^{\prime}$.

Given a hypergraph $H=(V,E)$, an _hyperedge covering_ of $H$ is a family of
hyperedges of $H$ whose union is the vertex set $V$. The _covering number_
$\rho(H)$ of $H$ is the minimum cardinality of a hyperedge covering of $H$.
When $H$ is not Sperner, we may consider its Sperner subhypergraph
$\widehat{H}=(V,\widehat{E})$, where the hyperedges in $\widehat{E}$ are the
maximal hyperedges in $H$. Clearly $\rho(H)=\rho(\widehat{H})$, so when
dealing with the covering number we can work with Sperner hypergraphs.

We refer to [5] and [7] for more information.

There is always a hypergraph $H(\sigma)=(V,E)$ canonically associated to any
Boolean function $\sigma:\mathcal{P}(Z)\to\\{0,1\\}$, with vertex set $V=Z$
and $E=\\{e\subseteq Z:\sigma(e)=0\\}$.

######  Remark 8.1.

Notice that for every subset $U\subseteq Z$, $\sigma(U)=0$ if and only if
$U=e$ for some $e\in E$. Hence, ${H}(\sigma)$ describes completely the Boolean
function $\sigma$. In fact, in this way any hypergraph $H$ describes a Boolean
function, denoted by $\sigma(H)$. Also observe that a hypergraph may be
associated to any function $\tau:\mathcal{A}\to\\{0,1\\}$ for a family of
subsets $\mathcal{A}\subseteq\mathcal{P}(Z)$.

Taking into account the previous considerations, the following result is
easily checked.

######  Proposition 8.2.

The $\sigma$-category defined by a Boolean function $\sigma$ coincides with
$\rho(H(\sigma))$, the covering number of $H(\sigma)$.

Given any finite $T_{0}$-space $X$, the previous proposition applies to the
Boolean functions $\sigma_{gcat}$ on $Z=X$, $\sigma_{cat}$ and
$\sigma_{gcat_{p}}$ on $Z=Max(X)$ and $\sigma_{Cat_{u}}$ on $Z=X_{0}$ (the
core of $X$). Therefore, the knowledge of these parameters provide the
knowledge of the corresponding covering number of the associated hypergraph
and conversely. It has been established that for a given hypergraph, computing
its covering number can be solved in polynomial time by using Boolean
functions defined over it hyperedges set. However, finding a covering with at
most $k$ hyperedges is an $NP$-complete problem whenever $k$ is not fixed,
[16].

Nevertheless, whenever the compatibility structure of $Z$ is completely known,
the associated hypergraph $H(\sigma)$ covering number and hence the
$\sigma$-category are bounded. For instance, according to [27], for a
hypergraph $H$ of $n$ vertices and $m$ hyperedges such that any vertex lies in
at least $b\geq 1$ hyperedges and every hyperedge size is at most $a$, it is
verified

$\frac{n}{a}\leq\rho(H)\leq\frac{ln(ml/bn)}{ln(1-b/n)}+\frac{m}{b}\sum_{1\leq
j\leq l}\frac{1}{j}$

for any integer $l$. Other bounds for some particular situations can be found
in [27].

The covering number can be reformulated as in terms of the transversal number
of a hypergraph, which we now define. Recall that, given a hypergraph
$H=(V,E)$, a set of vertices $B\subset V$ is said to be a _transversal_ if it
meets every hyperedge $e\in E$. The _transversal number_ $\tau(H)$ is the
minimum cardinality of a transversal. Each transversal of $H$ corresponds a
covering of the dual hypergraph $H^{d}=(V^{d},E^{d})$ of $H$, and viceversa.
Recall that the _dual hypergraph_ $H^{d}$ has $E$ as its vertex set,
$V^{d}=E$, and a hyperedge in $E^{d}$ is a family $e^{d}_{v}=\\{e\in E/v\in
e\\}$ for a given $v\in V$ (possibly $e^{d}_{v}=e^{d}_{w}$ for $w\neq v$), see
[23]. This way $\rho(H)=\tau(H^{d})$. In particular determining different
versions of the category of a finite $T_{0}$-space turns to be equivalent to
determining a transversal number from the viewpoint of graph theory.

These problems are in general $NP$-complete, see [19]. Furthermore, they are
related to computing the so called transversal hypergraph and hence to
enumerate maximal set of independent sets in a hypergraph [6], or to solve the
Boolean function dualization problem [14]. These invariants have many
applications in Computer Science and in particular to Logic and Artificial
Intelligence, as described in [13]. According to [26], the best known
algorithm for solving the hypergraph transversal problem is due to Fredman and
Khachiyan [17]. Actually, in [26] an algorithm for computing the minimum
covering (and transversal) number is obtained based on the semi-tensor product
of matrices, see [8] and [9].

Observe that, by Lemma 5.3 and Remark 5.5, we have a clear criterium about the
contractibility of a subspace of a finite $T_{0}$-space $X$ of height $1$, so
it is tempting to recreate the monotonic Boolean function $\sigma(H)$ induced
by a Sperner hypergraph $H=(V,E)$ as the monotonic Boolean function associated
to the LS-category of a suitable $X$ with $Max(X)=V$. The following example
shows that it is not possible to define such a space.

######  Example 8.3.

Consider the hypergraph $H_{1}=(V_{1},E_{1})$, where $V_{1}=\\{1,2,3,4,5\\}$
and
$E_{1}=\mathcal{P}(V_{1})-\\{\emptyset,\\{1,2,3,4\\},\\{1,2,3,5\\},\\{1,2,3,4,5\\}\\}$.
Its Sperner hypergraph has as hyperedges
$\hat{E}_{1}=\\{\\{1,2,3\\},\\{1,2,4,5\\},\\{1,3,4,5\\},\\{2,3,4,5\\}\\}$. If
there was a finite $T_{0}$-space $X$ of height $1$ so that
$\sigma_{cat}=\sigma(H_{1})$, then $\sigma_{cat}$ would be zero on all subsets
except for $\\{1,2,3,4\\}$, $\\{1,2,3,5\\}$ and $\\{1,2,3,4,5\\}$. This would
mean that $U=U_{1}\cup U_{2}\cup U_{3}\cup U_{4}$ and $V=U_{1}\cup U_{2}\cup
U_{3}\cup U_{5}$ would contain crowns $X(1)$ and $X(2)$ respectively, as
depicted in Figure 5 (see Remark 5.5). Notice that in both of them the order
of appearance of the vertices $\\{1,2,3\\}$ must be same otherwise
$\sigma_{cat}(U_{2}\cup U_{3})=1$.

Figure 5.

In these conditions, it should be true that $d(2)=d(2^{\prime})$ and
$d(3)=d(3^{\prime})$ otherwise $\sigma_{cat}(U_{1}\cup U_{2})=1$ and
$\sigma_{cat}(U_{2}\cup U_{3})=1$. Now we study the cases when $d(1)$ and
$d(1^{\prime})$ are or not equal and when $d(4)$ and $d(5)$ are or not equal.
In any of the four possible cases we obtain subsets on which $\sigma_{cat}$
takes on the value $1$ when it should not.

It is unknown to the authors whether there exists fixed $k>1$ such the Boolean
function $\sigma(H)$ associated to an arbitrary $H$ can be always modeled by
the Boolean function associated to the LS-category of a finite space of height
$k$. The same conclusion would be obtained regarding the computation of the
covering number of a hypergraph and, as apparently every combinatorial problem
can be reformulated as the determination of the covering number [18] this
would reduce such problems to the calculation of the LS-category of a finite
$T_{0}$-space of height $k$.

In the above recreation of a hypergraph, the collections of subsets of the
vertices which are not subsets of any hyperedge play an important role. In the
example described above these subsets and the intersections among them have
large cardinals with respect to the cardinal of the set of vertices. It seems
that if these subsets were small such a recreation would be plausible. The
following is an example of such phenomenon.

######  Example 8.4.

Let $H_{2}=(V_{2},E_{2})$ be the hypergraph with $V_{2}=\\{0,1,2,3,4\\}$ and
$E_{2}=\mathcal{P}(V_{2})-\\{\emptyset,U\subseteq V_{2}\textrm{ }|\textrm{
}U\mbox{ contains }\\{0,1\\},\\{1,2\\},\\{2,3\\},\\{3,4\\}\mbox{ or
}\\{0,4\\}\\}$. Its Sperner hypergraph has as hyperedges
$\hat{E}_{2}=\\{\\{0,2\\},\\{0,3\\},\\{1,3\\},\\{1,4\\},\\{2,4\\}\\}$. Then
the height $1$ finite $T_{0}$ space $X$ whose Hasse diagram is depicted below
has $\sigma_{cat}=\sigma(H_{2})$. Its Hasse diagram is the union of the Hasse
diagrams of the spaces (crowns) $X(i,i+1)$ considered as directed graphs where
the indices are $i=0,1,\dots,4\ mod\ 5$.

Figure 6.

We finish with a question that derives from the previous considerations. It
seems to be difficult and interesting.

Question. Identify those hypergraphs $H$ for which there exists a finite
$T_{0}$-space of height $1$ with $\sigma_{cat}=\sigma(H)$. That would help to
characterize those finite $T_{0}$-spaces for which the computation of its
$LS$-category can be reduced to that of a height $1$ space, where the homotopy
issues are under control.

## References

  * [1] S. Aaronson and N. Scoville.  Lusternik-Schnirelmann category for simplicial complexes.  Illinois J. Math., 57(3):743–753, 2013.
  * [2] P. Alexandroff.  Diskrete Räume.  Rec. Math. Moscou, n. Ser., 2:501–519, 1937.
  * [3] J. Barmak.  Algebraic topology of finite topological spaces and applications, volume 2032 of Lecture Notes in Mathematics.  Springer, Heidelberg, 2011.
  * [4] J. Barmak.  Algebraic topology of finite topological spaces and applications, volume 2032 of Lecture Notes in Mathematics.  Springer, Heidelberg, 2011.
  * [5] C. Berge.  Hypergraphs, volume 45 of North-Holland Mathematical Library.  North-Holland Publishing Co., Amsterdam, 1989.  Combinatorics of finite sets, Translated from the French.
  * [6] E. Boros, V. Gurvich, L. Khachiyan, and K. Makino.  Generating partial and multiple transversals of a hypergraph.  In Automata, languages and programming (Geneva, 2000), volume 1853 of Lecture Notes in Comput. Sci., pages 588–599. Springer, Berlin, 2000.
  * [7] A. Bretto.  Hypergraph theory.  Mathematical Engineering. Springer, Cham, 2013.
  * [8] D. Cheng and H. Qi.  Semi-tensor product of matrices-theory and applications.  Beijing: Science Press, 2007.
  * [9] D. Cheng, H. Qi, and Z. Li.  Analysis and control of Boolean networks.  Communications and Control Engineering Series. Springer-Verlag London, Ltd., London, 2011.
  * [10] E. Clader.  Inverse limits of finite topological spaces.  Homology Homotopy Appl., 11(2):223–227, 2009.
  * [11] O. Cornea, G. Lupton, J. Oprea, and D. Tanré.  Lusternik-Schnirelmann category, volume 103 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2003.
  * [12] D. Duffus and I. Rival.  Crowns in dismantlable partially ordered sets.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 of Colloq. Math. Soc. János Bolyai, pages 271–292. North-Holland, Amsterdam-New York, 1978.
  * [13] T. Eiter and G. Gottlob.  Hypergraph transversal computation and related problems in logic and AI.  In Logics in artificial intelligence, volume 2424 of Lecture Notes in Comput. Sci., pages 549–564. Springer, Berlin, 2002.
  * [14] T. Eiter, K. Makino, and G. Gottlob.  Computational aspects of monotone dualization: a brief survey.  Discrete Appl. Math., 156(11):2035–2049, 2008.
  * [15] D. Fernández-Ternero, E. Macías-Virgós, and J. A. Vilches.  Lusternik-Schnirelmann category of simplicial complexes and finite spaces.  Topology Appl., 194:37–50, 2015.
  * [16] W. Fischl, G. Gottlob, and R. Pichler.  General and fractional hypertree decompositions: Hard and easy cases.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 17–32, 2018.
  * [17] M. Fredman and L. Khachiyan.  On the complexity of dualization of monotone disjunctive normal forms.  J. Algorithms, 21(3):618–628, 1996.
  * [18] Z. Füredi.  Matchings and covers in hypergraphs.  Graphs Combin., 4(2):115–206, 1988.
  * [19] M. Garey and D. Johnson.  Computers and intractability.  W. H. Freeman and Co., San Francisco, Calif., 1979.
  * [20] J. González.  Simplicial complexity: piecewise linear motion planning in robotics.  New York J. Math., 24:279–292, 2018.
  * [21] D. Gries, A. J. Martin, J. L. A. van de Snepscheut, and J. T. Udding.  An algorithm for transitive reduction of an acyclic graph.  Science of Computer Programming, 12:151–155, 1989.
  * [22] M. Kukiela.  On homotopy types of Alexandroff spaces.  Order, 27(1):9–21, 2010.
  * [23] E. Lawler.  Covering problems: Duality relations and a new method of solution.  SIAM J. Appl. Math., 14:1115–1132, 1966.
  * [24] J.P. May.  Finite spaces and larger contexts.  Preliminary draft submitted to the AMS, 2014.
  * [25] M. McCord.  Singular homology groups and homotopy groups of finite topological spaces.  Duke Math. J., 33:465–474, 1966.
  * [26] M. Meng, J. Feng, and X. Li.  A matrix method to hypergraph transversal and covering problems with application in simplifying boolean functions.  In Control Conference (CCC), 2016 35th Chinese, pages 2772–2777. IEEE, 2016.
  * [27] C. Moreira and Y. Kohayakawa.  Bounds for optimal coverings.  Discrete Appl. Math., 141(1-3):263–276, 2004.
  * [28] G. Raptis.  Homotopy theory of posets.  Homology Homotopy Appl., 12(2):211–230, 2010.
  * [29] I. Rival.  A fixed point theorem for finite partially ordered sets.  J. Combinatorial Theory Ser. A, 21(3):309–318, 1976.
  * [30] R. Stong.  Finite topological spaces.  Trans. Amer. Math. Soc., 123:325–340, 1966.
  * [31] K. Tanaka.  Lusternik-Schnirelmann category for cell complexes and posets.  Illinois J. Math., 59:623–636, 2015.
  * [32] Kohei Tanaka.  Lusternik-Schnirelmann category of relation matrices on finite spaces and simplicial complexes.  Fund. Math., 249(2):149–167, 2020.