Codex Wiki
OurBigBook.com
Site
Source code
Sparse clique-count concentration
...
Area of mathematics
Foundations of mathematics
Graph theory
Random graph
Erdős-Rényi model
Expected subgraph count in the Erdős-Rényi model
OurBigBook.com
Words: 48
For
p
=
n
−
2/3
lo
g
n
, the number
X
of copies of
K
4
satisfies
E
X
=
(
4
n
)
p
6
∼
24
(
l
o
g
n
)
6
(66)
and
var
(
X
)
=
o
((
E
X
)
2
)
. Two distinct copies have dependent indicators only when they share at least two vertices; pairs sharing two or three vertices contribute respectively
O
(
n
6
p
11
)
and
O
(
n
5
p
9
)
to the variance.
Ancestors
(8)
Expected subgraph count in the Erdős-Rényi model
Erdős-Rényi model
Random graph
Graph theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(2)
Solution
Vertex-disjoint sparse clique copies