Mixing
Determine conditions on pn such that the probability that a random graph has at least one triangle goes to...
$begingroup$
I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $p_n$ such that the probability that $G(n, p_n)$ has at least one triangle goes to zero as $n → +∞$, also assuming that the probability that three vertices forms a triangle is $p_n^3$. I know I have to apply the first order method but I can't relate the theory with general properties.
triangles first-order-logic random-graphs
asked Feb 2 at 20:31
RampaRampa
212
$endgroup$
add a comment |
$begingroup$
I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $p_n$ such that the probability that $G(n, p_n)$ has at least one triangle goes to zero as $n → +∞$, also assuming that the probability that three vertices forms a triangle is $p_n^3$. I know I have to apply the first order method but I can't relate the theory with general properties.
triangles first-order-logic random-graphs
asked Feb 2 at 20:31
RampaRampa
212
$endgroup$
$begingroup$
Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"?
$endgroup$
– Misha Lavrov
Feb 3 at 0:36
add a comment |
$begingroup$
I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $p_n$ such that the probability that $G(n, p_n)$ has at least one triangle goes to zero as $n → +∞$, also assuming that the probability that three vertices forms a triangle is $p_n^3$. I know I have to apply the first order method but I can't relate the theory with general properties.
triangles first-order-logic random-graphs
asked Feb 2 at 20:31
RampaRampa
212
$endgroup$
I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $p_n$ such that the probability that $G(n, p_n)$ has at least one triangle goes to zero as $n → +∞$, also assuming that the probability that three vertices forms a triangle is $p_n^3$. I know I have to apply the first order method but I can't relate the theory with general properties.
triangles first-order-logic random-graphs
triangles first-order-logic random-graphs
asked Feb 2 at 20:31
RampaRampa
212
asked Feb 2 at 20:31
RampaRampa
212
edited Feb 2 at 20:39
Rampa
asked Feb 2 at 20:31
RampaRampa
212
asked Feb 2 at 20:31
RampaRampa
212
asked Feb 2 at 20:31
RampaRampa
212
212
$begingroup$
Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"?
$endgroup$
– Misha Lavrov
Feb 3 at 0:36
add a comment |
$begingroup$
Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"?
$endgroup$
– Misha Lavrov
Feb 3 at 0:36
$begingroup$
Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"?
$endgroup$
– Misha Lavrov
Feb 3 at 0:36
$begingroup$
Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"?
$endgroup$
– Misha Lavrov
Feb 3 at 0:36
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $T_n$ be the number of triangles in a $G(n,p_n)$ random graph. Then you should be able to get a formula for the expected number of triangles, $ET_n$. In order to ensure no triangles, or usually none, you should make (a) $ET _n$ large, or (b) $ET_n$ small.
Can you take it from there?
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
$endgroup$
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
add a comment |
$begingroup$
I don't know much about graph theory but you could work out the probability of that no triangle exists. Starting with one random point A and a random point B, the probability that no triangle exists of the form ABx is given by: $(1-p_n^3)^{n-2}$. Now pick a different point C and the probability that no triangle exists of the form ACx conditional on what we already know is given by $(1-p_n^3)^{n-3}$. Using this strategy you can calculate the probability of A not being in a triangle which will be of the order $(1-p_n^3)^{n^2}$. Can you continue?
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
$endgroup$
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3097764%2fdetermine-conditions-on-pn-such-that-the-probability-that-a-random-graph-has-at%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $T_n$ be the number of triangles in a $G(n,p_n)$ random graph. Then you should be able to get a formula for the expected number of triangles, $ET_n$. In order to ensure no triangles, or usually none, you should make (a) $ET _n$ large, or (b) $ET_n$ small.
Can you take it from there?
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
$endgroup$
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
add a comment |
$begingroup$
Let $T_n$ be the number of triangles in a $G(n,p_n)$ random graph. Then you should be able to get a formula for the expected number of triangles, $ET_n$. In order to ensure no triangles, or usually none, you should make (a) $ET _n$ large, or (b) $ET_n$ small.
Can you take it from there?
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
$endgroup$
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
add a comment |
$begingroup$
Let $T_n$ be the number of triangles in a $G(n,p_n)$ random graph. Then you should be able to get a formula for the expected number of triangles, $ET_n$. In order to ensure no triangles, or usually none, you should make (a) $ET _n$ large, or (b) $ET_n$ small.
Can you take it from there?
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
$endgroup$
Let $T_n$ be the number of triangles in a $G(n,p_n)$ random graph. Then you should be able to get a formula for the expected number of triangles, $ET_n$. In order to ensure no triangles, or usually none, you should make (a) $ET _n$ large, or (b) $ET_n$ small.
Can you take it from there?
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
answered Feb 2 at 20:47
kimchi loverkimchi lover
11.8k31229
11.8k31229
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
add a comment |
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
No I'm sorry. I can't relate the definition of first order methods to what you have said, but probably it's my fault.
$endgroup$
– Rampa
Feb 2 at 21:44
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
$begingroup$
Is courses.cs.washington.edu/courses/cse525/13sp/scribe/lec9.pdf anything like what you know?
$endgroup$
– kimchi lover
Feb 3 at 2:05
add a comment |
$begingroup$
I don't know much about graph theory but you could work out the probability of that no triangle exists. Starting with one random point A and a random point B, the probability that no triangle exists of the form ABx is given by: $(1-p_n^3)^{n-2}$. Now pick a different point C and the probability that no triangle exists of the form ACx conditional on what we already know is given by $(1-p_n^3)^{n-3}$. Using this strategy you can calculate the probability of A not being in a triangle which will be of the order $(1-p_n^3)^{n^2}$. Can you continue?
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
$endgroup$
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
add a comment |
$begingroup$
I don't know much about graph theory but you could work out the probability of that no triangle exists. Starting with one random point A and a random point B, the probability that no triangle exists of the form ABx is given by: $(1-p_n^3)^{n-2}$. Now pick a different point C and the probability that no triangle exists of the form ACx conditional on what we already know is given by $(1-p_n^3)^{n-3}$. Using this strategy you can calculate the probability of A not being in a triangle which will be of the order $(1-p_n^3)^{n^2}$. Can you continue?
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
$endgroup$
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
add a comment |
$begingroup$
I don't know much about graph theory but you could work out the probability of that no triangle exists. Starting with one random point A and a random point B, the probability that no triangle exists of the form ABx is given by: $(1-p_n^3)^{n-2}$. Now pick a different point C and the probability that no triangle exists of the form ACx conditional on what we already know is given by $(1-p_n^3)^{n-3}$. Using this strategy you can calculate the probability of A not being in a triangle which will be of the order $(1-p_n^3)^{n^2}$. Can you continue?
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
$endgroup$
I don't know much about graph theory but you could work out the probability of that no triangle exists. Starting with one random point A and a random point B, the probability that no triangle exists of the form ABx is given by: $(1-p_n^3)^{n-2}$. Now pick a different point C and the probability that no triangle exists of the form ACx conditional on what we already know is given by $(1-p_n^3)^{n-3}$. Using this strategy you can calculate the probability of A not being in a triangle which will be of the order $(1-p_n^3)^{n^2}$. Can you continue?
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
answered Feb 2 at 20:49
Stan TendijckStan Tendijck
2,248415
2,248415
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
add a comment |
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.)
$endgroup$
– Misha Lavrov
Feb 3 at 0:25
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_ncdotleft(1-(1-p_n^2)^{n-2}right) +(1-p_n)cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance.
$endgroup$
– Stan Tendijck
Feb 3 at 20:51
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
$begingroup$
But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover.
$endgroup$
– Stan Tendijck
Feb 3 at 20:58
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3097764%2fdetermine-conditions-on-pn-such-that-the-probability-that-a-random-graph-has-at%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"?
$endgroup$
– Misha Lavrov
Feb 3 at 0:36