What is the probability that a random $ntimes n$ bipartite graph has an isolated vertex?
Clash Royale CLAN TAG#URR8PPP
up vote
10
down vote
favorite
By a random $ntimes n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$.
I want to find the probability that such a graph contains an isolated vertex.
Let $X$ and $Y$ be the vertex classes. I can calculate the probability that $X$ contains an isolated vertex by considering one vertex first and using the fact that vertices in $X$ are independent.
But I don't know how to calculate the probability that $Xcup Y$ contains an isolated vertex. Can someone help? Thanks!
graph-theory inclusion-exclusion random-graphs
edited Mar 27 '16 at 7:22
joriki
168k10181337
asked Apr 22 '13 at 23:27
Spook
2,2021033
add a comment |Â
up vote
10
down vote
favorite
By a random $ntimes n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$.
I want to find the probability that such a graph contains an isolated vertex.
Let $X$ and $Y$ be the vertex classes. I can calculate the probability that $X$ contains an isolated vertex by considering one vertex first and using the fact that vertices in $X$ are independent.
But I don't know how to calculate the probability that $Xcup Y$ contains an isolated vertex. Can someone help? Thanks!
graph-theory inclusion-exclusion random-graphs
edited Mar 27 '16 at 7:22
joriki
168k10181337
asked Apr 22 '13 at 23:27
Spook
2,2021033
2
The same question was asked years ago: Isolated vertex probabilities for different random graphs, but it doesn't yet have a correct answer.
– Kundor
Apr 24 '13 at 19:34
add a comment |Â
up vote
10
down vote
favorite
up vote
10
down vote
favorite
By a random $ntimes n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$.
I want to find the probability that such a graph contains an isolated vertex.
Let $X$ and $Y$ be the vertex classes. I can calculate the probability that $X$ contains an isolated vertex by considering one vertex first and using the fact that vertices in $X$ are independent.
But I don't know how to calculate the probability that $Xcup Y$ contains an isolated vertex. Can someone help? Thanks!
graph-theory inclusion-exclusion random-graphs
edited Mar 27 '16 at 7:22
joriki
168k10181337
asked Apr 22 '13 at 23:27
Spook
2,2021033
By a random $ntimes n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$.
I want to find the probability that such a graph contains an isolated vertex.
Let $X$ and $Y$ be the vertex classes. I can calculate the probability that $X$ contains an isolated vertex by considering one vertex first and using the fact that vertices in $X$ are independent.
But I don't know how to calculate the probability that $Xcup Y$ contains an isolated vertex. Can someone help? Thanks!
graph-theory inclusion-exclusion random-graphs
graph-theory inclusion-exclusion random-graphs
edited Mar 27 '16 at 7:22
joriki
168k10181337
asked Apr 22 '13 at 23:27
Spook
2,2021033
edited Mar 27 '16 at 7:22
joriki
168k10181337
asked Apr 22 '13 at 23:27
Spook
2,2021033
edited Mar 27 '16 at 7:22
joriki
168k10181337
edited Mar 27 '16 at 7:22
joriki
168k10181337
edited Mar 27 '16 at 7:22
joriki
168k10181337
168k10181337
asked Apr 22 '13 at 23:27
Spook
2,2021033
asked Apr 22 '13 at 23:27
Spook
2,2021033
asked Apr 22 '13 at 23:27
Spook
2,2021033
2,2021033
2
The same question was asked years ago: Isolated vertex probabilities for different random graphs, but it doesn't yet have a correct answer.
– Kundor
Apr 24 '13 at 19:34
add a comment |Â
2
The same question was asked years ago: Isolated vertex probabilities for different random graphs, but it doesn't yet have a correct answer.
– Kundor
Apr 24 '13 at 19:34
2
2
The same question was asked years ago: Isolated vertex probabilities for different random graphs, but it doesn't yet have a correct answer.
– Kundor
Apr 24 '13 at 19:34
The same question was asked years ago: Isolated vertex probabilities for different random graphs, but it doesn't yet have a correct answer.
– Kundor
Apr 24 '13 at 19:34
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
This can be done using inclusion/exclusion. We have $n+n$ conditions for the individual vertices being isolated. There are $binom nkbinom nl$ combinations of these conditions that require $k$ particular vertices in $X$ and $l$ particular vertices in $Y$ to be isolated, and the probability for this is $q^kn+ln-kl$, with $q=1-p$. Thus by inclusion/exclusion the desired probability that at least one vertex is isolated is
beginalign
&1-sum_k=0^nsum_l=0^n(-1)^k+lbinom nkbinom nlq^kn+ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knsum_l=0^n(-1)^lbinom nlq^ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knleft(1-q^n-kright)^n\
=&1-sum_k=0^n(-1)^kbinom nkleft(q^k-q^nright)^n;.
endalign
answered Mar 7 '16 at 12:55
joriki
168k10181337
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
This can be done using inclusion/exclusion. We have $n+n$ conditions for the individual vertices being isolated. There are $binom nkbinom nl$ combinations of these conditions that require $k$ particular vertices in $X$ and $l$ particular vertices in $Y$ to be isolated, and the probability for this is $q^kn+ln-kl$, with $q=1-p$. Thus by inclusion/exclusion the desired probability that at least one vertex is isolated is
beginalign
&1-sum_k=0^nsum_l=0^n(-1)^k+lbinom nkbinom nlq^kn+ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knsum_l=0^n(-1)^lbinom nlq^ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knleft(1-q^n-kright)^n\
=&1-sum_k=0^n(-1)^kbinom nkleft(q^k-q^nright)^n;.
endalign
answered Mar 7 '16 at 12:55
joriki
168k10181337
add a comment |Â
up vote
2
down vote
This can be done using inclusion/exclusion. We have $n+n$ conditions for the individual vertices being isolated. There are $binom nkbinom nl$ combinations of these conditions that require $k$ particular vertices in $X$ and $l$ particular vertices in $Y$ to be isolated, and the probability for this is $q^kn+ln-kl$, with $q=1-p$. Thus by inclusion/exclusion the desired probability that at least one vertex is isolated is
beginalign
&1-sum_k=0^nsum_l=0^n(-1)^k+lbinom nkbinom nlq^kn+ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knsum_l=0^n(-1)^lbinom nlq^ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knleft(1-q^n-kright)^n\
=&1-sum_k=0^n(-1)^kbinom nkleft(q^k-q^nright)^n;.
endalign
answered Mar 7 '16 at 12:55
joriki
168k10181337
add a comment |Â
up vote
2
down vote
up vote
2
down vote
This can be done using inclusion/exclusion. We have $n+n$ conditions for the individual vertices being isolated. There are $binom nkbinom nl$ combinations of these conditions that require $k$ particular vertices in $X$ and $l$ particular vertices in $Y$ to be isolated, and the probability for this is $q^kn+ln-kl$, with $q=1-p$. Thus by inclusion/exclusion the desired probability that at least one vertex is isolated is
beginalign
&1-sum_k=0^nsum_l=0^n(-1)^k+lbinom nkbinom nlq^kn+ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knsum_l=0^n(-1)^lbinom nlq^ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knleft(1-q^n-kright)^n\
=&1-sum_k=0^n(-1)^kbinom nkleft(q^k-q^nright)^n;.
endalign
answered Mar 7 '16 at 12:55
joriki
168k10181337
This can be done using inclusion/exclusion. We have $n+n$ conditions for the individual vertices being isolated. There are $binom nkbinom nl$ combinations of these conditions that require $k$ particular vertices in $X$ and $l$ particular vertices in $Y$ to be isolated, and the probability for this is $q^kn+ln-kl$, with $q=1-p$. Thus by inclusion/exclusion the desired probability that at least one vertex is isolated is
beginalign
&1-sum_k=0^nsum_l=0^n(-1)^k+lbinom nkbinom nlq^kn+ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knsum_l=0^n(-1)^lbinom nlq^ln-kl\
=&1-sum_k=0^n(-1)^kbinom nkq^knleft(1-q^n-kright)^n\
=&1-sum_k=0^n(-1)^kbinom nkleft(q^k-q^nright)^n;.
endalign
answered Mar 7 '16 at 12:55
joriki
168k10181337
edited Sep 8 at 9:00
answered Mar 7 '16 at 12:55
joriki
168k10181337
answered Mar 7 '16 at 12:55
joriki
168k10181337
answered Mar 7 '16 at 12:55
joriki
168k10181337
168k10181337
add a comment |Â
add a comment |Â
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%2f369830%2fwhat-is-the-probability-that-a-random-n-times-n-bipartite-graph-has-an-isolate%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
2
The same question was asked years ago: Isolated vertex probabilities for different random graphs, but it doesn't yet have a correct answer.
– Kundor
Apr 24 '13 at 19:34