Realize the random graph process by giving every edge an independent uniform arrival time. For a fixed four-set , only its six internal edges and its outgoing edges affect whether it is an isolated clique. It is an isolated clique at some time exactly when all six internal edges arrive before every outgoing edge.
The relative ordering of these edges is uniform. The chance that the first six are exactly the six internal edges is . A union bound over the possible vertex sets gives
(1)
Edges entirely outside are irrelevant. Counting the whole arrival-order event avoids an invalid union over continuously many times.

Ancestors (12)

  1. 6
  2. B
  3. 2007
  4. Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford
  5. Graph Theory and Probabilistic Combinatorics course of the University of Oxford
  6. Year 4 of the mathematics course of the University of Oxford
  7. Mathematics course of the University of Oxford
  8. Undergraduate course of the University of Oxford
  9. Course of the University of Oxford
  10. University of Oxford
  11. List of universities
  12. Home

View article source

Discussion (0) 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