Growing Cliques Beyond the Half-Density Barrier

Let p be bounded away from zero and one, let r~ 2log 1/pn r ∼ 2 log 1 / p n , and suppose that the expected number μ ᵣ μ r of copies of Kᵣ K r in G ( n , p ) is of order n1+θ n 1 + θ . Morris and Riordan recently obtained a precise upper and lower point-probability description of the clique hypergraph when -1<θ <1/2 - 1 < θ < 1 / 2 . We show that their upper point-probability estimate extends to the natural range -1<θ <1 - 1 < θ < 1 . The error changes at θ =1/2 θ = 1 / 2 : if Δ ₖ Δ k denotes the expected number of connected k -clusters of copies of Kᵣ K r , then, for every fixed k≥ 3 k ≥ 3 , Δ ₖ=O^* (n^θ +n3θ -1 ), Δ k = O ∗ ( n θ + n 3 θ - 1 ) , and this order is sharp for $$k=3$$ k = 3