Mixing
What is the expectation of the clique number of a random graph?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Suppose we have a random graph with $n$ vertices and edges that are present independently with the probability $p$. What is the expectation of its clique number?
It is quite easy to calculate the expectation for small $n$-s. For example: if $n = 1$, then the answer is $1$, if $n=2$, then $1+p$, if $n = 3$, then $1 + 3p - 3p^2 + 2p^3$... However, I failed to find any general formula for arbitrary $n$.
Any help will be appreciated.
probability combinatorics discrete-mathematics graph-theory random-graphs
asked Jul 17 at 5:09
Yanior Weg
1,0661729
add a comment |Â
up vote
0
down vote
favorite
Suppose we have a random graph with $n$ vertices and edges that are present independently with the probability $p$. What is the expectation of its clique number?
It is quite easy to calculate the expectation for small $n$-s. For example: if $n = 1$, then the answer is $1$, if $n=2$, then $1+p$, if $n = 3$, then $1 + 3p - 3p^2 + 2p^3$... However, I failed to find any general formula for arbitrary $n$.
Any help will be appreciated.
probability combinatorics discrete-mathematics graph-theory random-graphs
asked Jul 17 at 5:09
Yanior Weg
1,0661729
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Suppose we have a random graph with $n$ vertices and edges that are present independently with the probability $p$. What is the expectation of its clique number?
It is quite easy to calculate the expectation for small $n$-s. For example: if $n = 1$, then the answer is $1$, if $n=2$, then $1+p$, if $n = 3$, then $1 + 3p - 3p^2 + 2p^3$... However, I failed to find any general formula for arbitrary $n$.
Any help will be appreciated.
probability combinatorics discrete-mathematics graph-theory random-graphs
asked Jul 17 at 5:09
Yanior Weg
1,0661729
Suppose we have a random graph with $n$ vertices and edges that are present independently with the probability $p$. What is the expectation of its clique number?
It is quite easy to calculate the expectation for small $n$-s. For example: if $n = 1$, then the answer is $1$, if $n=2$, then $1+p$, if $n = 3$, then $1 + 3p - 3p^2 + 2p^3$... However, I failed to find any general formula for arbitrary $n$.
Any help will be appreciated.
probability combinatorics discrete-mathematics graph-theory random-graphs
asked Jul 17 at 5:09
Yanior Weg
1,0661729
asked Jul 17 at 5:09
Yanior Weg
1,0661729
asked Jul 17 at 5:09
Yanior Weg
1,0661729
asked Jul 17 at 5:09
Yanior Weg
1,0661729
1,0661729
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Probability distributions of clique numbers are an active area of research. Most of the known results are in terms of bounds or asymptotic behavior. The following might all be of interest:
- Clique Number of Random Geometric Graphs
- Probability of Graph Having at Least 1 k-Clique
- The Largest Clique Size in a Random Graph
- And so on...
Your problem can at least be reduced to an arguably simpler combinatorial problem. Let $a(n,k,c)$ denote the number of graphs with $n$ vertices, $k$ edges, and clique number $c$. Let $N(n)=fracn(n-1)2$ be the total number of places one of those edges could be placed.
The probability of a graph having $k$ edges is modeled by the binomial distribution $$q(n,k)=N(n)choose kp^k(1-p)^N(n)-k.$$
The probability of a graph with $k$ vertices having clique number $c$ is $$r(n,k,c)=fraca(n,k,c)N(n)choose k.$$
The probability of a graph having $k$ edges AND having clique number $c$ is then $$beginalignedb(n,k,c)&=r(n,k,c)q(n,k)\&=a(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
To find the probability of having clique number $c$, we simply sum over the variable $k$ to obtain $$beginaligneds(n,c)&=sum_k=0^Nb(n,k,c)\&=sum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The expected value follows the standard procedure. $$beginalignedE(n)&=sum_c=1^nccdot s(n,c)\&=sum_c=1^ncsum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The only really troublesome part is the combinatorial question. How does one count $a(n,k,c)$?
One of the neat properties that we discovered in this process though is that the solution is a polynomial of maximum degree $N(n)$ with integer coefficients. This suggests a relationship to generating functions and chromatic polynomials which might allow low-ordered versions to be reasoned about in terms of roots and other qualitative properties. The roots are kind of weird even for the small examples you presented, and this could easily be a dead end as well.
answered Jul 17 at 6:14
Hans Musgrave
1,393111
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
accepted
Probability distributions of clique numbers are an active area of research. Most of the known results are in terms of bounds or asymptotic behavior. The following might all be of interest:
- Clique Number of Random Geometric Graphs
- Probability of Graph Having at Least 1 k-Clique
- The Largest Clique Size in a Random Graph
- And so on...
Your problem can at least be reduced to an arguably simpler combinatorial problem. Let $a(n,k,c)$ denote the number of graphs with $n$ vertices, $k$ edges, and clique number $c$. Let $N(n)=fracn(n-1)2$ be the total number of places one of those edges could be placed.
The probability of a graph having $k$ edges is modeled by the binomial distribution $$q(n,k)=N(n)choose kp^k(1-p)^N(n)-k.$$
The probability of a graph with $k$ vertices having clique number $c$ is $$r(n,k,c)=fraca(n,k,c)N(n)choose k.$$
The probability of a graph having $k$ edges AND having clique number $c$ is then $$beginalignedb(n,k,c)&=r(n,k,c)q(n,k)\&=a(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
To find the probability of having clique number $c$, we simply sum over the variable $k$ to obtain $$beginaligneds(n,c)&=sum_k=0^Nb(n,k,c)\&=sum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The expected value follows the standard procedure. $$beginalignedE(n)&=sum_c=1^nccdot s(n,c)\&=sum_c=1^ncsum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The only really troublesome part is the combinatorial question. How does one count $a(n,k,c)$?
One of the neat properties that we discovered in this process though is that the solution is a polynomial of maximum degree $N(n)$ with integer coefficients. This suggests a relationship to generating functions and chromatic polynomials which might allow low-ordered versions to be reasoned about in terms of roots and other qualitative properties. The roots are kind of weird even for the small examples you presented, and this could easily be a dead end as well.
answered Jul 17 at 6:14
Hans Musgrave
1,393111
add a comment |Â
up vote
2
down vote
accepted
Probability distributions of clique numbers are an active area of research. Most of the known results are in terms of bounds or asymptotic behavior. The following might all be of interest:
- Clique Number of Random Geometric Graphs
- Probability of Graph Having at Least 1 k-Clique
- The Largest Clique Size in a Random Graph
- And so on...
Your problem can at least be reduced to an arguably simpler combinatorial problem. Let $a(n,k,c)$ denote the number of graphs with $n$ vertices, $k$ edges, and clique number $c$. Let $N(n)=fracn(n-1)2$ be the total number of places one of those edges could be placed.
The probability of a graph having $k$ edges is modeled by the binomial distribution $$q(n,k)=N(n)choose kp^k(1-p)^N(n)-k.$$
The probability of a graph with $k$ vertices having clique number $c$ is $$r(n,k,c)=fraca(n,k,c)N(n)choose k.$$
The probability of a graph having $k$ edges AND having clique number $c$ is then $$beginalignedb(n,k,c)&=r(n,k,c)q(n,k)\&=a(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
To find the probability of having clique number $c$, we simply sum over the variable $k$ to obtain $$beginaligneds(n,c)&=sum_k=0^Nb(n,k,c)\&=sum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The expected value follows the standard procedure. $$beginalignedE(n)&=sum_c=1^nccdot s(n,c)\&=sum_c=1^ncsum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The only really troublesome part is the combinatorial question. How does one count $a(n,k,c)$?
One of the neat properties that we discovered in this process though is that the solution is a polynomial of maximum degree $N(n)$ with integer coefficients. This suggests a relationship to generating functions and chromatic polynomials which might allow low-ordered versions to be reasoned about in terms of roots and other qualitative properties. The roots are kind of weird even for the small examples you presented, and this could easily be a dead end as well.
answered Jul 17 at 6:14
Hans Musgrave
1,393111
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Probability distributions of clique numbers are an active area of research. Most of the known results are in terms of bounds or asymptotic behavior. The following might all be of interest:
- Clique Number of Random Geometric Graphs
- Probability of Graph Having at Least 1 k-Clique
- The Largest Clique Size in a Random Graph
- And so on...
Your problem can at least be reduced to an arguably simpler combinatorial problem. Let $a(n,k,c)$ denote the number of graphs with $n$ vertices, $k$ edges, and clique number $c$. Let $N(n)=fracn(n-1)2$ be the total number of places one of those edges could be placed.
The probability of a graph having $k$ edges is modeled by the binomial distribution $$q(n,k)=N(n)choose kp^k(1-p)^N(n)-k.$$
The probability of a graph with $k$ vertices having clique number $c$ is $$r(n,k,c)=fraca(n,k,c)N(n)choose k.$$
The probability of a graph having $k$ edges AND having clique number $c$ is then $$beginalignedb(n,k,c)&=r(n,k,c)q(n,k)\&=a(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
To find the probability of having clique number $c$, we simply sum over the variable $k$ to obtain $$beginaligneds(n,c)&=sum_k=0^Nb(n,k,c)\&=sum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The expected value follows the standard procedure. $$beginalignedE(n)&=sum_c=1^nccdot s(n,c)\&=sum_c=1^ncsum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The only really troublesome part is the combinatorial question. How does one count $a(n,k,c)$?
One of the neat properties that we discovered in this process though is that the solution is a polynomial of maximum degree $N(n)$ with integer coefficients. This suggests a relationship to generating functions and chromatic polynomials which might allow low-ordered versions to be reasoned about in terms of roots and other qualitative properties. The roots are kind of weird even for the small examples you presented, and this could easily be a dead end as well.
answered Jul 17 at 6:14
Hans Musgrave
1,393111
Probability distributions of clique numbers are an active area of research. Most of the known results are in terms of bounds or asymptotic behavior. The following might all be of interest:
- Clique Number of Random Geometric Graphs
- Probability of Graph Having at Least 1 k-Clique
- The Largest Clique Size in a Random Graph
- And so on...
Your problem can at least be reduced to an arguably simpler combinatorial problem. Let $a(n,k,c)$ denote the number of graphs with $n$ vertices, $k$ edges, and clique number $c$. Let $N(n)=fracn(n-1)2$ be the total number of places one of those edges could be placed.
The probability of a graph having $k$ edges is modeled by the binomial distribution $$q(n,k)=N(n)choose kp^k(1-p)^N(n)-k.$$
The probability of a graph with $k$ vertices having clique number $c$ is $$r(n,k,c)=fraca(n,k,c)N(n)choose k.$$
The probability of a graph having $k$ edges AND having clique number $c$ is then $$beginalignedb(n,k,c)&=r(n,k,c)q(n,k)\&=a(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
To find the probability of having clique number $c$, we simply sum over the variable $k$ to obtain $$beginaligneds(n,c)&=sum_k=0^Nb(n,k,c)\&=sum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The expected value follows the standard procedure. $$beginalignedE(n)&=sum_c=1^nccdot s(n,c)\&=sum_c=1^ncsum_k=0^Na(n,k,c)p^k(1-p)^N(n)-k.endaligned$$
The only really troublesome part is the combinatorial question. How does one count $a(n,k,c)$?
One of the neat properties that we discovered in this process though is that the solution is a polynomial of maximum degree $N(n)$ with integer coefficients. This suggests a relationship to generating functions and chromatic polynomials which might allow low-ordered versions to be reasoned about in terms of roots and other qualitative properties. The roots are kind of weird even for the small examples you presented, and this could easily be a dead end as well.
answered Jul 17 at 6:14
Hans Musgrave
1,393111
answered Jul 17 at 6:14
Hans Musgrave
1,393111
answered Jul 17 at 6:14
Hans Musgrave
1,393111
answered Jul 17 at 6:14
Hans Musgrave
1,393111
1,393111
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%2f2854150%2fwhat-is-the-expectation-of-the-clique-number-of-a-random-graph%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