Growing Cliques Beyond the Half-Density Barrier

Source abstract

Abstract Let p be bounded away from zero and one, let $$r\sim 2\log _{1/p}n$$ r ∼ 2 log 1 / p n , and suppose that the expected number $$\mu _r$$ μ r of copies of $$K_r$$ K r in G ( n , p ) is of order $$n^{1+\theta }$$ n 1 + θ . Morris and Riordan recently obtained a precise upper and lower point-probability description of the clique hypergraph when $$-1<\theta <1/2$$ - 1 &lt; θ &lt; 1 / 2 . We show that their upper point-probability estimate extends to the natural range $$-1<\theta <1$$ - 1 &lt; θ &lt; 1 . The error changes at $$\theta =1/2$$ θ = 1 / 2 : if $$\Delta _k$$ Δ k denotes the expected number of connected k -clusters of copies of $$K_r$$ K r , then, for every fixed $$k\ge 3$$ k ≥ 3 , $$\Delta _k=O^*\bigl (n^\theta +n^{3\theta -1}\bigr ),$$ Δ k = O ∗ ( n θ + n 3 θ - 1 ) , and this order is sharp for $$k=3$$ k = 3 . The local contribution is exactly $$\left( {\begin{array}{c}r+1\\ 3\end{array}}\right) \mu _{r+1}$$ r + 1 3 μ r + 1 ; the second term comes from dispersed clusters. This yields a transition in polynomial order at $$\theta =1/2$$ θ = 1 / 2 . We also prove a general variance inequality for cluster counts and deduce that the three-cluster count is concentrated throughout $$0<\theta <1$$ 0 &lt; θ &lt; 1 .