I'd like to understand the following random graph process. I'm not sure if it's difficult or straightforward, so apologies if this is below the level of mathoverflow, but I've gotten no response on math.stackexchange. Any pointers to useful references will also be appreciated.

The process works as follows: we have a set of vertices, $V$, and a set of colors, $C$, and we are going to build a digraph such that each edge has a color and each vertex has at most one outgoing edge of each color. Pick a starting vertex $v_0$, at random. At each step, whatever the current vertex is, say $v_i$, pick a color $c$ at random and a vertex $v_{i+1}$ uniformly among those vertices which do not have an outgoing edge of color $c$ to a vertex other than $v_i$. Then if there isn't already, add an edge of color $c$ from $v_{i+1}$ to $v_i$ and make $v_{i+1}$ the new current vertex.

For a given set of vertices and colors and number of steps, each allowable graph has some probability of occuring, and I'd like to understand in particular how far this probability is from being uniform on allowable graphs.

  • $\begingroup$ Not sure this quite rises to the level of "community norm", but in my experience people normally link to the math.SE version when they cross-post here. $\endgroup$ – benblumsmith Sep 27 '18 at 0:32
  • $\begingroup$ To be clear, if $v_{i+1}$ does have an edge of color $c$ to $v_i$, then it can be chosen, and in this case one just moves to $v_{i+1}$ without adding an edge? $\endgroup$ – benblumsmith Sep 27 '18 at 0:35
  • $\begingroup$ Yes, if there is an existing edge, you can use it to move from $v_i$ to $v_{i+1}$, but you don't add another edge. The original question is at math.stackexchange.com/questions/2930986/a-random-graph-process $\endgroup$ – manzana Sep 27 '18 at 0:52
  • $\begingroup$ Here are some suggestions regarding cross-posts between MO and ME meta.mathoverflow.net/a/2638 $\endgroup$ – j.c. Sep 27 '18 at 5:46

Your Answer

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

Browse other questions tagged or ask your own question.