Probability that a graph is bipartite
$begingroup$
Given the empty graph on $n$ vertices, we add $m$ of the $binom{n}{2}$ possible edges, uniformly at random.
What is the probability that the resulting graph is bipartite (equivalently, contains no odd cycles) ?
Alternative formulation: In the random graph model $G(n,m)$, how many of the $binom{binom{n}{2}}{m}$ graphs are bipartite ?
probability graph-theory random-graphs
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
$endgroup$
add a comment |
$begingroup$
Given the empty graph on $n$ vertices, we add $m$ of the $binom{n}{2}$ possible edges, uniformly at random.
What is the probability that the resulting graph is bipartite (equivalently, contains no odd cycles) ?
Alternative formulation: In the random graph model $G(n,m)$, how many of the $binom{binom{n}{2}}{m}$ graphs are bipartite ?
probability graph-theory random-graphs
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
$endgroup$
1
$begingroup$
This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix.
$endgroup$
– Sandeep Silwal
Dec 25 '18 at 15:39
add a comment |
$begingroup$
Given the empty graph on $n$ vertices, we add $m$ of the $binom{n}{2}$ possible edges, uniformly at random.
What is the probability that the resulting graph is bipartite (equivalently, contains no odd cycles) ?
Alternative formulation: In the random graph model $G(n,m)$, how many of the $binom{binom{n}{2}}{m}$ graphs are bipartite ?
probability graph-theory random-graphs
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
$endgroup$
Given the empty graph on $n$ vertices, we add $m$ of the $binom{n}{2}$ possible edges, uniformly at random.
What is the probability that the resulting graph is bipartite (equivalently, contains no odd cycles) ?
Alternative formulation: In the random graph model $G(n,m)$, how many of the $binom{binom{n}{2}}{m}$ graphs are bipartite ?
probability graph-theory random-graphs
probability graph-theory random-graphs
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
asked Dec 25 '18 at 9:09
TeddyTeddy
1,231817
1,231817
1
$begingroup$
This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix.
$endgroup$
– Sandeep Silwal
Dec 25 '18 at 15:39
add a comment |
1
$begingroup$
This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix.
$endgroup$
– Sandeep Silwal
Dec 25 '18 at 15:39
1
1
$begingroup$
This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix.
$endgroup$
– Sandeep Silwal
Dec 25 '18 at 15:39
$begingroup$
This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix.
$endgroup$
– Sandeep Silwal
Dec 25 '18 at 15:39
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
When $m ll n$, the probability is very high, since with high probability (that is, with probability tending to $1$) $G(n,m)$ is a forest - and all forests are bipartite.
When $m = frac12 cn$ (where $G(n,m)$ is very like a binomial random graph with edge probability $frac cn$) much depends on the value of $c$. If $0 < c < 1$, we are in the subcritical phase where, with high probability, the largest component of the random graph has $O(log n)$ vertices. Therefore we may determine if the graph is bipartite by counting the small cycles.
The expected number of cycles of length $k$ is asymptotically $frac{c^k}{2k}$, obtained by multiplying together the following factors:
- We have $binom nk sim frac{n^k}{k!}$ ways to choose $k$ vertices.
- There are $frac{k!}{2k}$ ways to choose a cycle on those $k$ vertices.
- There is a probability of $binom{binom n2-k}{m-k} / binom{binom n2}{m} sim frac{c^k}{n^k}$ that all edges in that cycle are present. (This is the approximation that requires $k$ to be small; here, we have $k = O(log n)$, but any $k = o(n)$ would do.)
It can be shown by the method of moments that the number of cycles of length $k$ is asymptotically Poisson (explained by the intuition that cycles arise from many nearly-independent events which are individually very unlikely). So the probability that there are no cycles of length $k$ is $e^{-c^k/2k}$ in the limit.
It would need more justification, but it is probably true that these events are asymptotically independent as $n to infty$. This means that the probability that $G(n,m)$ is bipartite is obtained by taking the product of these probabilities
$$
expleft(-frac{c^3}{6} - frac{c^5}{10} - frac{c^7}{14} - dotsright) = expleft(frac12c - frac12 operatorname{arctanh} cright).
$$
This probability tends to $0$ as $c to 1$, and so by monotonicity we see that when $m = frac12cn$ and $c>1$, the graph is not bipartite with high probability.
Intuitively, at this point, we are in the supercritical phase; the number of cycles (some of them quite long) tends to infinity, and since there is no particular reason forcing them to be even, it is likely that many of them are odd.
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
1
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
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%2f3051954%2fprobability-that-a-graph-is-bipartite%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$
When $m ll n$, the probability is very high, since with high probability (that is, with probability tending to $1$) $G(n,m)$ is a forest - and all forests are bipartite.
When $m = frac12 cn$ (where $G(n,m)$ is very like a binomial random graph with edge probability $frac cn$) much depends on the value of $c$. If $0 < c < 1$, we are in the subcritical phase where, with high probability, the largest component of the random graph has $O(log n)$ vertices. Therefore we may determine if the graph is bipartite by counting the small cycles.
The expected number of cycles of length $k$ is asymptotically $frac{c^k}{2k}$, obtained by multiplying together the following factors:
- We have $binom nk sim frac{n^k}{k!}$ ways to choose $k$ vertices.
- There are $frac{k!}{2k}$ ways to choose a cycle on those $k$ vertices.
- There is a probability of $binom{binom n2-k}{m-k} / binom{binom n2}{m} sim frac{c^k}{n^k}$ that all edges in that cycle are present. (This is the approximation that requires $k$ to be small; here, we have $k = O(log n)$, but any $k = o(n)$ would do.)
It can be shown by the method of moments that the number of cycles of length $k$ is asymptotically Poisson (explained by the intuition that cycles arise from many nearly-independent events which are individually very unlikely). So the probability that there are no cycles of length $k$ is $e^{-c^k/2k}$ in the limit.
It would need more justification, but it is probably true that these events are asymptotically independent as $n to infty$. This means that the probability that $G(n,m)$ is bipartite is obtained by taking the product of these probabilities
$$
expleft(-frac{c^3}{6} - frac{c^5}{10} - frac{c^7}{14} - dotsright) = expleft(frac12c - frac12 operatorname{arctanh} cright).
$$
This probability tends to $0$ as $c to 1$, and so by monotonicity we see that when $m = frac12cn$ and $c>1$, the graph is not bipartite with high probability.
Intuitively, at this point, we are in the supercritical phase; the number of cycles (some of them quite long) tends to infinity, and since there is no particular reason forcing them to be even, it is likely that many of them are odd.
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
1
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
add a comment |
$begingroup$
When $m ll n$, the probability is very high, since with high probability (that is, with probability tending to $1$) $G(n,m)$ is a forest - and all forests are bipartite.
When $m = frac12 cn$ (where $G(n,m)$ is very like a binomial random graph with edge probability $frac cn$) much depends on the value of $c$. If $0 < c < 1$, we are in the subcritical phase where, with high probability, the largest component of the random graph has $O(log n)$ vertices. Therefore we may determine if the graph is bipartite by counting the small cycles.
The expected number of cycles of length $k$ is asymptotically $frac{c^k}{2k}$, obtained by multiplying together the following factors:
- We have $binom nk sim frac{n^k}{k!}$ ways to choose $k$ vertices.
- There are $frac{k!}{2k}$ ways to choose a cycle on those $k$ vertices.
- There is a probability of $binom{binom n2-k}{m-k} / binom{binom n2}{m} sim frac{c^k}{n^k}$ that all edges in that cycle are present. (This is the approximation that requires $k$ to be small; here, we have $k = O(log n)$, but any $k = o(n)$ would do.)
It can be shown by the method of moments that the number of cycles of length $k$ is asymptotically Poisson (explained by the intuition that cycles arise from many nearly-independent events which are individually very unlikely). So the probability that there are no cycles of length $k$ is $e^{-c^k/2k}$ in the limit.
It would need more justification, but it is probably true that these events are asymptotically independent as $n to infty$. This means that the probability that $G(n,m)$ is bipartite is obtained by taking the product of these probabilities
$$
expleft(-frac{c^3}{6} - frac{c^5}{10} - frac{c^7}{14} - dotsright) = expleft(frac12c - frac12 operatorname{arctanh} cright).
$$
This probability tends to $0$ as $c to 1$, and so by monotonicity we see that when $m = frac12cn$ and $c>1$, the graph is not bipartite with high probability.
Intuitively, at this point, we are in the supercritical phase; the number of cycles (some of them quite long) tends to infinity, and since there is no particular reason forcing them to be even, it is likely that many of them are odd.
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
1
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
add a comment |
$begingroup$
When $m ll n$, the probability is very high, since with high probability (that is, with probability tending to $1$) $G(n,m)$ is a forest - and all forests are bipartite.
When $m = frac12 cn$ (where $G(n,m)$ is very like a binomial random graph with edge probability $frac cn$) much depends on the value of $c$. If $0 < c < 1$, we are in the subcritical phase where, with high probability, the largest component of the random graph has $O(log n)$ vertices. Therefore we may determine if the graph is bipartite by counting the small cycles.
The expected number of cycles of length $k$ is asymptotically $frac{c^k}{2k}$, obtained by multiplying together the following factors:
- We have $binom nk sim frac{n^k}{k!}$ ways to choose $k$ vertices.
- There are $frac{k!}{2k}$ ways to choose a cycle on those $k$ vertices.
- There is a probability of $binom{binom n2-k}{m-k} / binom{binom n2}{m} sim frac{c^k}{n^k}$ that all edges in that cycle are present. (This is the approximation that requires $k$ to be small; here, we have $k = O(log n)$, but any $k = o(n)$ would do.)
It can be shown by the method of moments that the number of cycles of length $k$ is asymptotically Poisson (explained by the intuition that cycles arise from many nearly-independent events which are individually very unlikely). So the probability that there are no cycles of length $k$ is $e^{-c^k/2k}$ in the limit.
It would need more justification, but it is probably true that these events are asymptotically independent as $n to infty$. This means that the probability that $G(n,m)$ is bipartite is obtained by taking the product of these probabilities
$$
expleft(-frac{c^3}{6} - frac{c^5}{10} - frac{c^7}{14} - dotsright) = expleft(frac12c - frac12 operatorname{arctanh} cright).
$$
This probability tends to $0$ as $c to 1$, and so by monotonicity we see that when $m = frac12cn$ and $c>1$, the graph is not bipartite with high probability.
Intuitively, at this point, we are in the supercritical phase; the number of cycles (some of them quite long) tends to infinity, and since there is no particular reason forcing them to be even, it is likely that many of them are odd.
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
When $m ll n$, the probability is very high, since with high probability (that is, with probability tending to $1$) $G(n,m)$ is a forest - and all forests are bipartite.
When $m = frac12 cn$ (where $G(n,m)$ is very like a binomial random graph with edge probability $frac cn$) much depends on the value of $c$. If $0 < c < 1$, we are in the subcritical phase where, with high probability, the largest component of the random graph has $O(log n)$ vertices. Therefore we may determine if the graph is bipartite by counting the small cycles.
The expected number of cycles of length $k$ is asymptotically $frac{c^k}{2k}$, obtained by multiplying together the following factors:
- We have $binom nk sim frac{n^k}{k!}$ ways to choose $k$ vertices.
- There are $frac{k!}{2k}$ ways to choose a cycle on those $k$ vertices.
- There is a probability of $binom{binom n2-k}{m-k} / binom{binom n2}{m} sim frac{c^k}{n^k}$ that all edges in that cycle are present. (This is the approximation that requires $k$ to be small; here, we have $k = O(log n)$, but any $k = o(n)$ would do.)
It can be shown by the method of moments that the number of cycles of length $k$ is asymptotically Poisson (explained by the intuition that cycles arise from many nearly-independent events which are individually very unlikely). So the probability that there are no cycles of length $k$ is $e^{-c^k/2k}$ in the limit.
It would need more justification, but it is probably true that these events are asymptotically independent as $n to infty$. This means that the probability that $G(n,m)$ is bipartite is obtained by taking the product of these probabilities
$$
expleft(-frac{c^3}{6} - frac{c^5}{10} - frac{c^7}{14} - dotsright) = expleft(frac12c - frac12 operatorname{arctanh} cright).
$$
This probability tends to $0$ as $c to 1$, and so by monotonicity we see that when $m = frac12cn$ and $c>1$, the graph is not bipartite with high probability.
Intuitively, at this point, we are in the supercritical phase; the number of cycles (some of them quite long) tends to infinity, and since there is no particular reason forcing them to be even, it is likely that many of them are odd.
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
edited Dec 28 '18 at 15:55
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
answered Dec 26 '18 at 22:18
Misha LavrovMisha Lavrov
47.6k657107
47.6k657107
1
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
add a comment |
1
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
1
1
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $binom{binom{n}{2}-k}{m-k}$, correct ?
$endgroup$
– Teddy
Dec 27 '18 at 8:16
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
@Teddy It should, yes. Thank you for the correction. With $k = O(log n)$, the approximation holds either way.
$endgroup$
– Misha Lavrov
Dec 27 '18 at 16:11
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
$begingroup$
(The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.)
$endgroup$
– Misha Lavrov
Dec 27 '18 at 19:28
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%2f3051954%2fprobability-that-a-graph-is-bipartite%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
1
$begingroup$
This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix.
$endgroup$
– Sandeep Silwal
Dec 25 '18 at 15:39