Mixing
Almost every graph has every vertex in a triangle?
$begingroup$
I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$).
A property of almost every graph is a property $A$ such that $lim_{n to infty} mathbb{P}(G(n,p)text{ has } A) = 1$.
The question I wish to solve is the following: is it the case that for almost every graph, every vertex is contained in a triangle?
My attempt: I suspect that this is a property of almost every graph, because $G(n,p)$ has $binom{n}{2}p sim n^2p$ edges on average, which is much more than the number of edges you would need to have every vertex be in a triangle $(leq 3n)$. It would suffice to prove the probability that some vertex is not in a triangle goes to zero. Call such a vertex a bad vertex. We have
begin{align*}
mathbb{P}(text{there exists a bad vertex}) &leq mathbb{E}[text{number of bad vertices}]\
&= sum_{v} mathbb{P}(v text{ is a bad vertex})\
&= n mathbb{P}(vtext{ is a bad vertex}).
end{align*}
So I would need an upper bound on $mathbb{P}(vtext{ is a bad vertex})$ that is $o(1/n$). So far I've been unable to come up with a useful bound. Any advice would be appreciated.
probability random-graphs
asked Jan 22 at 21:21
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$).
A property of almost every graph is a property $A$ such that $lim_{n to infty} mathbb{P}(G(n,p)text{ has } A) = 1$.
The question I wish to solve is the following: is it the case that for almost every graph, every vertex is contained in a triangle?
My attempt: I suspect that this is a property of almost every graph, because $G(n,p)$ has $binom{n}{2}p sim n^2p$ edges on average, which is much more than the number of edges you would need to have every vertex be in a triangle $(leq 3n)$. It would suffice to prove the probability that some vertex is not in a triangle goes to zero. Call such a vertex a bad vertex. We have
begin{align*}
mathbb{P}(text{there exists a bad vertex}) &leq mathbb{E}[text{number of bad vertices}]\
&= sum_{v} mathbb{P}(v text{ is a bad vertex})\
&= n mathbb{P}(vtext{ is a bad vertex}).
end{align*}
So I would need an upper bound on $mathbb{P}(vtext{ is a bad vertex})$ that is $o(1/n$). So far I've been unable to come up with a useful bound. Any advice would be appreciated.
probability random-graphs
asked Jan 22 at 21:21
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$).
A property of almost every graph is a property $A$ such that $lim_{n to infty} mathbb{P}(G(n,p)text{ has } A) = 1$.
The question I wish to solve is the following: is it the case that for almost every graph, every vertex is contained in a triangle?
My attempt: I suspect that this is a property of almost every graph, because $G(n,p)$ has $binom{n}{2}p sim n^2p$ edges on average, which is much more than the number of edges you would need to have every vertex be in a triangle $(leq 3n)$. It would suffice to prove the probability that some vertex is not in a triangle goes to zero. Call such a vertex a bad vertex. We have
begin{align*}
mathbb{P}(text{there exists a bad vertex}) &leq mathbb{E}[text{number of bad vertices}]\
&= sum_{v} mathbb{P}(v text{ is a bad vertex})\
&= n mathbb{P}(vtext{ is a bad vertex}).
end{align*}
So I would need an upper bound on $mathbb{P}(vtext{ is a bad vertex})$ that is $o(1/n$). So far I've been unable to come up with a useful bound. Any advice would be appreciated.
probability random-graphs
asked Jan 22 at 21:21
kccukccu
10.6k11229
$endgroup$
I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$).
A property of almost every graph is a property $A$ such that $lim_{n to infty} mathbb{P}(G(n,p)text{ has } A) = 1$.
The question I wish to solve is the following: is it the case that for almost every graph, every vertex is contained in a triangle?
My attempt: I suspect that this is a property of almost every graph, because $G(n,p)$ has $binom{n}{2}p sim n^2p$ edges on average, which is much more than the number of edges you would need to have every vertex be in a triangle $(leq 3n)$. It would suffice to prove the probability that some vertex is not in a triangle goes to zero. Call such a vertex a bad vertex. We have
begin{align*}
mathbb{P}(text{there exists a bad vertex}) &leq mathbb{E}[text{number of bad vertices}]\
&= sum_{v} mathbb{P}(v text{ is a bad vertex})\
&= n mathbb{P}(vtext{ is a bad vertex}).
end{align*}
So I would need an upper bound on $mathbb{P}(vtext{ is a bad vertex})$ that is $o(1/n$). So far I've been unable to come up with a useful bound. Any advice would be appreciated.
probability random-graphs
probability random-graphs
asked Jan 22 at 21:21
kccukccu
10.6k11229
asked Jan 22 at 21:21
kccukccu
10.6k11229
asked Jan 22 at 21:21
kccukccu
10.6k11229
asked Jan 22 at 21:21
kccukccu
10.6k11229
asked Jan 22 at 21:21
kccukccu
10.6k11229
10.6k11229
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A given vertex is a member of ${n-1 choose 2} sim frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(frac 12n^2)}$, which duly goes to $0$ as $n to infty$
If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
$endgroup$
1
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3083713%2falmost-every-graph-has-every-vertex-in-a-triangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A given vertex is a member of ${n-1 choose 2} sim frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(frac 12n^2)}$, which duly goes to $0$ as $n to infty$
If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
$endgroup$
1
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
add a comment |
$begingroup$
A given vertex is a member of ${n-1 choose 2} sim frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(frac 12n^2)}$, which duly goes to $0$ as $n to infty$
If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
$endgroup$
1
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
add a comment |
$begingroup$
A given vertex is a member of ${n-1 choose 2} sim frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(frac 12n^2)}$, which duly goes to $0$ as $n to infty$
If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
$endgroup$
A given vertex is a member of ${n-1 choose 2} sim frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(frac 12n^2)}$, which duly goes to $0$ as $n to infty$
If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
answered Jan 22 at 21:32
Ross MillikanRoss Millikan
299k24200374
299k24200374
1
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
add a comment |
1
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
1
1
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Thank you! I started down that pathway but got stuck on the triangles not actually being independent.
$endgroup$
– kccu
Jan 22 at 21:37
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ...
$endgroup$
– Hagen von Eitzen
Jan 22 at 21:39
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
@HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there.
$endgroup$
– Ross Millikan
Jan 22 at 21:44
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
$begingroup$
Alternatively, we could separately argue that, for example (1) every vertex has at least $frac n3$ neighbors w.h.p., and (2) there is no independent set of size $frac n3$ w.h.p.
$endgroup$
– Misha Lavrov
Jan 23 at 0:13
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%2f3083713%2falmost-every-graph-has-every-vertex-in-a-triangle%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
