Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 12 2 Solution Created 2026-10-03 Updated 2026-10-14
Take and , as required for the displayed sparse scaling and the later normalization. A strictly balanced graph satisfies for every proper nonempty subgraph . This forces to be connected and to have no isolated vertices: otherwise a component of at least the average density, or deletion of the isolated vertices, violates strict balance. Copies here are subgraphs, not induced subgraphs.
For fixed , the factorial moment counts ordered -tuples of distinct copies all present in the binomial random graph. The contribution of vertex-disjoint copies is exactlyThe factor removes the multiple embeddings of each copy coming from its graph automorphisms. For an overlapping tuple, let be its union. There are placements of each fixed union type, and the probability its edges are present is . When adding a copy meeting the earlier union in vertices and edges, the exponent changes byIt is strictly negative if this intersection is a proper nonempty subgraph, and zero only for an empty intersection or a whole copy. In particular the first vertex-overlapping copy has a proper nonempty intersection: the preceding copies are vertex-disjoint, and a connected copy contained in their union would have to equal one of them, contrary to distinctness. Its contribution is therefore strictly negative; later additions cannot undo that loss. Only finitely many union types occur for fixed , so their total contribution is . We have proved all the factorial moment limits, and the allowed factorial-moment criterion for Poisson convergence givesThis is the Poisson limit for strictly balanced subgraph counts.
The pendant-edge graph has density , whereas its proper core has density . Thus is not strictly balanced. The complete graph is strictly balanced, with 24 graph automorphisms, so at its copy count tends to .
Every copy has a unique four-vertex clique core and one selected edge joining it to a fifth vertex. For any four-set , let count the ambient edges between and its complement. Then , with mean . It is independent of the internal edges determining whether is a clique. Choose . A Chernoff bound and a union bound giveTherefore, simultaneously for every actual core, its number of pendant extensions is . Extra ambient edges cause no overcount: each selected seven-edge subgraph has exactly one core and one pendant edge. Summing over the cores yieldsbecause is uniformly tight. This is the pendant extensions of sparse clique copies mechanism. For , neither endpoint of is an integer, and its only nonnegative integer is . Convergence in distribution consequently givesThe positive- assumption matters: the quotient printed in the question is undefined when .