Skip to main content
3 of 3
Corrected idiotic mistake about number of functions
Vidit Nanda
  • 15.5k
  • 2
  • 63
  • 125

Uniformly sampling from the set of all simplicial maps

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$?

Vidit Nanda
  • 15.5k
  • 2
  • 63
  • 125