Skip to main content
Fixed some sentences
Source Link
ARG
  • 4.7k
  • 1
  • 26
  • 47

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. EDIT(EDIT: see explanation in J.W.'s answer below.)

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure" [EDIT: corrected, thanks to J.W.'s comment below]. Take an injective function $w$ from the set of edges $E$ to $[0,1]$. Construct a spanning treeLet $T_w$ as follows (ifbe the tree of minimal cost, if $w$ is thought of as the cost of an edge, this will be the tree of minimal cost). AnMany constructions are possible. For example, an edge $e$ belongs to $T_w$ if any path between its endpoints ($e$ excluded) contains an edge $e'$ with $w(e')>w(e)$.

Next consider $w$ given by independent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. EDIT: see explanation in answer below.

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure". Take an injective function $w$ from the set of edges $E$ to $[0,1]$. Construct a spanning tree $T_w$ as follows (if $w$ is thought of as the cost of an edge, this will be the tree of minimal cost). An edge $e$ belongs to $T_w$ if any path between its endpoints contains an edge $e'$ with $w(e')>w(e)$.

Next consider $w$ given by independent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. (EDIT: see explanation in J.W.'s answer below.)

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure" [EDIT: corrected, thanks to J.W.'s comment below]. Take an injective function $w$ from the set of edges $E$ to $[0,1]$. Let $T_w$ be the tree of minimal cost, if $w$ is thought of as the cost of an edge. Many constructions are possible. For example, an edge $e$ belongs to $T_w$ if any path between its endpoints ($e$ excluded) contains an edge $e'$ with $w(e')>w(e)$.

Next consider $w$ given by independent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

Corrected the definition of the minimal measure...
Source Link
ARG
  • 4.7k
  • 1
  • 26
  • 47

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. EDIT: see explanation in answer below.

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure". Take an injective function $w$ from the set of edges $E$ to $[0,1)$$[0,1]$. Pick $x \in [0,1]$ so that $\lbrace e \in E \mid w(e) <x \rbrace$ are the edges ofConstruct a spanning tree $T_w$ as follows (if $w$ is thought of as the cost of an edge, this iswill be the tree of minimal cost). Denote this treeAn edge $e$ belongs to $T_w$ if any path between its endpoints contains an edge $e'$ with $w(e')>w(e)$. 

Next consider $w$ given by i.i.d. functions with value uniformly inindependent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference].

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure". Take an injective function $w$ from the set of edges $E$ to $[0,1)$. Pick $x \in [0,1]$ so that $\lbrace e \in E \mid w(e) <x \rbrace$ are the edges of a spanning tree (if $w$ is thought of as the cost of an edge, this is the tree of minimal cost). Denote this tree $T_w$. Next consider $w$ given by i.i.d. functions with value uniformly in $[0,1]$. The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. EDIT: see explanation in answer below.

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure". Take an injective function $w$ from the set of edges $E$ to $[0,1]$. Construct a spanning tree $T_w$ as follows (if $w$ is thought of as the cost of an edge, this will be the tree of minimal cost). An edge $e$ belongs to $T_w$ if any path between its endpoints contains an edge $e'$ with $w(e')>w(e)$. 

Next consider $w$ given by independent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

Source Link
ARG
  • 4.7k
  • 1
  • 26
  • 47

Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference].

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure". Take an injective function $w$ from the set of edges $E$ to $[0,1)$. Pick $x \in [0,1]$ so that $\lbrace e \in E \mid w(e) <x \rbrace$ are the edges of a spanning tree (if $w$ is thought of as the cost of an edge, this is the tree of minimal cost). Denote this tree $T_w$. Next consider $w$ given by i.i.d. functions with value uniformly in $[0,1]$. The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.