"Simple to state, but difficult to solve" problems which require analyzing topology of simplicial complexes?

Question

In a User's Guide to Discrete Morse Theory, Robin Forman writes:

A number of questions from a variety of areas of mathematics lead one to the problem of analyzing the topology of a simplicial complex.

In order to appreciate this statement, can I have some examples of "simple to state, but difficult to solve" problems which require one to analyze the topology of a simplicial complex?

To me:

• "simple to state" means that the problem can be explained to an undergraduate student without domain-specific jargon. At first glance, it might even even seem rather easy to solve.

• "difficult to solve" means that the problem isn't easily solved using "everyday tools" provided by an undergraduate mathematics education. It requires some special insights, which help to illustrate the topic in question (in this case, discrete Morse theory).

Answer 1

From Wikipedia:

The inscribed square problem, also known as the square peg problem or the Toeplitz' conjecture, is an unsolved question in geometry: Does every plane simple closed curve contain all four vertices of some square?

See https://en.wikipedia.org/wiki/Inscribed_square_problem - current work on the problem leads one to analyze the topology of various configuration spaces.

Answer 2

A lot of work on the evasiveness conjecture uses topology of simplicial complexes. Here is a bit of an overview of the evasiveness conjecture: Suppose we have a graph on $n$ vertices and we want to test whether it has some particular property, such as being disconnected, or not having a Hamiltonian path, or being $3$-colorable. For the purposes of this discussion, one should think of the graph as being given as an $n \times n$ binary matrix which says, for every pair of vertices, whether or not they are connected by an edge. We will be interested in the "query complexity" of these questions, which means how many entries of the matrix we have to look at. So we are to imagine that computation time is cheap for us, but looking at an edge to determine whether or not it exists, is expensive.

If you play around with graph algorithms from this perspective, you'll see that the worst case query complexity of most interesting graph properties is $\binom{n}{2}$: There is always some branch of the algorithm which has to look at every edge.

The evasiveness conjecture tries to make this precise: It says that any property $P$ of graphs which is

(1) invariant under permuting vertices

(2) monotone, meaning deleting edges from a graph which has property $P$ will preserve the truth of $P$ and

(3) true for the empty graph and false for the complete graph

has worst case query complexity $\binom{n}{2}$.

The properties of being disconnected, of not having a Hamiltonian path, and of being $3$-colorable, satisfy all these conditions (except that condition (3) fails for a few small $n$).

Kahn, Saks and Sturtevant considered the simplicial complex whose vertices were the $\binom{n}{2}$ potential graph edges and whose faces are the sets of edges making a graph with property $P$. Condition (2) says that this is a simplicial complex, condition (1) says that it has an action of $S_n$ on it. They showed that, if $P$ were a counterexample to the evasiveness conjecture, then this complex would be contractible, and they used theorems about fixed points for $S_n$ actions on contractible spaces to prove the evasiveness conjecture for $n$ a prime power.

I believe there has been a lot of work on this since then, using the topological approach. It's not a topic I've followed, but Kahn et. al.'s work has 48 citations in MathSciNet.