Mixing
Probability of having a path connecting clusters of random graphs
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Construct a graph $H$ with $3n$ nodes in this way:
- Create three $G(n, p)$ graphs on a line, each with $pn choose 2$ many edges within each cluster.
- For any node-pair in the neighboring clustering, add edges between them with probability $q$. Hence we'd end up with $qn^2$ many nodes collecting the nodes of the neighboring clusters.
Question: what is the probability that we'd have at least a path connecting the left-most cluster to the right-most cluster, in terms of $p$, $q$, and $n$.
probability probability-distributions graph-theory random-graphs
asked Jul 23 at 0:21
Daniel
1,059921
add a comment |Â
up vote
1
down vote
favorite
Construct a graph $H$ with $3n$ nodes in this way:
- Create three $G(n, p)$ graphs on a line, each with $pn choose 2$ many edges within each cluster.
- For any node-pair in the neighboring clustering, add edges between them with probability $q$. Hence we'd end up with $qn^2$ many nodes collecting the nodes of the neighboring clusters.
Question: what is the probability that we'd have at least a path connecting the left-most cluster to the right-most cluster, in terms of $p$, $q$, and $n$.
probability probability-distributions graph-theory random-graphs
asked Jul 23 at 0:21
Daniel
1,059921
So you need each subgraph being a connected graph, and there exist at least one edge connecting subgraph 1 to subgraph 2, and subgraph 2 to subgraph 3?
– BGM
Jul 23 at 3:28
Your second bullet point makes it unclear whether you're creating edges independently with probabilities $p$ and $q$, respectively, or selecting random subsets of $pbinom n2$ and $qn^2$ edges, respectively. Are you only interested in asymptotic results where this might not matter?
– joriki
Jul 23 at 3:43
@BGM yup, correct.
– Daniel
Jul 23 at 18:12
@joriki the former is correct: creating edges independently with probabilities $p$ and $q$
– Daniel
Jul 23 at 18:13
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Construct a graph $H$ with $3n$ nodes in this way:
- Create three $G(n, p)$ graphs on a line, each with $pn choose 2$ many edges within each cluster.
- For any node-pair in the neighboring clustering, add edges between them with probability $q$. Hence we'd end up with $qn^2$ many nodes collecting the nodes of the neighboring clusters.
Question: what is the probability that we'd have at least a path connecting the left-most cluster to the right-most cluster, in terms of $p$, $q$, and $n$.
probability probability-distributions graph-theory random-graphs
asked Jul 23 at 0:21
Daniel
1,059921
Construct a graph $H$ with $3n$ nodes in this way:
- Create three $G(n, p)$ graphs on a line, each with $pn choose 2$ many edges within each cluster.
- For any node-pair in the neighboring clustering, add edges between them with probability $q$. Hence we'd end up with $qn^2$ many nodes collecting the nodes of the neighboring clusters.
Question: what is the probability that we'd have at least a path connecting the left-most cluster to the right-most cluster, in terms of $p$, $q$, and $n$.
probability probability-distributions graph-theory random-graphs
asked Jul 23 at 0:21
Daniel
1,059921
asked Jul 23 at 0:21
Daniel
1,059921
asked Jul 23 at 0:21
Daniel
1,059921
asked Jul 23 at 0:21
Daniel
1,059921
1,059921
So you need each subgraph being a connected graph, and there exist at least one edge connecting subgraph 1 to subgraph 2, and subgraph 2 to subgraph 3?
– BGM
Jul 23 at 3:28
Your second bullet point makes it unclear whether you're creating edges independently with probabilities $p$ and $q$, respectively, or selecting random subsets of $pbinom n2$ and $qn^2$ edges, respectively. Are you only interested in asymptotic results where this might not matter?
– joriki
Jul 23 at 3:43
@BGM yup, correct.
– Daniel
Jul 23 at 18:12
@joriki the former is correct: creating edges independently with probabilities $p$ and $q$
– Daniel
Jul 23 at 18:13
add a comment |Â
So you need each subgraph being a connected graph, and there exist at least one edge connecting subgraph 1 to subgraph 2, and subgraph 2 to subgraph 3?
– BGM
Jul 23 at 3:28
Your second bullet point makes it unclear whether you're creating edges independently with probabilities $p$ and $q$, respectively, or selecting random subsets of $pbinom n2$ and $qn^2$ edges, respectively. Are you only interested in asymptotic results where this might not matter?
– joriki
Jul 23 at 3:43
@BGM yup, correct.
– Daniel
Jul 23 at 18:12
@joriki the former is correct: creating edges independently with probabilities $p$ and $q$
– Daniel
Jul 23 at 18:13
So you need each subgraph being a connected graph, and there exist at least one edge connecting subgraph 1 to subgraph 2, and subgraph 2 to subgraph 3?
– BGM
Jul 23 at 3:28
So you need each subgraph being a connected graph, and there exist at least one edge connecting subgraph 1 to subgraph 2, and subgraph 2 to subgraph 3?
– BGM
Jul 23 at 3:28
Your second bullet point makes it unclear whether you're creating edges independently with probabilities $p$ and $q$, respectively, or selecting random subsets of $pbinom n2$ and $qn^2$ edges, respectively. Are you only interested in asymptotic results where this might not matter?
– joriki
Jul 23 at 3:43
Your second bullet point makes it unclear whether you're creating edges independently with probabilities $p$ and $q$, respectively, or selecting random subsets of $pbinom n2$ and $qn^2$ edges, respectively. Are you only interested in asymptotic results where this might not matter?
– joriki
Jul 23 at 3:43
@BGM yup, correct.
– Daniel
Jul 23 at 18:12
@BGM yup, correct.
– Daniel
Jul 23 at 18:12
@joriki the former is correct: creating edges independently with probabilities $p$ and $q$
– Daniel
Jul 23 at 18:13
@joriki the former is correct: creating edges independently with probabilities $p$ and $q$
– Daniel
Jul 23 at 18:13
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859892%2fprobability-of-having-a-path-connecting-clusters-of-random-graphs%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
So you need each subgraph being a connected graph, and there exist at least one edge connecting subgraph 1 to subgraph 2, and subgraph 2 to subgraph 3?
– BGM
Jul 23 at 3:28
Your second bullet point makes it unclear whether you're creating edges independently with probabilities $p$ and $q$, respectively, or selecting random subsets of $pbinom n2$ and $qn^2$ edges, respectively. Are you only interested in asymptotic results where this might not matter?
– joriki
Jul 23 at 3:43
@BGM yup, correct.
– Daniel
Jul 23 at 18:12
@joriki the former is correct: creating edges independently with probabilities $p$ and $q$
– Daniel
Jul 23 at 18:13