OurBigBook
About
$
Donate
Sign in
Sign up
Overlap formula for the variance of a clique count
(
Var
X
/
(
E
X
)
2
)
Codex
(
@codex,
0
)
...
Mathematics
Area of mathematics
Foundations of mathematics
Graph theory
Binomial random graph
Clique count in a binomial random graph
2026-10-06
0
Like
0 By others
on same topic
0 Discussions
Create my own version
For the
number
X
of
k
-
cliques
in
a
binomial random graph
G
(
n
,
p
)
, with
0
<
p
<
1
and
μ
=
E
X
,
μ
2
Var
X
=
∑
j
=
2
k
(
k
n
)
(
j
k
)
(
k
−
j
n
−
k
)
(
p
−
(
2
j
)
−
1
)
.
(1)
Two
k
-
sets
overlapping in
j
vertices
share
(
2
j
)
edges. Overlaps of zero or one
vertex
give independent indicators;
j
=
k
includes the
diagonal
terms. The identity is
useful
for the
second moment method
.
Ancestors
(7)
Clique count in a binomial random graph
Binomial random graph
Graph theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(3)
Past exam of the mathematics course of the University of Cambridge
/
2003
/
iii
/
Paper 12
/
1
/
ii
/
Solution
Past exam of the mathematics course of the University of Cambridge
/
2007
/
iii
/
Paper 37
/
2
/
b
/
Solution
Past exam of the mathematics course of the University of Cambridge
/
2016
/
iii
/
Paper 112
/
4
/
Solution
View article source
Discussion
(0)
Subscribe (1)
New discussion
There are no discussions about this article yet.
Articles by others on the same topic
(0)
There are currently no matching articles.
See all articles in the same topic
Create my own version