Consider a random graph $G$ on $n$ vertices $\{1, 2, . . . , n\}$ where every possible edge is present independently with probability $p \in [0, 1]$.

Introduce indicator random variables for complete subgraphs on five vertices in $G$ and compute the expected value of the number of complete subgraphs on five vertices in $G$.

How do you this?

  • $\begingroup$ The hint given is already very explicit, but to make it even more so: Introduce an indicator random variable for every possible complete subgraph ... $\endgroup$ – antkam Apr 25 '18 at 12:28
  • $\begingroup$ Is a subgraph when all elements are connected? $\endgroup$ – Lucky12456 Apr 25 '18 at 12:39
  • $\begingroup$ A complete subgraph is a subgraph which is a complete graph. In this example, a complete subgraph would be a subset of 5 vertices where every pair is connected. $\endgroup$ – antkam Apr 25 '18 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.