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

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 $|K_0| \cdot |L_0|!$$|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$?

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 $|K_0| \cdot |L_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$?

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

clarified title
Link
Vidit Nanda
  • 15.5k
  • 2
  • 63
  • 125

Uniformly sampling from the set of all simplicial maps

Source Link
Vidit Nanda
  • 15.5k
  • 2
  • 63
  • 125

Uniformly sampling 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 $|K_0| \cdot |L_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$?