1
$\begingroup$

Answer https://stackoverflow.com/a/26151549/1375882 suggests that Sperner's lemma can be used to prove the existence of index for the search Hamiltonian path in complete directed graph. But Sperner's lemma is about simplex, its triangulation and colouring. How such notions can be mapped to the complete graph with n-vertices?

$\endgroup$
1
$\begingroup$

Here is what it boils down to. There are $n$ vertices $v_1,\ldots,v_{n-1},v$. For each $i$, there is an edge either from $v$ to $v_i$ or from $v_i$ to $v$. We need to show that one of the following holds:

  • There is an edge from $v$ to $v_1$.
  • There is $i < n-1$ such that there are edges from $v_i$ to $v$ and from $v$ to $v_{i+1}$.
  • There is an edge from $v_{n-1}$ to $v$.

Let $x_i$ be a Boolean variable denoting that there is an edge from $v$ to $v_i$. Then we need to show that the following DNF is a tautology: $$ x_1 \lor (\lnot x_1 \land x_2) \lor \cdots \lor (\lnot x_{n-2} \land x_{n-1}) \lor \lnot x_{n-1}. $$ Hopefully you can manage to prove this yourself. It just states that if we have a string of 0s and 1s, then one of the following must happen:

  • The string starts with 1.
  • The string contains 01.
  • The string ends with 0.

The easiest way to see this is to prove the following:

If a binary string starts with 0 and ends with 1, it must contain 01.

This is just the trivial one-dimensional case of Sperner's lemma.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.