6
$\begingroup$

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.

How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial maps $K \to L$?

Recall that such a map must send vertices $K_0$ of $K$ to vertices $L_0$ of $L$ so that simplices map into simplices. Various inefficient strategies might come to mind: for instance, you might

  1. pre-compute all simplicial maps and choose one uniformly (there can't be more than $|L_0|^{|K_0|}$ of them), or
  2. try to randomly build partial simplicial maps from subsets of $K_0$ to those of $L_0$ and backtrack whenever you can't extend the existing assignments to a full simplicial map.
  3. something else?

But surely this is a well-studied combinatorial/algorithmic problem and there are slick strategies! If it helps, my main interest is in the following sub-question

How does one uniformly sample from the set of simplicial endomorphisms $K \to K$?

Improve this question
$\endgroup$
3
  • $\begingroup$ Sometimes people use the Metropolis-Hastings algorithm --- en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm). Not at all sure it applies here. $\endgroup$
    – Benjamin Young
    Commented Dec 13, 2013 at 4:04
  • $\begingroup$ That seems tricky even for graphs. Have you looked this special case first? $\endgroup$
    – Benoît Kloeckner
    Commented Dec 13, 2013 at 9:32
  • $\begingroup$ @BenoîtKloeckner Not yet. I was discouraged by the fact that simplicial maps don't restrict to simple graph homomorphisms on the 1-skeleta because an entire edge can map into a single vertex. But thank you for the suggestion, I will think about it! $\endgroup$
    – Vidit Nanda
    Commented Dec 13, 2013 at 16:12

0

Reset to default

You must log in to answer this question.